java - 面试问题:查找出现次数最多的ip
巴扎黑
巴扎黑 2017-04-18 10:31:54
0
9
745

就是 现在有一个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在第一步就被淘汰了?

巴扎黑
巴扎黑

全部回覆(9)
伊谢尔伦

正確答案是這個:sort|uniq -c

大家讲道理

a.b.c.d

先處理a。

所有檔案分為多次(例如255次)的讀取。

記錄接著分別存入255個文件中,分別對應 a (例如1.b.c.d ; 2.b.c.d;)

這樣可以得到最大的十個。

接下來處理b。

。 。 。

最後得到答案。

伊谢尔伦

這類問題可以使用最大-最小堆。

巴扎黑

基本思路

  1. 对所有的ip进行分组,统计出现次数,ip做key,出现次数做val,保存在关联数组中

  2. 数组按照键值(出现次数)降序排序,取出前 10 条记录

雖然不是java语言描述的,但javascript描述應該也看得懂吧,反正測試過能夠實現你的效果:

以下是完整實例程式碼:

    var data = [123.22.22.187 , 123.22.22.187 ....];  // 等价于日志中每行ip
    var data = getCount(data); // 对所有的ip进行分组,统计出现次数
                               // ip做key,出现次数做val,保存在关联数组中
    var rel  = getRecord(data , 10 , 'desc'); // 这个就是你想的结果了
    
    /*
     * ip 分组并统计次数的具体实现
     * @param Array data  日志文件中存放的那些所有ip组成的数组
     * @return Object
     */
    function getCount(data){
        var rel= {}; // 根据ip进行分组后的结果,由于js没有关联数组
                      // 所以用对象替换
        var i;
        var count;
        var n;
        var cur;
        var curC;
        // 判断是否已经统计过了的
        var checkIsCount = function(ip){
            var k;
            
            for (k in rel)
                {
                    if (k === ip) {
                        return true;
                    }
                }
            
            return false;
        };
        
        // 每次固定一个 ip
        // 先判断当前 ip 在 rel 中是否已经存在(排除已被统计的ip,避免重复统计)
        // 不存在的时候,开始统计其出现次数
        for (i = 0; i < data.length; ++i)
            {
                cur = data[i];
                count = 1;
                
                if (!checkIsCount(cur)) {
                    for (n = i + 1; n < data.length; ++n)
                        {
                            curC = data[n];
    
                            if (cur === curC) {
                                count++;
                            }    
                        }
    
                     rel[cur] = count;      
                }
            }
            
       // 保存了所有不同ip,及其出现次数的对象
       console.log('ip进行了分组并统计后的结果:' , rel);
       return rel;
    }
    
    /*
     * 数组按照键值(出现次数)降序排序,取出前 len 条记录
     * @param Object data 分组并统计出现次数后的对象
     * @param Number len  取出多少条
     * @param String sortType 升序还是降序(asc | desc)
     * @return Array
     */
    function getRecord(data , len , sortType){
        var rel = {};
        var result = [];
        var k;
        var k1;
        var curKey;
        var count = 0;
        // 检查 ip 是否已被获取
        var checkSorted = function(ip){
            var k;
            
            for (k in rel)
                {
                    if (k === ip) {
                        return true;
                    }
                }
                
            return false;
        };
    
        // 排序算法:选择排序
        for (k in data)
            {
                
               if (count >= len) {
                   break;
               }
               
               curKey = k;
               
               if (!checkSorted(k)) {
                   for (k1 in data) 
                       {
                           if (!checkSorted(k1)) {
                              if (sortType === 'asc' ? data[curKey] > data[k1] : data[curKey] < data[k1]) {
                                  curKey = k1;
                              } 
                           }
                       }
                   
                   
                   // 按照键值排序后的最大值|最小值
                   rel[curKey] = data[curKey];
    
                   // 返回可视化结果
                   result.push(curKey);
                   
                   // 获取的长度增加
                   count++
               }
            }
    
        // 按照键值排序后的 len 长度的记录
        console.log('取出指定长度记录的实际结果:' , rel);
        console.log('取出指定长度记录的可视化结果:' , result);
        return result;
    }
黄舟

map-reduce或sort | uniq -c
明顯是用hadoop(map-reduce)吧 ?

PHPzhong

先排序吧,排序之後就好處理了。

Ty80

這個問題應該需要拆成兩部分理解,
1、文件很大讀取一次讀取效率低
2、找出出現次數最多的前10條記錄
問題1:對於大文件讀取可以使用java AIO實作方式非同步讀取檔案
問題2:需要擴充LindedList,每次追加記錄時先取是否存在記錄,有的話就把記錄位置往前推(這比較類似java memcached 快取演算法)

巴扎黑

這類問題都有一個相同的思想,「分而治之」。
每個ip相當於一個32位元整數數字,遍歷所有日誌裡的ip,按值的範圍分成n個檔案保存起來(確保每個檔案夠小),這樣的話相同的ip肯定會被分到同一個文件中;然後逐一處理這n個文件,統計每個文件裡出現次數前10的ip;最後從這10*n個ip中得前10。

左手右手慢动作

使用正規判斷IP開頭的第一個數字:

1.2.3\n
4.5.6\n
1.2.3\n

行頭數字出現次數最多即最頻繁IP

熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板