从 N 条记录的文件中随机 select M 条记录
randomly select M records from a file of N records
需要从一个有N条记录（N>M）的文件中随机selectM条记录（即文件中每条记录有相同的概率被选择）。想知道是否有只读取文件一次的解决方案？
我想到的唯一方法是select每条记录的概率为M/N，但这种方法可能导致少于M条记录或多于M条记录。
欢迎任何更聪明的想法。
此致，
林
Select M unique个随机数，放到一个数组中，排序，然后一次读取文件。当你读入文件的第 i 条记录时，如果 i 在数组中则保留它，否则丢弃它。这需要 O(M) 内存，并且是 运行 时间 O(N + M log M)。
您可能需要的是水库采样算法 (link)。
它不仅允许您以相同的概率准确地获得 M 条记录，而且您只需要读取一次输入，而无需事先知道 N。
复杂度为 O(N)。
需要从一个有N条记录（N>M）的文件中随机selectM条记录（即文件中每条记录有相同的概率被选择）。想知道是否有只读取文件一次的解决方案？
我想到的唯一方法是select每条记录的概率为M/N，但这种方法可能导致少于M条记录或多于M条记录。
欢迎任何更聪明的想法。
此致， 林
Select M unique个随机数，放到一个数组中，排序，然后一次读取文件。当你读入文件的第 i 条记录时，如果 i 在数组中则保留它，否则丢弃它。这需要 O(M) 内存，并且是 运行 时间 O(N + M log M)。
您可能需要的是水库采样算法 (link)。
它不仅允许您以相同的概率准确地获得 M 条记录，而且您只需要读取一次输入，而无需事先知道 N。
复杂度为 O(N)。