Как я могу возвратить случайную строку из файла? Вопрос об интервью [закрывается]

1. Считайте все строки в массив, верните произвольную строку в диапазоне 1 и количество строк.

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

3. Нужно запомнить только одну строку. Каждая новая строка имеет вероятность 1/N (N - это чтение строк).

   Псевдокод:

   i = 1
   select_line = ""
   для очереди в очереди:
    if random() < 1/i: # random возвращает равномерное случайное число в [0,1)
    select_line = строка
    i += 1
   вернуть select_line
   

Алгоритм № 3 можно использовать и для 1 и 2.

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

linenum := 0
ret := ''
while more lines to read:
    line := readline()
    linenum := linenum + 1
    r := uniform_random(0, linenum)
    if r < 1:
        ret := line

return ret

Proof: Начнем с того, что мы всегда сохраняем первую строку в ret. Если в файле одна строка, то вы ее выбираете, и все.

Для двухстрочного файла ret сохранит первую строку 100% времени, а вторая строка будет сохранена в ret 50% времени во время второй итерации цикла. Таким образом, вероятность выбора каждой линии составляет 0.5.

Теперь предположим, что этот метод работает для файлов ≤N строк. Чтобы доказать, что это означает, что он работает для N+1, в (N+1)-итерации цикла существует вероятность того, что 1/(N+1) будет выбрана последняя строка (random(0, N+1) < 1 имеет такую вероятность). Таким образом, последняя строка имеет 1/(N+1) вероятность быть выбранной. Вероятность того, что все остальные выбранные строки все равно будут равны друг другу, назовем это x. Затем N*x + 1/(N+1) == 1, что означает, что x = 1/(N+1).

Доказательство индукцией завершено.

Редактирование : Упс, не видел третьего метода первого ответа, прежде чем ответить. Тем не менее, я оставлю этот пост здесь, если только для доказательства, и возможности для других людей исправить его, если в нем есть какие-то ошибки.

Re 1: Используйте решение для 2

Re 2: Вы должны сканировать весь файл, используя доступ RandomAccessFile для подсчета количества строк и (возможно) кэшировать указатели на файлы для каждого начала строки. Затем вы можете выбрать один из них случайным образом (я предполагаю, что этот вопрос не о том, как генерировать случайные числа) и вернуться к этой начальной точке, прочитать строку и вернуть ее. Если вы хотите, чтобы она была быстрой, то убедитесь, что вы буферизируете чтения (в противном случае raf - v медленно).

Re 3: Если поток не помещается в память (т.е. вы не можете кэшировать весь поток) и вы не знаете, сколько строк находится в потоке, не прочитав весь поток (предполагая, что вы сможете прочитать его только один раз), то я не вижу решения. Я тоже жду ответов.

#3: запишите поток в файл на диске и используйте решение 2. Не самое эффективное решение, конечно, но очень простое.