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

就是 现在有一个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

먼저 처리하세요.

모든 파일은 다중 읽기(예: 255회)로 나누어집니다.

그런 다음 기록은 각각 a(예: 1.b.c.d; 2.b.c.d;)에 해당하는 255개 파일에 저장됩니다.

이렇게 하면 가장 큰 10개를 얻을 수 있습니다.

다음으로 b를 처리합니다.

. . .

드디어 답을 얻었습니다.

伊谢尔伦

이런 유형의 문제는 최대-최소 힙을 사용할 수 있습니다.

巴扎黑

기본 아이디어

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

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

java语言描述的은 아니지만 javascript描述는 이해할 수 있습니다. 어쨌든 테스트해 본 결과 효과를 얻을 수 있습니다.

다음은 전체 예제 코드입니다.

으아악
黄舟

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 시작 부분의 첫 번째 숫자를 결정합니다.

으아악

가장 빈번한 IP는 줄 시작 부분의 숫자입니다

최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿