算法 - 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萬規模字串進行索引。