描述

Retrieving a Line at Random from a File of Unknown Size

读取未知大小文件的随机一行

问题 Problem

有文件，不清楚大小(但是可能非常大)，需要忽略文件，只读取数据的随机一行。

解决 Solution

We do need to read the whole file, but we don't have to read it all at once:

确实需要读取文件的全部数据, 但不是一次全部读出:

import random

def randomLine(file_object):
    "顺序读取文件内容,取文件的随机一行"
    lineNum = 0
    selected_line = ''

    while 1:
        aLine = file_object.readline(  )
        if not aLine: break
        lineNum = lineNum + 1
        # 是否选择本行？                      #译注：这里英语原文注释可能有错，根据程序逻辑译出   
        if random.uniform(0,lineNum)<1:    #译注: 算法的解释见讨论部分,请先考虑考虑,uniform函数用法附后            
            selected_line = aLine          
    file_object.close(  )
    return selected_line

讨论 Discussion

当然, 更直接的方法是这样的:

random.choice(file_object.readlines(  ))

但是, 这需要将全部文件内容读入内存, 对确实很大的文件可能有问题。

解决部分中算法的理论依据不是很明显，但是也不是太深奥: 当读取到文件第Ｎ行时，当前行(即变量selected_line指向的行)被随机取得的可能性是1/N。容易看出算法选择当前最后读取的一行的可能性是对的，因为此处我们明确地以1.0/lineNum可能性选择最后一行。

由归纳法可以证明算法的合理性：如果读取第N-1行时，选择N-1行的可能性是对的，那么显然对于第N行时算法也是对的。由于(仅读取到第一行)选择第一行的可能性是1, 因此，算法的随机选择处理直到第N行都是对的。

同样的技巧对于从有限序列中，应用均匀分布的可能性，一次处理一个元素(原因未知)地随机选择一个元素也是适用的。但是除了从比如/usr/dict/words 这样的文件中随机选择一个单词以外，这个理论的应用不是很广。

参考 See Also

Python 库参考 random模块部分

#译注：为阅读方便，这里给出random模块两个函数的说明

uniform( a, b) ：Return a random real number N such that a <= N < b.

choice( seq) ：Return a random element from the non-empty sequence seq.

-  ⇤ ← Revision 5 as of 2004-09-21 06:19:42 → 
  Size: 2850
  Editor: 61
  Comment:
+   ← Revision 11 as of 2004-09-21 18:05:06 → ⇥
  Size: 2790
  Editor: 61
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 17:
-有文件，不清楚大小(但是可能非常大)，需要忽略文件本身，只读取数据的随机一行。
+有文件，不清楚大小(但是可能非常大)， 需要忽略文件， 只读取数据的随机一行。
 Line 22:
-需要读取文件的全部数据,但不是一次全部读出:
+确实需要读取文件的全部数据, 但不是一次全部读出:
-Line 27:
+Line 28:
-    "顺序读取文件内容,取文件的随机的一行"
+    "顺序读取文件内容,取文件的随机一行"
-Line 35:
+Line 36:
-        # 本行有多大可能性是文件最后一行?          
        if random.uniform(0,lineNum)<1:              #译注：这里请思考1分钟(天才除外 :)                   
            selected_line = aLine
+        # 是否选择本行？                      #译注：这里英语原文注释可能有错，根据程序逻辑译出   
        if random.uniform(0,lineNum)<1:    #译注: 算法的解释见讨论部分,请先考虑考虑,uniform函数用法附后            
            selected_line = aLine
-Line 42:
+Line 43:
-#译注: 算法的解释见讨论部分
-Line 46:
+Line 47:
-当然,更明了的方法是这样的:
+当然, 更直接的方法是这样的:
-Line 50:
+Line 51:
-但是,这需要将全部文件内容读入内存,对确实很大的文件可能有问题。
+但是, 这需要将全部文件内容读入内存, 对确实很大的文件可能有问题。
-Line 52:
+Line 53:
-This recipe works thanks to an unobvious but not terribly deep theorem: when we have seen the first N lines in the file, there is a probability of exactly 1/N that each of them is the one selected so far (i.e., the one to which the selected_line variable refers at this point). This is easy to see for the last line (the one just read into the aLine variable), because we explicitly choose it with a probability of 1.0/lineNum. The general validity of the theorem follows by induction. If it was true after the first N-1 lines were read, it's clearly still true after the Nth one is read. As we select the very first line with probability 1, the limit case of the theorem clearly does hold when N=1.
+解决部分中算法的理论依据不是很明显，但是也不是太深奥: 当读取到文件第'''Ｎ'''行时，当前行(即变量'''selected_line'''指向的行)被随机取得的可能性是'''1/N'''。 容易看出算法选择当前最后读取的一行的可能性是对的，因为此处我们明确地以'''1.0/lineNum'''可能性选择最后一行。
-Line 54:
+Line 55:
-上面算法的理论依据不是很明显，但是也不是太深奥: 当读取到文件第'''Ｎ'''行时，当前行(即变量'''selected_line'''指向的行)被随机取得的可能性是'''1/N'''。 容易看出算法选择当前最后读取一行的可能性是对的，因为此处我们以可能性'''1.0/lineNum'''的选择最后一行。
+由归纳法可以证明算法的合理性：如果读取第'''N-1'''行时，选择'''N-1'''行的可能性是对的，那么显然对于第'''N'''行时算法也是对的。由于(仅读取到第一行)选择第一行的可能性是'''1''', 因此，算法的随机选择处理直到第'''N'''行都是对的。
-Line 56:
+Line 57:
-由归纳法可以证明算法的合理性：如果读取第'''N-1'''行时，选择'''N-1'''行的可能性是对的，那么显然对于第'''N'''行时算法也是对的。由于(仅读取到)选择第一行的可能性是'''1''',因此，算法的随机选择处理直到第'''N'''行都是对的。
 Line 58:
-...
+同样的技巧对于从有限序列中，应用均匀分布的可能性，一次处理一个元素(原因未知)地随机选择一个元素也是适用的。但是除了从比如/usr/dict/words 这样的文件中随机选择一个单词以外，这个理论的应用不是很广。
 Line 61:
+Python 库参考 '''random'''模块部分

#译注：为阅读方便，这里给出random模块两个函数的说明

uniform( a, b) ：Return a random real number N such that a <= N < b. 

choice( seq)   ：Return a random element from the non-empty sequence seq.

Diff for "PyCkBk-4-6"

描述

问题 Problem

解决 Solution

讨论 Discussion

参考 See Also