#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 .