Ограниченный алгоритм сортировки / фильтрации

Question

У меня довольно большой список элементов (сотни тысяч).

У меня есть фильтр, который может принимать или не принимать элементы.

Мне нужны первые 100 элементов, которые удовлетворяютфильтр.

Пока что я сначала отсортировал результаты, а затем взял 100 лучших, которые удовлетворяют фильтру.Это объясняется тем, что фильтр не совсем быстрый.

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

Существует ли алгоритм, объединяющий задачи сортировки / фильтрации, чтобы получить 100 лучших результатов, удовлетворяющих фильтру, без затрат на сортировку всех элементов?

Answer 1

Мой инстинкт - выбрать 100 лучших элементов из списка (гораздо дешевле, чем сортировать, используйте ваш любимый вариант QuickSelect).Запустите их через фильтр, получив n успехов и 100-n сбоев.Если n < 100, то повторите, выбрав 100-n элементов в верхней части остальной части списка:

k = 100
while (k > 0):
    select top k from list and remove them
    filter them, yielding n successes
    k = k - n

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

Я ожидаю, что это имеет некоторые плохие случаи.Если почти все элементы не проходят фильтрацию, это значительно медленнее, чем просто сортировка, поскольку в итоге вы выберете тысячи раз.Таким образом, вы можете захотеть, чтобы некоторые критерии выручили, если он выглядит плохо, и вернулись к сортировке всего списка.

У него также есть проблема, заключающаяся в том, что он, вероятно, выполнит большое количество маленьких выборок в конце, так какмы ожидаем, что k будет уменьшаться экспоненциально, если критерии фильтра не связаны с критериями сортировки.Таким образом, вы могли бы улучшить его, выбрав несколько больше чем k элементов на каждом шаге.Скажем, k делится на ожидаемую частоту успеха фильтра плюс небольшую константу.Ожидание, основанное на прошлой производительности, если нет знания предметной области, которое вы можете использовать, чтобы предсказать его, и небольшую константу, выбранную экспериментально, чтобы избежать досадно большого количества шагов, чтобы найти несколько последних элементов.Если на каком-либо этапе вы получите больше элементов, которые прошли фильтр, чем число, которое вы все еще ищете (т. Е. N> k), то выберите верхний k из текущей серии успехов, и все готово.

Поскольку QuickSelect дает вам верхнее k без сортировки этих k, вам нужно будет выполнить окончательную сортировку из 100 элементов, если вам нужны верхние 100 по порядку.

Answer 2

Предложение Стива использовать Quicksort хорошее.

1 Прочитайте первые 1000 или около того элементов.
2 Сортируйте их и выберите 100-й по величине элемент.
3 Выполните один проход быстрой сортировки по всему файлу с элементом из шага 2 в качестве сводной.
4 Выберите верхнюю половину результата прохода быстрой сортировки для дальнейшей обработки.

Вам гарантировано не менее 100 элементов в верхней половине одного прохода быстрой сортировки. Предполагая, что первые 1000 достаточно представительны для всего файла, вы должны получить примерно одну десятую от первоначальных элементов на шаге 4.

Answer 3

Я, вероятно, сначала отфильтрую, а затем вставлю результат этого в очередь с приоритетами. Следите за количеством элементов в PQ, и после того, как вы сделаете вставку, если она больше, чем число, которое вы хотите сохранить (100 в вашем случае), вытолкните самый маленький элемент и выбросьте его.

Answer 4

Если я правильно понимаю, у вас есть два варианта:

• Выбор 100 элементов - N операций проверки фильтра. Тогда 100 (LG 100) для сортировки.

• Сортировка, затем выбор 100 элементов - как минимум N (lg N) для сортировки, затем выбор.

первый звук короче, чем сортировка и выбор.

Answer 5

Я решил эту проблему, используя двоичное дерево для сортировки и ведя подсчет элементов слева от текущего узла во время вставки. Подробнее см. http://pub.uni -bielefeld.de / публикация / 2305936 (рисунок 4.4 и др.).