Jun
14
海量数据处理:找出现次数最多的那些...
回忆一下tx的二面,有一道题是这样的:
假设有1kw个身份证号,以及他们对应的数据。身份证号可能重复,要求找出出现次数最多的身份证号。
一个很显然的做法是,hash之,O(n)搞定。这前提是内存中可以存下。
如果是中国的13亿人口,内存中存不下呢?借用磁盘,多次扫描?磁盘IO的速度慢得能让你疯掉。
这时候你终于感受到,中国人口真TMD多阿。。。
--
然后再看看今天的astar复赛第一题:
百度每天都会接受数亿的查询请求, 如何在这么多的查询(Query)中找出高频的Query是一个不小的挑战. 而你的任务则更加艰巨, 你需要在极其有限的资源下来找出这些高频的Query.(使用内存不得多于1MB) 。输入文件是一行一个Query, 以文件结束符结尾。每个Query字节数L(一个汉字两个字节)满足:0<L<=16. 输入大小不超过1GB(包括换行符)。 输出你认为最高频的100个query. 每行一个, 不能有重复, 不能多输出, 但可以少输出(见样例).
用1M的内存来统计1GB的东西,而且还只能读取一遍?也许你会以为出题人疯了,或者你自己直接疯了。别激动,想想nike的广告。
然后再仔细看看题目的要求。
注意!有三个字“你认为”。然后再看看 百度之星吧 里面astar2006的答疑,给了一个明确的信息:
这题要求的不是准确的答案,而是近似答案。
回头想想,其实当时在tx面试的时候就应该问清楚,需要的是精确的还是近似的答案。现在终于豁然开朗了。
---- 传说中的分割线,下面就不是废话了 ----
要求使用1MB以内的空间,在只有一遍扫描的情况下,尽可能找出出现次数在TOP100里面的Query。
于是很显然,hash是必须的了。
由于内存限制相当严格,所以hash表只能开到很小,比如,103(因为103是个素数)。
在扫描的过程中,为了限制内存的使用,你需要按照某种规则不断地替换掉一些entry。
在遍历完以后需要归并,因为要求TOP100,所以每个hash值对应的list应该要有100个元素(因为只要近似,所以并不需要很严格)。
然后你就发现,这个东西怎么那么像计算机组成原理里面的多路组相联Cache阿。。。
那替换的规则几乎就不用想了,找出出现次数最少的那个,直接掐掉。
于是整个算法框架就完整了。
------
测试:
随机生成长度为1~16的1,000,000个字符串,字符串仅包含小写字母。数据文件为8.6MB。
显然出现次数最多的应该是单字母串。如果你的结果不是这样,那属于RPWT。
程序平均运行时间: 1.04s (Ubuntu 9.04, g++ 4.3.3, T2410[2.0G/533MHz],开着n个进程,包括一个跑着QQ的虚拟的XP)
程序内存占用:568KB (Gnome系统监视器数据)
程序统计结果:
1. 前26个结果为字母,顺序不定。
2. 看了下a~f的出现频率统计,仅有a和e的统计次数比出现次数少1,其他都完全一致。
这个结果比我想像中的还要NB。我被震撼了。
OVER。
代码(主程序 以及 数据生成代码):
p.s. 代码写得很烂,有些地方为了效率和内存占用妥协了。
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
假设有1kw个身份证号,以及他们对应的数据。身份证号可能重复,要求找出出现次数最多的身份证号。
一个很显然的做法是,hash之,O(n)搞定。这前提是内存中可以存下。
如果是中国的13亿人口,内存中存不下呢?借用磁盘,多次扫描?磁盘IO的速度慢得能让你疯掉。
这时候你终于感受到,中国人口真TMD多阿。。。
--
然后再看看今天的astar复赛第一题:
百度每天都会接受数亿的查询请求, 如何在这么多的查询(Query)中找出高频的Query是一个不小的挑战. 而你的任务则更加艰巨, 你需要在极其有限的资源下来找出这些高频的Query.(使用内存不得多于1MB) 。输入文件是一行一个Query, 以文件结束符结尾。每个Query字节数L(一个汉字两个字节)满足:0<L<=16. 输入大小不超过1GB(包括换行符)。 输出你认为最高频的100个query. 每行一个, 不能有重复, 不能多输出, 但可以少输出(见样例).
用1M的内存来统计1GB的东西,而且还只能读取一遍?也许你会以为出题人疯了,或者你自己直接疯了。别激动,想想nike的广告。
然后再仔细看看题目的要求。
引用
输出你认为最高频的100个query
注意!有三个字“你认为”。然后再看看 百度之星吧 里面astar2006的答疑,给了一个明确的信息:
这题要求的不是准确的答案,而是近似答案。
回头想想,其实当时在tx面试的时候就应该问清楚,需要的是精确的还是近似的答案。现在终于豁然开朗了。
---- 传说中的分割线,下面就不是废话了 ----
要求使用1MB以内的空间,在只有一遍扫描的情况下,尽可能找出出现次数在TOP100里面的Query。
于是很显然,hash是必须的了。
由于内存限制相当严格,所以hash表只能开到很小,比如,103(因为103是个素数)。
在扫描的过程中,为了限制内存的使用,你需要按照某种规则不断地替换掉一些entry。
在遍历完以后需要归并,因为要求TOP100,所以每个hash值对应的list应该要有100个元素(因为只要近似,所以并不需要很严格)。
然后你就发现,这个东西怎么那么像计算机组成原理里面的多路组相联Cache阿。。。
那替换的规则几乎就不用想了,找出出现次数最少的那个,直接掐掉。
于是整个算法框架就完整了。
------
测试:
随机生成长度为1~16的1,000,000个字符串,字符串仅包含小写字母。数据文件为8.6MB。
显然出现次数最多的应该是单字母串。如果你的结果不是这样,那属于RPWT。
程序平均运行时间: 1.04s (Ubuntu 9.04, g++ 4.3.3, T2410[2.0G/533MHz],开着n个进程,包括一个跑着QQ的虚拟的XP)
程序内存占用:568KB (Gnome系统监视器数据)
程序统计结果:
1. 前26个结果为字母,顺序不定。
2. 看了下a~f的出现频率统计,仅有a和e的统计次数比出现次数少1,其他都完全一致。
这个结果比我想像中的还要NB。我被震撼了。
OVER。
代码(主程序 以及 数据生成代码):
p.s. 代码写得很烂,有些地方为了效率和内存占用妥协了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int hashm = 103;
inline int hash(char *p){
int t = 0;
while (*p){
t = (*p++) + (t << 6) + (t << 16) - t;
}
return ((t & 0x7fffffff) % hashm);
}
struct node_t{
char s[17];
int count;
node_t& operator=(const char *t){
strcpy(s, t);
count = 1;
return (*this);
}
};
struct great_node_t{
char *s;
int count;
bool operator<(const great_node_t &a)const{
return (count > a.count);
}
great_node_t(const char *_s, int &_count){
s = (char*)_s;
count = _count;
}
};
node_t tbl[hashm][100];
int tblc[hashm];
vector<great_node_t> ans;
int main(){
char t[20];
int i, j;
int v;
//freopen("a.in", "r", stdin);
for (i = 0; i < hashm; ++i){
tblc[i] = 0;
}
while (scanf("%s", t) == 1){
v = hash(t);
for(i = 0, j = 0; i < tblc[v]; ++i){
if(strcmp(tbl[v][i].s, t) == 0){
tbl[v][i].count++;
break;
}
if(tbl[v][i].count < tbl[v][j].count){
j = i;
}
}
if(i == tblc[v]){
if(i < 99){
tblc[v]++;
tbl[v][i] = t;
}else{
tbl[v][j] = t;
}
}
}
for (i = 0; i < hashm; ++i){
for (j = 0; j < tblc[i]; ++j){
ans.push_back(great_node_t(tbl[i][j].s, tbl[i][j].count));
}
}
sort(ans.begin(), ans.end());
for(int i = 0; i < 100 && i < (int)ans.size(); ++i){
printf("(%d) %s\n", ans[i].count, ans[i].s);
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int hashm = 103;
inline int hash(char *p){
int t = 0;
while (*p){
t = (*p++) + (t << 6) + (t << 16) - t;
}
return ((t & 0x7fffffff) % hashm);
}
struct node_t{
char s[17];
int count;
node_t& operator=(const char *t){
strcpy(s, t);
count = 1;
return (*this);
}
};
struct great_node_t{
char *s;
int count;
bool operator<(const great_node_t &a)const{
return (count > a.count);
}
great_node_t(const char *_s, int &_count){
s = (char*)_s;
count = _count;
}
};
node_t tbl[hashm][100];
int tblc[hashm];
vector<great_node_t> ans;
int main(){
char t[20];
int i, j;
int v;
//freopen("a.in", "r", stdin);
for (i = 0; i < hashm; ++i){
tblc[i] = 0;
}
while (scanf("%s", t) == 1){
v = hash(t);
for(i = 0, j = 0; i < tblc[v]; ++i){
if(strcmp(tbl[v][i].s, t) == 0){
tbl[v][i].count++;
break;
}
if(tbl[v][i].count < tbl[v][j].count){
j = i;
}
}
if(i == tblc[v]){
if(i < 99){
tblc[v]++;
tbl[v][i] = t;
}else{
tbl[v][j] = t;
}
}
}
for (i = 0; i < hashm; ++i){
for (j = 0; j < tblc[i]; ++j){
ans.push_back(great_node_t(tbl[i][j].s, tbl[i][j].count));
}
}
sort(ans.begin(), ans.end());
for(int i = 0; i < 100 && i < (int)ans.size(); ++i){
printf("(%d) %s\n", ans[i].count, ans[i].s);
}
return 0;
}
//数据生成代码
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main(){
int i, j;
srand(time(NULL));
const int maxline = 1000000;
freopen("a.in", "w", stdout);
for (i = 0; i < maxline; ++i){
int t = rand() % 15 + 1;
for (j = 0; j < t; ++j){
printf("%c", rand() % 26 + 'a');
}
printf("\n");
}
return 0;
}
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main(){
int i, j;
srand(time(NULL));
const int maxline = 1000000;
freopen("a.in", "w", stdout);
for (i = 0; i < maxline; ++i){
int t = rand() % 15 + 1;
for (j = 0; j < t; ++j){
printf("%c", rand() % 26 + 'a');
}
printf("\n");
}
return 0;
}
欢迎扫码关注:
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
因为看你的算法框架描述还不太理解,呵呵
hash()函数里面的
t = (*p++) + (t << 6) + (t << 16) - t;//这句是什么意思呢,为什么选择6和16呢,只是做//哈希的一种方法么?还是特意选择的?
return ((t & 0x7fffffff) % hashm);//0x7fffffff是31位后面为1的二进制数,为什么要这样呢?是不是怕t超出了int所能表示的正数值范围,屏蔽了最高位为1,即是负数的情况?
main()里面的while循环中,j是不是表示当前tbl[v]里面query出现次数最少的那个node_t呢?这样就防止如果一个query集中出现在文件的后半部分,无法进入top100的情况呢?
我的问题好像很多很麻烦,小菜鸟飘过,希望大牛能指点指点~
具体做法就是替换出现次数最少的那个 :)
-----------------------------
你确定?
不懂。。
膜拜大牛