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

Question

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

Вариант использования для генератора паролей, который объединяет N случайных слов, извлеченных из файла словаря, по одному слову в строке (например, /usr/share/dict/words). Вы можете придумать angela.ham.lewis.pathos. Прямо сейчас он считывает весь файл словаря в массив и выбирает из этого массива N случайных элементов. Я хотел бы исключить массив или любое другое хранилище файла в памяти и прочитать файл только один раз.

(Нет, это не практическое упражнение по оптимизации. Мне интересен алгоритм.)

Обновление : Спасибо всем за ответы.

Ответы делятся на три категории: модификации алгоритма полного чтения, случайный поиск или индексирование строк и поиск по ним случайным образом.

Произвольный поиск намного быстрее и постоянен по размеру файла, но распределяется по размеру файла, а не по количеству слов. Это также позволяет дублировать (этого можно избежать, но это делает алгоритм O (inf)). Вот мое переопределение моего генератора паролей с использованием этого алгоритма. Я понимаю, что при чтении вперед с точки поиска, а не назад, она имеет ошибку «один за другим», если поиск падает в последнюю строку. Исправление оставлено в качестве упражнения для редактора.

#!/usr/bin/perl -lw

my $Words       = "/usr/share/dict/words";
my $Max_Length  = 8;
my $Num_Words   = 4;

my $size = -s $Words;

my @words;
open my $fh, "<", $Words or die $!;

for(1..$Num_Words) {
    seek $fh, int rand $size, 0 or die $!;
    <$fh>;
    my $word = <$fh>;
    chomp $word;
    redo if length $word > $Max_Length;
    push @words, $word;
}
print join ".", @words;

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

#!/usr/bin/perl -lw

my $Words       = "/usr/share/dict/words";
my $Max_Length  = 8;
my $Num_Words   = 4;

my @words;
open my $fh, "<", $Words or die $!;
my $count = 0;
while(my $line = <$fh>) {
    chomp $line;
    $count++;
    if( $count <= $Num_Words ) {
        $words[$count-1] = $line;
    }
    elsif( rand($count) <= $Num_Words ) {
        $words[rand($Num_Words)] = $line;
    }
}

print join ".", @words;

Наконец, алгоритм индекса и поиска имеет преимущество распределения по слову, а не по размеру файла. Недостатком является то, что он считывает весь файл, а использование памяти линейно зависит от количества слов в файле. Можно также использовать алгоритм Гуффы.

Answer 1

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

cnt = 0
while not end of file {
   read line
   cnt = cnt + 1
   if random(1 to cnt) = 1 {
      result = line
   }
}

Как видите, идея в том, что вы читаете каждую строку в файле и вычисляете вероятность того, что строка должна быть выбранной. После прочтения первой строки вероятность составляет 100%, после прочтения второй строки вероятность составляет 50% и т. Д.

Это можно расширить, выбрав N элементов, сохранив массив с размером N вместо одной переменной и рассчитав вероятность замены строки одним из текущих в массиве:

var result[1..N]
cnt = 0
while not end of file {
   read line
   cnt = cnt + 1
   if cnt <= N {
      result[cnt] = line
   } else if random(1 to cnt) <= N {
      result[random(1 to N)] = line
   }
}

Edit:
Вот код, реализованный в C #:

public static List<string> GetRandomLines(string path, int count) {
    List<string> result = new List<string>();
    Random rnd = new Random();
    int cnt = 0;
    string line;
    using (StreamReader reader = new StreamReader(path)) {
        while ((line = reader.ReadLine()) != null) {
            cnt++;
            int pos = rnd.Next(cnt);
            if (cnt <= count) {
                result.Insert(pos, line);
            } else {
                if (pos < count) {
                    result[pos] = line;
                }
            }
        }
    }
    return result;
}

Я сделал тест, выполнив метод 100000 раз, выбрав 5 строк из 20 и посчитал вхождения строк. Это результат:

25105
24966
24808
24966
25279
24824
25068
24901
25145
24895
25087
25272
24971
24775
25024
25180
25027
25000
24900
24807

Как видите, дистрибутив настолько хорош, насколько вы могли когда-либо захотеть. :)

(Я переместил создание объекта Random из метода при запуске теста, чтобы избежать проблем с заполнением, поскольку начальное число берется из системных часов.)

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

Редактировать 2:
Я изменил код, чтобы использовать List<string> вместо string[]. Это позволяет легко вставлять первые N элементов в случайном порядке. Я обновил тестовые данные из нового тестового прогона, чтобы вы могли видеть, что распределение все еще в порядке.

Answer 2

Если вам не нужно делать это в рамках Perl, shuf - действительно хорошая утилита командной строки для этого. Чтобы сделать то, что вы хотите сделать:

$ shuf -n N file > newfile

Answer 3

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

srand;
(rand($.) < 1 && ($line1 = $_)) || (rand($.) <1 && ($line2 = $_)) while <>;

Как и в оригинальном алгоритме, это однопроходная и постоянная память.

Редактировать Я только что понял, что вам нужно N, а не 2. Вы можете повторить выражение OR-ed N раз, если знаете заранее N.

Answer 4

Впервые я вижу некоторый Perl-код ... он невероятно нечитабелен ...;) Но это не должно иметь значения. Почему бы вам просто не повторить загадочную строку N раз?

Если бы мне пришлось написать это, я бы просто искал случайную позицию в файле, прочитал до конца строки (следующую новую строку), а затем прочитал одну строку до следующей строки. Добавьте некоторую обработку ошибок, если вы только что просмотрели последнюю строку, повторите все это N раз, и все готово. Я думаю

srand;
rand($.) < 1 && ($line = $_) while <>;

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

UPDATE

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

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

Answer 5

Выберите случайную точку в файле, посмотрите назад для предыдущего EOL, ищите вперед для текущего EOL и верните строку.

FILE * file = fopen("words.txt");
int fs = filesize("words.txt");
int ptr = rand(fs); // 0 to fs-1
int start = min(ptr - MAX_LINE_LENGTH, 0);
int end = min(ptr + MAX_LINE_LENGTH, fs - 1);
int bufsize = end - start;

fseek(file, start);
char *buf = malloc(bufsize);
read(file, buf, bufsize);

char *startp = buf + ptr - start;
char *finp = buf + ptr - start + 1;

while (startp > buf  && *startp != '\n') {
    startp--;
}

while (finp < buf + bufsize && *finp != '\n') {
    finp++;
}

*finp = '\0';
startp++;
return startp;

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

Но вы должны понять.

Более длинные линии статистически имеют более высокий шанс выбора, чем более короткие линии. Но время выполнения этого практически постоянно независимо от размера файла. Если у вас много слов в основном одинаковой длины, статистики не будут счастливы (они никогда не будут так или иначе), но на практике это будет достаточно близко.

Answer 6

Быстрый и грязный удар

function randomLine {
  numlines=`wc -l $1| awk {'print $1'}`
  t=`date +%s`
  t=`expr $t + $RANDOM`
  a=`expr $t % $numlines + 1`
  RETURN=`head -n $a $1|tail -n 1`
  return 0
}

randomLine test.sh
echo $RETURN

Answer 7

Вы можете сделать алгоритм 2 прохода. Сначала получите позиции каждой новой строки, толкая эти позиции в вектор. Затем выберите случайные элементы в этом векторе, назовите это i.

Считайте файл из позиции v [i] в ​​v [i + 1], чтобы узнать вашу строку.

Во время первого прохода вы читаете файл с небольшим буфером, чтобы не прочитать его все в ОЗУ сразу.

Answer 8

Я бы сказал:

• Прочтите файл и найдите сумму \n. Это количество строк - назовем это L
• Сохранять свои позиции в небольшом массиве в памяти
• Получите две случайные строки ниже L, извлеките их смещения, и все готово.

Вы бы использовали небольшой массив и прочитали весь файл один раз + 2 строки после этого.