Случайно выбирая строки из файлов

Question

У меня есть куча файлов, и сам файл имеет заголовок из 5 строк. В остальной части файла пара строк образует запись. Мне нужно случайным образом выбрать запись из этих файлов. Как я могу выбрать случайные файлы и случайные записи (пара строк, без заголовка)?

Answer 1

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

Вот интуитивное объяснение алгоритма.

Process the file line by line.
pick = line, with probability 1/N, where N = line number

Другими словамив строке 1 мы выберем строку 1 с вероятностью 1/1.В строке 2 мы изменим выбор к строке 2 с вероятностью 1/2.В строке 3 мы изменим выбор на строку 3 с вероятностью 1/3.И т. Д.

Для наглядного доказательства представьте файл из 3 строк:

        1            Pick line 1.
       / \
     .5  .5
     /     \
    2       1        Switch to line 2?
   / \     / \
 .67 .33 .33 .67
 /     \ /     \
2       3       1    Switch to line 3?

Вероятность для каждого результата:

Line 1: .5 * .67     = 1/3
Line 2: .5 * .67     = 1/3
Line 3: .5 * .33 * 2 = 1/3

Оттуда остальноеиндукция.Например, предположим, что файл имеет 4 строки.Мы уже убедились в том, что по состоянию на строке 3 каждая строка (1, 2, 3) будет иметь равные шансы быть нашим текущим выбором.Когда мы перейдем к строке 4, у нее будет 1/4 шанс быть выбранным - именно таким, каким он должен быть, таким образом уменьшая вероятности на предыдущих 3 строках точно на правильную величину (1/3 * 3/4 = 1/4).

Вот ответ на вопрос Perl , адаптированный к вашей проблеме.

use strict;
use warnings;

# Ignore 5 lines.
<> for 1 .. 5;

# Use reservoir sampling to select pairs from remaining lines.
my (@picks, $n);
until (eof){
    my @lines;
    $lines[$_] = <> for 0 .. 1;

    $n ++;
    @picks = @lines if rand($n) < 1;
}

print @picks;

Answer 2

Вы можете найти perlfaq5 полезным.

Answer 3

Решение Python - считывает файл только один раз и требует мало памяти

Invoke как так getRandomItems(file('myHuge.log'), 5, 2) - вернет список из 2 строк

from random import randrange

def getRandomItems(f, skipFirst=0, numItems=1):
    for _ in xrange(skipFirst):
        f.next()
    n = 0; r = []
    while True:
        try:
            nxt = [f.next() for _ in range(numItems)]
        except StopIteration: break
        n += 1
        if not randrange(n):
            r = nxt
    return r

Возвращает пустой список, если не может получитьпервые проходимые предметы из ф.Единственным требованием кода является то, что аргумент f является итератором (поддерживает метод next()).Следовательно, мы можем передать что-то отличное от файла, скажем, мы хотим увидеть распределение:

>>> s={}
>>> for i in xrange(5000):
...     r = getRandomItems(iter(xrange(50)))[0]
...     s[r] = 1 + s.get(r,0)
... 
>>> for i in s: 
...     print i, '*' * s[i]
... 
0 ***********************************************************************************************
1 **************************************************************************************************************
2 ******************************************************************************************************
3 ***************************************************************************
4 *************************************************************************************************************************
5 ********************************************************************************
6 **********************************************************************************************
7 ***************************************************************************************
8 ********************************************************************************************
9 ********************************************************************************************
10 ***********************************************************************************************
11 ************************************************************************************************
12 *******************************************************************************************************************
13 *************************************************************************************************************
14 ***************************************************************************************************************
15 *****************************************************************************************************
16 ********************************************************************************************************
17 ****************************************************************************************************
18 ************************************************************************************************
19 **********************************************************************************
20 ******************************************************************************************
21 ********************************************************************************************************
22 ******************************************************************************************************
23 **********************************************************************************************************
24 *******************************************************************************************************
25 ******************************************************************************************
26 ***************************************************************************************************************
27 ***********************************************************************************************************
28 *****************************************************************************************************
29 ****************************************************************************************************************
30 ********************************************************************************************************
31 ********************************************************************************************
32 ****************************************************************************************************
33 **********************************************************************************************
34 ****************************************************************************************************
35 **************************************************************************************************
36 *********************************************************************************************
37 ***************************************************************************************
38 *******************************************************************************************************
39 **********************************************************************************************************
40 ******************************************************************************************************
41 ********************************************************************************************************
42 ************************************************************************************
43 ****************************************************************************************************************************
44 ****************************************************************************************************************************
45 ***********************************************************************************************
46 *****************************************************************************************************
47 ***************************************************************************************
48 ***********************************************************************************************************
49 ****************************************************************************************************************

Answer 4

sed "1,5d" < FILENAME | sort -R | head -2

Answer 5

Ответ на Python.Предполагая, что вы можете прочитать весь файл в память.

#using python 2.6
import sys
import os
import itertools
import random

def main(directory, num_files=5, num_entries=5):
    file_paths = os.listdir(directory)

    # get a random sampling of the available paths
    chosen_paths = random.sample(file_paths, num_files)

    for path in chosen_paths:
        chosen_entries = get_random_entries(path, num_entries)
        for entry in chosen_entries:
            # do something with your chosen entries
            print entry

def get_random_entries(file_path, num_entries):
    with open(file_path, 'r') as file:
        # read the lines and slice off the headers
        lines = file.readlines()[5:]

        # group the lines into pairs (i.e. entries)
        entries = list(itertools.izip_longest(*[iter(lines)]*2))

        # return a random sampling of entries
        return random.sample(entries, num_entries)

if __name__ == '__main__':
    #use optparse here to do fancy things with the command line args
    main(sys.argv[1:])

Ссылки: itertools , random , optparse

Answer 6

Два других способа сделать это: 1 - с помощью генераторов (может потребоваться много памяти): http://www.usrsb.in/Picking-Random-Items--Take-Two--Hacking-Python-s-Generators-.html

2 - с помощью умного поиска (на самом деле лучший метод): http://www.regexprn.com/2008/11/read-random-line-in-large-file-in.html

Я здесь копирую код умного Джонатана Купфермана:

#!/usr/bin/python

import os,random

filename="averylargefile"
file = open(filename,'r')

#Get the total file size
file_size = os.stat(filename)[6]

while 1:
      #Seek to a place in the file which is a random distance away
      #Mod by file size so that it wraps around to the beginning
      file.seek((file.tell()+random.randint(0,file_size-1))%file_size)

      #dont use the first readline since it may fall in the middle of a line
      file.readline()
      #this will return the next (complete) line from the file
      line = file.readline()

      #here is your random line in the file
      print line

Answer 7

Еще один вариант Python; чтение содержимого всех файлов в память:

import random
import fileinput

def openhook(filename, mode):
    f = open(filename, mode)
    headers = [f.readline() for _ in range(5)]
    return f

num_entries = 3
lines = list(fileinput.input(openhook=openhook))
print random.sample(lines, num_entries)