从C中删除数组中大量元素的最快方法

我有动态数组,包含数千个元素甚至更多,为了不消耗大量的内存,我可以从中删除不需要的元素(即元素已被使用,不再需要它们)所以从一开始我通过估计每次删除元素后所需的最大大小,可以分配更小的内存大小。

我用这种方式但是需要很长时间才能完成,有时需要30分钟!

int x, y ; for (x = 0 ; x<number_of_elements_to_remove ; x++){ for (y = 0 ; y<size_of_array; y++ ){ array[y] = array[y+1]; } } 

有比这更快的方法吗?

不是一次删除一个元素,而是使用两个循环制作O(n 2 )解决方案,您可以使用单个读取和单个写入索引创建单个循环。 浏览数组,随时复制项目:

 int rd = 0, wr = 0; while (rd != size_of_array) { if (keep_element(array[rd])) { array[wr++] = array[rd]; } rd++; } 

在循环结束时, wrarray保留的元素数。

因为我注意到你只想删除数组开头的元素,试试这个:

  int x; for(x = 0 ; x< size_of_array - number_of_elements_to_remove; x++) array[x] = array[number_of_elements_to_remove + x]; 

这样你就可以使用一个for循环来降低复杂性

看来你基本上做了

 int y; for (y = 0; y 

上面应该更快,但是你的代码仍然存在一些警告/问题(例如,超出数组末尾的访问)。

这是对数组进行碎片整理的代码。

 int sparse_to_compact(int*arr, int total, int*is_valid) { int i = 0; int last = total - 1; // trim the last invalid elements for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements from last // now we keep swapping the invalid with last valid element for(i=0; i < last; i++) { if(is_valid[i]) continue; arr[i] = arr[last]; // swap invalid with the last valid last--; for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements } return last+1; // return the compact length of the array } 

我复制了这个答案的代码。

我认为更有效的方法是使用桶的链接列表。 并且桶由位串存储器管理器管理。 它如下,

 struct elem { uint32_t index; /* helper to locate it's position in the array */ int x; /* The content/object kept in the array */ } 

假设,我们的数组内容是int ,它封装在一个名为struct elem的结构中。

 enum { MAX_BUCKET_SIZE = 1024, MAX_BITMASK_SIZE = (MAX_BUCKET_SIZE + 63) >> 6, }; struct bucket { struct bucket*next; /* link to the next bucket */ uint64_t usage[MAX_BITMASK_SIZE]; /* track memory usage */ struct elem[MAX_BUCKET_SIZE]; /* the array */ }; 

存储桶被定义为struct elem和usage mask的数组。

 struct bucket_list { struct bucket*head; /* dynamically allocated bucket */ }container; 

存储桶列表是包含所有存储桶的链接列表。

所以我们需要编写内存管理器代码。

首先,我们需要在需要时分配新的存储桶。

 struct bucket*bk = get_empty_bucket(&container); if(!bk) { /* no empty bucket */ /* allocate a bucket */ struct bucket*bk = (struct bucket*)malloc(sizeof(struct bucket)); assert(bk); /* cleanup the usage flag */ memset(bk->usage, 0, sizeof(bk->usage)); /* link the bucket */ bk->next = container.head; container.head = bk; } 

现在我们有了存储桶,我们需要在需要时设置数组中的值。

 for(i = 0; i < MAX_BITMASK_SIZE; i++) { uint64_t bits = ~bk.usage[i]; if(!bits) continue; /* no space */ /* get the next empty position */ int bit_index = _builtin_ctzl(bits); int index = (i<<6)+bit_index; /* set the array value */ bk->elem[index].index = index; bk->elem[index].x = 34/* my value */; bk.usage[i] |= 1< 

删除数组元素很容易,以便将它们标记为未使用。 现在,当存储桶中的所有元素都未使用时,我们可以从链接列表中删除存储桶。

我们有时可以对存储桶进行碎片整理或优化它们以适应更小的空间。 否则,当我们分配新元素时,我们可以在不那么拥挤的情况下选择更拥挤的桶。 当我们删除时,我们可以将不那么拥挤的元素交换为更拥挤的元素。

可以有效地删除数组元素,

 int remove_element(int*from, int total, int index) { if(index != (total-1)) from[index] = from[total-1]; return total; // **DO NOT DECREASE** the total here } 

它通过使用最后一个值交换元素来完成。