q*s
2 楼
有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
什么好的算法么？
什么好的算法么？
R*G
3 楼
这个不用种了吧，直接下肚就行。
g*e
4 楼
google reservoir sampling
【在 q***s 的大作中提到】
: 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
: 什么好的算法么？
【在 q***s 的大作中提到】
: 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
: 什么好的算法么？
q*s
5 楼
多谢！我的意思是用java来实现，不是借助外部的工具。
b*y
6 楼
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);
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
7 楼
咋样?
g*g
8 楼
If you really want to do it quickly, you should build an index.
【在 q***s 的大作中提到】
: 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
: 什么好的算法么？
【在 q***s 的大作中提到】
: 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
: 什么好的算法么？
q*s
9 楼
谢谢Briteguy的详细介绍，这也是我想到的，问题是需要更快。我想到下列一些方法：
1、把这些行倒到数据库中
2、把大文件分裂为小文件
3、建立index（谢谢googbug）
1、把这些行倒到数据库中
2、把大文件分裂为小文件
3、建立index（谢谢googbug）
h*c
10 楼
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?
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
11 楼
你倒到数据库的时间比读取一次文件的时间多多了，不划算。
我想到的另一个办法就是，可能统计上有点技巧，比如说, 第一行的时候，几率的
threshhold小，然后，随着读取的行数增加，threshhold不断增加。
但问题是不知道行数，所以，好像不容易设置dynamic的threshhold...
【在 q***s 的大作中提到】
: 谢谢Briteguy的详细介绍，这也是我想到的，问题是需要更快。我想到下列一些方法：
: 1、把这些行倒到数据库中
: 2、把大文件分裂为小文件
: 3、建立index（谢谢googbug）
m*r
12 楼
这个可以读一次解决。
基本办法是，
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 的大作中提到】
: 有一个很大的文件，不可能一次全读到计算机中，想随机地读出其中的某一行，大家有
: 什么好的算法么？
基本办法是，
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
13 楼
then it's not strictly random distribution
【在 b******y 的大作中提到】
:
: 你倒到数据库的时间比读取一次文件的时间多多了，不划算。
: 我想到的另一个办法就是，可能统计上有点技巧，比如说, 第一行的时候，几率的
: threshhold小，然后，随着读取的行数增加，threshhold不断增加。
: 但问题是不知道行数，所以，好像不容易设置dynamic的threshhold...
【在 b******y 的大作中提到】
:
: 你倒到数据库的时间比读取一次文件的时间多多了，不划算。
: 我想到的另一个办法就是，可能统计上有点技巧，比如说, 第一行的时候，几率的
: threshhold小，然后，随着读取的行数增加，threshhold不断增加。
: 但问题是不知道行数，所以，好像不容易设置dynamic的threshhold...
q*s
14 楼
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?
【在 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
15 楼
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
chance of getting picked.
【在 q***s 的大作中提到】
: cool, this should be the best one, I ever met
相关阅读
Eclipse不自动prompt methods咋搞定？请问公司里用Java主要干啥？java画图难题？？？求助如何在java中用visual studio的iconsC language的functoin-based reuse的问题(概念级的)Java Concurrency in Practise, 哪里有？求一个书的电子版。不知道是否有人有？ (转载)谁给推荐一个简单的ORM吧aspectJ questionhow to map one to many relation for a single table in hibemessageBundle一问JBoss 4.0.4 is slow down in every 20 dayshow to read from a non-return socket stream?java 的函数 xxx(a, b,c)能够向a 写入数据吗？请goodbug和诸位大牛帮忙：Swing 的lookandfeel 设置请问如何在java中寻找文件夹的深度（by recursive）？问个gwt client code调用远程object的问题do-while question如何用JAVA中的circular array of queue 解决Josephus problem?探讨一个java, sql设计问题