Finding к величине элементы очень большой файл (в то время как к очень большой)

Question

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

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

Как мы делаем это в O(n)?

То, что я подумал:

Мы начинаем чтение файла и проверяем его с другим файлом, который удерживает k наибольшие элементы (отсортированных в порядке возрастания), если элемент чтения больше, чем в первой строке второго файл мы удаляем первую строку, и мы вставляем ее во второй файл, временная сложность будет O(NlogK) (если у нас есть случайный доступ к этому файлу, в противном случае это будет «O (Nk)»

Любая идея это в O(n), я думаю, если у нас есть внешняя версия Selection algorithm (алгоритм секционирования в quicksort), мы могли бы сделать это в O(n) но я не смог найти его где-нибудь

Answer 1

PS: Мое определение K отличается. Это небольшое число, например, 2 или 100 или 1000. Здесь m соответствует определению OPS k. Извини за это.

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

Шаг 1: Выберите K случайных чисел через целых данных
Шаг 2: Сортировка числа К (предположим, что индекс от 1 до K)
Шаг 3: Создание K + 1 отдельные файлы и назовите их от 0 до K
Шаг 4: Для каждого элемента данных, если он находится между i-м и i-м элементом, поместите его в i-й файл.
Шаг 5: основываясь на размере каждого файла, выберите файл, который будет иметь номер mth.
Шаг 6: Повторите все с новым файлом и новым м (new_m = м - sum_of_size_of_all_lower_files)

Что касается последнего шага, если K = 2, т = 1000 и размер файла 0 составляет 800, 1 900 и 2 равно 200, new_m = m-800 = 200 и работать с файлом 1 итеративно.

Answer 2

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

Answer 3

Если все значения различны или мы можем игнорировать дублеты и у нас есть 32-битные целые числа, я бы просто использовать один бит на возможное значение (потребности 2^32 бит = 2^29 байт = 512 мегабайт (должен вписываться в ваш ОЗУ)).

1. Инициализировать 512 с 0
2. В то время как линейное чтение файла (О (п)) установлен соответствующий бит для каждого считанного значения.
3. В конце найдите первые k установите бит, чтобы получить наибольшие значения k. (O (2^32) разрядные тесты)

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

Answer 4

Вы можете сделать это довольно легко с помощью стандартного алгоритма слияния.

Скажем, у вас есть 100 миллиардов номеров, и вы хотите получить 10 миллиардов долларов. Мы скажем, что вы можете хранить 1 миллиард номеров в памяти в любое время.

Таким образом, вы сделать проход:

while not end of input 
    read 1 billion numbers 
    sort them in descending order 
    save position of output file 
    write sorted numbers to output file 

Вы тогда файл, содержащий 100 блоков 1 млрд номеров каждый. Каждый блок сортируется в порядке убывания.

Теперь создайте максимальную кучу. Добавьте первое число каждого блока в кучу. Вам также нужно будет добавить номер блока или позицию номера в файле, чтобы вы могли прочитать следующий номер.

Тогда:

while num_selected < 10 billion 
    selected = heap.remove() 
    ++num_selected 
    write selected to output 
    read next number from the selected block and place on heap 

Там небольшой кусочек сложности участие, отслеживание которых блокировать номер пришел, но это не так уж плохо.

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

Это в основном просто сортировка диска, но с ранним выходом.

Сложность первого прохода b * (m log m), где b - количество блоков, а m - количество элементов в блоке. N, общее количество элементов в файле, равно b * m. Сложность второго прохода k log b, где k - количество элементов для выбора, а b - количество блоков.

Answer 5

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

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

• Если это не так - проверьте, меньше ли минимальный, чем новый элемент, а если он есть, вытащите его и вставьте вместо него новый элемент.

Когда вы закончите - у вас есть куча, содержащая k наибольших элементов. Это решение - сложность O (nlogk), где n - количество элементов, а k - количество необходимых вам элементов.

• Это может быть сделано также в O (N), используя алгоритм выбора - сохранить все элементы, а затем найти (k+1)th наибольший элемент, и вернуть все больше, то это. Но его сложнее реализовать и для разумного ввода размера - может быть, не лучше. Кроме того, если поток содержит дубликаты, требуется больше обработки