Frequent inserts into sorted collection

Question

I have sorted collection (List) and I need to keep it sorted at all times.

I am currently using List.BinarySearch on my collection and then insert element in right place. I have also tried sorting list after every insertion but the performance in unacceptable.

Is there a solution that will give better performance? Maybe I should use other collection.

(I am aware of SortedList but it is restricted to unique keys)

What is the type you are sorting on ?...string, int, other.. — Rusty, Jul 20 '10 at 14:54

score 3 · Answer 1 · answered Jul 20 '10 at 14:49

3

If you're using .Net 4, you can use a SortedSet<T>

http://msdn.microsoft.com/en-us/library/dd412070.aspx

For .Net 3.5 and lower, see if a SortedList<TKey,TValue> works for you.

http://msdn.microsoft.com/en-us/library/ms132319.aspx

answered Jul 20 '10 at 14:49

BFree

102,548
21
159
201

2

SortedSet won't allow duplicates. And neither will SortedList – H H Jul 20 '10 at 14:59

Wilka · Accepted Answer · 2016-09-26T09:21:38.140

3

PowerCollections has an OrderedBag type which may be good for what you need. From the docs

Inserting, deleting, and looking up an an element all are done in log(N) + M time, where N is the number of keys in the tree, and M is the current number of copies of the element being handled.

However, for the .NET 3.5 built in types, using List.BinarySearch and inserting each item into the correct place is a good start - but that uses an Array internally so your performance will drop due to all the copying you're doing when you insert.

If you can group your inserts into batches that will improve things, but unless you can get down to only a single sort operation after all your inserting you're probably better off using OrderedBag from PowerCollections if you can.

edited Sep 26 '16 at 09:21

answered Jul 20 '10 at 14:51

Wilka

28,701
14
75
97

PowerCollections and its OrderedBag is great however I ended up using a Priority Queue (also not available in the .NET) – zby_szek Oct 30 '10 at 09:16
is this still the case 6 years later? – mcmillab Sep 26 '16 at 05:36
@mcmillab I haven't looked at the perf, but if I needed this today I'd start with [C5 Collections](https://github.com/sestoft/C5) and look at [TreeBag](https://c5docs.azurewebsites.net/class_c5_1_1_tree_bag.html) – Wilka Sep 26 '16 at 09:25

score 1 · Answer 3 · answered Jul 20 '10 at 14:48

1

Try to aggregate insertions into batches, and sort only at the end of each batch.

answered Jul 20 '10 at 14:48

Dan Stocker

702
7
5

Frequent inserts into sorted collection

3 Answers3

Linked