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

Question

就是 现在有一个log 里面全都是访问者的ip(数据很大很大) 一行一个ip比如123.22.22.187123.22.22.182123.22.21.187123.22.42.187123.23.22.187123.22.22.182121.22.22.182.... 怎么查出来访问次数最多的10个IP? ...

伊谢尔伦 · Answer

La bonne réponse est la suivante : sort|uniq -c

大家讲道理 · Answer

a.b.c.d

Traiter une première.

Tous les fichiers sont divisés en plusieurs lectures (par exemple 255 fois).

Les enregistrements sont ensuite stockés dans 255 fichiers, correspondant à un (tel que 1.b.c.d ; 2.b.c.d ;)

De cette façon, vous pouvez obtenir les dix plus grands.

Ensuite, traitez avec b.

. . .

J'ai enfin la réponse.

伊谢尔伦 · Answer

Ce type de problème peut utiliser un tas max-min.

巴扎黑 · Answer

Idée de base

对所有的ip进行分组，统计出现次数，ip做key，出现次数做val，保存在关联数组中
数组按照键值（出现次数）降序排序，取出前 10 条记录

Bien que ce ne soit pas java语言描述的, javascript描述 devrait être compréhensible Quoi qu'il en soit, je l'ai testé et il peut produire votre effet :

.

Ce qui suit est l'exemple de code complet :

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

黄舟 · Answer

map-reduce ou sort | uniq -c
Utiliser évidemment hadoop (map-reduce) ?

PHPz · Answer

Triez-le d'abord, ce sera plus facile à gérer après le tri.

PHP中文网 · Answer

Cette question doit être divisée en deux parties pour comprendre,
1 Le fichier est très volumineux et l'efficacité de lecture est faible
2 Trouvez les 10 premiers enregistrements avec le plus d'occurrences
Question 1 : Pour la lecture de fichiers volumineux, vous pouvez utiliser l'implémentation Java AIO pour lire les fichiers de manière asynchrone
Question 2 : LindedList doit être étendue chaque fois qu'un enregistrement est ajouté, vérifiez d'abord s'il existe un enregistrement et, si c'est le cas, avancez la position de l'enregistrement (. cela ressemble plus à l'algorithme de mise en cache Java Memcached)

巴扎黑 · Answer

Ces types de problèmes ont tous la même idée, « diviser pour mieux régner ».
Chaque IP équivaut à un nombre entier de 32 bits. Parcourez toutes les IP dans le journal, divisez-les en n fichiers selon la plage de valeurs et enregistrez-les (assurez-vous que chaque fichier est suffisamment petit dans ce cas). la même adresse IP sera définitivement divisée dans le même fichier ; puis traitez ces n fichiers un par un, et comptez les 10 premières adresses IP qui apparaissent dans chaque fichier, enfin, obtenez le top 10 de ces 10*n IP ;

ringa_lee · Answer

Utilisez des expressions régulières pour déterminer le premier nombre au début de l'IP :

1.2.3

4.5.6

1.2.3

L'IP la plus fréquente est le numéro en début de ligne

数据量非常大 不可能直接读进来 然后排序。。。

数据量非常大不可能直接读进来然后排序。。。