日志统计脚本

今天同学说让我写个脚本统计日志。日志是一些ip的捕捉记录，根据协议的类型定义了一些ID和子ID。统计的需求是统计出各个类型的客户ip和服务ip。

这些日志是自动写入的，每天会根据日期生成一个文件夹，文件夹中每个小时生成一个日志文档。脚本要做的就是便利24个文档，读取内容进行分析。

由于需要把24个文档在一起分析，所以同学一开始的思路是：

对每一个类型进行统计，每次统计都遍历所有文件

明显效率不怎么样，但是实际上也够用了因为只要在服务器上让脚本跑起来，过几分钟回去看结果就行了

但是因为脚本要给别人看==，所以不能太难看，因此要重新写一下。

开始的脚本是shell脚本，我不太熟悉，所以用python重写了

思路就是定义一堆list变量用来记录ip，每读入一个ip就在list里面查找（not in），如果找不到就插进去。

最后统计list的长度

这样只需遍历一边文件就行了，但是……………………………………


不知道为啥，貌似python写完之后比原来还慢

后来同学一句话点破，not in 查找的时候需要对字符串进行匹配，而原来的shell脚本是用sort排序之后用unique进行去重统计，难怪这么慢。

于是考虑将ip字符串转换成long型再存储在list里面，这样匹配的时候是不是能快点？

但是结果好象还是不理想。在少量数据（两个日志文件）的时候，大概能比shell（8s）脚本慢几秒种（16s，是两倍左右），但是在大数据量的情况下就不容乐观了（多出1/3左右的时间）。

大量数据的情况下会慢几分钟==

不过貌似数据量越大差距越小，足够大的话游客能超过shell，但是差距还是太差了啊.


后来在网上查找了一下，发现原来字典的查找速度更快，因为字典在查找的时候使用hash。于是尝试把所有list换成字典。

果然效果神速。在两个文件的时候，2.9秒左右。既然hash了，那么将ip转化位long型也没有意义了反而做了无用工。去掉之后大概是2.7秒。

然后调整了匹配的顺序，将数量较多的类型先匹配，这样又快了一点点。

如此做一个总结：

1.python中list进行查找和去重的时候（in 操作），使用字符串的匹配，所以速度比较慢。如果存储的是整型则会快一些（数量多的时候还是很慢）。
2.字典使用哈希查找，因此速度很快。
3.调整匹配顺序也可在一定程度上优化速度。

提取url中的主机地址和资源地址

这是网易笔试的一道题目，比如
http://www.mp3.com/test.mp3
则需要提取出主机地址：www.mp3.com
需要提取出资源地址：/test.mp3

由于没有限定语言，处理字符串当然首选python

当时给出的测试域名全部是.com，所以直接就这么写了：

f = open('url.file','r')    #打开测试文件
for l in f.readlines():
   s = l.find('://')           #查找到://作为开始
   e = l.find('com/')      #查找到.com作为结束
   host = l[s+3:e+3]    #://和com之间的是主机
   src = l[e+3:]            #.com/后面的是src
   print("host:"+host)
   print("src:"+src)
#end for

上面的做法有明显的彼端，遇到非.com域名就悲剧了

所以还是应该使用正则

代码如下：

import re
f = open('url.file','r')
rc = re.compile('://[\S]+/) #正则匹配://xxxxx.xxx.xxx/
for l in f.readlines():
sch = rc.search(l) #在url中查找匹配字符，返回一个正则的对象
s = sch.start()
e = sch.end() #返回匹配到的字符串在url中的起始和终止位置，终止位置会在‘/’后面一个字符的位置，所以下面的处理中不必进行e+1
host = l[s+3:e]
src = l[e:]
print("host:"+host)
print("src:"+src)
#endfor

读取文件奇数行

今天处理“如何读取文件偶/奇数行”这个问题的时候，本来是打算用python来解决

python本身是很简单的，偶数代码如下：

f = open('./test.file','r')

while f.readline():

print f.readline()

奇数行代码如下：

f = open('./test.file','r')

print f.readline()

while f.readline():

print f.readline()

在网上想看看别人怎么做的，结果发现大部分是shell中的实现，尤其是用sed命令实现。以前没用过这个工具，居然这么简单：

读取奇数行：

sed -n 'p;n' ./test.file

读取偶数行:

sed -n 'n;p' ./test.file

-n:quite，就是不会将读取的文件行默认显示出来

'n;p'：这是两个命令，读取一行之后，对这一行进行两个操作

n就是直接读取下一行

p就是打印该行

于是效果就是，读两行打印一行

'n;p'和'p;n'的区别就是先读还是先打印了，也就达到奇偶切换

海量数据处理总结

备战百度，在海量数据处理的主题上做一个总结。

详情来自http://www.cnblogs.com/pkuoliver/archive/2010/10/02/mass-data-topic-1.html

1.bloom filter

将数据通过hash函数映射到位数组，比如hash(str)=3则将位数组第三位置为1

对每一条数据都用k个hash函数进行映射，也就是一条数据会将位数组的最多k位的值置1

在查找数据是否存在的时候，则对其进行k次hash，如果位数组中对应的各位都被置1了，则说明该数据已经存在（明显是有一定错误率的）

bloom filter可以用来实现数据字典，进行数据的判重，或者集合求交集

同时，对其进行改进，即位数组每一位不再是0/1，而是数据出现的次数counter，那么出现数据则+1，删除数据则-1，这样可以实现删除操作。

实例：

给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。

2.hash表

hash表主要是整合了线性表”定位容易，添加删除复杂“和链表”添加删除容易定位复杂“的特点，将二者结合起来。线性表每一个元素位一个指针，指向一个链表。通过hash函数将一个数据映射到某个元素指向的链表上。如此查找是可以通过hash定位到链表，在链表中进行添加删除操作。

散列的方法有很多，不同的散列算法会导致链表的分布均衡问题。比较好的算法是非波那契算法

i ndex = (value * 理想乘数) >> 28

其中理想乘数为：

1，对于16位整数而言，这个乘数是40503

2，对于32位整数而言，这个乘数是2654435769

3，对于64位整数而言，这个乘数是11400714819323198485

适用

hash表适用于快速查找，但是需要数据可以全部放入内存。

作为扩展，可以使用d-left hashing

d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个 位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。

实例：

海量日志数据，提取出某日访问百度次数最多的那个IP。

IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

3.Bit Map

类似遇bloom filter。若value==3，则将位数组第3位置1。这样，对于一串数字，进行如此造作后，从便利该位数组，若某位为1则输出下标，这样便完成了排序。

和插入排序很类似，但是其存储空间很小，适用于大量数据的排序，查重等操作。

实例

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==12.4MBytes，这样，就用了小小的12.4M左右的内存表示了所有的8位数的电话）

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。

4.堆

二叉堆是一种二叉树，最大堆为例，没一个节点都小于它的字节点。树是完全平衡的，并且最后一层的树叶都在最左边。

堆的操作主要是添加和删除。

适用

海量数据前n大，并且n比较小，堆可以放入内存

实例

最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元 素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。

5.双层桶思想

当数据量过大的时候，进行比较，查找处理较为复杂，因此可以考虑将大量数据操作划分位对很多小部分数据的操作。直接看例子：

实例

1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。 当然这个题也可以用我们前面讲过的BitMap方法解决，正所谓条条大道通罗马~~~

2).5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几 大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

3).现在有一个0-30000的随机数生成器。请根据这个随机数生成器，设计一个抽奖范围是0-350000彩票中奖号码列表，其中要包含20000个中奖号码。

这个题刚好和上面两个思想相反，一个0到3万的随机数生成器要生成一个0到35万的随机数。那么我们完全可以将0-35万的区间分成35/3=12个区间，然后每个区间的长度都小于等于3万，这样我们就可以用题目给的随机数生成器来生成了，然后再加上该区间的基数。那么要每个区间生成多少个随机数呢？计算公式就是：区间长度*随机数密度，在本题目中就是30000*（20000/350000）。最后要注意一点，该题目是有隐含条件的：彩票，这意味着你生成的随机数里面不能有重复，这也是我为什么用双层桶划分思想的另外一个原因。

6.数据库索引

7.倒排索引

所谓倒排索引的意思，就是建立索引的时候，不是按照key-文档，value-语素这样的形式建立，而是按照key-语素，value-文档这种形式，而且在value中保存了文档编号和该文档中出现语素的次数等信息。

因此在检索的时候，不必遍历所有文档，而只需便利查找的query关键字即可。