Sorting a ConcurrentDictionary by Value

Question

I am able to sort my ConcurrentDictionary by value like so:

static ConcurrentDictionary<string, Proxy> Proxies = 
    new ConcurrentDictionary<string, Proxy>();

Proxies.OrderBy(p => p.Value.Speed);

Which is great, except I want to set that new re-ordered list AS the dictionary, effectively sorting the dictionary itself rather than just receiving a result list of sorted items.

I try to do something like this but had no luck - the dictionary is still unordered after:

Proxies = new ConcurrentDictionary<string,Proxy>(
    Proxies.OrderBy(p => p.Value.Speed));

It seems like doing that has no effect on the dictionary. I also tried casting the OrderBy result to a new var thinking that it may have an effect on the delegate but still no luck.

How can I re-order this ConcurrentDictionary and then force the dictionary to be the re-ordered result from OrderBy?

Kazue

If you need the fast access properties of a dictionary, combined with thread-safety and continuous sorting, you need something like a concurrent B-tree. I don't believe there is one readily available in .NET. Perhaps third party? Any chance you could just use OrderBy() when you need the results? – Klepac

Answer 1

Simple dictionaries are not sorted collections. They are merely a collection which maps keys to values. ConcurrentDictionary is no different.

You'd instead need a SortedConcurrentDictionary (akin to SortedDictionary), however, this data structure does not exist.

As for if you actually require a sorted "dictionary", we'd need to hear more about your use case. Is this a faux priority queue? Could you simply use a ConcurrentBag<Proxy> and perform ordering after the fact?

If you need to take the collection and in a downstream parallel method use the proxies in sorted order, I suggest taking a look at creating a custom Partitioner, potentially borrowing from the MSDN example of an OrderablePartitioner.

Steffin

The dictionary was only being used to prevent duplicate values from being added. Previously, I was simply using a List<Proxy> and checking if the values existed before adding. I could use a ConcurrentBag<Proxy> but that would require using two separate lists as I keep an actively visible and maintained view of the proxies in a ListView, allowing the proxies to be seen/managed/etc. The previous implementation of the List<proxy> with locking mechanisms was working fairly well until I reached a bug recently with null items being present, so I tried switching to a ConcurrentBag/Dictionary/etc... – Kazue

So it sounds like you needed a concurrent HashSet, which the ConcurrentBag isn't as you found. Is this concurrent because another thread comes by and updates it? – Steffin

Rgiht, I'm using multiple threads to check the proxies and update the list accordingly. – Kazue

Just so nobody else spends 2 hours implementing a HashSet<T> and then a List<T> to act as the 'sorted' viewer: .NET 4.0 added a 'SortedSet<T>' which is a sorted HashSet. /smash-face-on-keyboard – Kazue

I'm in core 2.2 also using a concurrentdictionary for the threadsafe aspects, I put a check in on loading and accessing that verifies the list is in the order I'm expecting (iterating over each item). Not perfect, but it seems to show that the load order is how it stays persisted. – Dosi

Answer 2

A dictionary, especially ConcurrentDictionary, is essentially unsorted.

If you need a sorted collection, you'll need to store the values in some other type, such as a SortedDictionary<T,U>.

Refute

I was hoping to utilize the built-in .NET concurrency offered by the ConcurrentDictionary, though. I can see this is not possible while offering sorted capabilities. Back to using lock() statements... thanks. – Kazue

@Kazue Just be careful - ordering and concurrent collections usually conflict... Typically, (when possible) it's a good idea to keep your data in a concurrent collection while working on it, then extract the items in a specific order to present results, etc. – Refute

But retrieving items in a given order where working with the collection is more read intensive than write intensive can be rather expensive. I see a case for wanting to update a ConcurrentDictionary and have the sorting of the items be atomically part of the update. Rather than having to reinitialize the entire Dictionary in the desired sort order. To that end, ConcurrentSortedDictionary or SortedConcurrentDictionary will be a nice to have in the BCL. – Priapism

Answer 3

Maybe not efficient if you call it often in an immutable class, but simple:

Imports System.Collections.Concurrent

Public Class SortedConcurrentDictionary(Of TKey, Tvalue)
Inherits ConcurrentDictionary(Of TKey, Tvalue)

    Shadows ReadOnly Property Values As IEnumerable(Of Tvalue)
        Get
            If MyBase.Values.Count = 0 Then
                Return MyBase.Values
            End If
            Return From k In Keys Order By k Select Me(k)
        End Get
    End Property
End Class

Setup

Interesting idea, but how performant is this? It seems the keys are sorted on every enumeration of the contents? – Priapism

@Priapism You're quite right, like I said, "Maybe not efficient". A more sophisticated version would cache and refresh the cache when the ditionary is changed. – Setup

Answer 4

ConcurrentDictionary, just like Dictionary, doesn't know the concept of sorting, i.e. it doesn't contain any ordering information. The result of OrderBy() has a specific order, but when assigned to Proxies the order information is lost.

Note that there are sorted implementations of IDictionary, namely SortedDictionary and SortedList.

Belaud

Certainly this is an issue the BCL Team can look into? – Priapism

Answer 5

The solution is to use a SortedSet<T>, discovered after many hours of research and code revision. A sorted set offers the unique-ness of a Dictionary or HashSet, but also allows sorting - neither a Dictionary nor a HashSet allow sorting.

Kazue

Except that a SortedSet is not Concurrent? I think having a collection that supports sorting and is concurrent is an essential item in our tool bag. I think we should encourage the BCL team to take a look at this. – Priapism