Funny enough, this is probably the problem
The following procedure (explanation follows) works great for really small lists, but when the list contains more items (1/2 million), the application goes into a "not responding" state and it takes about 2.5 minutes to complete (very bad time) ... I can add an app to handle lists of 100 million items at least (eventually).
here is the code for the problematic procedure:
public void removeItems(List<long> L, SortedList<long, List<long>> _subLists)
{
foreach (KeyValuePair<long, List<long>> kvp in _subLists)
{
foreach (long duplicate in kvp.Value)
{
int j = L.IndexOf(duplicate);
L.RemoveRange(j,(int)kvp.Key);
}
}
}
L is a list of long values. _subLists is a sorted list, where each value is a list of values from L, starting a series of arithmetic progressions of some difference (doesn't matter). the key associated with this value is the length of the row containing the values.
Example:
L = {1,2,3,5,6,7,18,20,21} _subLists = {2, <20>} {3, <1,5>}
The procedure simply removes a series of arithmetic progressions from L.
The execution time of this procedure in a large O record will be n ^ 2, which is quite slow, and you can expect a slow execution time if one of the lists contains 100 million records. There is no stack overflow problem here, it just slows down the iteration of that data. I really don't see the question here, would you like to do this faster? If so, then the nested loop would definitely be a problem.
a source to share
Your problem is that you are removing many items from L, which is a very costly operation. Each time an item is removed, memory is copied to move all items above the removed items. The more items are removed, the more items are shuffled, the longer it takes. Memory is a performance bottleneck, RAM is slower than the processor and if you are paging to disk, not very slow.
How can you improve this.
The easiest option is to use a container for L, which has the best performance for deleting elements - like LinkedList. LinkedLists do not need to move elements in memory when elements are removed, but it does take more memory to store data (two pointers per value). If this is too much overhead, then perhaps instead LinkedList <List <long>>
, where each List <long>
contains the maximum number of values.
Alternatively, change the deletion algorithm so that you iterate over the list L and create a new list containing the values not found in _subLists. You can change the way _subLists stores data to make it faster to find items in ranges.
a source to share
If possible:
A) Convert L to a sorted list. O: n * log (n)
B) Convert subscriptions to pairs of sorted lists where the first element is # in the sequence in L (duplicate in the code snippet) and the second is the length of the sequence. O: n * log (n)
C) Perform a single pass through L using sublists to determine how many items to remove at a given location in L. Take advantage of the fact that both lists are sorted so as not to indent in either list. O: n
Should be able to get O: n * log (n) complexity from this if possible. Of course, I'm not 100% sure about all the details of the problem. For example, can you duplicate? If so, does the sublist order matter? Depending on the answers to them, you may be forced to migrate or modify such an algorithm. Also, this will obviously use more memory.
a source to share