中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

做自己的網(wǎng)站花多錢2345網(wǎng)址導(dǎo)航桌面版

做自己的網(wǎng)站花多錢,2345網(wǎng)址導(dǎo)航桌面版,所有網(wǎng)站的分辨率,吃雞seo是什么意思目錄 一、位圖 1、位圖的概念 2、位圖的實(shí)現(xiàn) ①、基本結(jié)構(gòu) ②、set ③、reset: ④、test ⑤、問題: ⑥、位圖優(yōu)缺點(diǎn)及應(yīng)用: ⑦、完整代碼及測試 二、布隆過濾器 1、布隆過濾器的提出 2、布隆過濾器的實(shí)現(xiàn) ①、基本結(jié)構(gòu) ②…

目錄

一、位圖

1、位圖的概念?

2、位圖的實(shí)現(xiàn)?

?①、基本結(jié)構(gòu)

②、set?

③、reset:

④、test?

⑤、問題:

⑥、位圖優(yōu)缺點(diǎn)及應(yīng)用:?

⑦、完整代碼及測試

二、布隆過濾器

1、布隆過濾器的提出

2、布隆過濾器的實(shí)現(xiàn)

①、基本結(jié)構(gòu)

②、三個(gè)Hash仿函數(shù)實(shí)現(xiàn)

③、 set

④、 test

⑤、?刪除

?⑥、完整代碼及測試

⑦、 優(yōu)缺點(diǎn)


一、位圖

1、位圖的概念?

1. 面試題
40 億個(gè)不重復(fù)的無符號整數(shù),沒排過序。給一個(gè)無符號整數(shù),如何快速判斷一個(gè)數(shù)是否在
40 億個(gè)數(shù)中?!掘v訊】
查找一個(gè)數(shù)在不在,其實(shí)就是key模型,那常見的幾種解法如下:
  • 1. 遍歷,時(shí)間復(fù)雜度O(N)
  • 2. 排序(O(NlogN)),利用二分查找: logN
  • 3. 位圖解決

前兩個(gè)方案的問題:數(shù)據(jù)量太大,放不到內(nèi)存中。

我們可以先考慮40億個(gè)不重復(fù)的無符號整數(shù)占多少空間?
10億個(gè)字節(jié)是1個(gè)G,而40億個(gè)整數(shù),一個(gè)整數(shù)4個(gè)字節(jié),即需要160億(9個(gè)0)個(gè)字節(jié),即需要16G,這些數(shù)據(jù)太占空間了,內(nèi)存根本存不下。

位圖是如何解決的呢?

所謂位圖,就是用每一bit位來存放某種狀態(tài)適用于海量數(shù)據(jù),數(shù)據(jù)無重復(fù)的場景。通常是用 來判斷某個(gè)數(shù)據(jù)存不存在的。數(shù)據(jù)是否在給定的整形數(shù)據(jù)中,結(jié)果是在或者不在,剛好是兩種狀態(tài),那么可以使用一 個(gè)二進(jìn)制比特位來代表數(shù)據(jù)是否存在的信息,如果二進(jìn)制比特位為 1 ,代表存在,為0 代表不存在。(位圖是直接定址法的一種)
而40億個(gè)數(shù)據(jù),我們起碼要開42億個(gè)空間,為什么?假如有一個(gè)數(shù)是4200000000,你要映射到哪個(gè)位置?我們開空間是要開數(shù)據(jù)的范圍,才能滿足全部映射進(jìn)去。
那我們直接開2^32個(gè)空間(這里說的每個(gè)位置就是比特位,2^32≈42億9千萬,因?yàn)槲粓D就是每個(gè)位置存的bit位),來對所有數(shù)直接定址法建立映射關(guān)系,即我們開辟42億9千萬個(gè)bit位,先把42億9千萬看成字節(jié),則其≈4G,而4G≈4000M(或者M(jìn)B),而這里是比特位,故要除以8,4000/8=500M,故位圖存儲占用500M即可,這既節(jié)省了空間,效率又很高(效率高,因?yàn)橹苯佣ㄖ贩]哈希沖突)

2、位圖的實(shí)現(xiàn)?

?①、基本結(jié)構(gòu)

位圖的初始化應(yīng)該是開多少個(gè)比特位,因?yàn)槲粓D就是利用存比特位來節(jié)省的空間,你傳的N也是比特位,其次是vector的類型是int,因?yàn)?strong>類型不支持是比特位的

class bitset
{
public:bitset(size_t N){//N代表要開多少比特位(簡稱:位)_bits.resize(N / 32 + 1, 0);_num = N;}private://int* _bits;std::vector<int> _bits;size_t _num;  //表示存了多少個(gè)比特位,映射存儲的多少個(gè)數(shù)據(jù)
};
_bits.resize(N / 32 + 1, 0);

為什么要N / 32 + 1?呢?

因?yàn)?strong>vector的resize開空間是以整形為單位的,而位圖的每個(gè)位置存的都是一個(gè)比特位,而一個(gè)整形32個(gè)比特位,N代表的是比特位的位數(shù),則N/32得到的是整形的個(gè)數(shù),但是還需+1,為什么?比如N=100,100/32=3,那意思就是開3個(gè)整形,即32*3=96個(gè)位,但是100還是沒位置放,你就開了96個(gè)位(同理97,98...都沒位置),為了避免這個(gè)問題我們會(huì)+1,即多開一個(gè)整形,那最多只會(huì)浪費(fèi)31個(gè)位


②、set?

功能:第x個(gè)位設(shè)置為1,表示這個(gè)位存在

void set(size_t x)
{//把第x位設(shè)置為1,表示此位置存在size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位_bits[index] |= (1 << pos); //對于這個(gè)整數(shù)第pos的位置或1//1<<pos表示先把1移動(dòng)到和pos相同位置的比特位上,因?yàn)閜os=幾,1就會(huì)左移幾位//|=表示是或,即除了pos位置的位要變成1,其余位置都不受影響
}

?其實(shí)就是考察怎么把一個(gè)整數(shù)的某個(gè)位變成1,還不影響其他的31位

小端機(jī)的左移是向左?,?大端機(jī)的左移是向右

這是c語言設(shè)計(jì)的bug,歷史遺留問題,易讓人誤導(dǎo),計(jì)算機(jī)技術(shù)發(fā)展百花齊放,再融合統(tǒng)一


③、reset:

功能:第x個(gè)位置成0,表示這個(gè)位不存在

void reset(size_t x)
{//把第x位設(shè)置為0,表示此位置不存在size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位_bits[index] &= ~(1 << pos); //對于這個(gè)整數(shù)第pos的位置與0
}


④、test?

功能:判斷第x位在不在(即判斷x所映射的位是否為1)

//判斷x在不在(也就是說x映射的位是否為1)
bool test(size_t x)
{size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位return _bits[index] & (1 << pos); //結(jié)果非0為真,0則為假
}


⑤、問題:

理論上這40億個(gè)數(shù)不可能存在內(nèi)存當(dāng)中,應(yīng)該存在文件中,那我們就要去讀文件,40億個(gè)數(shù)因?yàn)橐捶秶_,故要開42億9千萬的空間,怎么開這么大的空間?常見方法如下:

①、bitset bs(-1);? //因?yàn)槲粓D的構(gòu)造函數(shù)參數(shù)是size_t,那-1若看為無符號數(shù)就是整形的最大值

②、bitset bs(0xffffffff);


⑥、位圖優(yōu)缺點(diǎn)及應(yīng)用:?

優(yōu)點(diǎn):節(jié)省空間、效率高

缺點(diǎn):只能處理整形

應(yīng)用:

  • 快速查找某個(gè)數(shù)據(jù)是否在一個(gè)集合中
  • 排序 + 去重
  • 求兩個(gè)集合的交集、并集等
  • 操作系統(tǒng)中磁盤塊標(biāo)記


⑦、完整代碼及測試

#pragma once
#include<iostream>
#include<vector>namespace mz
{class bitset{public:bitset(size_t N){//N代表要開多少比特位(簡稱:位)_bits.resize(N / 32 + 1, 0);_num = N;}void set(size_t x){//把第x位設(shè)置為1,表示此位置存在size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位_bits[index] |= (1 << pos); //對于這個(gè)整數(shù)第pos的位置或1//1<<pos表示先把1移動(dòng)到和pos相同位置的比特位上,因?yàn)閜os=幾,1就會(huì)左移幾位//|=表示是或,即除了pos位置的位要變成1,++_num;}void reset(size_t x){//把第x位設(shè)置為0,表示此位置不存在size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位_bits[index] &= ~(1 << pos); //對于這個(gè)整數(shù)第pos的位置與0--_num;}//判斷x在不在(也就是說x映射的位是否為1)bool test(size_t x){size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位return _bits[index] & (1 << pos); //結(jié)果非0為真,0則為假}private://int* _bits;std::vector<int> _bits;size_t _num;  //表示存了多少個(gè)比特位,映射存儲的多少個(gè)數(shù)據(jù)};void test_bitset(){bitset bs(100);bs.set(99);bs.set(98);bs.set(97);bs.reset(98);for (size_t i = 0; i < 100; ++i){printf("[%d]:%d\n", i, bs.test(i));}}}

部分測試結(jié)果如下:?

?


二、布隆過濾器

1、布隆過濾器的提出

我們在使用新聞客戶端看新聞時(shí),它會(huì)給我們不停地推薦新的內(nèi)容,它每次推薦時(shí)要去重,去掉 那些已經(jīng)看過的內(nèi)容。問題來了,新聞客戶端推薦系統(tǒng)如何實(shí)現(xiàn)推送去重的? 用服務(wù)器記錄了用 戶看過的所有歷史記錄,當(dāng)推薦系統(tǒng)推薦新聞時(shí)會(huì)從每個(gè)用戶的歷史記錄里進(jìn)行篩選,過濾掉那 些已經(jīng)存在的記錄。 如何快速查找呢?
  • 1. 哈希表存儲用戶記錄,缺點(diǎn):浪費(fèi)空間
  • 2. 用位圖存儲用戶記錄,缺點(diǎn):位圖一般只能處理整形,如果內(nèi)容編號是字符串,就無法處理
  • 3. 哈希與位圖結(jié)合,即布隆過濾器
布隆過濾器是 由布隆( Burton Howard Bloom )在 1970 年提出的 一種緊湊型的、比較巧妙的 率型數(shù)據(jù)結(jié)構(gòu) ,特點(diǎn)是 高效地插入和查詢,可以用來告訴你 某樣?xùn)|西一定不存在或者可能存 ,它是用多個(gè)哈希函數(shù),將一個(gè)數(shù)據(jù)映射到位圖結(jié)構(gòu)中。此種方式 不僅可以提升查詢效率,也 可以節(jié)省大量的內(nèi)存空間 。


2、布隆過濾器的實(shí)現(xiàn)

①、基本結(jié)構(gòu)

?一般布隆過濾器存的是字符串或結(jié)構(gòu)體等,一般不會(huì)是整形,因?yàn)檎尉陀梦粓D來存了

布隆過濾器底層就是用位圖實(shí)現(xiàn)的,因?yàn)樽址容^常用,故我們直接把字符串作為默認(rèn)模板參數(shù),其他三個(gè)Hash模板參數(shù)表示的是用三個(gè)位置來映射一個(gè)值

構(gòu)造函數(shù)開多少個(gè)空間?

有大佬已經(jīng)計(jì)算過了,10個(gè)元素就需要長度為43位,那我們干脆初始開個(gè)5倍

template<class K = string, class Hash1 = HashStr1, class Hash2 = HashStr2, class Hash3 = HashStr3>
class bloomfilter
{
public://直接上來開滿會(huì)有問題,因?yàn)榭赡芪冶旧砜赡芫蜎]映射幾個(gè)值//那就根據(jù)你大概會(huì)存多少個(gè)數(shù)據(jù),來對應(yīng)開空間//到底開多少比較好有人算過,即你存多少個(gè)值就要映射到多少個(gè)位bloomfilter(size_t num):_bs(5 * num),_N(5 * num){}private:bitset _bs;	//底層是一個(gè)位圖size_t _N;
};

②、三個(gè)Hash仿函數(shù)實(shí)現(xiàn)

?因?yàn)橐萌齻€(gè)映射位置來映射一個(gè)值,故要寫三個(gè)字符串轉(zhuǎn)為整形的函數(shù),而又因?yàn)閟tring類型比較常用,這三個(gè)仿函數(shù)會(huì)作為默認(rèn)模板參數(shù)

下面是能降低哈希沖突的字符串算法(我們下面三個(gè)仿函數(shù)就選用下面三個(gè)算法):

struct HashStr1
{size_t operator()(const string& str){	//運(yùn)用BKDRHashsize_t hash = 0;for (size_t i = 0; i < str.size(); ++i){hash *= 131;hash += str[i];}return hash;}
};struct HashStr2
{size_t operator()(const string& str){	//運(yùn)用RSHashsize_t hash = 0;size_t magic = 63689; //魔數(shù)for (size_t i = 0; i < str.size(); ++i){hash *= magic;hash += str[i];magic *= 378551;}return hash;}
};struct HashStr3
{size_t operator()(const string& str){	//運(yùn)用SDBMHashsize_t hash = 0;for (size_t i = 0; i < str.size(); ++i){hash *= 65599;hash += str[i];}return hash;}
};

③、 set

函數(shù)是想把key這個(gè)數(shù)標(biāo)志為存在,而我們說了要用三個(gè)位置來映射這個(gè)key值,則調(diào)用Hash仿函數(shù)先計(jì)算出字符串的映射位置,%_N是因?yàn)槲覀儎傞_始給位圖就開了_N個(gè)比特位,你算出的映射位置很可能大于_N,故都%_N,既能存儲也能統(tǒng)一,則一個(gè)key值就能用三個(gè)映射位置來表示

注:Hash1是仿函數(shù)類型,Hash1()是仿函數(shù)對象,當(dāng)然你也可以寫為Hash1 hs1;?hs1(key) % _N;但是明顯更麻煩

void set(const K& key)
{size_t index1 = Hash1()(key) % _N;//利用Hash1類型的匿名對象size_t index2 = Hash2()(key) % _N;size_t index3 = Hash3()(key) % _N;_bs.set(index1);//表示index1這個(gè)位置存在_bs.set(index2);_bs.set(index3);
}

④、 test

功能:判斷key值存不存在

因?yàn)橐粋€(gè)值用了三個(gè)映射位置,故我們判斷計(jì)算出key的三個(gè)映射位置在位圖中是否同時(shí)存在,同時(shí)存在key值才存在,反之有一個(gè)不存在就肯定不存在

bool test(const K& key)
{size_t index1 = Hash1()(key) % _N;if (_bs.test(index1) == false)return false;size_t index2 = Hash2()(key) % _N;if (_bs.test(index2) == false)return false;size_t index3 = Hash3()(key) % _N;if (_bs.test(index3) == false)return false;return true;  //但這里也不一定是真的在,還是可能存在誤判//判斷在,是不準(zhǔn)確的,可能存在誤判//判斷不在,是準(zhǔn)確的
}

⑤、?刪除

布隆過濾器不能直接支持刪除工作,因?yàn)樵趧h除一個(gè)元素時(shí),可能會(huì)影響其他元素。

一種支持刪除的方法:將布隆過濾器中的每個(gè)比特位擴(kuò)展成一個(gè)小的計(jì)數(shù)器,插入元素時(shí)給 k個(gè)計(jì) 數(shù)器 (k 個(gè)哈希函數(shù)計(jì)算出的哈希地址 ) 加一,刪除元素時(shí),給 k個(gè)計(jì)數(shù)器減一,通過多占用幾倍存儲 空間的代價(jià)來增加刪除操作。
缺陷:
1. 無法確認(rèn)元素是否真正在布隆過濾器中
2. 存在計(jì)數(shù)回繞

void reset(const K& key)	
{//將映射的位置給置0就可以?//不支持刪除,可能會(huì)存在誤刪,故布隆過濾器一般不支持刪除
}

?⑥、完整代碼及測試

#pragma once
#include"bitset.h"
#include<string>using std::string;
using std::cout;
using std::endl;namespace mz
{struct HashStr1{size_t operator()(const string& str){	//運(yùn)用BKDRHashsize_t hash = 0;for (size_t i = 0; i < str.size(); ++i){hash *= 131;hash += str[i];}return hash;}};struct HashStr2{size_t operator()(const string& str){	//運(yùn)用RSHashsize_t hash = 0;size_t magic = 63689; //魔數(shù)for (size_t i = 0; i < str.size(); ++i){hash *= magic;hash += str[i];magic *= 378551;}return hash;}};struct HashStr3{size_t operator()(const string& str){	//運(yùn)用SDBMHashsize_t hash = 0;for (size_t i = 0; i < str.size(); ++i){hash *= 65599;hash += str[i];}return hash;}};template<class K = string, class Hash1 = HashStr1, class Hash2 = HashStr2, class Hash3 = HashStr3>class bloomfilter{public://直接上來開滿會(huì)有問題,因?yàn)榭赡芪冶旧砜赡芫蜎]映射幾個(gè)值//那就根據(jù)你大概會(huì)存多少個(gè)數(shù)據(jù),來對應(yīng)開空間//到底開多少比較好有人算過,即你存多少個(gè)值就要映射到多少個(gè)位bloomfilter(size_t num):_bs(5 * num),_N(5 * num){}void set(const K& key){size_t index1 = Hash1()(key) % _N;//利用Hash1類型的匿名對象size_t index2 = Hash2()(key) % _N;size_t index3 = Hash3()(key) % _N;_bs.set(index1);_bs.set(index2);_bs.set(index3);}bool test(const K& key){size_t index1 = Hash1()(key) % _N;if (_bs.test(index1) == false)return false;size_t index2 = Hash2()(key) % _N;if (_bs.test(index2) == false)return false;size_t index3 = Hash3()(key) % _N;if (_bs.test(index3) == false)return false;return true;  //但這里也不一定是真的在,還是可能存在誤判//判斷在,是不準(zhǔn)確的,可能存在誤判//判斷不在,是準(zhǔn)確的}void reset(const K& key){//將映射的位置給置0就可以?//不支持刪除,可能會(huì)存在誤刪,故布隆過濾器一般不支持刪除}private:bitset _bs;	//底層是一個(gè)位圖size_t _N;};void test_bloomfilter(){bloomfilter<string> bf(100); //這里不給string,直接用<>也行,因?yàn)閟tring是默認(rèn)的bf.set("abcd");bf.set("aadd");bf.set("bcad");cout << bf.test("abcd") << endl;cout << bf.test("aadd") << endl;cout << bf.test("bcad") << endl;cout << bf.test("cbad") << endl;}
}


⑦、 優(yōu)缺點(diǎn)

布隆過濾器優(yōu)點(diǎn)
  • 1. 增加和查詢元素的時(shí)間復(fù)雜度為:O(K), (K為哈希函數(shù)的個(gè)數(shù),一般比較小),與數(shù)據(jù)量大小無
  • 關(guān)
  • 2. 哈希函數(shù)相互之間沒有關(guān)系,方便硬件并行運(yùn)算
  • 3. 布隆過濾器不需要存儲元素本身,在某些對保密要求比較嚴(yán)格的場合有很大優(yōu)勢
  • 4. 在能夠承受一定的誤判時(shí),布隆過濾器比其他數(shù)據(jù)結(jié)構(gòu)有這很大的空間優(yōu)勢
  • 5. 數(shù)據(jù)量很大時(shí),布隆過濾器可以表示全集,其他數(shù)據(jù)結(jié)構(gòu)不能
  • 6. 使用同一組散列函數(shù)的布隆過濾器可以進(jìn)行交、并、差運(yùn)算
布隆過濾器缺陷
  • 1. 有誤判率,即存在假陽性(False Position),即不能準(zhǔn)確判斷元素是否在集合中(補(bǔ)救方法:再
  • 建立一個(gè)白名單,存儲可能會(huì)誤判的數(shù)據(jù))
  • 2. 不能獲取元素本身
  • 3. 一般情況下不能從布隆過濾器中刪除元素
  • 4. 如果采用計(jì)數(shù)方式刪除,可能會(huì)存在計(jì)數(shù)回繞問題

http://www.risenshineclean.com/news/52724.html

相關(guān)文章:

  • 如何做網(wǎng)站插件無限制搜索引擎排名
  • 正規(guī)的合肥網(wǎng)站建設(shè)商家推廣平臺有哪些
  • 住房與城鄉(xiāng)建設(shè)部網(wǎng)站職責(zé)營銷策劃案例
  • 免費(fèi)微商城平臺官網(wǎng)最優(yōu)化方法
  • 網(wǎng)站怎么做導(dǎo)航條新聞發(fā)布會(huì)稿件
  • wordpress加授權(quán)網(wǎng)絡(luò)優(yōu)化的基本方法
  • 用rp怎么做網(wǎng)站按鈕下拉菜單百度移動(dòng)首頁
  • 簡述網(wǎng)站建設(shè)優(yōu)劣的評價(jià)標(biāo)準(zhǔn)外貿(mào)營銷網(wǎng)站
  • 網(wǎng)站免費(fèi)虛擬空間3小時(shí)百度收錄新站方法
  • 軟件開發(fā)是編程嗎windows優(yōu)化大師怎么用
  • 鄭州聯(lián)通網(wǎng)站備案百度競價(jià)推廣價(jià)格
  • 博樂建設(shè)工程信息網(wǎng)站南昌百度seo
  • 自學(xué)做網(wǎng)站的書網(wǎng)絡(luò)營銷七個(gè)步驟
  • 做網(wǎng)站時(shí)java都做什么網(wǎng)站到首頁排名
  • 注冊一個(gè)公司網(wǎng)站的費(fèi)用東莞推廣服務(wù)
  • dedecms采集規(guī)則各類網(wǎng)站網(wǎng)站生成器
  • 網(wǎng)站建設(shè)技術(shù)部獎(jiǎng)懲制度快速建站網(wǎng)站
  • 用手機(jī)域名做網(wǎng)站有多少大數(shù)據(jù)精準(zhǔn)獲客軟件
  • 有哪個(gè)網(wǎng)站能賣自己做的衣服信息推廣平臺
  • 快速免費(fèi)做網(wǎng)站教育培訓(xùn)機(jī)構(gòu)有哪些
  • 做網(wǎng)站項(xiàng)目需要多少錢百度地圖推廣怎么做的
  • 做網(wǎng)站開發(fā)的有哪些公司好人工智能培訓(xùn)課程
  • 江蘇營銷型網(wǎng)站推廣網(wǎng)絡(luò)營銷組合策略
  • 洛陽網(wǎng)站建設(shè)哪家專業(yè)新聞源軟文推廣平臺
  • paypal綁定wordpressseo專業(yè)培訓(xùn)學(xué)費(fèi)多少錢
  • 長沙網(wǎng)站優(yōu)化方式代推廣平臺
  • 四川個(gè)人網(wǎng)站備案百度地圖客服人工電話
  • 怎樣將自己做的網(wǎng)站發(fā)布到外網(wǎng)上二維碼推廣賺傭金平臺
  • 著名網(wǎng)站設(shè)計(jì)師廣告設(shè)計(jì)需要學(xué)什么
  • 如何通過axure做網(wǎng)站架構(gòu)信息流推廣方式