Блог

Главная - Вопросы по программированию - дерево выражений вместо использования LINQ

дерево выражений вместо использования LINQ

#c#

#c#

Вопрос:

У меня есть LIST<T> where T:IComparable<T>

Я хочу написать a List<T> GetFirstNElements (IList<T> list, int n) where T :IComparable <T> , который возвращает первые n отдельных самых больших элементов (в списке могут быть дубликаты), используя деревья выражений.

Комментарии:

1. Почему бы не использовать LINQ? И как именно деревья выражений помогут решить эту проблему?

2. Почему? Что не так с LINQ? Используйте подходящий инструмент.

3. @Elena: Как вы думаете, почему деревья выражений ускорят работу? Когда вы говорите, что боитесь , что это неэффективно, есть ли у вас доказательства того, что это слишком медленно для того, что вы хотите?

4. @Elena даже с этим разъяснением я не вижу никакой связи с использованием деревьев выражений здесь…

5. @Merlyn — не совсем; представьте себе данные «1,2,3,4,5,6,7»; distinct — «1,2,3,4,5,6,7»; take n = 3 — «1,2,3»; sort (desc) — «3,2,1» — теперь, что случилось с 7, 6, 5 и 4?

Ответ №1:

В каком-то критически важном для производительности коде, который я недавно написал, у меня было очень похожее требование — набор кандидатов был очень большим, а число требовалось очень маленьким. Чтобы избежать сортировки всего набора кандидатов, я использую пользовательский метод расширения, который просто сохраняет n самых больших элементов, найденных до сих пор в связанном списке. Тогда я могу просто:

  • цикл один раз по кандидатам
  • если я еще не нашел «n» элементов или текущий элемент лучше, чем худший из уже выбранных, добавьте его (в правильном положении) в связанный список (вставки здесь дешевы)
    • если теперь у нас выбрано больше, чем «n», отбросьте худшее (удаления здесь дешевы)

тогда мы закончили; в конце этого связанный список содержит лучшие «n» элементов, уже отсортированных. Нет необходимости использовать деревья выражений и нет накладных расходов «сортировать огромный список». Что-то вроде:

 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>.Defau<
    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 amp;amp; selected.Count < count) selected.AddLast(value);
        }
    }
    foreach (var value in selected) yield return value;
}

Комментарии:

1. Будет ли это логически отличаться от или гарантированно лучше, чем: list.Distinct().Take(n).OrderBy(t => t) ?

2.@Merlyn да; во-первых, это будет правильно — если вы Take и затем OrderBy , вы сортируете только первые n элементы, которые находятся в последовательности, что совсем не похоже на получение верхних n элементов. Во-вторых, сортировка является дорогостоящей (для большого списка) — при O(m*log(m)) (для размера списка m ) вышеуказанное должно быть намного ближе O(m) к небольшому n . Однако он немного уязвим для патологических крайних случаев, но обратите внимание, что он также экономит пространство; он не требует много рабочего пространства.

3. 1; Я получаю разницу между сортировкой, а не сортировкой. У меня сложилось впечатление, что OP пытался избежать O(N) операции. Видя, что это не так, я думаю, я понимаю, что ваше решение по-прежнему O(N) , но экономит пространство, а при низком N и хорошем списке кандидатов все еще может быть экономичным по времени.

4.@Merlyn обычный порядок — это O(m*log(m)) примечание, поэтому переход к O(m) нему — хорошая вещь

5. Теперь я говорю расплывчато 🙂 Я полагал, что это может быть почти O(n) вместо O(m) или больше. Это невозможно, поэтому ваша реализация кажется удачной (помимо доказательства патологических проблем, вызывающих высокую амортизированную стоимость, которую я не в состоянии предоставить, и у меня пока нет оснований полагать. Вы уже обрабатываете предварительно отсортированные случаи, так что не беспокойтесь).

Ответ №2:

Если я правильно понял вопрос, вы просто хотите отсортировать записи в списке.
Разве вы не могли бы реализовать IComparable и использовать метод «Сортировки» списка?
Код в «IComparable» может обрабатывать сравнение дерева и все, что вы хотите использовать для сравнения и сортировки, поэтому на данном этапе вы можете просто использовать механизм сортировки.

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

Это был бы не самый быстрый код 😉

Ответ №3:

Стандартный алгоритм для этого, который занимает ожидаемое время O(список.Длина) находится в Википедии как «quickfindFirstK» на этой странице:

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

Это улучшает ответ @Marc Gravell, потому что ожидаемое время его выполнения линейно по длине входного списка, независимо от значения n .