就是 现在有一个log 里面全都是访问者的ip(数据很大很大) 一行一个ip
比如
123.22.22.187
123.22.22.182
123.22.21.187
123.22.42.187
123.23.22.187
123.22.22.182
121.22.22.182
....
怎么查出来访问次数最多的10个IP?
方式:
第一步:
如下读取:
声明一个变量 dictionary <string ,long> record
123.22.22.187
123.22.22.182
123.22.21.187
123.22.42.187
123.23.22.187
123.22.22.182
121.22.22.182
先与蓝色部分为key ,key 出现的次数为value 存在 record中。
这样 ,record的最大个数是255个,不算多,更说不上要多少内存。
再来一次大扫除,
使record 剩下 最多的 10 个元素
以这10 个元素为条件,再扫描一次表,把符合条件的数据写到另一个[文件A]中,
第二步:
扫描 [文件A] 以下面数据蓝色部分为key ,以出现次数为value 写到 变量 dictionary <string ,long> record 中
123.22.22.187
123.22.22.182
123.22.21.187
123.22.42.187
123.23.22.187
123.22.22.182
121.22.22.182
。。。
第三步:
。。。
第四步:
。。。
就这样,
用4 步相同的方法,提出最多的数据:10条,
问题,上面这种方式感觉不行啊,是我没理解吗??
比如说:
123,125,196,158,假设这个ip地址出现的次数最多,那么如下,
121,123
121,14
121,56
123,125,196,158,
123,125,196,158,
如果分段比较次数,那么123,125,196,158, 这个ip在第一步就被淘汰了?
正確答案是這個:sort|uniq -c
a.b.c.d
先處理a。
所有檔案分為多次(例如255次)的讀取。
記錄接著分別存入255個文件中,分別對應 a (例如1.b.c.d ; 2.b.c.d;)
這樣可以得到最大的十個。
接下來處理b。
。 。 。
最後得到答案。
這類問題可以使用最大-最小堆。
基本思路
对所有的ip进行分组,统计出现次数,ip做key,出现次数做val,保存在关联数组中
数组按照键值(出现次数)降序排序,取出前 10 条记录
雖然不是
java语言描述的
,但javascript描述
應該也看得懂吧,反正測試過能夠實現你的效果:以下是完整實例程式碼:
map-reduce或sort | uniq -c
明顯是用hadoop(map-reduce)吧 ?
先排序吧,排序之後就好處理了。
這個問題應該需要拆成兩部分理解,
1、文件很大讀取一次讀取效率低
2、找出出現次數最多的前10條記錄
問題1:對於大文件讀取可以使用java AIO實作方式非同步讀取檔案
問題2:需要擴充LindedList,每次追加記錄時先取是否存在記錄,有的話就把記錄位置往前推(這比較類似java memcached 快取演算法)
這類問題都有一個相同的思想,「分而治之」。
每個ip相當於一個32位元整數數字,遍歷所有日誌裡的ip,按值的範圍分成n個檔案保存起來(確保每個檔案夠小),這樣的話相同的ip肯定會被分到同一個文件中;然後逐一處理這n個文件,統計每個文件裡出現次數前10的ip;最後從這10*n個ip中得前10。
使用正規判斷IP開頭的第一個數字:
行頭數字出現次數最多即最頻繁IP