玩蛇网提供最新Python编程技术信息以及Python资源下载!
您现在的位置: 玩蛇网首页 > Python问题解答 > 正文内容

Python检测数据是否为空用什么方法

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

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

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

问题在:内存/效率

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

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

因为hash 40位,是16进制数的,我将字母替换为数字,然后转化为数字来存,这样应该可以省内存,效率应该会比较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++来做最好不过了,效率和内存但可以提高!

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

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

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

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

bucket = bsddb.btopen(None)

bucket = bsddb.hashopen(dbfilename)

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

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

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

data.keys()

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

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

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

可以尝试用MapReduce解决,请参考:
Implementing MapReduce with multiprocessing

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

假设长度为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万,因而推荐方法一。

玩蛇网文章,转载请注明出处和文章网址:http://www.iplaypy.com/wenda/wd19544.html

相关文章 Recommend

玩蛇网Python互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年06月01日 - 10时06分38秒 发布自玩蛇网

我要分享到:

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules