Получение 100 лучших номеров из ста миллионов номеров

Question

Один из моих друзей задал вопрос

Извлечение макс. 100 лучших номеров из ста миллионов номеров

в недавнем собеседовании. У вас есть идея найти эффективный способ ее решения?

Answer 1

Пропустите их через мин-кучу размера 100: для каждого входного числа k замените текущий минимум m на max(k, m). После этого в куче хранятся 100 самых больших входных данных.

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

Редактировать: Я провалил собеседование - я дважды неправильно понял детали (после того, как сделал это раньше, на производстве). Вот код, чтобы проверить это; это почти так же, как стандарт Python heapq.nlargest():

import heapq

def funnel(n, numbers):
    if n == 0: return []
    heap = numbers[:n]
    heapq.heapify(heap)
    for k in numbers[n:]:
        if heap[0] < k:
            heapq.heapreplace(heap, k)
    return heap

>>> funnel(4, [3,1,4,1,5,9,2,6,5,3,5,8])
[5, 8, 6, 9]

Answer 2

Хорошо, вот действительно глупый ответ, но он правильный:

• Загрузить все 100 миллионов записей в массив
• Вызвать некоторую реализацию быстрой сортировки
• Возьмите последние 100 предметов (сортировка по возрастанию) или первые 100, если можно сортировать по убыванию.

Рассуждение:

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

Это правильное решение для какой-то разовой операции. Это было бы отстойно запускать его x раз в секунду или что-то в этом роде. Но тогда нам нужно больше контекста - как и у mclientk со своим простым оператором SQL - предположить, что 100 миллионов чисел не существует в памяти - это выполнимый вопрос, потому что ... они могут поступать из базы данных, и в большинстве случаев при разговоре о бизнес соответствующие номера.

Таким образом, на вопрос действительно трудно ответить - сначала нужно определить эффективность.

Answer 3

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

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

В алгоритме выбора вы выполняете шаг разделения точно так же, как и раньше - но вместо рекурсивной сортировки обоих разделов вы смотрите, какой раздел содержит нужные вам элементы, и рекурсивно выбираете ТОЛЬКО в этом разделе , Например, при условии, что ваш 100 миллионов элементов разделен почти пополам, на первых нескольких итерациях вы будете смотреть только на верхний раздел.

В конце концов, вы, вероятно, достигнете точки, в которой нужная вам часть «соединяет» два раздела - например, у вас есть раздел из ~ 150 чисел, а когда вы разбиваете, у вас получается два фрагмента из ~ 75 кусочек. В этот момент изменяется только одна незначительная деталь: вместо отклонения одного раздела и продолжения работы только с другим, вы принимаете верхний раздел из 75 элементов, а затем продолжаете искать верхние 25 в нижнем разделе.

Если вы делали это в C ++, вы могли бы сделать это с std::nth_element (который обычно будет реализован примерно так, как описано выше). В среднем, это имеет линейную сложность, которая, я считаю, примерно так же хороша, как вы можете надеяться (без какого-либо существовавшего ранее порядка я не вижу способа найти верхние N элементов, не глядя на все элементы).

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

Что, вероятно, не так очевидно (но на самом деле верно), что вы обычно не хотите использовать max-heap для этой задачи. На первый взгляд, кажется довольно очевидным: если вы хотите получить максимальное количество предметов, вы должны использовать максимальную кучу.

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

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

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

Answer 4

Mergesort партиями по 100, тогда сохраняются только первые 100.

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

Answer 5

Под TOP 100 вы имеете в виду 100 крупнейших? Если так:

SELECT TOP 100 Number FROM RidiculouslyLargeTable ORDER BY Number DESC

Обязательно сообщите интервьюеру, что вы считаете, что таблица проиндексирована правильно.

Answer 6

Нет причин сортировать весь список. Это должно быть выполнимо за O (n) время. В псевдокоде:

List top = new List

for each num in entireList
    for i = 0 to top.Length
        if num > top[i] then
            top.InsertBefore(num, i)
            if top.Length > 100 then
                top.Remove(top.Length - 1)
            end if
            exit for
        else
            if i = top.Length - 1 and i < 100 then
                top.Add(num)
            end if
        end if
    next
next

Answer 7

Я храню первые 100 чисел в Max -Heap размера 100.

• На последнем уровне я отслеживаю минимальный номер и новый номер, который вставляю, и проверяю с помощью минимального номера. Является ли входящий номер кандидатом в топ-100.

  - Снова я вызываю reheapify, чтобы у меня всегда была максимальная куча топ-100.

  Так что его сложность O (nlogn).

Answer 8

Heapify массив в O (n). Тогда возьмите лучшие 100 элементов.

Answer 9

Предположим, что mylist - это список из сотен миллионов данных. так что мы можем отсортировать список и взять последние сто данных из mylist.

mylist.sort ()

MyList [-100:]

Второй способ:

Импорт heapq

heapq.nlargest (100, mylist)

Answer 10

Первая итерация:

Быстрая сортировка, возьмите топ 100. O (n log n). Просто, легко кодировать. Очень очевидно.

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

Какие-нибудь другие соображения? Ну, миллион чисел не много памяти, но если вы хотите минимизировать память, вы сохраняете до 100 встреченных чисел, а затем просто сканируете числа. Что будет лучшим способом?

Некоторые упоминают кучу, но немного лучшим решением может быть двусвязный список, в котором вы сохраняете указатель на минимум из 100 лучших, найденных до сих пор. Если вы встретите число a, которое больше текущего наименьшего в списке, по сравнению со следующим элементом, и перемещайте число от следующего к текущему, пока не найдете место для нового номера. (Это в основном просто специализированная куча для ситуации). При некоторой настройке (если число больше текущего минимума, сравните с текущим максимумом, чтобы увидеть, в каком направлении идти список, чтобы найти точку вставки), это будет относительно эффективно и займет всего 1,5 КБ памяти.