x**y
发帖数: 1086 | 1 一个含1 million 32位整数的文件，统计不同整数出现次数的直方图，以及算法复杂度.
要求：文件内容只能顺序读取，可以自己建临时文件进行读写，同时可打开的文件数无
限制，但是内存中只能保留3000个整数。
想不出来该怎么做，哪位能指点一下，谢谢！ | A*H
发帖数: 127 | 2 map/reduce, read numbers and write to different temp files based on the
range (partition 32 bit numbers), and count on each temp file, each map jobs
can run in parallels | j*****u
发帖数: 1133 | 3 这种题真无聊
1 million int=4MB is nothing，非要split成1M/3000个temp file。。。
度.
【在 x**y 的大作中提到】
: 一个含1 million 32位整数的文件，统计不同整数出现次数的直方图，以及算法复杂度.
: 要求：文件内容只能顺序读取，可以自己建临时文件进行读写，同时可打开的文件数无
: 限制，但是内存中只能保留3000个整数。
: 想不出来该怎么做，哪位能指点一下，谢谢！
| a***c
发帖数: 2443 | 4 its not that bad. If you tweaked the problem a little bit and make a
dynamic version out of it, you could write a paper about it
http://www.google.com/url?
sa=t&source=web&cd=2&ved=0CBoQFjAB&url=http%3A%2F%2Fciteseerx.ist.psu.e
du%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.151.5909%26rep%3Drep1%26type%3Dp
df&ei=b7jdTKboPImisAOjpJ2jCg&usg=AFQjCNEYdtuky0sBzQ7kHeKblwqXOkmELA&sig
2=7zl4nStfKHQdoLKxWEKqZg
【在 j*****u 的大作中提到】
: 这种题真无聊
: 1 million int=4MB is nothing，非要split成1M/3000个temp file。。。
:
: 度.
| x**y
发帖数: 1086 | 5 多谢各位，还有个问题就是如果这样做的话，每个integer读入内存的次数的上限应该
怎么确定啊 | x**y
发帖数: 1086 | 6 如果不用mapreduce的话，该怎么设计呢，思考中。。。。。。。。 | j*****u
发帖数: 1133 | 7 我上面说了啊，split成1M/3000=334个file
scan file的同时写这334个temp file，按照range决定比如第一个file是0-2999
然后读每个temp file，sort后写输出，就分别都是sort好的
第二步没有map reduce,单机的话即使你同时做，因为瓶颈是IO(sort 3000 items is
nothing)也不会快
【在 x**y 的大作中提到】
: 如果不用mapreduce的话，该怎么设计呢，思考中。。。。。。。。
| x**y
发帖数: 1086 | 8 有个问题，你所说的range是指integer的value吧，如果说在某个range里，比如0-2999
，有10000个数，只有3000的内存，怎么sort？
【在 j*****u 的大作中提到】
: 我上面说了啊，split成1M/3000=334个file
: scan file的同时写这334个temp file，按照range决定比如第一个file是0-2999
: 然后读每个temp file，sort后写输出，就分别都是sort好的
: 第二步没有map reduce,单机的话即使你同时做，因为瓶颈是IO(sort 3000 items is
: nothing)也不会快
| m*****k
发帖数: 731 | 9 keep reading Ints in from the 1M Ints,
constructing a Sorted map, key is the Int, value is its freq,
once the mem is full, say 1500 entries,
output to a temp file,
repeat this step,
.....
now u get at the most ceil(1M/1500) = 667 tmp files, all sorted internally
by key with key-value pairs,
now take the first entry from each tmp file,
MERGE: merge in mem, say <1, 5> and <1, 2> merge to <1, 7>,
remember the min key is from which tmp fileS, it may come from more than 1
tmp file,say tmp x and tmp y,
output the min key with its freq and remove the entry from mem,
read in next entries from tmp x and tmp y(if there r still entries)
if map is empty, done,
else goto MERGE | s*******r
发帖数: 47 | 10 two-pass external sort, again?
2999
【在 x**y 的大作中提到】
: 有个问题，你所说的range是指integer的value吧，如果说在某个range里，比如0-2999
: ，有10000个数，只有3000的内存，怎么sort？
|
|
