Каков наиболее эффективный способ создания верхних N элементов объединения M отсортированных множеств

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

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

Лучший способ, которым я мог подумать, - это:

  1. Возьмите верхние N элементов из каждого набора
  2. Найдите предмет с самым низким рангом и самым высоким счетом для этого ранга.
  3. Поделитесь этим счетом количеством наборов. (Любой ключ со счетом ниже этого никогда не может быть в верхней части N)
  4. Возьмите союз этих ключей. (Игнорирование баллов)
  5. Найдите оценки для всех ключей во всех наборах. (Ключ может иметь счет 1 в одном наборе и 10000 в другом)

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

[edit] Ключи встречаются в одном или нескольких наборах, и их суммарные баллы определяют окончательный результат. Таким образом, ключ, который находится во всех наборах с низкой оценкой, может иметь более высокий балл, чем ключ с высоким счетом, который находится только в одном наборе.

1 ответ

Алгоритм, который вы предлагаете, кажется довольно неудобным. Просто выполните одно из следующих действий:

Простой способ

for i = 1 to n
 loop through all sets and look at their smallest element,
 pick the smallest element and remove it from the sets

Сложность: O (n * s), где n - количество элементов, которые вы хотите, а s - количество наборов.

Конечно, если вам не разрешено удалять элементы из наборов, вы также можете поддерживать iterators в каждом наборе, чтобы получить элементы из них в отсортированном порядке без необходимости изменять наборы.

Более эффективный способ

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

Сложность. Предположим, что простая очередь приоритетов с сложностью O(log n) 'insert' и O(log n) 'remove smallest element'. Есть лучшие, такие как кубики фибоначчи, но это будет хорошо. Тогда мы имеем:

  • s для заполнения очереди приоритетов в начале, поэтому O(s log s).
  • n "удалить наименьший элемент" + вставить новый, так что O(n log s) (так как в очереди всегда есть s элементов)

Таким образом, мы достигаем O(s log s + n log s) который лучше.

сравнение

Пока s довольно мало, не должно быть большой разницы между алгоритмами, и вы также можете выбрать простой. Если у вас много наборов, вам обязательно нужно пойти на второй подход.

Сложность поиска

В моем анализе я опустил логарифмический коэффициент поиска, чтобы найти наименьший элемент для каждого набора, и предположил, что наименьший элемент каждого набора можно получить в O(1), как в отсортированном списке. Изменение стоимости поиска от O(1) до O(log n) просто вводит дополнительный фактор, который не изменяет алгоритмы. Кроме того, вы обычно только платите O(log n) один раз при первом поиске. Впоследствии у вас обычно есть итератор для самого маленького элемента. Доступ к каждому последующему элементу с использованием итератора тогда будет только O(1).

licensed under cc by-sa 3.0 with attribution.