h**********d
发帖数: 4313 | 1 Large file, multiple lines, how to get any line in equal probablity. 这题
可以问得很深入，比如文件太大内存无法装入如何办。
有人有内存不够大的做法吗，能不能讲一下，谢谢 |
g*********s
发帖数: 1782 | 2 题意不清。什么叫”get any line in equal probablity“？
【在 h**********d 的大作中提到】
: Large file, multiple lines, how to get any line in equal probablity. 这题
: 可以问得很深入，比如文件太大内存无法装入如何办。
: 有人有内存不够大的做法吗，能不能讲一下，谢谢
|
h**********d
发帖数: 4313 | 3 就是一个很大的file，不知道有多少行，问你怎么才能random的选其中一行，使得每行
被选的概率相等
【在 g*********s 的大作中提到】
: 题意不清。什么叫”get any line in equal probablity“？
|
z****u
发帖数: 24 | 4 我有一个笨方法
拆分这个大文件为很多个小的可以装入内存的文件
一个一个调入内存，计算总的函数，和每个文件对应的行数范围
产生一个随机数 [1, 总行数]
找到对应的文件
找到对应的行 |
g*********s
发帖数: 1782 | 5 i think it's just the classical online algorithm to pick up a number in a
infinite stream: 1/2*2/3*3/4... = 1/n.
【在 h**********d 的大作中提到】
: 就是一个很大的file，不知道有多少行，问你怎么才能random的选其中一行，使得每行
: 被选的概率相等
|
h**********d
发帖数: 4313 | 6 好吧，这可以算brute force的了，谢谢
【在 z****u 的大作中提到】
: 我有一个笨方法
: 拆分这个大文件为很多个小的可以装入内存的文件
: 一个一个调入内存，计算总的函数，和每个文件对应的行数范围
: 产生一个随机数 [1, 总行数]
: 找到对应的文件
: 找到对应的行
|
h**********d
发帖数: 4313 | 7 可以说再详细点吗，thanks
a
【在 g*********s 的大作中提到】
: i think it's just the classical online algorithm to pick up a number in a
: infinite stream: 1/2*2/3*3/4... = 1/n.
|
j*t
发帖数: 184 | |
h**********d
发帖数: 4313 | 9 明白了，谢谢
我找到了一个类似题目的解法，是一个file里选10行
public void reservoirSampling () throws FileNotFoundException,
IOException {
File f = new File("data.txt");
BufferedReader br = new BufferedReader(new FileReader(f));
String currentLine;
int reservoirSize=10;
List reservoirList= new ArrayList(reservoirSize);
int count=0;
Random ra = new Random();
int randomNumber;
while ((currentLine = br.readLine()) != null){
count ++;
if (count<=10){
reservoirList.add(currentLine);
}
else {
randomNumber = (int)ra.nextInt(count);
if (randomNumber
{
reservoirList.set(randomNumber, currentLine);
}
}
}
}
【在 j*t 的大作中提到】
: Reservoir sampling
: http://en.wikipedia.org/wiki/Reservoir_sampling
|
