提取出某日访问百度次数最多的那个IP

标签: 访问 百度 次数 | 发表时间:2012-09-07 23:24 | 作者:zz198808
出处:http://blog.csdn.net

问题描述:海量日志数据,提取出某日访问百度次数最多的那个IP。

方法: 计数法

    假设一天之内某个IP访问百度的次数不超过40亿次,则访问次数可以用unsigned表示.用数组统计出每个IP地址出现的次数,  即可得到访问次数最大的IP地址.

    IP地址是32位的二进制数,所以共有N=2^32=4G个不同的IP地址, 创建一个unsigned count[N];的数组,即可统计出每个IP的访问次数,而sizeof(count) == 4G*4=16G, 远远超过了32位计算机所支持的内存大小,因此不能直接创建这个数组.下面采用划分法解决这个问题.

    假设允许使用的内存是512M,  512M/4=128M 即512M内存可以统计128M个不同的IP地址的访问次数.而N/128M =4G/128M = 32 ,所以只要把IP地址划分成32个不同的区间,分别统计出每个区间中访问次数最大的IP, 然后就可以计算出所有IP地址中访问次数最大的IP了.

    因为2^5=32, 所以可以把IP地址的最高5位作为区间编号, 剩下的27为作为区间内的值,建立32个临时文件,代表32个区间,把相同区间的IP地址保存到同一的临时文件中.

例如:

ip1=0x1f4e2342

ip1的高5位是id1  =  ip1 >>27 = 0x11 = 3

ip1的其余27位是value1  =  ip1 &0x07ffffff = 0x074e2342

所以把 value1 保存在tmp3文件中.

由id1和value1可以还原成ip1, 即 ip1 =(id1<<27)|value1

    按照上面的方法可以得到32个临时文件,每个临时文件中的IP地址的取值范围属于[0-128M),因此可以统计出每个IP地址的访问次数.从而找到访问次数最大的IP地址

程序源码:

test.cpp是c++源码.

  1. #include <fstream>   
  2. #include <iostream>   
  3. #include <ctime>   
  4.   
  5. using namespace std;  
  6. #define N 32           //临时文件数   
  7.   
  8. #define ID(x)  (x>>27)                 //x对应的文件编号   
  9. #define VALUE(x) (x&0x07ffffff)        //x在文件中保存的值   
  10. #define MAKE_IP(x,y)  ((x<<27)|y)      //由文件编号和值得到IP地址.   
  11.   
  12. #define MEM_SIZE  128*1024*1024       //需分配内存的大小为 MEM_SIZE*sizeof(unsigned)      
  13.   
  14. char* data_path="D:/test/ip.dat";        //ip数据   
  15.   
  16.  //产生n个随机IP地址   
  17. void make_data(const int& n)         
  18. {  
  19.     ofstream out(data_path,ios::out|ios::binary);  
  20.     srand((unsigned)(time(NULL)));  
  21.     if (out)  
  22.     {  
  23.         for (int i=0; i<n; ++i)  
  24.         {  
  25.             unsigned val=unsigned(rand());           
  26.             val = (val<<24)|val;              //产生unsigned类型的随机数   
  27.   
  28.             out.write((char *)&val,sizeof (unsigned));  
  29.         }  
  30.     }  
  31. }  
  32.   
  33. //找到访问次数最大的ip地址   
  34. int main()  
  35. {  
  36.     //make_data(100);     //    
  37.     make_data(100000000);       //产生测试用的IP数据   
  38.     fstream arr[N];  
  39.       
  40.     for (int i=0; i<N; ++i)                 //创建N个临时文件   
  41.     {  
  42.         char tmp_path[128];     //临时文件路径   
  43.         sprintf(tmp_path,"D:/test/tmp%d.dat",i);  
  44.         arr[i].open(tmp_path, ios::trunc|ios::in|ios::out|ios::binary);  //打开第i个文件   
  45.   
  46.         if( !arr[i])  
  47.         {  
  48.             cout<<"open file"<<i<<"error"<<endl;  
  49.         }  
  50.     }  
  51.   
  52.     ifstream infile(data_path,ios::in|ios::binary);   //读入测试用的IP数据   
  53.     unsigned data;  
  54.   
  55.     while(infile.read((char*)(&data), sizeof(data)))  
  56.     {  
  57.         unsigned val=VALUE(data);  
  58.         int key=ID(data);  
  59.         arr[ID(data)].write((char*)(&val), sizeof(val));           //保存到临时文件件中   
  60.     }  
  61.   
  62.     for(unsigned i=0; i<N; ++i)  
  63.     {  
  64.         arr[i].seekg(0);  
  65.     }  
  66.     unsigned max_ip = 0;    //出现次数最多的ip地址   
  67.     unsigned max_times = 0;     //最大只出现的次数   
  68.   
  69.     //分配512M内存,用于统计每个数出现的次数   
  70.     unsigned *count = new unsigned[MEM_SIZE];    
  71.   
  72.     for (unsigned i=0; i<N; ++i)  
  73.     {  
  74.         memset(count, 0, sizeof(unsigned)*MEM_SIZE);  
  75.   
  76.         //统计每个临时文件件中不同数字出现的次数   
  77.         unsigned data;  
  78.         while(arr[i].read((char*)(&data), sizeof(unsigned)))       
  79.         {  
  80.             ++count[data];  
  81.         }  
  82.           
  83.         //找出出现次数最多的IP地址   
  84.         for(unsigned j=0; j<MEM_SIZE; ++j)                             
  85.         {  
  86.             if(max_times<count[j])             
  87.             {  
  88.                 max_times = count[j];  
  89.                 max_ip = MAKE_IP(i,j);        // 恢复成原ip地址.   
  90.             }  
  91.         }  
  92.     }  
  93.     delete[] count;  
  94.     unsigned char *result=(unsigned char *)(&max_ip);  
  95.     printf("出现次数最多的IP为:%d.%d.%d.%d,共出现%d次",   
  96.         result[0], result[1], result[2], result[3], max_times);  
  97. }  
#include <fstream>
#include <iostream>
#include <ctime>

using namespace std;
#define N 32           //临时文件数

#define ID(x)  (x>>27)                 //x对应的文件编号
#define VALUE(x) (x&0x07ffffff)        //x在文件中保存的值
#define MAKE_IP(x,y)  ((x<<27)|y)      //由文件编号和值得到IP地址.

#define MEM_SIZE  128*1024*1024       //需分配内存的大小为 MEM_SIZE*sizeof(unsigned)   

char* data_path="D:/test/ip.dat";        //ip数据

 //产生n个随机IP地址
void make_data(const int& n)       
{
	ofstream out(data_path,ios::out|ios::binary);
	srand((unsigned)(time(NULL)));
	if (out)
	{
		for (int i=0; i<n; ++i)
		{
			unsigned val=unsigned(rand());         
			val = (val<<24)|val;				//产生unsigned类型的随机数

			out.write((char *)&val,sizeof (unsigned));
		}
	}
}

//找到访问次数最大的ip地址
int main()
{
	//make_data(100);     // 
	make_data(100000000);       //产生测试用的IP数据
	fstream arr[N];
	
	for (int i=0; i<N; ++i)                 //创建N个临时文件
	{
		char tmp_path[128];     //临时文件路径
		sprintf(tmp_path,"D:/test/tmp%d.dat",i);
		arr[i].open(tmp_path, ios::trunc|ios::in|ios::out|ios::binary);  //打开第i个文件

		if( !arr[i])
		{
			cout<<"open file"<<i<<"error"<<endl;
		}
	}

	ifstream infile(data_path,ios::in|ios::binary);   //读入测试用的IP数据
	unsigned data;

	while(infile.read((char*)(&data), sizeof(data)))
	{
		unsigned val=VALUE(data);
		int key=ID(data);
		arr[ID(data)].write((char*)(&val), sizeof(val));           //保存到临时文件件中
	}

	for(unsigned i=0; i<N; ++i)
	{
		arr[i].seekg(0);
	}
	unsigned max_ip = 0;    //出现次数最多的ip地址
	unsigned max_times = 0;     //最大只出现的次数

	//分配512M内存,用于统计每个数出现的次数
	unsigned *count = new unsigned[MEM_SIZE];  

	for (unsigned i=0; i<N; ++i)
	{
		memset(count, 0, sizeof(unsigned)*MEM_SIZE);

		//统计每个临时文件件中不同数字出现的次数
		unsigned data;
		while(arr[i].read((char*)(&data), sizeof(unsigned)))     
		{
			++count[data];
		}
		
		//找出出现次数最多的IP地址
		for(unsigned j=0; j<MEM_SIZE; ++j)                           
		{
			if(max_times<count[j])           
			{
				max_times = count[j];
				max_ip = MAKE_IP(i,j);        // 恢复成原ip地址.
			}
		}
	}
	delete[] count;
	unsigned char *result=(unsigned char *)(&max_ip);
	printf("出现次数最多的IP为:%d.%d.%d.%d,共出现%d次", 
		result[0], result[1], result[2], result[3], max_times);
}

原博客是 http://blog.csdn.net/v_july_v/article/details/6712171

执行结果.

作者:zz198808 发表于2012-9-7 23:24:04 原文链接
阅读:0 评论:0 查看评论

相关 [访问 百度 次数] 推荐:

提取出某日访问百度次数最多的那个IP

- - CSDN博客推荐文章
问题描述:海量日志数据,提取出某日访问百度次数最多的那个IP.     假设一天之内某个IP访问百度的次数不超过40亿次,则访问次数可以用unsigned表示.用数组统计出每个IP地址出现的次数,  即可得到访问次数最大的IP地址..     IP地址是32位的二进制数,所以共有N=2^32=4G个不同的IP地址, 创建一个unsigned count[N];的数组,即可统计出每个IP的访问次数,而sizeof(count) == 4G*4=16G, 远远超过了32位计算机所支持的内存大小,因此不能直接创建这个数组.下面采用划分法解决这个问题..

深入理解 Google Analytics 中的“访问次数”

- - 搜索引擎周边
访问次数是 GA 中最基本的概念之一,用一句话概括就是:您网站的所有访问者发起的具体会话次数. 在老版本的 GA 中,如果某次访问停留时间超过30分钟且没有活动,再次活动时会被算作一个新的访次;如果用户关闭浏览器,再次访问时,算作新的访次;如果某次会话跨度了一天,算两个访次. 在2011年的时候,GA 更新了访问次数的定义,具体见 这里,唯一的变化就是,用户关闭浏览器窗口,在半小时之内再次打开您的网站,那么仍然算上次的访次,这也许和很多浏览器的启动自动恢复标签页有关.

从1亿个ip中找出访问次数最多的IP

- - CSDN博客互联网推荐文章
看了 教你如何迅速秒杀掉:99%的海量数据处理面试题一文,的确是挺有收获的,特别是对这种海量数据的处理,的确是有了一个挺清晰的思路,特别感谢原文博主July. 处理海量数据问题存在的原因就在于1)数据量太大,无法在短时间内解决;2)内存不够,没办法装下那么多的数据. 而对应的办法其实也就是分成1)针对时间,合适的算法+合适的数据结构来提高处理效率;2)针对空间,就是分而治之,将大数据量拆分成多个比较小的数据片,然后对其各个数据片进行处理,最后再处理各个数据片的结果.

nginx限制某个IP同一时间段的访问次数

- - 企业架构 - ITeye博客
如何设置能限制某个IP某一时间段的访问次数是一个让人头疼的问题,特别面对恶意的ddos攻击的时候. 其中CC攻击(Challenge Collapsar)是DDOS(分布式拒绝服务)的一种,也是一种常见的网站攻击方法,攻击者通过代理服务器或者肉鸡向向受害主机不停地发大量数据包,造成对方服务器资源耗尽,一直到宕机崩溃.

hbase client访问的超时时间、重试次数、重试间隔时间的配置

- - 数据库 - ITeye博客
   超时时间、重试次数、重试时间间隔的配置也比较重要,因为默认的配置的值都较大,如果出现hbase集群或者RegionServer以及ZK关掉,则对应用程序是灾难性的,超时和重新等会迅速占满web容器的链接,导致web容器停止服务,关于socket的超时时间,有两种:1:建立连接的超时时间;2:读数据的超时时间.

百度急了

- - 创业家杂志社
来源: 21世纪经济报道 作者:汤浔芳. 2013年1月,百度CEO李彦宏在百度2012年表现中“公司系数”一栏的打分是0. 在不少员工看来,这是Robin(李彦宏的英文名)对百度在“移动互联网”上的表现不满意. 这个史无前例的差评让不少员工开始在网上吐槽年终奖会不会大幅缩水,因为公司系数占年终奖的30%.

该死的百度

- 菡萏 - Pure Pleasure - Reborn
之前,百度把收费的医药、医院广告链接掺杂在搜索结果里,被央视点名批评(其实谁都知道它们都心怀不轨),但百度是不怕的,受伤的是民众、草根,发不出声音——于是此事不了了之(后来的结果是李彦宏在央视打广告、上春晚). 再后来,百度封杀淘宝联盟的40万站长,很多小站被迫停止运营;站长们跑到百度办公楼前抗议,但百度是不怕的,因为这些站长还是发不出声音(网站都开不下去了,只能亲自示威)——于是此事再次不了了之⋯⋯可这次,百度惹到作者头上了,别管这些作者质量是否良莠不齐(韩寒、郭敬明、贾平凹、王三表等等一并出现在声讨百度的队伍中),但他们是天然的“自媒体”,百度开始以为没事儿,两三天下来才发现捅了马蜂窝⋯⋯.

百度献礼门

- Shawn - wsmlby的Plog
来源: 温广阳KinKer的日志. 如果你以为我单指在百度里面输入“建党”就会看见的红旗赞歌的话,你就大错特错了. 本来这种媚上的传统也算是几千年文化的一部分了,无需大惊小怪,发这样的状态,估计只会被认为是抓住一切机会讥讽社会主义伟大建设的行为,所以我看见梅姐也同瞎就很开心地继续复习了,但是师傅说他献了整整10束花才发现没有献花上限,令我心里陡然一动.

Google和SugarSync访问异常

- Freeman - 月光博客
  今天下午,Https的Google出现了短时间的访问异常,国内各地网友发现其访问出现不稳定状态,有时可以访问,有时无法访问.   这对中国用户最直接的影响是,很多用户无法访问Https版Google Reader,还有一些用户无法登录Gmail邮箱.   今天的另一个坏消息是,知名美国云存储服务SugarSync网站的域名被关键字屏蔽,目前已经无法从中国访问,虽然SugarSync的上传速度比起Dropbox还有差距,但至少美国的服务用起来放心一些,早先云存储服务Dropbox被屏蔽时不少网友转到了SugarSync这个服务,不过值得庆幸的是,该服务的电脑客户端和iPhone手机端都可以正常使用,上传和下载文件都没有问题.

昨天访问了李娜

- sg - 咆哮女郎柏邦妮
昨天访问李娜,当然也见到了姜山. 体育界人士,原本不在我专业范围内,但是有一种朴素的好奇. 当世的一流高手,是怎么样的状态. 拄着网球拍,坐在镜头前,如沉渊一样深静. 环抱着网球拍,像剑客抱着自己的剑,有一种不怒而威的自信. 在镜头前走动,跑动,是不擅拍照人的青涩,. 但是表演挥拍动作时,几万个小时的积累就化作了自然,.