z****e
发帖数: 2024 | 1 如何找出纽约州一天内使用最频繁的5个电话号码？ 假如一天之内有100万个电话号码
被使用（同一个号码用两次算两次），内存有限，该怎么办？
100M numbers=(4 byte/per int) *100M=400MB ???
怎么就 “内存有限”了？
如果内存放不下，怎么办呢？ |
l*******r
发帖数: 511 | 2 我想可以模仿 most recently used cache的设计方法吧
【在 z****e 的大作中提到】
: 如何找出纽约州一天内使用最频繁的5个电话号码？ 假如一天之内有100万个电话号码
: 被使用（同一个号码用两次算两次），内存有限，该怎么办？
: 100M numbers=(4 byte/per int) *100M=400MB ???
: 怎么就 “内存有限”了？
: 如果内存放不下，怎么办呢？
|
q*c
发帖数: 9453 | 3 100M != 一百万 == 1M.
4M 内存行
【在 z****e 的大作中提到】
: 如何找出纽约州一天内使用最频繁的5个电话号码？ 假如一天之内有100万个电话号码
: 被使用（同一个号码用两次算两次），内存有限，该怎么办？
: 100M numbers=(4 byte/per int) *100M=400MB ???
: 怎么就 “内存有限”了？
: 如果内存放不下，怎么办呢？
|
z****e
发帖数: 2024 | 4 如果内存不限，hash？
如果有限，咋整？比如1G电话号码。 |
s*w
发帖数: 729 | 5 this is actually a open research problem, which I believe there is no exact
answer. I got this impression after digging online.
if no limitation on memory, just count for every distinct key and then sort
the frequencies. It has nothing to do with hashing.
Limitation on memory = live data stream here. you have no way to feed live
data stream in the memory. 1M phone numbers for 1k memory = live data
stream.
I glanced at only one paper titled "finding frequent items in data stream".
So I may b |
U********d
发帖数: 577 | 6 我觉得你这个问题应该是说“假如内存不够怎么办”吧？因为光纽约州的肯定没有问题
的，普通pc机处理全世界电话号码应该都没问题。
如果是内存不够的问题，有几个思路，一个是硬盘交换文件（泪奔~），如果你的设备
没有硬盘等其他设备，那就只能考虑压缩了，电话号码还是比较好处理的，当全部变成
顺序的以后，我觉得你可以考虑某些图像无损压缩算法。 |
h*******c
发帖数: 248 | 7 这个问题我工作中常碰到。我的做法是，对电话号码hash，按hash把数据分块。每块儿
小于内存，然后一块一块的数。
顺便给大家贡献一个hash的perl code，是我知道的最简单，最快的玩儿法了：
use B;
$hash=B::hash("abscd");
$int_hash=hex($hash);
这个结果是个大整数。分块儿求mod就是了。 |
z****e
发帖数: 2024 | 8 “一块一块的数”，这个怎么搞？
因为再单独一个块里边出现最多的，未必是全局出现最多的。
单独一块里边的出现频率比较低的，有可能最后是全局出现频率最高的啊。
数每一块的时候记录什么信息呢？
多谢。
【在 h*******c 的大作中提到】
: 这个问题我工作中常碰到。我的做法是，对电话号码hash，按hash把数据分块。每块儿
: 小于内存，然后一块一块的数。
: 顺便给大家贡献一个hash的perl code，是我知道的最简单，最快的玩儿法了：
: use B;
: $hash=B::hash("abscd");
: $int_hash=hex($hash);
: 这个结果是个大整数。分块儿求mod就是了。
|
h*******c
发帖数: 248 | 9 你不是就要top-5吗？
每块里面保留top-5不就行了？ |
z****e
发帖数: 2024 | 10 不一定呀。
比如
块1
前5：A(三次) B(三次) C(三次) D(三次) E(三次)
第六F（2次）
块2
前5：G(三次) H(三次) I(三次) J(三次) K(三次)
第六F（2次）
于是，最多的就是F（4次），但是由于每块保留top5,没有F。
也许我理解你的做法不清楚。还请明示。
【在 h*******c 的大作中提到】
: 你不是就要top-5吗？
: 每块里面保留top-5不就行了？
|
|
|
s*w
发帖数: 729 | 11 还在折腾这个阿，我前面说过了，这个live stream 的问题只能求近似解 |
s*w
发帖数: 729 | 12 用 了文件，相当于虚拟内存
【在 h*******c 的大作中提到】
: 这个问题我工作中常碰到。我的做法是，对电话号码hash，按hash把数据分块。每块儿
: 小于内存，然后一块一块的数。
: 顺便给大家贡献一个hash的perl code，是我知道的最简单，最快的玩儿法了：
: use B;
: $hash=B::hash("abscd");
: $int_hash=hex($hash);
: 这个结果是个大整数。分块儿求mod就是了。
|
z****e
发帖数: 2024 | 13 there is an exact solution.
I'm thinking the following.
say we have 10G phone numbers saved as files, but 500M memory. and we want the top 5 highest frequency.
then we can use brute force.
1. take one number from the file, scan the files to count the frequency of this number, finally save the number and its frequency as a pair in another file FFF.
2. repeat the above for all numbers in the 10G files. and our FFF will be appended until the last number is scanned.
for 1, and 2. the orginal 10G fil
【在 s*w 的大作中提到】
: 还在折腾这个阿，我前面说过了，这个live stream 的问题只能求近似解
|
X****r
发帖数: 3557 | 14 你没有看到说按hash分块吗？同一个号码必然到同一块。
【在 z****e 的大作中提到】
: 不一定呀。
: 比如
: 块1
: 前5：A(三次) B(三次) C(三次) D(三次) E(三次)
: 第六F（2次）
: 块2
: 前5：G(三次) H(三次) I(三次) J(三次) K(三次)
: 第六F（2次）
: 于是，最多的就是F（4次），但是由于每块保留top5,没有F。
: 也许我理解你的做法不清楚。还请明示。
|
s*w
发帖数: 729 | 15 Your solution is fine for not so huge data. But usually the problem is posed
for such huge data that it has to be modelled as live stream data. You see
one number at one time, and it never ends (with respect to your available
computer resources).
we want to scan just once, no matter the data is fixed size or live stream.
I also thought about the exact solution for the limited data case. We may
save some space by throwing away those absolutely no chance to make into top
K. Just like in NBA, team
【在 z****e 的大作中提到】
: there is an exact solution.
: I'm thinking the following.
: say we have 10G phone numbers saved as files, but 500M memory. and we want the top 5 highest frequency.
: then we can use brute force.
: 1. take one number from the file, scan the files to count the frequency of this number, finally save the number and its frequency as a pair in another file FFF.
: 2. repeat the above for all numbers in the 10G files. and our FFF will be appended until the last number is scanned.
: for 1, and 2. the orginal 10G fil
|
z****e
发帖数: 2024 | 16 red pig master!
醍醐灌顶。
【在 X****r 的大作中提到】
: 你没有看到说按hash分块吗？同一个号码必然到同一块。
|
h*******c
发帖数: 248 | 17 幸亏我这两天没上这儿来。小红猪又挡了这一枪，否则肯定要一口血吐在屏幕上。
【在 z****e 的大作中提到】
: red pig master!
: 醍醐灌顶。
|
h**k
发帖数: 3368 | 18 每个块里选前5名，然后比较所有块的前五名。
块的大小的选择很重要。
【在 z****e 的大作中提到】
: “一块一块的数”，这个怎么搞？
: 因为再单独一个块里边出现最多的，未必是全局出现最多的。
: 单独一块里边的出现频率比较低的，有可能最后是全局出现频率最高的啊。
: 数每一块的时候记录什么信息呢？
: 多谢。
|
