5
\$\begingroup\$

I had a problem where I needed to go through 9 million objects and I wanted to find the Top 10 based on some number (e.g. Result from a function)

I originally started off storing the number and object and then just using LINQ to OrderByDescending().Take(10) but I realized it was creating a huge array of references.

I decided I could use SortedList or SortedDictionary to keep a list of 10 things and have it constantly sorted and maintained but I ran into an issue where I wasn't allowed to have the same key appear twice. I came across https://stackoverflow.com/questions/5716423/c-sharp-sortable-collection-which-allows-duplicate-keys which eluded to solution for a limited sorted list that allows you specify how many top x or bottom x you want and allows you to feed it slowly while not taking up space.

I am asking for code review on LimitedSortedList. Looking for code quality or readability suggestions; I don't like the boolean in the constructor on determining top/bottom order.

Rather Tuple or KeyValuePair would be better for speed and space.

And if I should implement Insertion Sort instead of relying on C#'s Sort's generic Introsort which uses Insertion Sort only if the partition is less than 16; The sort algorithm will typically be sorting on a partially sorted array.

I have a feeling calling Sort (Insertion or not) so many times (potentially N times) that it may not be performant if I was just to mainained some sort of balanced tree and utilize that. Any suggestions?

public class LimitedSortedList<T1, T2> : List<Tuple<T1, T2>> where T1 : IComparable
{
    private readonly int _limit;
    private T1 _lowestKey;
    private readonly short _sortModifier;

    public LimitedSortedList(int limit, bool descending = true)
    {
        _limit = limit;
        _sortModifier =  (short) (descending ? -1 : 1);
    }

    public void Add(T1 key, T2 value)
    {
        if (Count < _limit || _sortModifier * key.CompareTo(_lowestKey) < 0)
        {
            Add(new Tuple<T1, T2>(key, value));
        }

        if (Count <= _limit) return;

        Sort();
        RemoveAt(_limit);
        _lowestKey = this[_limit - 1].Item1;
    }

    public new void Sort()
    {
        Comparison<Tuple<T1, T2>> c = (a, b) => _sortModifier * a.Item1.CompareTo(b.Item1);
        Sort(c);
    }
}

Here is example usage:

internal class Program
    {
        public class CustomObject
        {
            public int Id { get; set; }
            public double SortValue { get; set; }
            public override string ToString()
            {
                return $"Id: {Id}, SortValue: {SortValue}";
            }
        }
        private static void Main()
        {
            var list = new List<CustomObject>
            {
                new CustomObject {Id = 1, SortValue = 412421.123},
                new CustomObject {Id = 2, SortValue = 0.0},
                new CustomObject {Id = 3, SortValue = 0.0},
                new CustomObject {Id = 4, SortValue = 1.0},
                new CustomObject {Id = 5, SortValue = 1.34324},
                new CustomObject {Id = 6, SortValue = 4.432},
                new CustomObject {Id = 7, SortValue = -1.34324},
            };


            var top3 = new LimitedSortedList<double, CustomObject>(3);

            foreach (var o in list)
                top3.Add(o.SortValue, o);

            var bottom5 = new LimitedSortedList<double, CustomObject>(5, false);

            foreach (var o in list)
                bottom5.Add(o.SortValue, o);

            foreach (var x in top3)
                Console.WriteLine($"{x.Item1} {x.Item2}");

            foreach (var x in bottom5)
                Console.WriteLine($"{x.Item1} {x.Item2}");

            Console.ReadKey();
        }
    }

Output:

412421.123 Id: 1, SortValue: 412421.123
4.432 Id: 6, SortValue: 4.432
1.34324 Id: 5, SortValue: 1.34324

-1.34324 Id: 7, SortValue: -1.34324
0 Id: 2, SortValue: 0
0 Id: 3, SortValue: 0
1 Id: 4, SortValue: 1
1.34324 Id: 5, SortValue: 1.34324

This use-case may be trivial and perhaps not showing off the benefits of this class but it just gives you an idea. My original use-case of needing a result of a function AND also needed to store that functions result to be used later was key to this design. Using MoreLINQ's MaxBy allowed me to get the value but not the key and also would load all results into memory : https://stackoverflow.com/questions/19484563/morelinq-maxby-vs-linq-max-where

\$\endgroup\$
  • \$\begingroup\$ Not a review, but have you looked at Quickselect? If I've understood your problem correctly, this could be a simple solution. \$\endgroup\$ – hnefatl Aug 15 '17 at 10:45
1
\$\begingroup\$
  • Avoid special cases. The condition Count <= _limit is false about 9 million times, and the compiler has no means to optimize it. Better prefill your list with the first ten values, and get rid of this test.

  • As you mentioned, a boolean flag to govern sorting feels unclean. Consider passing a comparator object instead.

  • 10 is quite small, and pretty much any sorting technique will fit good. However, if you want this code to be scalable, consider a partial sort approach.

\$\endgroup\$
  • \$\begingroup\$ I agree prefilling would be ideal, but the nature is that the elements are adding one by one. The class won't know the first 10. Perhaps a way to send it 10 at a time? or somehow allow the caller to prefill it if they wanted to take advantage? I feel like this may be a micro-optimization at the cost of more complex code. Let me know what you think \$\endgroup\$ – ParoX Jun 18 '17 at 20:46
  • \$\begingroup\$ @ParoX Correct me if I am wrong, but you are passing limit anyway, don't you? So the class does know. \$\endgroup\$ – vnp Jun 18 '17 at 20:49
  • \$\begingroup\$ Yes it knows the limit but it doesnt get passed an IEnumerable, it gets passed a value. Perhaps I should have it take in an IEnumerable \$\endgroup\$ – ParoX Jun 18 '17 at 20:53
  • \$\begingroup\$ @ParoX Oh I see. I didn't realize that the class doesn't pull tuples, but is fed with them. That's another point I should add: a train is almost always better pulled than pushed. \$\endgroup\$ – vnp Jun 18 '17 at 20:59
1
\$\begingroup\$

1) You should use KeyValuePair instead of Tuple. Key is easier to read than Item1.

2) You might want to remove IComparable constraint and create two constructors: one that takes IComparer<T1> and another that uses Comparer<T1>.Default. That would be in line with other similar .Net collections.

3) T1 and T2 are poor names for generic parameters. TKey and TValue are better.

4) Your collection claims to be sorted. Yet it isn't until it reaches the limit. This is a pretty big surprise factor.

5) You extend List<T>, that has a pretty extensive api. Yet you only override Add method. And if you call other public methods it will likely break your collection. I suggest you use aggregation instead of inheritance an expose single Add method, to be safe.

6) Instead of sorting on every "add" operation you might want to do a linear or binary search (hard to tell which is better, it depends), and insert new item in its place straight away.

\$\endgroup\$
0
\$\begingroup\$

I had a problem where I needed to go through 9 million objects and I wanted to find the Top 10 based on some number (e.g. Result from a function)

I originally started off storing the number and object and then just using LINQ to OrderByDescending().Take(10) but I realized it was creating a huge array of references.

My original use-case of needing a result of a function AND also needed to store that functions result to be used later was key to this design. Using MoreLINQ's MaxBy allowed me to get the value but not the key and also would load all results into memory

Both of those approaches are extension methods which operate on an IEnumerable<T>. Why does the final code not do the same?

In addition, you state that MoreLINQ doesn't meet your requirements because it requires loading all the results into memory, but the code you posted also requires loading all the results into memory. On the other hand, MaxBy selects a single element rather than a configurable number of them.

I'm left with a strong feeling that the overall design is completely wrong, and I'm not sure you've accurately explained your requirements. On the basis of the requirements stated, I think you should be looking to implement the method signature

public static IQueryable<KeyValuePair<TKey, TSource>> Top<TSource, TKey>(
    this IQueryable<TSource> source,
    int n,
    Expression<Func<TSource, TKey>> keySelector,
    IComparer<TKey> comparer)

But on the basis of the requirements inferred from the actual code, I wonder whether you might really need the simpler

public static IEnumerable<KeyValuePair<TKey, TSource>> Top<TSource, TKey>(
    this IEnumerable<TSource> source,
    int n,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer)

I decided I could use SortedList or SortedDictionary to keep a list of 10 things and have it constantly sorted and maintained but I ran into an issue where I wasn't allowed to have the same key appear twice.

That's not a problem. It's easy to make the keys distinct by lifting to a tuple which pairs the key with the index in the source.

public static IEnumerable<KeyValuePair<Tuple<TKey, int>, TSource>
    ProjectDistinct<TSource, TKey>(this IEnumerable<TSource> elts,
                                   Func<TSource, TKey> proj)
{
    return elts.Select((elt, idx) => new KeyValuePair<Tuple<TKey, int>, TSource>(
               Tuple.Create(proj(elt), idx),
               elt));
}

Then you just need to wrap your IComparer<TKey> to make an IComparer<Tuple<TKey, int>> which breaks ties on the index.


Rather Tuple or KeyValuePair would be better for speed and space.

It's class vs struct. With only two elements, the struct is probably going to be better, but it's unlikely to be a bottleneck either way.


And if I should implement Insertion Sort instead of relying on C#'s Sort's generic Introsort which uses Insertion Sort only if the partition is less than 16; The sort algorithm will typically be sorting on a partially sorted array.

I have a feeling calling Sort (Insertion or not) so many times (potentially N times) that it may not be performant if I was just to mainained some sort of balanced tree and utilize that. Any suggestions?

On the basis of KISS and YAGNI you should start by using C#'s Sort. If profiling shows it to be worth optimising, you can consider more complicated approaches. But I doubt that it's worth maintaining a balanced tree. If you need to go beyond a simple sort, it probably makes more sense to pick a buffer size N (I imagine that something on the order of 2n/3 makes sense, but I haven't worked through the calculations in detail) and use a binary heap of size N:

  1. Take the first n elements from the source, put them into an array top, and sort it.
  2. Read elements from the source, discarding them if they're smaller than the smallest element of top, and otherwise inserting them into the binary heap. Do this until the heap is full or you reach the end of the source.
  3. Combine the top n elements of the binary heap with top, either by insertion sort or by merge sort.
  4. If there are more elements, clear the heap and loop back to step 2.
  5. return top;
\$\endgroup\$
-1
\$\begingroup\$

This will be pretty efficient. Just using int for ease.

For your class implement iComparable

public static int Kth(List<int> list, int k)
{
    SortedSet<int> ss = new SortedSet<int>();
    if(k > list.Count)
    {
        throw new IndexOutOfRangeException();
    }
    int count = 0;
    foreach(int i in list)
    {               
        if(count < k)
        {
            ss.Add(i);
        }
        else if (i > ss.Min)
        {
            ss.Remove(ss.Min);
            ss.Add(i);
        }
        count++;
    }

    return ss.Min;
} 
\$\endgroup\$
  • 1
    \$\begingroup\$ I need the ability to have non-unique values though, which I believe none of the sorted data structures support \$\endgroup\$ – ParoX Jul 16 '17 at 17:45
  • \$\begingroup\$ You could use a binary tree. It is actually faster than SortedSet. \$\endgroup\$ – paparazzo Jul 16 '17 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.