dollar
@dollar
123

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

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

С тегами вроде всё просто - это хеширование. Если раскидать ссылки на элементы по хеш-таблицам, то можно почти за O(1) выбрать все нужные. Но потом в любом случае придётся сортировать. Можно ли как-то оптимизировать эту сортировку или избавиться от неё? Потому что на счету каждая микросекунда.
  • Вопрос задан
  • 90 просмотров
Решения вопроса 1
dollar
@dollar Автор вопроса
123
В общем, оказалось, что существенно ускорить алгоритм можно, если хоть капельку известна природа исходных данных.
  • Если известно распределение и границы, то почти точно вычисляем порог, выше которого будут наши 10 элементов. Раскладываем массив на две части (выше порога и ниже порога) за O(N). Даже если набрали 11-12 элементов больше порога, то за O(мало) уже смело сортируем и находим 10.
  • Если распределение не известно, но известны границы (то есть минимум и максимум), то делаем предположение, что распределение равномерное, после чего вычисляем порог и задача сводится к предыдущему пункту.
  • Если границы не известны, то за O(N) вычисляем минимум и максимум, после чего задача сводится к предыдущему пункту.

Конечно, всегда можно специально подсунуть такие данные, что алгоритм будет не эффективен. Но противодействие такому за рамками вопроса.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
Куча/heap. Стройте кучу длиной 10 штук, пока выбираете. Куча может быть очень эффективно представлена массивом, имеет качественные реализации на почти всех языках. Ваша задача - академический пример применения кучи.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы