随机从文件中选择行

Question

我有一堆文件，每个文件的开头都有5行标题。接下来的内容是成对的行，组成一个条目。我需要从这些文件中随机选择一些条目。
我该怎么做才能随机选择文件和随机选择条目（成对的行，排除标题）呢？

Answer 1

Python解决方案 - 只读取文件一次，内存占用少

可以这样调用：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 2

你可以看看这个链接 perlfaq5，里面有一些有用的信息。

Answer 3

如果文件比较小，可以把每一对行读到内存里，然后从这些数据中随机选择。如果文件太大，Eugene Y 提供了正确的解决方案：使用水库抽样。

下面是这个算法的简单解释。

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

换句话说，在第一行时，我们会以1/1的概率选择第一行。在第二行时，我们会以1/2的概率把选择改为第二行。在第三行时，我们会以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行。我们已经说服自己，在第三行时，之前的每一行（1、2、3）都有相等的机会成为我们当前的选择。当我们到达第四行时，它将有1/4的机会被选中——这正是它应该有的机会，因此之前的3行的概率会恰好减少到正确的数值（1/3 * 3/4 = 1/4）。

这里是Perl FAQ 的答案，已经调整为适合你的问题。

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;