search

Home  >  Q&A  >  body text

java - 面试问题:查找出现次数最多的ip

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

巴扎黑巴扎黑2888 days ago747

reply all(9)I'll reply

  • 伊谢尔伦

    伊谢尔伦2017-04-18 10:33:54

    The correct answer is this: sort|uniq -c

    reply
    0
  • 大家讲道理

    大家讲道理2017-04-18 10:33:54

    a.b.c.d

    Deal with a first.

    All files are divided into multiple reads (such as 255 times).

    The records are then stored in 255 files, corresponding to a (such as 1.b.c.d; 2.b.c.d;)

    This way you can get the largest ten.

    Next, deal with b.

    . . .

    Finally got the answer.

    reply
    0
  • 伊谢尔伦

    伊谢尔伦2017-04-18 10:33:54

    This kind of problem can use max-min heap.

    reply
    0
  • 巴扎黑

    巴扎黑2017-04-18 10:33:54

    Basic idea

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

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

    Although it’s not java语言描述的,但javascript描述, I should be able to understand it. Anyway, I have tested it and it can achieve your effect:

    The following is the complete example code:

        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;
        }

    reply
    0
  • 黄舟

    黄舟2017-04-18 10:33:54

    map-reduce or sort | uniq -c
    Obviously use hadoop (map-reduce)?

    reply
    0
  • PHPz

    PHPz2017-04-18 10:33:54

    Sort it first, it will be easier to deal with after sorting.

    reply
    0
  • PHP中文网

    PHP中文网2017-04-18 10:33:54

    This question should be broken into two parts to understand,
    1. Reading a large file at once is inefficient
    2. Find the top 10 records with the most occurrences
    Question 1: For reading large files, you can use java AIO Implementation method reads files asynchronously
    Question 2: LindedList needs to be extended. Each time a record is appended, first check whether a record exists, and if so, push the record position forward (this is more similar to the java memcached caching algorithm)

    reply
    0
  • 巴扎黑

    巴扎黑2017-04-18 10:33:54

    These types of problems all have the same idea, "divide and conquer".
    Each IP is equivalent to a 32-bit integer number. Traverse all the IPs in the log, divide them into n files according to the value range and save them (make sure each file is small enough). In this case, the same IP will definitely be assigned to the same file. In a file; then process these n files one by one, count the top 10 IPs that appear in each file; finally get the top 10 from these 10*n IPs.

    reply
    0
  • ringa_lee

    ringa_lee2017-04-18 10:33:54

    Use regular expressions to determine the first number at the beginning of the IP:

    1.2.3\n
    4.5.6\n
    1.2.3\n
    

    The number at the beginning of the line that appears the most is the most frequent IP

    reply
    0
  • Cancelreply