Как оптимизировать выборку с одновременной сортировкой?

Question

[dollar]

Есть большое множество элементов (в оперативной памяти), каждый из которых имеет некоторый набор тегов и вес (число, критерий для сортировки). Нужно сначала выбрать все элементы по 2-3 тегам, а потом из результата выбрать 10 штук с наибольшим весом.

С тегами вроде всё просто - это хеширование. Если раскидать ссылки на элементы по хеш-таблицам, то можно почти за O(1) выбрать все нужные. Но потом в любом случае придётся сортировать. Можно ли как-то оптимизировать эту сортировку или избавиться от неё? Потому что на счету каждая микросекунда.

Comments

[Lynn «Кофеман»]

Для выбора 10 максимальных сортировка не нужна. Достаточно одного прохода.

[Lynn «Кофеман»]

Но в целом непонятно почему нельзя просто взять хоть тот же mysql.

[dollar]

Алексей Тен,

Для выбора 10 максимальных сортировка не нужна.

Постойте. Как это сделать без сортировки?

[Lynn «Кофеман»]

Про один проход я кажется соврал, но линейный в среднем алгоритм есть https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...

[dmshar]

Алексей Тен, Да вроде не соврали. Именно за один проход выбирается K наибольших элементов неупорядоченного массива. Другое дело, что при обработке каждого нового элемента проводится его сравнение с ранее найденными K наибольшими ранее просмотренными на данный момент времени элементами массива. Но это фиксированная по времени операция.

Answer 1

[dollar]

В общем, оказалось, что существенно ускорить алгоритм можно, если хоть капельку известна природа исходных данных.

• Если известно распределение и границы, то почти точно вычисляем порог, выше которого будут наши 10 элементов. Раскладываем массив на две части (выше порога и ниже порога) за O(N). Даже если набрали 11-12 элементов больше порога, то за O(мало) уже смело сортируем и находим 10.
  
• Если распределение не известно, но известны границы (то есть минимум и максимум), то делаем предположение, что распределение равномерное, после чего вычисляем порог и задача сводится к предыдущему пункту.
  
• Если границы не известны, то за O(N) вычисляем минимум и максимум, после чего задача сводится к предыдущему пункту.
  

Конечно, всегда можно специально подсунуть такие данные, что алгоритм будет не эффективен. Но противодействие такому за рамками вопроса.

Answer 2

[uvelichitel]

Куча/heap. Стройте кучу длиной 10 штук, пока выбираете. Куча может быть очень эффективно представлена массивом, имеет качественные реализации на почти всех языках. Ваша задача - академический пример применения кучи.