当前位置:  技术问答>linux和unix

百度面试题，望牛人解答

    来源: 互联网  发布时间：2016-10-09

    本文导语:  在一个有10个亿IP的文件中找出重复数相同次数最高的IP。不能用文件做中间存储，要考虑内存受限的情况。 我在网上搜了下，有的人说用trie树，但是它只适合重复度比较高并且种类比较少的情况，ip的情况不合适。 ...

在一个有10个亿IP的文件中找出重复数相同次数最高的IP。不能用文件做中间存储，要考虑内存受限的情况。

我在网上搜了下，有的人说用trie树，但是它只适合重复度比较高并且种类比较少的情况，ip的情况不合适。

有的人说用hash将ip分到不同的桶，然后统计桶内数据最多的桶，再来处理。其实这个方法不一定是对的，因为重复次数最多的ip并不一定落在最大的那个桶内。

有牛人帮我解答下吗？

不甚感激，我很急的。

|
我完成一个,Python实现, 两个文件,一个用于生成测试ip文件, 一个生成ip统计结果文件.
如下:
ProduceIpFile.py


#!/usr/bin/env python



import random

import sys



f = open('ip.txt', 'w')



a = 0



while True:

    f.write('%d.%d.%d.%dn' % (192, 168, random.randrange(1, 255), random.randrange(1, 255)))

    a += 1

    if a % 10000 == 0:

        print '+',

        sys.stdout.flush()

    if a > 10000000:

        break


CountIp.py


#!/usr/bin/env python

IpCount = {}

for a in open('ip.txt', 'r'):

    if a in IpCount:

        IpCount[a] += 1

    else:

        IpCount[a] = 1



b = sorted(IpCount.iteritems(), key = lambda d : d[1])



f = open('ipsort.txt', 'w')

for i in b:

    f.write('%10d, %s' % (i[1], i[0]))

f.close()


|
正常的业务产生的ip，去掉保留ip, 另外业务产生的ip都有重复性的倾向，不同的ip数少一个数量级以上已经是比较极端了．

当然当做纯粹的理论问题来说的话又是另一回事，可以这么考虑, 差不多利用归并的思想, 需要重复多读几次文件罢了．
比如
第一次读处理123.123.xxx.xxx，　取得以123.123开头的重复数最多的ip及其数量，
第二次读处理123.124.xxx.xxx,  取得以123.124开头的重复数最多的ip及数量，

以此类推，得到最多255 * 255个不同段内的最多重复数的ip数，　这样只需要比较这255 * 255个ip就可以了．




|
你没有看明白我说的吧,又或者我表达能务不够好. 你说的这个当然不行了.
拿你的例子(当然我是拿前两段来举例子),我说的是找123开头的,重复数最多的ip, 然后找124开头的重复数最多的ip, 最后只需要比较123段最多的跟124最多的就可以了.
举例子来说是
123.0.0.1
123.0.0.1
123.0.0.2
124.0.0.1
124.0.0.1
124.0.0.1
123.0.0.3
得
123.0.0.1 2次
124.0.0.1 3次
所以最多的是:
124.0.0.1 3

面试官说不要把ip看成那几段字符,说白了就是多用hash, 我的第一个解法用的python的字典, 里面的键自动hash生成的. 里面只关注不同的ip数.

后面说的解法,相当于做了两次hash, 每次16个bit, 也就是对于32位机, 内存足够用了. 第一个解法速度快, 占用内存多. 第二个解法占用内存少,速度慢. 对应实际应用, 谁都会用第一种解法. 





|
闲来无事, 把我第二种解法也实现了一下, 同样用python, 测试的时候请在Ip文件最后多加一个换行符. 懒得去处理了


import sys

import random



IpCount = {}



first_second_list = [(str(i), str(j)) for i in range(1,256) for j in range(256)]



first_second_dict = {}.fromkeys(first_second_list, None)



#first_second_dict = {('192', '168'): None,('192','167'): None, ('192', '166'): None}

for ipkey in first_second_dict:

    print 'start to count %s.%s.xxx.xxx' % (ipkey[0], ipkey[1])

    Ip1stCount = {}

    Ip2ndCount = {}

    for line in open('ip.txt', 'r'):

        linelist = line.split('.')

        if (ipkey[0] == (linelist[0])) and (ipkey[1] == (linelist[1])):

            if (linelist[2], linelist[3]) in Ip2ndCount:

                Ip2ndCount[linelist[2], linelist[3]] += 1

            else:

                Ip2ndCount[linelist[2], linelist[3]] = 1



    if len(Ip2ndCount) > 0:

        MaxItems = max(Ip2ndCount.iteritems(), key = lambda x : x[1])

        MaxNum = MaxItems[1]



        Ip2ndList = []

        for line in Ip2ndCount.iteritems():

            if line[1] == MaxNum:

                Ip2ndList.append(line[0])



        Ip1stCount[MaxNum] = Ip2ndList



        first_second_dict[ipkey] = Ip1stCount



        #print '%s.%s.xxx.xxx   %dn %s' % (ipkey[0], ipkey[1], MaxNum, first_second_dict[ipkey])

    else:

        #print '%s.%s.xxx.xxx   Null' % (ipkey[0], ipkey[1])



IpCount = max(first_second_dict.iteritems(), key = lambda x : x[1])

MaxIpCount = list(IpCount[1])[0]

for ipkey in first_second_dict:

    Count = list(first_second_dict[ipkey])[0]

    if Count == MaxIpCount:

        for ip in first_second_dict[ipkey][Count]:

            print '%s.%s.%s.%s     %d' %(ipkey[0], ipkey[1], ip[0], ip[1].strip(), Count)


|
我不知道你为什么会说我用了中间文件来存储信息.
第一个文件只是生成一个测试文件罢了.也就是生成你的保存ip信息的文件.
至于第二个文件, 完全是为了好看. 让你看一下所有ip按出现次数的排序. 你只要不写入文件,直接把最多的打印出来不就行了吗?


|
按楼上的意识就是用分段的方法了？
关注！

|
楼主喜欢抬扛啊,我一再说明第一种方法只适合正常业务产生的ip,也就是ip重复度高的情况.另外sorted也只是为了给你一个清晰的结果而已(就像是你最初说的我用了两个文件一样),你并不需要用sorted排序, 你换sorted(...)为max(...)就是找重复度最多的了.

15楼的解释不知你看明白了没有, 第二种方法只需要65535个整数, 内存需求量已经很少了.


|
20楼代码更新一下:


import sys

import random



IpCount = {}



first_second_dict = {}



#produce key

for line in open('ip.txt', 'r'):

    linelist = line.split('.')

    if (linelist[0], linelist[1]) not in first_second_dict:

        first_second_dict[linelist[0], linelist[1]] = 0



for ipkey in first_second_dict:

    print 'start to count %s.%s.xxx.xxx' % (ipkey[0], ipkey[1])

    Ip1stCount = {}

    Ip2ndCount = {}

    for line in open('ip.txt', 'r'):

        linelist = line.split('.')

        if (ipkey[0] == (linelist[0])) and (ipkey[1] == (linelist[1])):

            if (linelist[2], linelist[3]) in Ip2ndCount:

                Ip2ndCount[linelist[2], linelist[3]] += 1

            else:

                Ip2ndCount[linelist[2], linelist[3]] = 1



    if len(Ip2ndCount) > 0:

        MaxItems = max(Ip2ndCount.iteritems(), key = lambda x : x[1])

        MaxNum = MaxItems[1]



        Ip2ndList = []

        for line in Ip2ndCount.iteritems():

            if line[1] == MaxNum:

                Ip2ndList.append(line[0])



        Ip1stCount[MaxNum] = Ip2ndList



        first_second_dict[ipkey] = Ip1stCount



        print '%s.%s.xxx.xxx   %dn %s' % (ipkey[0], ipkey[1], MaxNum, first_second_dict[ipkey])

    else:

        pass

IpCount = max(first_second_dict.iteritems(), key = lambda x : x[1])

MaxIpCount = list(IpCount[1])[0]

for ipkey in first_second_dict:

    Count = list(first_second_dict[ipkey])[0]

    if Count == MaxIpCount:

        for ip in first_second_dict[ipkey][Count]:

            print '%s.%s.%s.%s     %d' %(ipkey[0], ipkey[1], ip[0], ip[1].strip(), Count)


测试文件:


192.168.1.1

192.168.1.2

192.168.1.3

192.168.1.4

192.168.1.5

192.167.2.1

192.167.2.1

192.167.2.1

192.167.2.2

192.166.2.1

192.166.2.1

192.166.2.1


测试结果:


start to count 192.168.xxx.xxx

192.168.xxx.xxx   1

 {1: [('1', '3n'), ('1', '2n'), ('1', '1n'), ('1', '5n'), ('1', '4n')]}

start to count 192.167.xxx.xxx

192.167.xxx.xxx   3

 {3: [('2', '1n')]}

start to count 192.166.xxx.xxx

192.166.xxx.xxx   3

 {3: [('2', '1n')]}

192.167.2.1     3

192.166.2.1     3


|
一个ip地址 说白了也就是个int，
那么题目是否也就转化成：求10亿个int里面出现最多的数

把这10亿个数进行hash
申请10亿个元素的数组，占用的空间是3.7G，存储每个hash后的值出现的次数，
如果嫌大，可以把10亿个数分段处理，然后归并

|
申请10亿个元素的数组? 你这就浪费了大量的内存内间.
要分配的空间应该是hash到不同的结果的个数, 也就是说如果只有100万个不同的ip, 就应该只分100万个无素的空间. 直接分10亿个元素的数据,还要hash干嘛呢.


|
每个IP就是一个32位整数而已
利用位图的思想，10亿个数占用的内存不会很大（这些位数组可以用整数数组来模拟）
算法的时间复杂度只是遍历一次数组的时间

也就是说：
1、对于存在IP数N，对应第N个二进制位置为1，若不存在置为0；
2、遍历10亿个数，对二进制位的进行递增
3、最后选出最大的IP

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。












  • 相关文章推荐
  • 各位朋友，小弟过两天要到创智去面试了，这是我头一次去参加面试，不知道要问些什么问题，请大家多提点，提点。
  • 高分求进外企面试时的英语面谈经历
  • linux内核与驱动面试
  • 面试过linux c的进来
  • 去建行面试应该注意些什么？帮帮我！
  • Unix/Linux下的开发经验,谁有这方面面试题.
  • 急!!! Java面试时的一个排列组合问题
  • 一家月薪上万的外企的面试题（Linux C工程師）
  • ### java面试问题集 ###
  • 请你展望一下软件技术未来的发展?（面试题）
  • 用UNIX/Linux开发的公司，面试都问些啥？？？？
  • 哪位大哥知道浙大兰德怎么样?面试会试些什么呀?
  • 哪位大哥知道杭州CSK公司怎么样?面试会试些什么呀? 薪水大概多少？急！！谢谢！！
  • 急:我要去面试,大家给指点一下(在线等)
  • 谁有腾讯面试题目，请提供以下，谢谢~其他的也可以，谢谢~
  • H3C面试问题
  • Linux平台下的面试~~~
  • 关于招聘面试
  • 笔试和面试时回答不出具体服务的配置怎么办？有些Linux服务都是看书才会做的。
  • 这个面试题该怎么回答啊？


    • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除！

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3