large data process

6月 8 2015

astounding 令人震惊的
budget 预算
fiscal 财政的

python 一句话搞定 reversestring

著名面试题，单词之间顺序reverse，本身不变
return ‘ ‘.join([word[::-1] for word in s[::-1].split()])

python 的代码真是写的可以短到不能再短了

支持多个变量一行同时赋值
i, j=i+1, j+1
虽然没有引用传递，但是参数返回个数可变，多个返回是非常方便的
h, isBBT=self.B(root)

附上判断一颗树是否BBT的python代码

真是pythonic啊！

class Solution:
    # @param {TreeNode} root
    # @return {boolean}
    def isBalanced(self, root):
        h, isBBT=self.B(root)
        return isBBT

    def B(self, root):
        if root is None:
            return 0, True
        lh, Left=self.B(root.left)
        rh, Right=self.B(root.right)
        h=max(lh, rh)+1
        return h, Left and Right and abs(rh-lh)<=1

海量数据处理往往有几种思路。

多半是数据量太大，内存放不下，优化空间

一种是bitmap，来优化，判重是可以用BloomFilter，该方法非常牛，
在BigTable，QQmail spamemail 判重等领域都广泛运用，因为全世界的垃圾邮件域名在一直增长。

题目是给定10^7个-10^7~10^7范围的数，文件里面，给定1MB内存，要求进行排序，存回文件。

题目说的是7位整数，但如果非负的话，范围应该是10^8了。

用bitmap的话，10^7/8=1.25MB，因此解决方案是把整数划分为两段，然后每一段分别做一次基于bitmap的排序，然后两个文件分别归并依次就好了。

编程珠玑第二炮，40亿个32位整数找一个不在里面的数。

1）内存1G
2) 内存10MB，有一些外存

第一个，bitmap空间, bitmap切记与数据范围有关，2^32/8/1024/1024/1024=0.5GB, 直接bitmap建立，然后扫一遍第一个为0的就是了。

第二个分块，1000大小例如，0-999在block0，1000-1999在block1，
对于那些块的计数器<1000的一定有不存在的数，(>=1000的只是可能有，但是<1000的是一定有),然后读取所有数，在这块里面的第一次0的就是目标值

今天看到知乎黑July的，我是非常反对的。July大神的能力已经毋庸置疑，最佩服的也正是本人缺乏的，一直想追寻的执行力，专注力，效率，我也一直想学习的。

于是我打算再写一遍KMP

void GetNext(string pat)
{
    int n=pat.size();
    Next[0]=-1;
    for(int i=0;i<=n-2;i++)
    {
        int k=Next[i];
        while(k!=-1 && pat[k]!=pat[i])
            k=Next[k];
        Next[i+1]=k+1;
    }
}

int KMP(string str, string pat)
{
    GetNext(pat);
    int m=str.size(), n=pat.size();
    int i=0, j=0;
    while(i<m && j<n)
    {
        if(j==-1 || str[i]==pat[j])
            i++, j++;
        else
            j=Next[j];
        if(j==n)
            return i-j;
    }
    return -1;
}

Python版的，主要是想试试Python在字符串处理的优势

__author__ = 'richard'


def GetNext(pat, Next):
    n=len(pat)
    Next[0]=-1
    for i in range(n-1):
        k=Next[i]
        while k!=-1 and pat[k]!=pat[i]:
            k=Next[k]
        Next[i+1]=k+1

def KMP(str, pat):
    Next=[0]*len(pat)
    GetNext(pat, Next)
    m, n, i, j=len(str), len(pat), 0, 0
    while i<m and j<n:
        if j==-1 or str[i]==pat[j]:
            i, j=i+1, j+1
        else:
            j=Next[j]
        if j==n:
            return i-j
    return -1

str='zhangruichang'
pat='chang'
print KMP(str,pat)

bloomfilter是压缩空间的优良去重数据结构，但是有一定的错误率，也就是
会把可能不属于集合里的认为是集合里的。

因此这个作为垃圾邮件的判重器会有比较大的代价，因为把一个好邮件判为
垃圾邮件代价是非常大的，解决方法好像是建立一个白名单，但是具体怎么弄的还不是很清楚

Posted by richard爱闹 - 6月 8 2015
如需转载，请注明：本文来自 Richard

留言