I have a very large list of integers (about 2 billion elements) and a list with indices (couple thousand elements) at which I need to remove elements from the first list. My current approach is to loop over all indices in the second list, passing each to the RemoveAt() method of the first list:
indices.Sort();
indices.Reverse();
for (i = 0; i < indices.Count; i++)
{
largeList.RemoveAt(indices[i]);
}
However, it takes about 2 minutes to finish. I really need to perform this operation much faster. Is there any way of optimizing this?
I have a Intel i9X CPU with 10 cores, so maybe some way of parallel processing?
Since the order of the source list is significant, you can move each item down the list, skipping indices to be removed, and then remove the end of the list.
UPDATE: Took the .Net Core source code for RemoveAll and modified it for a indice list instead of a predicate.
UPDATE 2: Optimized to not repeat tests if possible.
UPDATE 3: Simplified as optimization having extra code proved slower in benchmarks.
Having src as the large list, and removeAtList as the indices to remove in some random order, you can do:
removeAtList.Sort();
var srcCount = src.Count;
var ralCount = removeAtList.Count;
var removeAtIndice = 1;
var freeIndex = removeAtList[0];
var current = freeIndex+1;
while (current < srcCount) {
while (removeAtIndice < ralCount && current == removeAtList[removeAtIndice]) {
++current;
++removeAtIndice;
}
if (current < srcCount)
src[freeIndex++] = src[current++];
}
src.RemoveRange(freeIndex, srcCount-freeIndex);
For a one billion element list of random integers, and a 1000 - 3000 element list of random indices, I get 1.1 ms per remove with this algorithm. Using RemoveAt, I get over 232.77 ms per remove, so this is about 200 times faster.
One way to allow this to be parallelized would be to break the list into multiple fragments; perhaps initially (arbitrarily) separate slabs of 1 million elements. As long as each slab maintains its own count, you can split the work by index into removals from different slabs (based purely on the counts), and then do the actual removal work concurrently. If you leave some spare capacity in each, you can also add elements into the middle more cheaply, as you are usually only touching one slab. Random access will be a little slower, as you may need to look at multiple slab counts to determine the correct slab, but if the slab counts are maintained in a contiguous vector (rather than against each slab), you should have excellent memory cache hit while doing it.