Объединение инвертированных списков

Дайте k отсортированных инвертированных списков, я хочу эффективный алгоритм, чтобы получить объединение этих K списков? Каждый инвертированный список является массивом только для чтения в памяти, каждый список содержит целое число в отсортированном порядке. результат будет сохранен в предопределенном массиве, который достаточно велик. Есть ли алгоритм лучше, чем k-way merge?

2 2
algorithm search-engine information-retrieval

2 ответа:

K-образное слияние является оптимальным. Он имеет O(log(k)*n) ops [где n - число элементов во всех списках вместе взятых].

Легко видеть, что это не может быть сделано лучше - как упоминал @jpalecek, в противном случае вы могли бы сортировать любой массив лучше, чем O(nlogn), разбивая его на куски [инвертированные индексы] размера 1.

    Примечание: этот ответ предполагает, что важно, чтобы инвертированные индексы [результирующий массив] будет отсортирован. Это предположение справедливо для большинства приложения, использующие инвертированные индексы, особенно в городе. Информационно-поисковая зона. Эта функция [сортированные индексы] позволяет элегантное и быстрое пересечение индексов.
  • примечание: что стандартное K-образное слияние допускает дублирование, вам придется убедитесь, что если элемент появляется в двух списках, он будет добавлено только один раз [легко сделать это, просто проверив последний элемент в целевой массив перед добавлением].
2

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

Что-то вроде (Perl): 

my %seen;
@merged = grep { exists $seen{$_} ? 0 : ($seen{$_} = 1) } (map {(@$_)} @inputs);
-1