q***s
发帖数: 2243 | 1 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
什么好的算法么？ |
g**e
发帖数: 6127 | 2 google reservoir sampling
【在 q***s 的大作中提到】
: 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
: 什么好的算法么？
|
q***s
发帖数: 2243 | 3 多谢！我的意思是用java来实现，不是借助外部的工具。 |
b******y
发帖数: 9224 | 4 Random rand = new Random();
BufferedReader reader = new BufferedReader(new FileReader("bigfile.txt"));
// get the number of lines
int numLines = 0;
while (true)
{
String line = reader.readLine();
if (line == null) break;
numLines++;
}
// second pass, randomly get a line
String line = null;
float threshHold = 1 / (float) numLines;
for (int i = 0; i < numLines; i++)
{
line = reader.readLine();
if (rand.nextFloat() < threshHold)
{
// we got the line, break
break;
}
}
System.out.println("the random line is: " + line); |
b******y
发帖数: 9224 | |
g*****g
发帖数: 34805 | 6 If you really want to do it quickly, you should build an index.
【在 q***s 的大作中提到】
: 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
: 什么好的算法么？
|
q***s
发帖数: 2243 | 7 谢谢Briteguy的详细介绍，这也是我想到的，问题是需要更快。我想到下列一些方法：
1、把这些行倒到数据库中
2、把大文件分裂为小文件
3、建立index（谢谢googbug） |
h**********c
发帖数: 4120 | 8 This is more like a operating system question.
the file has a size,
postion = rand (sizeofile);
sizeoffile <=0 error
put file pointer to position,
I. read forward two '\n' '\n', the line should be in between.
II. Or read backward two '\n' '\n' if not I.
III. If neither I nor II,...
should O(1).
btw, do you mean, read to memory at once? |
b******y
发帖数: 9224 | 9
你倒到数据库的时间比读取一次文件的时间多多了，不划算。
我想到的另一个办法就是，可能统计上有点技巧，比如说, 第一行的时候，几率的
threshhold小，然后，随着读取的行数增加，threshhold不断增加。
但问题是不知道行数，所以，好像不容易设置dynamic的threshhold...
【在 q***s 的大作中提到】
: 谢谢Briteguy的详细介绍，这也是我想到的，问题是需要更快。我想到下列一些方法：
: 1、把这些行倒到数据库中
: 2、把大文件分裂为小文件
: 3、建立index（谢谢googbug）
|
m****r
发帖数: 6639 | 10 这个可以读一次解决。
基本办法是，
count = 0;
result = null;
while (true) {
line = readLine();
if line == null {
break;
} else {
result = random(1,count) == 1? line : result;
}
}
result = random(1,count) == 1? line : result;
return result；
差不多就是这个意思。 我的code肯定有错， 倒是。
【在 q***s 的大作中提到】
: 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
: 什么好的算法么？
|
g**e
发帖数: 6127 | 11 then it's not strictly random distribution
【在 b******y 的大作中提到】
:
: 你倒到数据库的时间比读取一次文件的时间多多了，不划算。
: 我想到的另一个办法就是，可能统计上有点技巧，比如说, 第一行的时候，几率的
: threshhold小，然后，随着读取的行数增加，threshhold不断增加。
: 但问题是不知道行数，所以，好像不容易设置dynamic的threshhold...
|
q***s
发帖数: 2243 | 12 cool, this should be the best one, I ever met
【在 h**********c 的大作中提到】
: This is more like a operating system question.
: the file has a size,
: postion = rand (sizeofile);
: sizeoffile <=0 error
: put file pointer to position,
: I. read forward two '\n' '\n', the line should be in between.
: II. Or read backward two '\n' '\n' if not I.
: III. If neither I nor II,...
: should O(1).
: btw, do you mean, read to memory at once?
|
m****r
发帖数: 6639 | 13 but this clearly is not uniformedly distributed. longer lines has high
chance of getting picked.
【在 q***s 的大作中提到】
: cool, this should be the best one, I ever met
|
