c/c++语言开发共享从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 ² ）解决方案，您可以使用单个读取和单个写入索引创建单个循环。浏览数组，随时复制项目：

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

在循环结束时， wr是array保留的元素数。

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

  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 } 
 它通过使用最后一个值交换元素来完成。


       

      		 以上就是c/c++开发分享从C中删除数组中大量元素的最快方法相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
                                                        本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304

本文章地址：https://www.ctvol.com/c-cdevelopment/545842.html

c/c++语言开发共享从C中删除数组中大量元素的最快方法

精彩推荐