ConcurrentDictionary<TKey, TValue> - How to efficiently "get N elements, starting from key K"?

user_982149 0
Viewed 124

Situation as follows:

  • I have a ConcurrentDictionary<TId, TItem>
  • For efficient paging, we want to implement "get N Items, starting from key K"

The best approach I came up with was:

public IEnumerable<TItem> Get( TId fromKey, int count )
{
    // parameter validation left out for brevity

    return items.Keys // KeyCollection of the Dictionary, please assume 'items' is a class field
             .SkipWhile(key => key != fromKey)
             .Take(count)
             .Select(x => items[x])
             .ToList();
}

But that feels really wrong. Especially because we explicitly do not want to "SkipWhile". If I was OK to Skip, I could just do .Skip(n).Take(m) on the Values but that's explicitly not wanted. Requirement for me is: starting at key K, return N elements.

Maybe I am overthinking this and I should push back. But I have the feeling, I am missing something here.

So my question is: Is there a way to do this, without having to "skip over" in either KeyCollection or ValueCollection of the Dictionary?

EDIT

  • ConcurrentDictionary<TKey, TVaue> is where I picked up the task. It is not carved in stone to keep that Type.
  • Order is no priority. Seniors and PO view it "good enough" to go by whatever order results from KeyCollection. But that's a good point to keep in mind looking to possible future feature requests.
dictionary c#
1 Answers

Well, based on the comments, it sounds a bit bizarre, but I'm sure there are reasons you can't go into the backstory or details.

I would say this.

SkipWhile(key => key != fromKey) is really the only way you can find a key for the purpose of finding more keys "after it", so in that sense, what you have is correct. If your keyspace is not ridiculously large, that seems sufficient.

That said, a different data structure would be better. For example, you could implement a concurrent version of a dictionary + array or dictionary + linked list that allows you to access a key in O(1) and then the subsequent elements in O(m) inside of a lock (you could even make it a ReaderWriterLockSlim). That avoids the O(n) scan to find the key if just using ConcurrentDictionary.

Insertion would be a bit strange, because you'd have to maintain a somewhat arbitrary notion of what before and after mean. In the dictionary + array case for example, you could add key 'foo' into the dictionary and into slot 0 in the array. Key 'bar' would go into the dictionary as usual, and into slot 1, and so on.

Oh - and your dictionary entry would have to point to the location in the array or the linked list to get that O(m), as well as the data itself. And, if you want to de-duplicate the data, the array/list could point back to the dictionary entry instead of just holding the data.

Arrays will leave you with holes when items are deleted! That's where a linked list would be helpful. Writes will be a bit slower to maintain "ordering" (using this term loosely) and because you are accessing two underlying data structures.

user_643480
Related