1

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.

Jan
  • 1,905
  • 17
  • 41
  • Hash sets aren't sorted. – Colin DeClue Apr 22 '13 at 16:48
  • 3
    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 Apr 22 '13 at 16:50
  • @Vladimir Schmidt See here: http://stackoverflow.com/questions/1552225/hashset-that-preserves-ordering – Jon Senchyna Apr 22 '13 at 16:50
  • How about a [SortedDictionary](http://msdn.microsoft.com/en-gb/library/f7fta44c.aspx)? – Matthew Watson Apr 22 '13 at 16:54
  • 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 Apr 22 '13 at 16:58
  • @Colin DeClue but linq are – Vladimir Shmidt Apr 22 '13 at 17:05

1 Answers1

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.

DMac the Destroyer
  • 5,240
  • 6
  • 36
  • 56
  • 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 Apr 22 '13 at 18:47
  • 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 – Jan Apr 22 '13 at 18:54
  • 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 Apr 22 '13 at 20:55
  • 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. – DMac the Destroyer Apr 22 '13 at 21:02
  • 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 – Jan Apr 23 '13 at 04:48