Fastest way to remove huge number of elements from an array in C

Question

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.

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?

Answer 1

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

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

Answer 2

as I noticed you want to only delete elements from the start of the array, try this:

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

this way you're using one for loop which reduces the complexity alot