Top N max/min values

[OtherSide]

Пусть есть задача, по моему достаточно хрестоматийная, взять Top max N значений массива длиной M
можно конечно квиксортнуть и взять топ, но логика подсказывает можно сделать быстрее чем o ( N * Log N)

Создаем отсортированный массив длиной N и идем по основному, если значение больше минимального в отсортированном, вставляем, а нижнее выкидываем, т.е. при N << M сложность стремится к o(N)

Вопрос - есть ли этот алгоритм в стандартных библеотеках (LINQ)

[Pantigalt]

Пусть есть задача, по моему достаточно хрестоматийная, взять Top max N значений массива длиной M
можно конечно квиксортнуть и взять топ, но логика подсказывает можно сделать быстрее чем o ( N * Log N)

Создаем отсортированный массив длиной N и идем по основному, если значение больше минимального в отсортированном, вставляем, а нижнее выкидываем, т.е. при N << M сложность стремится к o(N)

Вопрос - есть ли этот алгоритм в стандартных библеотеках (LINQ)

1. Если идет проход по основному массиву длины M то сложность будет M*N, в этом случае я не пойму чем это лучше просто последовательной выборки максимального элемента (partial select sort).

2. Насколько я понимаю ваша задача сводится к следующей проблеме - find the kth smallest element in an unordered list.
Зная этот элемент можно разделить массив по этому элементу.

3. Eсли брать С++ то в стандарте есть такой метод std::nth_element.
Думаю если посмотреть на шаблонный код можно конвертировать его в C# код.

Вопрос - есть ли этот алгоритм в стандартных библеотеках (LINQ)

4. Я лично не знаю эффективного эквивалента. В LINQ обычно идет простая итерация по интерфейсу IEnumerable, нет произвольного доступа к массиву.

[OtherSide]

1. Если идет проход по основному массиву длины M то сложность будет M*N, в этом случае я не пойму чем это лучше просто последовательной выборки максимального элемента (partial select sort).

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

[tessob]

Я думал, что чтение из сортированного массива - log n, а вставка дорогое удовольствие. Что-то поменялось? ))

[Dweller]

Я думал, что чтение из сортированного массива - log n, а вставка дорогое удовольствие. Что-то поменялось? ))

Priority queue

[tessob]

Я думал, что чтение из сортированного массива - log n, а вставка дорогое удовольствие. Что-то поменялось? ))

Priority queue

"из сортированного массива"?

[Dweller]

Я думал, что чтение из сортированного массива - log n, а вставка дорогое удовольствие. Что-то поменялось? ))

Priority queue

"из сортированного массива"?

это и есть сортированный массив, и вставка туда log(n)

[M. Ridcully]

Min (for max elements) heap of size n.
Никаких сортировок.

[M. Ridcully]

Кстати, если про C++ говорить, то чтобы заменить минимальный элемент bubble_down ручками писать придётся.
Строго говоря, это будет быстрее, чем pop_heap & push_heap.

[OtherSide]

Min (for max elements) heap of size n.
Никаких сортировок.

и как это будет на Linq?

[M. Ridcully]

Min (for max elements) heap of size n.
Никаких сортировок.

и как это будет на Linq?

Сорри, я Dweller-у, отвечал, на его "сортировки". Что сортировать ничего для priority queue не надо.
Про Linq ничего не знаю.

[Dweller]

Min (for max elements) heap of size n.
Никаких сортировок.

и как это будет на Linq?

Сорри, я Dweller-у, отвечал, на его "сортировки". Что сортировать ничего для priority queue не надо.
Про Linq ничего не знаю.

причем тут сортировка? priority queue и делается с помощью heap

[M. Ridcully]

причем тут сортировка? priority queue и делается с помощью heap

Ну да, я это и хотел сказать.
Выше просто чего-то про "сортированный массив" было, я как раз и хотел написать, что никаких сортированных массивов не нужно.
Почитал повыше - может, это и не вам...

[AndreyT]

Пусть есть задача, по моему достаточно хрестоматийная, взять Top max N значений массива длиной M
можно конечно квиксортнуть и взять топ, но логика подсказывает можно сделать быстрее чем o ( N * Log N)

Квиксортнуть и взять топ будет O( M * Log M)

Создаем отсортированный массив длиной N и идем по основному, если значение больше минимального в отсортированном, вставляем, а нижнее выкидываем, т.е. при N << M сложность стремится к o(N)

Задача решается алгоритмом, который похож на квиксорт по своей структуре, но не занимается лишней работой, т.е. 1) не сортирует больше, чем надо, 2) не обрабатывает заведомо ненужный "хвост" массива.

Сначала выполняем классический partitioning из квиксорта. Пусть после partitioning правая половина массива содержит R значений.
* Если R == N, то вся правая половина - искомый результат. Стоп.
* Если R < N, то вся правая половина массива входит в наши искомые значения. Далее рекурсивно применяем этот же алгоритм к левой половине массива для поиска недостающих N-R максимальных значений.
* Если R > N, то левая половина нас больше не интересует. Рекурсивно применяем этот же алгоритм к правой половине для поиска N максимальных значений.

На каждом уровне делается только один рекурсивный вызов (а не два, как в квиксорте), т.е. алгоритм натурально цикличен. Сложность в среднем - O(M).

Однако если заведомо известно, что N << M, то из практических соображений лучше подойдет именно ваш алгоритм. Не составит труда интегрировать его в вышеприведенный алгоритм для решения подзадач именно при условии N << M.

[OtherSide]

--

[OtherSide]

Однако если заведомо известно, что N << M, то из практических соображений лучше подойдет именно ваш алгоритм. Не составит труда интегрировать его в вышеприведенный алгоритм для решения подзадач именно при условии N << M.

Да неохота что то интегрировать, изобретать велосипед. Реализация тривиальная, неужели нет готового? Ну или хотя бы правильное название задачи, что бы нагуглить чей то гитхаб или код на stackoverflow