描述:
现在的实现是一个字典类型，拥有500万条数据，KEY是40位的Hash
做的是从里面确定某个Hash是否存在，但是这样的方法内存占用太多了
准备尝试bloomfilter替换但是感觉增加数据有点麻烦，是否有其他类似的算法可以用？
==== 另一种介绍 ===
每次拿到一个HASH在列表中寻找，如果有，则停止执行，如果没有，则将该HASH添加到列表，继续重复执行。
问题在：内存/效率
解决方案1:
如果是40位16进制的hash（我猜可能是sha1），对500万数据来说有点浪费。
换句话说，与其40位16进制字符串进行索引，不如考虑怎么对500万规模字符串进行索引。
解决方案2:思路：python的对象机制，决定了python肯定不会像C那么省内存，一个str都会多占一部分内存
- 如果一定要放在内存中，考虑redis，无论算法还是内存都是一个不错的选择
- 如果可以放在磁盘上，bsddb应该是不错的选择
说到底，需要考虑的是架构，这年代算法几乎无需自己动刀了
解决方案3:用 bsddb 模块好了，虽然不是标准库，但也算常见的 python 模块，
bucket = bsddb.btopen(None)
或
bucket = bsddb.hashopen(dbfilename)
使用磁盘时存储对象也可以 pickle 下直接当 key
解决方案4:可以尝试用MapReduce解决，请参考：
Implementing MapReduce with multiprocessing
假设长度为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万，因而推荐方法一。
解决方案6:下面连接中的方法，供参考：https://github.com/qiwsir/algorithm/blob/master/same_element_in_list.md
解决方案7:果断bloom filter，实现简单，内存小，最重要的效率高
Java版
第一反应是用元组，但是不知道效率如何，你可以试试？
#!/usr/bin/env python3
data = {"a":1, "b":2, "c":3, "d":4, "a":5, "c":6}
data.keys()
t应该就是一个不重复的hash key元组吧。
如果用bloomfilter会引入一定的错误率, 看你的项目是否可以接收, 如果可以自然这个是最优选择.
不行就弄个trie树吧, 推荐marisa比较省空间.
解决方案10:因为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++来做最好不过了，效率和内存但可以提高！