Sorting

Perhaps one of the most common questions I am asked with dynamic data is about sorting data. The observable cache has for years had many sorting options yet the observable list has been lacking anything but basic sorting. This has been rectified from Dynamic Data v5 (if using Rx v3) or v4.8.1 (if using Rx 2.2.5).

The example here illustrates sorting an observable list only. The observable cache sorting options are almost identical and are not shown here.

Note: When using the source cache, sort is only respected by the bind, page and virtualise operator. This is for performance reasons as the state is stored in a dictionary which has no concept of ordering. Therefore you should apply the sort immediately before Bind.

The basics

Out of the box sorting is simple. If you have the following observable list.

var list = new SourceList<Person>();

it can be sorted like this

var myComparer = SortExpressionComparer<Person>.Ascending(p => p.Name).ThenByAscending(p => p.Age);
var sorted = list.Connect().Sort(myComparer);

When the source list is amended the data is arranged into its correct position. If your data is immutable this works like a charm and there is nothing to worry about.

If the values which you are sorting on are immutable the following option can be passed in which can lead to a significant performance increase particularly when there is a lot of data.

var sorted = list.Connect().Sort(myComparer, SortOptions.UseBinarySearch);

SortOptions.UseBinarySearch allows the algorithm to find existing items and to determine insert positions using binary search algorithm. If the values are mutable and this option is specified an exception will be thrown.

Another optimisation when using large data sets is to specify a reset threshold. When sorting, the algorithm has to either find the position of an item which is to be removed and the insert position of a new item. For large numbers of changes finding the position for each item can be very slow. The reset threshold is used to instruct the algorithm to re-sort all items when the total number of changes exceeds the threshold.

var withThreshold = list.Connect().Sort(myComparer,resetThreshold:50);

In my experience I mostly do not have to specify these optimisations except for the rare occasion that performance is suffering from sorting large data sets.

Dynamically changing the comparer

The sort order can be dynamically changed by specifying an observable comparer.

IObservable<IComparer<T>> comparerObservable= \\...;
var sorted = list.Connect().Sort(myComparer, comparerChanged: comparerObservable)

The list will reorder itself when the comparer observable notifies a different comparer.

Sorting on mutable values

I love and am a great advocate of immutability. However life is not always easy and sometimes we are required to sort on a value which changes. The change may be caused by a property change or because it depends on some external value or function.

The following overload is used to resort on a value which can change.

IObservable<Unit> resortObservable = \\...;
var sorted = list.Connect().Sort(myComparer, resort: resortObservable)

The resort overload is an optimised means of reordering. The observable is a simple instruction to say there is a need to re-evaluate the sorted set. The difference between this and changing comparer is the algorithm will only move items which have changed, whereas changing the comparer will force the entire set to be reordered.

In the case of property changes I usually resort like this.

var propertyChanges = list.Connect().WhenPropertyChanged(p => p.Age)
	.Throttle(TimeSpan.FromMilliseconds(250))
	.Select(_ => Unit.Default);
	
var sorted = list.Connect().Sort(myComparer, resort: propertyChanges);

The reason I have not created an automatic sorter is the consumer only has to do a small amount of plumbing yet they are empowered to optimise the performance i.e. if the object sorts after each change, performance would be poor when there are a large number of successive property changes.