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

问题描述：

我有一个动态数组，其中包含数千个甚至更多个元素，为了不占用大量内存，我可以从中删除不需要的元素（即已经使用了元素，不再需要它们了），因此开始时，我可以通过每次删除元素后估计所需的最大大小来分配较小的内存大小。

I have dynamic array that contains thousands of elements or even more, in order not to consume a large size of memory, I can remove unwanted elements from it (i.e elements have been used and no need for them any more) so from the beginning I can allocate a smaller memory size by estimating the maximum required size after removing the elements each time.

我使用这种方式，但是这需要非常长的时间完成，有时需要30分钟！

I use this way but it takes a very very long time to finish, sometime takes 30 minutes!

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];
    }
}

有没有比这更快的方法？

Is there a faster way than this?

答

不是一次删除一个元素，而是通过两个循环生成O（n ²）解决方案，您可以创建一个循环，并进行一次读取和一次写入索引。遍历数组，同时复制项目：

Instead of removing elements one at a time, with two loops making for an O(n²) solution, you can make a single loop, with a single read and a single write index. Go through the array, copying items as you go:

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

循环结束时 wr 是数组中保留的元素数。

At the end of the loop wr is the number of elements kept in the array.

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

相关推荐