выбор / слияние топ-к

Question

У меня есть n отсортированные списки (5

Пример для k = 2:

top2 (L1: [ 'a': 10, 'b': 4, 'c':3 ]) = ['a':10 'b':4]
top2 (L2: [ 'c': 5, 'b': 2, 'a':0 ]) = ['c':5 'b':2]

Интересно, когда мне нужно, чтобы комбинировал top k во всех отсортированных списках .

top2(L1+L2) = ['a':10, 'c':8]

Простое объединение верхней k индивидуального списка не обязательно даст правильные результаты:

top2(top2(L1)+top2(L2)) = ['a':10, 'b':6]

Цель состоит в том, чтобы уменьшить необходимое пространство и сохранить отсортированныесписки малы.

top2(topX(L1)+topX(L2)) = ['a':10, 'c':8]

Вопрос в том, существует ли алгоритм для вычисления комбинированной вершины k, имеющей правильный порядок , при отрезании длинного хвоста списков в определенной позиции.И если есть: Как найти предел X, где безопасно сократить?

Примечание: правильные значения не важны .Только заказ.

top2(magic([L1,L2])) = ['a', 'c']

Answer 1

Этот алгоритм использует память O (U), где U - количество уникальных ключей. Я сомневаюсь, что могут быть достигнуты более низкие границы памяти, поскольку невозможно определить, какие ключи можно отбросить, пока все ключи не будут удалены. были суммированы.

1. Составьте основной список (key: total_count) кортежей. Просто просмотрите каждый список по одному элементу за раз, подсчитав, сколько раз каждый ключ был просмотрен.
2. Используйте любой алгоритм выбора top-k в основном списке, который не использует дополнительную память. Одним простым решением является сортировка списка по месту.

Answer 2

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

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

Answer 3

Есть разумный способ реализовать это через mapreduce:

http://www.yourdailygeekery.com/2011/05/16/top-k-with-mapreduce.html

Answer 4

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

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

Например, если есть n = 100 отсортированных списков, и вы просматривали каждый список до тех пор, пока счетчик не станет равным 2, то максимальное общее количество ключей может увеличиться на 200.

Я предлагаю использовать итеративный подход:

1. Подсчитывайте каждый список до тех пор, пока не будет достигнут определенный нижний порог счета L.
2. Понизьте L, чтобы включить больше кортежей.
3. Добавьте новые кортежи к подсчетам на данный момент.
4. Переходите к шагу 2 до тех пор, пока понижение L не изменит число верхних k более чем на определенный процент.

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

Answer 5

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

(Новый) Алгоритм:

1. (Повторная сортировка каждого списка по идентификатору (, а не поподсчитывать ).Чтобы освободить память, список можно записать обратно на диск.Требуется только достаточно памяти для самого длинного списка.
2. Получите следующий наименьший необработанный идентификатор и найдите общее количество во всех списках.
3. Вставьте идентификатор в приоритетную очередь из k узлов.Используйте общее количество как приоритет узла (не идентификатор).Эта очередь приоритетов удаляет самый нижний узел, если вставлено более k узлов.
4. Переходите к шагу 2, пока не будут исчерпаны все идентификаторы.

Анализ: этот алгоритм может быть реализован с использованием только O (k) дополнительной памяти для хранениямин-куча.Для этого необходимо выполнить несколько компромиссов:

1. Списки отсортированы по идентификатору на месте;первоначальные заказы по счетам теряются.В противном случае требуется O (U) дополнительная память для создания основного списка с идентификатором: total_count, где кортежи, где U - число уникальных идентификаторов.
2. Следующий наименьший идентификатор найден за время O (n) путем проверки первого кортежа.каждого списка.Это повторяется U раз, где U - количество уникальных идентификаторов.Это может быть улучшено с использованием минимальной кучи для отслеживания следующего наименьшего идентификатора.Это потребует O (n) дополнительной памяти (и может не быть быстрее во всех случаях).

Примечание. Этот алгоритм предполагает, что идентификаторы можно быстро сравнивать.Сравнение строк не тривиально.Я предлагаю хеширование идентификаторов строк для целых чисел.Они не обязательно должны быть уникальными хэшами, но коллизии должны проверяться, чтобы все идентификаторы были правильно отсортированы / сопоставлены.Конечно, это увеличит сложность памяти / времени.

Answer 6

В общем, я думаю, что у вас проблемы. Представьте себе следующие списки:

['a':100, 'b':99, ...]
['c':90, 'd':89, ..., 'b':2]

и у вас есть k = 1 (т.е. вы хотите только верхний). «b» - правильный ответ, но вам нужно посмотреть до конца второго списка, чтобы понять, что «b» превосходит «a».

Edit:

Если у вас правильное распределение (длинные хвосты с небольшим количеством), вы можете добиться большего успеха. Давайте пока держим k = 1, чтобы облегчить нашу жизнь.

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

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

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

Answer 7

1. Свяжите индекс с каждым из ваших n списков. Установите его так, чтобы он указывал на первый элемент в каждом случае.
2. Создание списка списков и сортировка его по индексированным элементам.
3. Индексированный элемент в верхнем списке в списке списков - ваш первый элемент.
4. Увеличьте индекс для самого верхнего списка, удалите этот список из списка списков и заново вставьте его на основе нового значения его индексированного элемента.
5. Индексируемый элемент в верхнем списке в вашем списке списков - ваш следующий элемент
6. Перейти к 4 и повторять до тех пор, пока не будет сделано.

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