Сегодня я пошел на собеседование и задал этот вопрос:
Предположим, что у вас есть один миллиард целых чисел, которые несортированы в файле диска. Как бы вы определили наибольшие сотни номеров?
Я даже не знаю, где я начну с этого вопроса. Каков наиболее эффективный процесс для правильного результата? Нужно ли мне через файл диска сто раз захватывать самое большое число, еще не включенное в мой список, или есть лучший способ?
Здесь мой первоначальный алгоритм:
create array of size 100 [0..99].
read first 100 numbers and put into array.
sort array in ascending order.
while more numbers in file:
get next number N.
if N > array[0]:
if N > array[99]:
shift array[1..99] to array[0..98].
set array[99] to N.
else
find, using binary search, first index i where N <= array[i].
shift array[1..i-1] to array[0..i-2].
set array[i-1] to N.
endif
endif
endwhile
Это имеет (очень небольшое) преимущество в том, что нет O (n ^ 2) перетасовки для первых 100 элементов, всего лишь сортировка O (n log n) и что вы очень быстро идентифицируете и выбрасываете те, которые слишком маленький. Он также использует бинарный поиск (максимум 7 сравнений), чтобы найти правильную точку вставки, а не 50 (в среднем) для упрощенного линейного поиска (не то, что я предлагаю, чтобы кто-то еще предлагал такое решение, просто чтобы он мог произвести впечатление на интервьюера).
Вы даже можете получить бонусные баллы за предложение использовать оптимизированные операции shift, такие как memcpy в C, если вы можете быть уверены, что перекрытие не является проблемой.
Еще одна возможность, которую вы можете рассмотреть, состоит в том, чтобы поддерживать три списка (до 100 целых чисел каждый):
read first hundred numbers into array 1 and sort them descending.
while more numbers:
read up to next hundred numbers into array 2 and sort them descending.
merge-sort lists 1 and 2 into list 3 (only first (largest) 100 numbers).
if more numbers:
read up to next hundred numbers into array 2 and sort them descending.
merge-sort lists 3 and 2 into list 1 (only first (largest) 100 numbers).
else
copy list 3 to list 1.
endif
endwhile
Я не уверен, но это может оказаться более эффективным, чем постоянное перетасовка.
Слияние-сортировка - это простой выбор по строкам (для списков сортировки слияния 1 и 2 по 3):
list3.clear()
while list3.size() < 100:
while list1.peek() >= list2.peek():
list3.add(list1.pop())
endwhile
while list2.peek() >= list1.peek():
list3.add(list2.pop())
endwhile
endwhile
Проще говоря, вытащить 100 лучших значений из объединенного списка в силу того факта, что они уже отсортированы в порядке убывания. Я не проверял подробно, будет ли это более эффективным, я просто предлагаю его как возможность.
Я подозреваю, что интервьюеры будут впечатлены возможностью мыслить "из коробки" и тем фактом, что вы заявили, что ее следует оценивать для производительности.
Как и в большинстве интервью, технические навыки - это одна из тех вещей, на которые они смотрят.
Очевидно, интервьюеры хотят, чтобы вы указали на два ключевых факта:
Get-Size: получить количество значений в контейнере.Find-Min: получите наименьшее значение.Delete-Min: удалите наименьшее значение, чтобы заменить его новым большим значением.Insert: Вставьте еще один элемент в контейнер.Оценив требования к структуре данных, профессор компьютерных наук ожидал, что вы порекомендуете использовать Heap (Min-Heap), так как он предназначен для поддержки точно операций, которые нам нужны здесь.
Например, для Fibonacci heaps операции Get-Size, Find-Min и Insert - это O(1) и Delete-Min O(log n) (с n <= 100 в этом случае).
На практике вы можете использовать приоритетную очередь из вашей любимой языковой стандартной библиотеки (например, priority_queue из #include <queue> в С++), которая обычно выполняется с использованием кучи.
Создайте массив из 100 чисел, все из которых равны -2 ^ 31.
Убедитесь, что первое число, которое вы читаете с диска, больше, чем первое в списке. Если он копирует массив вниз по 1 индексу и обновляет его до нового номера. Если не проверить следующее в 100 и т.д.
Когда вы закончите читать все 1 миллиард цифр, у вас должно быть самое высокое 100 в массиве.
Задание выполнено.
Я бы переместил список по порядку. Когда я иду, я добавляю элементы в набор (или мультимножество в зависимости от дубликатов). Когда набор достиг 100, я бы только вставлял, если значение было больше, чем мин в наборе (O (log m)). Затем удалите мин.
Вызов числа значений в списке n и числа значений для поиска m:
это O (n * log m)
Скорость алгоритма обработки абсолютно неуместна (если только она не полностью тупая).
Узким местом здесь является ввод-вывод (он указал, что они находятся на диске). Поэтому убедитесь, что вы работаете с большими буферами.
Сохранять фиксированный массив из 100 целых чисел. Инициализируйте их в Int.MinValue. Когда вы читаете, от 1 миллиарда целых чисел, сравнивайте их с числами в первой ячейке массива (индекс 0). Если больше, то перейдите к следующему. Опять же, если больше, то продвигайтесь вверх, пока не нажмете на конец или меньшее значение. Затем сохраните значение в индексе и сдвиньте все значения в предыдущих ячейках на одну ячейку вниз... сделайте это, и вы найдете 100 максимальных целых чисел.
Я считаю, что самый быстрый способ сделать это - использовать очень большую битовую карту для записи чисел, которые присутствуют. Чтобы представить 32-битное целое число, это должно быть 2 ^ 32/8 байт, которое составляет около 536 МБ. Сканирование через целые числа, просто устанавливающие соответствующий бит в битовой карте. Затем найдите самые высокие 100 записей.
ПРИМЕЧАНИЕ. Если вы видите разницу, это находит самые высокие 100 номеров, а не самые высокие 100 экземпляров числа.
Такой подход обсуждается в очень хорошей книге "Программирование жемчуга", которую, возможно, читал ваш интервьюер!
Вам нужно будет проверить каждый номер, нет никакого способа обойти это.
Так же, как небольшое улучшение предлагаемых решений,
Учитывая список из 100 номеров:
9595
8505
...
234
1
Вы проверили, будет ли новое найденное значение > min значением нашего массива, если оно есть, вставьте его. Однако выполнять поиск снизу вверх может быть довольно дорогостоящим, и вы можете подумать о том, чтобы использовать подход "разделение и завоевание", например, оценивая 50-й элемент в массиве и проводя сравнение, тогда вы знаете, нужно ли вставить значение в первые 50 элементов или нижний 50. Вы можете повторить этот процесс для более быстрого поиска, поскольку мы устранили 50% нашего пространства поиска.
Также рассмотрим тип данных целых чисел. Если они 32-битные целые числа, и вы находитесь в 64-битной системе, вы можете сделать некоторые умные операции с памятью и побитовые операции, чтобы иметь дело с двумя номерами на диске одновременно, если они постоянны в памяти.
Я думаю, что кто-то должен был упомянуть приоритетную очередь. Вам просто нужно сохранить текущие 100 лучших номеров, знать, что самое низкое, и иметь возможность заменить их на большее число. То, что делает очередь приоритетов для вас - некоторые реализации могут сортировать список, но это не требуется.
Предполагая, что в память вписываются 1 номер + 100ion лучший алгоритм сортировки - сортировка кучи. сформировать кучу и получить первые 100 номеров. сложность o (nlogn + 100 (для извлечения первых 100 номеров))
улучшение решения
разделите реализацию на две кучи (так что вставка менее сложна), и при извлечении первых 100 элементов выполняется алгоритм имперского слияния.
Здесь приведен код python, который реализует алгоритм, предложенный ferdinand beyer выше. по сути, это куча, единственное отличие состоит в том, что удаление было объединено с операцией вставки
import random
import math
class myds:
""" implement a heap to find k greatest numbers out of all that are provided"""
k = 0
getnext = None
heap = []
def __init__(self, k, getnext ):
""" k is the number of integers to return, getnext is a function that is called to get the next number, it returns a string to signal end of stream """
assert k>0
self.k = k
self.getnext = getnext
def housekeeping_bubbleup(self, index):
if index == 0:
return()
parent_index = int(math.floor((index-1)/2))
if self.heap[parent_index] > self.heap[index]:
self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
self.housekeeping_bubbleup(parent_index)
return()
def insertonly_level2(self, n):
self.heap.append(n)
#pdb.set_trace()
self.housekeeping_bubbleup(len(self.heap)-1)
def insertonly_level1(self, n):
""" runs first k times only, can be as slow as i want """
if len(self.heap) == 0:
self.heap.append(n)
return()
elif n > self.heap[0]:
self.insertonly_level2(n)
else:
return()
def housekeeping_bubbledown(self, index, length):
child_index_l = 2*index+1
child_index_r = 2*index+2
child_index = None
if child_index_l >= length and child_index_r >= length: # No child
return()
elif child_index_r >= length: #only left child
if self.heap[child_index_l] < self.heap[index]: # If the child is smaller
child_index = child_index_l
else:
return()
else: #both child
if self.heap[ child_index_r] < self.heap[ child_index_l]:
child_index = child_index_r
else:
child_index = child_index_l
self.heap[index], self.heap[ child_index] = self.heap[child_index], self.heap[index]
self.housekeeping_bubbledown(child_index, length)
return()
def insertdelete_level1(self, n):
self.heap[0] = n
self.housekeeping_bubbledown(0, len(self.heap))
return()
def insert_to_myds(self, n ):
if len(self.heap) < self.k:
self.insertonly_level1(n)
elif n > self.heap[0]:
#pdb.set_trace()
self.insertdelete_level1(n)
else:
return()
def run(self ):
for n in self.getnext:
self.insert_to_myds(n)
print(self.heap)
# import pdb; pdb.set_trace()
return(self.heap)
def createinput(n):
input_arr = range(n)
random.shuffle(input_arr)
f = file('input', 'w')
for value in input_arr:
f.write(str(value))
f.write('\n')
input_arr = []
with open('input') as f:
input_arr = [int(x) for x in f]
myds_object = myds(4, iter(input_arr))
output = myds_object.run()
print output
Если вы найдете статистическую статистику 100-го порядка, используя быструю сортировку, она будет работать в среднем O (миллиард). Но я сомневаюсь, что с такими числами и из-за случайного доступа, необходимого для этого подхода, он будет быстрее, чем O (млрд. Log (100)).
Вот еще одно решение (примерно через некоторое время, мне не жалко жаль!) на основе второго, предоставленного @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
Критическим шагом является функция для нахождения наибольших чисел x в массиве2. Но вы можете использовать тот факт, что вы знаете минимум и максимум, чтобы ускорить работу по поиску наибольших чисел x в массиве2.
На самом деле, существует множество возможных оптимизаций, так как вам не нужно сортировать его, вам просто нужны самые большие числа.
Кроме того, если k достаточно велико, и у вас достаточно памяти, вы можете даже превратить его в рекурсивный алгоритм для нахождения n наибольших чисел.
Наконец, если числа уже отсортированы (в любом порядке), алгоритм O (n).
Очевидно, это просто теоретически, потому что на практике вы должны использовать стандартные алгоритмы сортировки, и узким местом, вероятно, будет IO.
Существует множество умных подходов (таких как решения с приоритетной очередью), но одна из самых простых вещей, которые вы можете сделать, также может быть быстрой и эффективной.
Если вы хотите верхнюю k of 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 th наибольшего значения, которое было обнаружено до сих пор. Если у вас есть миллиард входных данных, только небольшая часть, вероятно, будет больше, чем 100. Пока что
(Вы можете интерпретировать вход в худшем случае, где каждое значение больше, чем его предшественник, что требует k сравнений и перемещений для каждого входа. Но это по существу сортированный вход, а оператор проблемы говорит, что вход несортирован.)
Даже улучшение двоичного поиска (для поиска точки вставки) сокращает сравнение только с ceil(log_2(k)), и если вы не делаете лишнего сравнения с k th-so-far, вы гораздо менее вероятны чтобы получить тривиальное отклонение подавляющего большинства входных данных. И он не делает ничего, чтобы уменьшить количество ходов, в которых вы нуждаетесь. Учитывая схемы кэширования и предсказание ветвей, выполнение 7 последовательных сравнений, а затем 50 последовательных ходов, похоже, не будет значительно быстрее, чем выполнение 50 последовательных сравнений и ходов. Это почему многие виды системы отказываются от Quicksort в пользу сортировки вставки для небольших размеров.
Также подумайте, что это требует почти никакой дополнительной памяти и что алгоритм чрезвычайно кэширован (что может быть или не быть правдой для кучи или очереди приоритетов), и это тривиально писать без ошибок.
Процесс чтения файла, вероятно, является основным узким местом, поэтому реальное повышение производительности, вероятно, будет простым простейшим решением для выбора, вы можете сосредоточить свои усилия на поиске хорошей стратегии буферизации для минимизации ввода/вывода.
Если k может быть сколь угодно большим, приближаясь к n, тогда имеет смысл рассмотреть приоритетную очередь или другую более интеллектуальную структуру данных. Другой вариант - разбить вход на несколько кусков, отсортировать каждый из них параллельно и затем слить.