CODEWITHSUNDEEP
c#
Elena
Elena

Reputation: 839

expression tree instead of using LINQ

I have a LIST<T> where T:IComparable<T>

I want to write a List<T> GetFirstNElements (IList<T> list, int n) where T :IComparable <T> which returns the first n distinct largest elements ( the list can have dupes) using expression trees.

Upvotes: 0

Views: 218

Answers (3)

Corey Kosak
Corey Kosak

Reputation: 2625

The standard algorithm for doing so, which takes expected time O(list.Length) is in Wikipedia as "quickfindFirstK" on this page:

http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements

This improves on @Marc Gravell's answer because the expected running time of it is linear in the length of the input list, regardless of the value of n.

Upvotes: 0

Marc Gravell
Marc Gravell

Reputation: 1062780

In some performance-critical code I wrote recently, I had a very similar requirement - the candidate set was very large, and the number needed very small. To avoid sorting the entire candidate set, I use a custom extension method that simply keeps the n largest items found so far in a linked list. Then I can simply:

  • loop once over the candidates
  • if I haven't yet found "n" items, or the current item is better than the worst already selected, then add it (at the correct position) in the linked-list (inserts are cheap here)
    • if we now have more than "n" selected, drop the worst (deletes are cheap here)

then we are done; at the end of this, the linked-list contains the best "n" items, already sorted. No need to use expression-trees, and no "sort a huge list" overhead. Something like:

public static IEnumerable<T> TakeTopDistinct<T>(this IEnumerable<T> source, int count)
{
    if (source == null) throw new ArgumentNullException("source");
    if (count < 0) throw new ArgumentOutOfRangeException("count");
    if (count == 0) yield break;

    var comparer = Comparer<T>.Default;
    LinkedList<T> selected = new LinkedList<T>();

    foreach(var value in source)
    {
        if(selected.Count < count // need to fill
            || comparer.Compare(selected.Last.Value, value) < 0 // better candidate
            )
        {
            var tmp = selected.First;
            bool add = true;
            while (tmp != null)
            {
                var delta = comparer.Compare(tmp.Value, value);
                if (delta == 0)
                {
                    add = false; // not distinct
                    break;
                }
                else if (delta < 0)
                {
                    selected.AddBefore(tmp, value);
                    add = false;
                    if(selected.Count > count) selected.RemoveLast();
                    break;
                }
                tmp = tmp.Next;
            }
            if (add && selected.Count < count) selected.AddLast(value);
        }
    }
    foreach (var value in selected) yield return value;
}

Upvotes: 3

oberfreak
oberfreak

Reputation: 1807

If i get the question right, you just want to sort the entries in the list.
Wouldn't it be possible for you to implement the IComparable and use the "Sort" Method of the List?
The code in "IComparable" can handle the tree compare and everything you want to use to compare and sort so you just can use the Sort mechnism at this point.

List<T> GetFirstNElements (IList<T> list, int n) where T :IComparable <T>{
    list.Sort();
    List<T> returnList = new List<T>();
    for(int i = 0; i<n; i++){
        returnList.Add(list[i]);
    }
    return returnList;
}

Wouldn't be the fastest code ;-)

Upvotes: 0

Related Questions