Есть ли в 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, но вся коллекция будет отсортирована в этом процессе.