我有动态数组,包含数千个元素甚至更多,为了不消耗大量的内存,我可以从中删除不需要的元素(即元素已被使用,不再需要它们)所以从一开始我通过估计每次删除元素后所需的最大大小,可以分配更小的内存大小。
我用这种方式但是需要很长时间才能完成,有时需要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++; }
在循环结束时, 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