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

Question

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

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

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

Answer 1

Очевидно, что интервьюеры хотят, чтобы вы указали два ключевых факта:

• Вы не можете прочитать весь список целых чисел в памяти, так как он слишком велик.Поэтому вам придется читать его один за другим.
• Вам нужна эффективная структура данных для хранения 100 самых больших элементов.Эта структура данных должна поддерживать следующие операции:
  • Get-Size: получить количество значений в контейнере.
  • Find-Min: получить наименьшее значение.
  • Delete-Min: удалить наименьшее значение, чтобы заменить его новым, большим значением.
  • Insert: вставить другой элемент в контейнер.

ByОценивая требования к структуре данных, профессор компьютерных наук будет ожидать, что вы порекомендуете использовать Heap (Min-Heap), поскольку он предназначен для поддержки именно тех операций, которые нам нужны здесь.

Например, для куч Фибоначчи , операции Get-Size, Find-Min и Insert - это O(1), а Delete-Min - O(log n) (с n <= 100 в данном случае).

На практике вы можете использовать очередь с приоритетами из стандартной библиотеки вашего любимого языка (например, priority_queue из #include <queue> в C ++), которая обычно реализуется с использованием кучи.

Answer 2

Вот мой первоначальный алгоритм:

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

Это имеет (очень незначительное) преимущество в том, что для первых 100 элементов нет перетасовки O (n ^ 2), только 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

Я не уверен, но это может оказаться более эффективным, чем непрерывныйshuffling.

Сортировка слиянием - это простой выбор по строкам (для списков сортировки слиянием 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 значенийиз объединенного списка в силу того, что они уже отсортированы в порядке убывания.Я не проверил подробно, будет ли это более эффективным, я просто предлагаю это как возможность.

Я подозреваю, что интервьюеры будут впечатлены потенциалом мышления «из коробки» ифакт, что вы заявили, что его следует оценивать на результативность.

Как и в большинстве интервью, технические навыки составляют один из того, на что они смотрят.

Answer 3

Создайте массив из 100 чисел, каждый из которых равен -2 ^ 31.

Проверьте, больше ли первое число, которое вы прочитали с диска, чем первое в списке. Если это скопировать массив на 1 индекс и обновить его до нового номера. Если нет, проверьте следующее в 100 и т. Д.

Когда вы закончите читать все 1 миллиард цифр, у вас должно быть самое большое 100 в массиве.

Работа выполнена.

Answer 4

Я бы прошел список по порядку. По мере добавления я добавляю элементы в набор (или мультимножество в зависимости от дубликатов). Когда набор достигнет 100, я бы вставил, только если значение было больше, чем минимум в наборе (O (log m)) Затем удалите мин.

Вызов числа значений в списке n и количества значений для поиска m:

это O (n * log m)

Answer 5

Скорость алгоритма обработки абсолютно не имеет значения (если он не совсем тупой).

Узким местом здесь является ввод / вывод (указано, что они на диске)Поэтому убедитесь, что вы работаете с большими буферами.

Answer 6

Я считаю, что самый быстрый способ сделать это - использовать очень большую битовую карту для записи присутствующих чисел. Для представления 32-разрядного целого числа это должно быть 2 ^ 32/8 байтов, что составляет около = 536 МБ. Просматривайте целые числа, просто устанавливая соответствующий бит в битовой карте. Затем найдите 100 самых высоких записей.

ПРИМЕЧАНИЕ. Если вы заметите разницу, то будут найдены самые высокие 100 чисел, а не самые высокие 100 экземпляров числа.

Такой подход обсуждается в очень хорошей книге «Программирование жемчуга», которую, возможно, прочитал ваш интервьюер!

Answer 7

Сохраняйте фиксированный массив из 100 целых чисел. Инициализируйте их в Int.MinValue. Когда вы читаете, из 1 миллиарда целых чисел сравните их с числами в первой ячейке массива (индекс 0). Если больше, то переходите к следующему. Опять же, если больше, то двигайтесь вверх, пока не достигнете конца или меньшего значения. Затем сохраните значение в индексе и сдвиньте все значения в предыдущих ячейках на одну ячейку вниз ... сделайте это, и вы найдете 100 максимум целых чисел.

Answer 8

Вот некоторый код на python, который реализует алгоритм, предложенный Фердинандом Бейером выше.по сути это куча, единственное отличие в том, что удаление было объединено с операцией вставки

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

Answer 9

1. Предполагая, что 1 банкнота + 100ion чисел помещаются в память лучший алгоритм сортировки - сортировка кучи. сформируйте кучу и получите первые 100 чисел. сложность o (nlogn + 100 (для получения первых 100 чисел))

   улучшение решения

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

Answer 10

Я думаю, что кто-то должен был упомянуть приоритетную очередь к настоящему времени. Вам просто нужно сохранить текущие первые 100 чисел, знать, что является самым низким, и иметь возможность заменить его на более высокое число. Вот что делает для вас приоритетная очередь - некоторые реализации могут сортировать список, но это не обязательно.