Найти сотню самых больших чисел в файле из миллиарда

Question

Сегодня я пошел на собеседование и мне задали этот вопрос:

Предположим, у вас есть один миллиард целых чисел, которые не отсортированы в файле на диске.Как бы вы определили самые большие сто чисел?

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

Answer 1

Вам придется проверять каждое число, и нет никакого способа обойти это.

Как небольшое улучшение предлагаемых решений,

Учитывая список из 100 чисел:

9595
8505
...
234
1

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

Также рассмотрим тип данных целых чисел.Если они являются 32-разрядными целыми числами, а вы работаете в 64-разрядной системе, вы можете выполнить некоторые хитрые операции с памятью и побитовые операции для одновременной обработки двух чисел на диске, если они непрерывны в памяти.

Answer 2

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

Если вы хотите, чтобы верх k из n, рассмотрите:

allocate an array of k ints
while more input
  perform insertion sort of next value into the array

Это может показаться абсурдно упрощенным. Вы можете ожидать, что это будет O(n^2), но на самом деле это всего лишь O(k*n), и если k намного меньше, чем n (как это постулируется в постановке задачи), оно приближается к O(n).

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

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

Даже улучшение бинарного поиска (чтобы найти точку вставки) только сокращает сравнение до ceil(log_2(k)), и, если вы не сделаете особый случай дополнительного сравнения с k th-до сих пор, у вас гораздо меньше шансов чтобы получить тривиальный отказ от подавляющего большинства входов. И это не делает ничего, чтобы уменьшить количество ходов, которые вам нужны. Учитывая схемы кэширования и прогноз ветвления, выполнение 7 непоследовательных сравнений, а затем 50 последовательных ходов, похоже, не будет значительно быстрее, чем выполнение 50 последовательных сравнений и ходов. Вот почему многие системные сортировки отказываются от Quicksort в пользу сортировки вставкой для небольших размеров.

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

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

Если k может быть сколь угодно большим, приближаясь к n, то имеет смысл рассмотреть очередь с приоритетами или другую, более разумную структуру данных. Другой вариант - разделить входные данные на несколько частей, отсортировать их параллельно, а затем объединить.

Answer 3

Вот еще одно решение (примерно через год, мне не стыдно извиниться!), Основанное на втором, предоставленном @paxdiablo.Основная идея заключается в том, что вы должны читать другие k чисел только в том случае, если они больше минимума, который у вас уже есть, и что сортировка не действительно необходима:

// your variables
n = 100
k = a number > n and << 1 billion
create array1[n], array2[k]

read first n numbers into array2
find minimum and maximum of array2 
while more numbers:
  if number > maximum:
    store in array1
    if array1 is full: // I don't need contents of array2 anymore
       array2 = array1
       array1 = []
  else if number > minimum:
    store in array2
    if array2 is full:
       x = n - array1.count()
       find the x largest numbers of array2 and discard the rest
       find minimum and maximum of array2
  else:
    discard the number
endwhile

// Finally
x = n - array1.count()
find the x largest numbers of array2 and discard the rest
return merge array1 and array2 

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

На самом деле, существует множество возможных оптимизаций, так как вам не нужно их сортировать, вам просто нужно x самых больших чисел.

Кроме того, если k достаточно велико и у вас достаточно памяти, вы можете даже превратить его в рекурсивный алгоритм для поиска n самых больших чисел.

Наконец, если числа уже отсортированы (в любом порядке), алгоритм O (n).

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

Answer 4

Если вы найдете 100-ую статистику с использованием быстрой сортировки, она будет работать в среднем O (млрд). Но я сомневаюсь, что с такими числами и из-за произвольного доступа, необходимого для этого подхода, это будет быстрее, чем O (млрд. Log (100)).