亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

Python+Redis實現(xiàn)布隆過濾器

 更新時間:2019年12月08日 14:00:01   作者:Sgoyi  
布隆過濾器(Bloom Filter)是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。這篇文章主要介紹了Python+Redis實現(xiàn)布隆過濾器,需要的朋友可以參考下

布隆過濾器是什么

  布隆過濾器(Bloom Filter)是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多,缺點是有一定的誤識別率和刪除困難。

布隆過濾器的基本思想

  通過一種叫作散列表(又叫哈希表,Hash table)的數(shù)據(jù)結(jié)構(gòu)。它可以通過一個Hash函數(shù)將一個元素映射成一個位陣列(Bit array)中的一個點。這樣一來,我們只要看看這個點是不是1就可以知道集合中有沒有它了

布隆過濾器的優(yōu)缺點

優(yōu)點:

  1.布隆過濾器的存儲空間和插入/查詢時間都是常數(shù)

  2.Hash函數(shù)相互之間沒有關系,方便由硬件并行實現(xiàn)

  3.布隆過濾器不需要存儲元素本身,在某些對保密要求非常嚴格的場合有優(yōu)勢

  4.布隆過濾器可以表示全集,其它任何數(shù)據(jù)結(jié)構(gòu)都不能

缺點:

  1.存在一定的誤算率,隨著存入的元素數(shù)量增加,誤算率隨之增加

   ?。ǔR姷难a救辦法是建立一個小的白名單,存儲那些可能被誤判的元素。但是如果元素數(shù)量太少,則使用散列表足矣)

  2.一般情況下不能從布隆過濾器中刪除元素

    首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點單憑這個過濾器是無法保證的。另外計數(shù)器回繞也會造成問題。這就導致刪除元素需要很高的成本。

正文

簡單的python實現(xiàn)

pip install mmh3

對于安裝報錯,c++編譯錯誤問題:可以安裝    Microsoft Visual C++ Build Tools()

 例子轉(zhuǎn)載(http://chabaoo.cn/article/175929.htm

from bitarray import bitarray
# 3rd party
import mmh3
class BloomFilter(set):
 def __init__(self, size, hash_count):
 super(BloomFilter, self).__init__()
 self.bit_array = bitarray(size)
 self.bit_array.setall(0)
 self.size = size
 self.hash_count = hash_count
 def __len__(self):
 return self.size
 def __iter__(self):
 return iter(self.bit_array)
 def add(self, item):
 for ii in range(self.hash_count):
  index = mmh3.hash(item, ii) % self.size
  self.bit_array[index] = 1
 return self
 def __contains__(self, item):
 out = True
 for ii in range(self.hash_count):
  index = mmh3.hash(item, ii) % self.size
  if self.bit_array[index] == 0:
  out = False
 return out
def main():
 bloom = BloomFilter(10000, 10)
 animals = ['dog', 'cat', 'giraffe', 'fly', 'mosquito', 'horse', 'eagle',
  'bird', 'bison', 'boar', 'butterfly', 'ant', 'anaconda', 'bear',
  'chicken', 'dolphin', 'donkey', 'crow', 'crocodile']
 # First insertion of animals into the bloom filter
 for animal in animals:
 bloom.add(animal)
 # Membership existence for already inserted animals
 # There should not be any false negatives
 for animal in animals:
 if animal in bloom:
  print('{} is in bloom filter as expected'.format(animal))
 else:
  print('Something is terribly went wrong for {}'.format(animal))
  print('FALSE NEGATIVE!')
 # Membership existence for not inserted animals
 # There could be false positives
 other_animals = ['badger', 'cow', 'pig', 'sheep', 'bee', 'wolf', 'fox',
   'whale', 'shark', 'fish', 'turkey', 'duck', 'dove',
   'deer', 'elephant', 'frog', 'falcon', 'goat', 'gorilla',
   'hawk' ]
 for other_animal in other_animals:
 if other_animal in bloom:
  print('{} is not in the bloom, but a false positive'.format(other_animal))
 else:
  print('{} is not in the bloom filter as expected'.format(other_animal))
if __name__ == '__main__':
 main()

運行結(jié)果

dog is in bloom filter as expected
cat is in bloom filter as expected
giraffe is in bloom filter as expected
fly is in bloom filter as expected
mosquito is in bloom filter as expected
horse is in bloom filter as expected
eagle is in bloom filter as expected
bird is in bloom filter as expected
bison is in bloom filter as expected
boar is in bloom filter as expected
butterfly is in bloom filter as expected
ant is in bloom filter as expected
anaconda is in bloom filter as expected
bear is in bloom filter as expected
chicken is in bloom filter as expected
dolphin is in bloom filter as expected
donkey is in bloom filter as expected
crow is in bloom filter as expected
crocodile is in bloom filter as expected


badger is not in the bloom filter as expected
cow is not in the bloom filter as expected
pig is not in the bloom filter as expected
sheep is not in the bloom, but a false positive
bee is not in the bloom filter as expected
wolf is not in the bloom filter as expected
fox is not in the bloom filter as expected
whale is not in the bloom filter as expected
shark is not in the bloom, but a false positive
fish is not in the bloom, but a false positive
turkey is not in the bloom filter as expected
duck is not in the bloom filter as expected
dove is not in the bloom誤報 filter as expected
deer is not in the bloom filter as expected
elephant is not in the bloom, but a false positive
frog is not in the bloom filter as expected
falcon is not in the bloom filter as expected
goat is not in the bloom filter as expected
gorilla is not in the bloom filter as expected
hawk is not in the bloom filter as expected

 從輸出結(jié)果可以發(fā)現(xiàn),存在不少誤報樣本,但是并不存在假陰性。

不同于這段布隆過濾器的實現(xiàn)代碼,其它語言的多個實現(xiàn)版本并不提供哈希函數(shù)的參數(shù)。這是因為在實際應用中誤報比例這個指標比哈希函數(shù)更重要,用戶可以根據(jù)誤報比例的需求來調(diào)整哈希函數(shù)的個數(shù)。通常來說,size和error_rate是布隆過濾器的真正誤報比例。如果你在初始化階段減小了error_rate,它們會調(diào)整哈希函數(shù)的數(shù)量。

誤報

布隆過濾器能夠拍著胸脯說某個元素“肯定不存在”,但是對于一些元素它們會說“可能存在”。針對不同的應用場景,這有可能會是一個巨大的缺陷,亦或是無關緊要的問題。如果在檢索元素是否存在時不介意引入誤報情況,那么你就應當考慮用布隆過濾器。

另外,如果隨意地減小了誤報比率,哈希函數(shù)的數(shù)量相應地就要增加,在插入和查詢時的延時也會相應地增加。本節(jié)的另一個要點是,如果哈希函數(shù)是相互獨立的,并且輸入元素在空間中均勻的分布,那么理論上真實誤報率就不會超過理論值。否則,由于哈希函數(shù)的相關性和更頻繁的哈希沖突,布隆過濾器的真實誤報比例會高于理論值。

在使用布隆過濾器時,需要考慮誤報的潛在影響。

確定性

當你使用相同大小和數(shù)量的哈希函數(shù)時,某個元素通過布隆過濾器得到的是正反饋還是負反饋的結(jié)果是確定的。對于某個元素x,如果它現(xiàn)在可能存在,那五分鐘之后、一小時之后、一天之后、甚至一周之后的狀態(tài)都是可能存在。當我得知這一特性時有一點點驚訝。因為布隆過濾器是概率性的,那其結(jié)果顯然應該存在某種隨機因素,難道不是嗎?確實不是。它的概率性體現(xiàn)在我們無法判斷究竟哪些元素的狀態(tài)是可能存在。

換句話說,過濾器一旦做出可能存在的結(jié)論后,結(jié)論不會發(fā)生變化。

python 基于redis實現(xiàn)的bloomfilter(布隆過濾器),BloomFilter_imooc

BloomFilter_imooc下載

下載地址:https://github.com/liyaopinner/BloomFilter_imooc

 py_bloomfilter.py(布隆過濾器)源碼:

import mmh3
import redis
import math
import time
class PyBloomFilter():
 #內(nèi)置100個隨機種子
 SEEDS = [543, 460, 171, 876, 796, 607, 650, 81, 837, 545, 591, 946, 846, 521, 913, 636, 878, 735, 414, 372,
  344, 324, 223, 180, 327, 891, 798, 933, 493, 293, 836, 10, 6, 544, 924, 849, 438, 41, 862, 648, 338,
  465, 562, 693, 979, 52, 763, 103, 387, 374, 349, 94, 384, 680, 574, 480, 307, 580, 71, 535, 300, 53,
  481, 519, 644, 219, 686, 236, 424, 326, 244, 212, 909, 202, 951, 56, 812, 901, 926, 250, 507, 739, 371,
  63, 584, 154, 7, 284, 617, 332, 472, 140, 605, 262, 355, 526, 647, 923, 199, 518]
 #capacity是預先估計要去重的數(shù)量
 #error_rate表示錯誤率
 #conn表示redis的連接客戶端
 #key表示在redis中的鍵的名字前綴
 def __init__(self, capacity=1000000000, error_rate=0.00000001, conn=None, key='BloomFilter'):
 self.m = math.ceil(capacity*math.log2(math.e)*math.log2(1/error_rate)) #需要的總bit位數(shù)
 self.k = math.ceil(math.log1p(2)*self.m/capacity)    #需要最少的hash次數(shù)
 self.mem = math.ceil(self.m/8/1024/1024)     #需要的多少M內(nèi)存
 self.blocknum = math.ceil(self.mem/512)     #需要多少個512M的內(nèi)存塊,value的第一個字符必須是ascii碼,所有最多有256個內(nèi)存塊
 self.seeds = self.SEEDS[0:self.k]
 self.key = key
 self.N = 2**31-1
 self.redis = conn
 # print(self.mem)
 # print(self.k)
 def add(self, value):
 name = self.key + "_" + str(ord(value[0])%self.blocknum)
 hashs = self.get_hashs(value)
 for hash in hashs:
  self.redis.setbit(name, hash, 1)
 def is_exist(self, value):
 name = self.key + "_" + str(ord(value[0])%self.blocknum)
 hashs = self.get_hashs(value)
 exist = True
 for hash in hashs:
  exist = exist & self.redis.getbit(name, hash)
 return exist
 def get_hashs(self, value):
 hashs = list()
 for seed in self.seeds:
  hash = mmh3.hash(value, seed)
  if hash >= 0:
  hashs.append(hash)
  else:
  hashs.append(self.N - hash)
 return hashs
pool = redis.ConnectionPool(host='127.0.0.1', port=6379, db=0)
conn = redis.StrictRedis(connection_pool=pool)
# 使用方法
# if __name__ == "__main__":
# bf = PyBloomFilter(conn=conn)  # 利用連接池連接Redis
# bf.add('www.jobbole.com')  # 向Redis默認的通道添加一個域名
# bf.add('www.luyin.org')   # 向Redis默認的通道添加一個域名
# print(bf.is_exist('www.zhihu.com')) # 打印此域名在通道里是否存在,存在返回1,不存在返回0
# print(bf.is_exist('www.luyin.org')) # 打印此域名在通道里是否存在,存在返回1,不存在返回0

總結(jié)

以上所述是小編給大家介紹的Python+Redis實現(xiàn)布隆過濾器,希望對大家有所幫助,如果大家有任何疑問歡迎給我留言,小編會及時回復大家的!

相關文章

  • 淺析python中的del用法

    淺析python中的del用法

    python中的del用法比較特殊,新手學習往往產(chǎn)生誤解,弄清del的用法,可以幫助深入理解python的內(nèi)存方面的問題。這篇文章主要介紹了python中的del用法,需要的朋友可以參考下
    2020-09-09
  • Python繪制散點密度圖的三種方式詳解

    Python繪制散點密度圖的三種方式詳解

    散點密度圖是在散點圖的基礎上,計算了每個散點周圍分布了多少其他的點,并通過顏色表現(xiàn)出來。本文主要介紹了Python繪制散點密度圖的三種方式,需要的可以參考下
    2022-06-06
  • python用folium繪制地圖并設置彈窗效果

    python用folium繪制地圖并設置彈窗效果

    這篇文章主要介紹了python用folium繪制地圖并設置彈窗,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-09-09
  • Keras 在fit_generator訓練方式中加入圖像random_crop操作

    Keras 在fit_generator訓練方式中加入圖像random_crop操作

    這篇文章主要介紹了Keras 在fit_generator訓練方式中加入圖像random_crop操作,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-07-07
  • ptyhon實現(xiàn)sitemap生成示例

    ptyhon實現(xiàn)sitemap生成示例

    這篇文章主要介紹了ptyhon實現(xiàn)sitemap生成示例,需要的朋友可以參考下
    2014-03-03
  • Python通過kerberos安全認證操作kafka方式

    Python通過kerberos安全認證操作kafka方式

    這篇文章主要介紹了Python通過kerberos安全認證操作kafka方式,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-06-06
  • python?密碼驗證(滑塊驗證)

    python?密碼驗證(滑塊驗證)

    滑塊密碼在很多登錄界面都可以看到,本文主要介紹了python?密碼驗證(滑塊驗證),文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • Python 使用folium繪制leaflet地圖的實現(xiàn)方法

    Python 使用folium繪制leaflet地圖的實現(xiàn)方法

    今天小編就為大家分享一篇Python 使用folium繪制leaflet地圖的實現(xiàn)方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-07-07
  • python多線程同步之文件讀寫控制

    python多線程同步之文件讀寫控制

    這篇文章主要為大家詳細介紹了python多線程同步之文件讀寫控制,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-08-08
  • Python給你的頭像加上圣誕帽

    Python給你的頭像加上圣誕帽

    這篇文章主要為大家詳細介紹了Python給你的頭像加上圣誕帽 ,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-01-01

最新評論