Efficent C# sorted collection of fixed number of mutable objects

Question

I'm trying to think about efficient ways of maintaining collection of small fixed finite number of objects (few dozens), that will change very frequently (at least few times per second up to few dozen times per second). Is there an existing sorted collection which would have functionality of updating key (ranking) of existing inserted item?

Let's consider following item definition:

public class Item
{
    public decimal Ranking { get; private set; }
    public IIdentity Identity { get; private set; }
    public IOtherInfo OtherInfo { get; private set; }
}

I'll have incoming stream of those items (usually updating Ranking, sometimes invalidating the previous Ranking - that can be e.g. simplified by setting Ranking to 0 or Infinite). There will be just few variations of Identity values (and it can be quickly converted to index 0 to N), the OtherInfo can change (but it can be easily stored in separate look-up array), and most importantly the Ranking will change quickly. I was thinking about SortedCollection, however need for removing and reading item whenever the Ranking changes (which is very often) sounds inefficient.

Any suggestion for collection that allows update of item and its resorting in collection will be appreciated.

Given that the number if items is very small (a few dozen items is nothing) I highly doubt it will matter. Even a poor data structure won't have a problem with a data set that small. On top of that, updating the content a few dozen times per second is not a lot. That's still hundreds of milliseconds you have to do the update. This should only take a few dozen nanoseconds. You could probably do the updates hundreds of times per second, even with a mediocre implementation. — Servy
– Servy, Commented Apr 22, 2013 at 16:50
@Vladimir Schmidt See here: stackoverflow.com/questions/1552225/… — Jon Senchyna
– Jon Senchyna, Commented Apr 22, 2013 at 16:50
Hash Set will only contains data and provide good perfomance abbility to add and remove opperations, so with OrderBy (linq) it bring best way to get what you want, isn't it? — Vladimir Shmidt
– Vladimir Shmidt, Commented Apr 22, 2013 at 16:58

DMac the Destroyer · Accepted Answer · 2013-04-22 17:03:08Z

1

For the load you're reporting, I'd say you should go with a data structure that lends itself to better maintainability than worry about squeezing out a few extra CPU cycles. Go with a SortedList or a SortedSet, and only worry about improving performance if you're experiencing unacceptable results.

I would say that this is one of those cases where premature optimization is the root of all evil.

answered Apr 22, 2013 at 17:03

DMac the Destroyer

5,3407 gold badges39 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Jan Over a year ago

This is absolutely valid point. I still don't have the solid numbers.However this is strongly expected to be a weak point. There will be hundreds of those structures in my app and there'll be (N x hundreds) of corresponding concurrent data-streams (streaming over the local gigabit link)

Jan Over a year ago

Rest of app will be pretty straightforward (consuming of the data) and without needs for synchronization. Those structures would however consume data from those multiple threads. Think e.g. about aggregation of stock prices from multiple sources. I should have mention this in my question but I didn't want to add distracting details

DMac the Destroyer Over a year ago

the fact that you need these collections to be thread-safe is quite a big deal, and the other points you mention suggests that there are architectural decisions that were made that should also be taken into consideration... I'd suggest either re-working or (probably better) creating a new question to include these points

DMac the Destroyer Over a year ago

also, just as a recommendation, if this particular aspect of your application is so mission-critical that you're already looking to squeeze more performance out of it, then you should benchmark its performance as soon at possible.

Jan Over a year ago

Fair enough. Sounds like I should start with most simple code possible even though it might look like inefficient. And then return to it after perf. measurements

Collectives™ on Stack Overflow

Efficent C# sorted collection of fixed number of mutable objects

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related