expression tree instead of using LINQ

I have a 开发者_JAVA技巧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.

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;
}

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 ;-)

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.