one algorithm question# CS - 计算机科学
c*d
1 楼
a log file contains n diferent kinds of items
how to count the occurence for each items if n is too big(out of memory)?
thx
how to count the occurence for each items if n is too big(out of memory)?
thx
f*p
2 楼
Is it a algorithm question? Are you counting how many stars in the universe?
【在 c**d 的大作中提到】
: a log file contains n diferent kinds of items
: how to count the occurence for each items if n is too big(out of memory)?
: thx
【在 c**d 的大作中提到】
: a log file contains n diferent kinds of items
: how to count the occurence for each items if n is too big(out of memory)?
: thx
b*n
3 楼
how big is too big? greater than 2^(4G) ?
【在 c**d 的大作中提到】
: a log file contains n diferent kinds of items
: how to count the occurence for each items if n is too big(out of memory)?
: thx
【在 c**d 的大作中提到】
: a log file contains n diferent kinds of items
: how to count the occurence for each items if n is too big(out of memory)?
: thx
c*d
4 楼
assume it does not fit into memory
【在 b***n 的大作中提到】
: how big is too big? greater than 2^(4G) ?
【在 b***n 的大作中提到】
: how big is too big? greater than 2^(4G) ?
s*e
5 楼
允许写文件吗？说个简单的。
读item,遇到新type，用一个新空间记录count，遇到已有type，增加count
如果memory已满，输出没处理的新type的item到新文件。
下次再扫描这个新文件。
【在 c**d 的大作中提到】
: a log file contains n diferent kinds of items
: how to count the occurence for each items if n is too big(out of memory)?
: thx
读item,遇到新type，用一个新空间记录count，遇到已有type，增加count
如果memory已满，输出没处理的新type的item到新文件。
下次再扫描这个新文件。
【在 c**d 的大作中提到】
: a log file contains n diferent kinds of items
: how to count the occurence for each items if n is too big(out of memory)?
: thx
f*p
6 楼
我怀疑他根本就没听懂问题。
【在 s***e 的大作中提到】
: 允许写文件吗？说个简单的。
: 读item,遇到新type，用一个新空间记录count，遇到已有type，增加count
: 如果memory已满，输出没处理的新type的item到新文件。
: 下次再扫描这个新文件。
【在 s***e 的大作中提到】
: 允许写文件吗？说个简单的。
: 读item,遇到新type，用一个新空间记录count，遇到已有type，增加count
: 如果memory已满，输出没处理的新type的item到新文件。
: 下次再扫描这个新文件。
m*s
7 楼
Right on. It is too vague.
What is contained in the log? Strings? Objects?
If strings, use tries/hash.
If objects, convert to binary, then use hash.
Either way, split and store chunks of temp data on disk. cache them if needed.
【在 f*****p 的大作中提到】
: 我怀疑他根本就没听懂问题。
What is contained in the log? Strings? Objects?
If strings, use tries/hash.
If objects, convert to binary, then use hash.
Either way, split and store chunks of temp data on disk. cache them if needed.
【在 f*****p 的大作中提到】
: 我怀疑他根本就没听懂问题。
c*c
8 楼
这个好像是search engine的interview里头比较容易碰到的问题?
如果是有多台机器可以一起跑, 指定一台为front end, 其余机器
为back end, 每台back end机器负责一部分item的计数(比如第一
台机器负责A打头的字符串, 第二台机器负责B打头的字符串, 诸
如此类); 由front end机器顺序读那个文件, 把每个item发给相
应的backend机器让它计数. 最后处理完后每台back end机器按
顺序把计好的数写到一个文件里就行了.
如果只有一台机器, 没有多台机器一起跑, 但允许随时写文件,
俺突然想到的, 似乎有一种比较通用的一种做法, 在memory满之
前跟你说的一样, 但memory满之后, 要把当前memory的内容排个
序然后dump到一个新文件里, 然后接着读原来的文件, 一样的做
法, 到memory满了再dump到一个新的文件. 最后全部处理完了,
把新生成的那一堆文件打开, 因为都已经排好序了, 很容易就可
以把结果combine起来, 写入一个最终的结果文件.
【在 s***e 的大作中提到】
: 允许写文件吗？说个简单的。
: 读item,遇到新type，用一个新空间记录count，遇到已有type，增加count
: 如果memory已满，输出没处理的新type的item到新文件。
: 下次再扫描这个新文件。
如果是有多台机器可以一起跑, 指定一台为front end, 其余机器
为back end, 每台back end机器负责一部分item的计数(比如第一
台机器负责A打头的字符串, 第二台机器负责B打头的字符串, 诸
如此类); 由front end机器顺序读那个文件, 把每个item发给相
应的backend机器让它计数. 最后处理完后每台back end机器按
顺序把计好的数写到一个文件里就行了.
如果只有一台机器, 没有多台机器一起跑, 但允许随时写文件,
俺突然想到的, 似乎有一种比较通用的一种做法, 在memory满之
前跟你说的一样, 但memory满之后, 要把当前memory的内容排个
序然后dump到一个新文件里, 然后接着读原来的文件, 一样的做
法, 到memory满了再dump到一个新的文件. 最后全部处理完了,
把新生成的那一堆文件打开, 因为都已经排好序了, 很容易就可
以把结果combine起来, 写入一个最终的结果文件.
【在 s***e 的大作中提到】
: 允许写文件吗？说个简单的。
: 读item,遇到新type，用一个新空间记录count，遇到已有type，增加count
: 如果memory已满，输出没处理的新type的item到新文件。
: 下次再扫描这个新文件。
w*e
9 楼
Assume n is too big, and existed items are sparse compared to n, you may
want to look at the multiple-dimension aggregation algorithm in data mining
. Although it is multi-dimension, the algorithm have good performance on how
to iterate through the whole dimension and acount for each item in cell.
【在 c**c 的大作中提到】
: 这个好像是search engine的interview里头比较容易碰到的问题?
: 如果是有多台机器可以一起跑, 指定一台为front end, 其余机器
: 为back end, 每台back end机器负责一部分item的计数(比如第一
: 台机器负责A打头的字符串, 第二台机器负责B打头的字符串, 诸
: 如此类); 由front end机器顺序读那个文件, 把每个item发给相
: 应的backend机器让它计数. 最后处理完后每台back end机器按
: 顺序把计好的数写到一个文件里就行了.
: 如果只有一台机器, 没有多台机器一起跑, 但允许随时写文件,
: 俺突然想到的, 似乎有一种比较通用的一种做法, 在memory满之
: 前跟你说的一样, 但memory满之后, 要把当前memory的内容排个
want to look at the multiple-dimension aggregation algorithm in data mining
. Although it is multi-dimension, the algorithm have good performance on how
to iterate through the whole dimension and acount for each item in cell.
【在 c**c 的大作中提到】
: 这个好像是search engine的interview里头比较容易碰到的问题?
: 如果是有多台机器可以一起跑, 指定一台为front end, 其余机器
: 为back end, 每台back end机器负责一部分item的计数(比如第一
: 台机器负责A打头的字符串, 第二台机器负责B打头的字符串, 诸
: 如此类); 由front end机器顺序读那个文件, 把每个item发给相
: 应的backend机器让它计数. 最后处理完后每台back end机器按
: 顺序把计好的数写到一个文件里就行了.
: 如果只有一台机器, 没有多台机器一起跑, 但允许随时写文件,
: 俺突然想到的, 似乎有一种比较通用的一种做法, 在memory满之
: 前跟你说的一样, 但memory满之后, 要把当前memory的内容排个
M*e
10 楼
if you are asking a research question, then check papers on streaming algorith
ms that uses a log space to do approximate counting.
【在 c**d 的大作中提到】
: assume it does not fit into memory
ms that uses a log space to do approximate counting.
【在 c**d 的大作中提到】
: assume it does not fit into memory
s*m
11 楼
hash.
【在 c**d 的大作中提到】
: a log file contains n diferent kinds of items
: how to count the occurence for each items if n is too big(out of memory)?
: thx
【在 c**d 的大作中提到】
: a log file contains n diferent kinds of items
: how to count the occurence for each items if n is too big(out of memory)?
: thx
相关阅读
请推荐本 Data Analysis 的书请推荐一本操作系统的书算法问题問個aaai 2008 投稿問題求Operating System的考题[合集] Any conferences on system security area?请教:CS PhD的生活请推荐一个处理sparse matrix SVD的java library请问wikibooks里的C++课本如何求解方程2*x^3+10*x^2=3?? (转载)请问谁有这本书的solutions for exercisegood journal for database?[合集] 好吧, 我来个流氓揭发 :p[合集] 大家说小硕如果去中国微软研究院能拿多少？请问几个ＣＳ方向的前景？请教一下Wisconsin-Madison (转载)请问做并行，前景好么？Conditionally Accepted with Shepherding 最终录取可能有多大?问一个关于局域网的简单问题 (转载)ACM的latex模板怎么改成10pt字体大小？