Как перетасовать строки в файле, не читая весь файл заранее?

Question

Какой хороший алгоритм для перестановки строк в файле без предварительного чтения всего файла?

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

Может ли кто-то проверить / доказать это и / илиможет быть, постобработанный (perl, python и т. д.) код?

Смежные вопросы, но не смотря на алгоритмы с эффективным использованием памяти:

• Как я могу перетасовать строкитекстовый файл в командной строке Unix или в сценарии оболочки?
• Как можно рандомизировать строки в файле с помощью стандартных инструментов в Red Hat Linux?
• Как я могу напечатать строки в STDIN в случайном порядке в Perl?

Answer 1

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

Я не знаком с perl или python, номожно продемонстрировать с помощью php.

<?php
$offsets = array();

$f = fopen("file.txt", "r");
$offsets[] = ftell($f);
while (! feof($f))
{
  if (fgetc($f) == "\n") $offsets[] = ftell($f);
}

shuffle($offsets);
foreach ($offsets as $offset)
{
  fseek($f, $offset);
  echo fgets($f);
}
fclose($f);
?>

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

1. Определение размера файла
2. Создание списка смещений и длин, уже записанных в стандартный вывод
3. Цикл до bytes_written == размер файла
4. Поиск случайного смещениякоторого нет в вашем списке уже записанных значений
5. Резервное копирование с этого поиска на предыдущую новую строку или начало файла
6. Показать эту строку и добавить ее в список смещений и длиннаписано
7. Перейти к 3.

Answer 2

Следующий алгоритм равен linear по количеству строк во входном файле.

Препроцессирование:

1. Найдите n (общее количество строк) путем сканирования новых строк (или чего-либо еще), но сохраните номер символа, обозначающий начало и конец каждой строки. Таким образом, у вас будет 2 вектора, скажем, s и e размером n, где нумерация символов от s[i] до e[i] во входном файле - это i-я строка. В C ++ я бы использовал vector.

2. Произвольно переставить вектор целых чисел от 1 до n (в C ++ это будет random_shuffle) и сохранить его в векторе, скажем, p (например, 1 2 3 4 становится p = [3 1 4 2]). Это означает, что строка i нового файла теперь является строкой p[i] в исходном файле (т. Е. В приведенном выше примере 1-я строка нового файла - 3-я строка исходного файла) .

Главная

1. Создать новый файл

2. Введите первую строку в новом файле, прочитав текст в исходном файле в диапазоне от s[p[0]] до e[p[0]] и добавив его в новый файл.

3. Продолжите, как в шаге 2 для всех остальных строк.

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

Answer 3

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

Просто пример на python:

import sys
import random

CACHE_SIZE = 23

lines = {}

for l in sys.stdin: # you can replace sys.stdin with xrange(200) to get a test output
    i = random.randint(0, CACHE_SIZE-1)
    old = lines.get(i)
    if old:
        print old,
    lines[i] = l

for ignored, p in lines.iteritems():
    print p,