Есть ли в C# эквивалент std::nth_element?

Question

Я переношу некоторый код C++ на C#.

Есть ли в C# эквивалент std::nth_element() или мне нужно самому свернуть?

Answer 1

Я предполагаю, что вы ищете метод доступа, который возвращает N-й элемент неупорядоченной коллекции, выполняя частичную сортировку коллекции. Это бывает полезно, когда у вас очень большая коллекция и вас интересует один из первых элементов на основе некоторого предиката упорядочивания.

Насколько мне известно, ни расширения .NET BCL, ни LINQ не предлагают эквивалента. Все методы сортировки (включая Enumerable.OrderBy) выполняют полное упорядочивание коллекции.

Если вам нужна эффективная версия Nth, для этого вам потребуется внедрить собственный метод расширения в IEnumerable.Если вы собираетесь использовать свои собственные средства, возможно, вам стоит изучить Алгоритм быстрого выбора, который имеет производительность O(n).

Если версии грубой силы достаточно, вы можете использовать LINQ:

var someCollection = new []{ 5, 2, 8, 9, 0, 1, 3, 12, 4 };

var fifthItem = someCollection.NthItem(5);

public static class NthExtensions 
{
    public static T NthItem(this IEnumerable<T> coll, int n) 
    {
        return coll.OrderBy(x => x).Skip(n - 1).First();
    }
}

Answer 2

Нет, это не так.Вам придется написать алгоритм выбора (желательно быстрый выбор) рукой.

Answer 3

Прямого эквивалента нет.Потенциально вы могли бы использовать LINQ OrderBy и Take/Skip для достижения тех же целей на любом IEnumerable, но в этом процессе будет отсортирована вся коллекция.