算法 - Python检测是否已有数据

Question

现在的实现是一个字典类型，拥有500万条数据，KEY是40位的Hash
做的是从里面确定某个Hash是否存在，但是这样的方法内存占用太多了

准备尝试bloomfilter替换但是感觉增加数据有点麻烦，是否有其他类似的算法可以用？

==== 另一种介绍 ===
每次拿到一个HASH在列表中寻找，如果有，则停止执行，如果没有，则将该HASH添加到列表，继续重复执行。

问题在：内存/效率

Answer 1

因为hash 40位，是１６进制数的，我将字母替换为数字，然后转化为数字来存，这样应该可以省内存，效率应该会比较O(n)低。
我的代码:

#!/usr/bin/env python
#-*- coding:utf-8 -*-

SHIFT = 5  # 如果计算机为32位,SHIFT为5;如果计算机为64位,SHIFT为6
MASK = 0x1F  # 如果计算机为32位,MASK为0x1F;如果计算机为64位,MASK为0x3F

class BitBucket(object):
    def __init__(self):
        self._unique_key_count = 0   # 唯一的key有多少个
        self._total_key_count = 0    # 加入的key有多少个
        self._bit = {}
        self._map = {'a': '1', 'b': '2', 'c': '3', 'd': '4', 'e': '5', 'f':'6'}

    def set(self, value):
        """return last bit"""
        value = self._translate(value)
        self._total_key_count += 1

        if not self._has_key(value):
            self._unique_key_count += 1
            key = value >> SHIFT
            self._bit[key] = self._bit.get(key, 0) | (1 << (value & MASK))
            return 0
        return 1

    def exist(self, value):
        value = self._translate(value)
        if self._has_key(value):
            return True
        return False

    def clear(self, value):
        value = self._translate(value)
        if self._has_key(value):
            self._unique_key_count -= 1
            self._total_key_count -= 1

            key = value >> SHIFT
            self._bit[key] = self._bit[key] & (~(1 << (value & MASK)))
            return True
        return False

    def get_total_count(self):
        return self._total_key_count

    def get_bit_count(self):
        return self._unique_key_count

    def _has_key(self, value):
        key = value >> SHIFT
        return self._bit.get(key, 0) & (1 << (value & MASK))

    def _translate(self, value):
        value = value.lower()
        return long(''.join([self._map.get(c, c) for c in value]))

if __name__ == '__main__':
    bitBucket = BitBucket()
    bitBucket.set("a"*40)
    print bitBucket.exist("a" * 40)
    print bitBucket.exist("b" * 40)

    bitBucket.clear("a" * 40)

    import hashlib

    for i in range(1, 27):
        a = chr(i)
        sha1 = hashlib.sha1()
        sha1.update(a)
        bitBucket.set(sha1.hexdigest())

    print bitBucket.get_total_count() 
    print bitBucket.get_bit_count()

    count = 0
    for i in range(1, 30):
        a = chr(i)
        sha1 = hashlib.sha1()
        sha1.update(a)
        if bitBucket.exist(sha1.hexdigest()):
            count += 1

    assert count == bitBucket.get_bit_count()

或者可以考虑用字典树来做，用C++来做最好不过了，效率和内存但可以提高！

Answer 2

如果用bloomfilter会引入一定的错误率, 看你的项目是否可以接收, 如果可以自然这个是最优选择.

不行就弄个trie树吧, 推荐marisa比较省空间.

Answer 3

第一反应是用元组，但是不知道效率如何，你可以试试？

#!/usr/bin/env python3
data = {"a":1, "b":2, "c":3, "d":4, "a":5, "c":6}

data.keys()

t应该就是一个不重复的hash key元组吧。

Answer 4

果断bloom filter，实现简单，内存小，最重要的效率高
Java版

Answer 5

下面连接中的方法，供参考：https://github.com/qiwsir/algorithm/blob/master/same_element_in_list.md

Answer 6

假设长度为500万的数据为字典source_dict，需要判断的为列表hash_list，那么：
result = [item for item in hash_list if item in source_dict]

source_dict是必须先载入内存的，如果闲占用内存，可以先source_dict.keys()获取键列表，假设为source_keys，那么：
result = [item for item in hash_list if item in source_keys]。

考虑到字典的遍历的速度为O(1)，列表为O(n)，而这里的数据量又为500万，因而推荐方法一。

Answer 7

可以尝试用MapReduce解决，请参考：
Implementing MapReduce with multiprocessing

Answer 8

用 bsddb 模块好了，虽然不是标准库，但也算常见的 python 模块，

bucket = bsddb.btopen(None)

或

bucket = bsddb.hashopen(dbfilename)

使用磁盘时存储对象也可以 pickle 下直接当 key

Answer 9

思路：python的对象机制，决定了python肯定不会像C那么省内存，一个str都会多占一部分内存

• 如果一定要放在内存中，考虑redis，无论算法还是内存都是一个不错的选择
• 如果可以放在磁盘上，bsddb应该是不错的选择

说到底，需要考虑的是架构，这年代算法几乎无需自己动刀了

Answer 10

如果是40位16进制的hash（我猜可能是sha1），对500万数据来说有点浪费。

换句话说，与其40位16进制字符串进行索引，不如考虑怎么对500万规模字符串进行索引。