비트 맵 (BitMap) & & 블 룸 필터 (BloomFilter)
● 이 문 제 를 보고 가장 먼저 떠 오 르 는 방법 은 이 40 억 개의 수 를 옮 겨 다 니 며 순서대로 판단 하 는 것 이다. 그러나 이 방법 에 필요 한 메모리 가 매우 크다. 약 15G (400000000 * 4 이다. ÷ (1024 * 1024 * 1024)) 를 보면 이 알고리즘 은 바람 직 하지 않다 는 것 을 알 수 있다.
● 메모리 가 충분 하 다 면, 우 리 는 비트 맵 을 통 해 이 루어 질 수 있 습 니 다. 비트 맵 의 한 배열 의 모든 바 이 너 리 는 하나의 데 이 터 를 표시 하고, 한 사람 은 0, 1 로 현재 이 위치 에 값 이 저장 되 어 있 는 지 여 부 를 표시 하 며, 마찬가지 로 하 쉬 를 이용 하여 저장 하 는 방법 입 니 다.이 방법 은 메모 리 를 크게 줄 일 수 있 습 니 다. 이 문 제 는 int 형식 으로 32 비트 를 프로 그래 밍 할 수 있 습 니 다. 필요 한 메모리 공간 은 15G 에서 500 M 으로 낮 출 수 있 습 니 다.
구체 적 인 실현 은 다음 과 같다.
#pragma
class BitMap//
{
public:
BitMap()
:_size(0)
{}
BitMap(size_t size)//size ，
: _size(size)
{// size / 32 + 1 5 1（ 1： size， 10%8=1， 2）
_a.resize((size >> 5) + 1);
}
// ， 1 num 32-num；
void Set(size_t x)// x ， 1
{
size_t index = x >> 5;
size_t num = x % 32;//eg:x = 35,num = 3, _a[1] 001
++_size;
_a[index] |= 1 << num;//1 3 ， | _a
}
void Remove(size_t x)// x ， 0
{
size_t index = x >> 5;
size_t num = x % 32;//eg:x = 35,num = 3, _a[1] 110
--_size;
_a[index] &= (~(1 << num));//1 3 0， & _a 0
}
bool Test(size_t x)//
{
size_t index = x >> 5;
size_t num = x % 32;
if (_a[index] & (1 << num))// 1，
{
return true;
}
return false;
}
void Resize(size_t size)//
{
_a.resize((size >> 5) + 1);
}
size_t Size()//
{
return _size;
}
size_t Capacity()// int
{
return _a.size();
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i] << " " << endl;
}
cout << endl;
}
private:
vector<size_t> _a;
size_t _size;
};
void TestBitMap()
{
BitMap bm(65);
bm.Set(3);
bm.Set(4);
bm.Set(5);
bm.Print();
cout << "is 4 EXTST? " << bm.Test(4) << endl;
cout << "is 8 EXTST? " << bm.Test(8) << endl;
bm.Remove(4);
cout << "is 4 EXTST? " << bm.Test(4) << endl;
bm.Print();
cout << "size: " << bm.Size() << endl;
cout << "capacity: " << bm.Capacity() << endl;
bm.Resize(100);
cout << "capacity: " << bm.Capacity() << endl;
}● Bloom Filter 는 공간 효율 이 높 은 랜 덤 데이터 구조 로 Bloom filter 는 bit - map 에 대한 확장 이 라 고 볼 수 있 습 니 다. 그 원 리 는:
원소 가 집합 에 들 어 갔 을 때, K 개. Hash 함 수 는 이 요 소 를 비트 배열 (Bit array) 의 K 점 으로 매 핑 하여 설정 합 니 다. 1。검색 할 때 이 점 들 이 모두 1 인지 아 닌 지 를 보면 집합 에 있 는 지 없 는 지 알 수 있다.
1. 만약 에 이런 점 에 0 이 있 으 면 검색 요소 가 없 을 것 입 니 다.
2. 모두 1 이 라면 검색 요소 가 있 을 수 있 습 니 다.
소수 표 와 6 개의 해시 알고리즘 을 사 용 했 습 니 다.
#pragma
size_t _GetNextPrime(size_t size)// ：
{
const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
for (size_t i = 0; i < _PrimeSize; ++i)
{
if (_PrimeList[i] > size)
{
return _PrimeList[i];
}
return _PrimeList[i - 1];
}
return _PrimeList[_PrimeSize];// size ，
}
//6
template<class T>
size_t BKDRHash(const T * str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch; // 31、131、1313、13131、131313..
}
return hash;
}
template<class T>
size_t SDBMHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
template<class T>
size_t RSHash(const T *str)
{
register size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
{
hash = hash * magic + ch;
magic *= 378551;
}
return hash;
}
template<class T>
size_t APHash(const T *str)
{
register size_t hash = 0;
size_t ch;
for (long i = 0; ch = (size_t)*str++; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}
template<class T>
size_t JSHash(const T *str)
{
if (!*str) // ， 0
return 0;
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}
template<class T>
size_t DEKHash(const T* str)
{
if (!*str) // 0
return 0;
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
}
return hash;
}
//6 6
template<class T>
struct _HashFunc1
{
size_t operator()(const T& str)
{
return BKDRHash(str.c_str());
}
};
template<class T>
struct _HashFunc2
{
size_t operator()(const T& str)
{
return SDBMHash(str.c_str());
}
};
template<class T>
struct _HashFunc3
{
size_t operator()(const T& str)
{
return RSHash(str.c_str());
}
};
template<class T>
struct _HashFunc4
{
size_t operator()(const T& str)
{
return APHash(str.c_str());
}
};
template<class T>
struct _HashFunc5
{
size_t operator()(const T& str)
{
return JSHash(str.c_str());
}
};
template<class T>
struct _HashFunc6
{
size_t operator()(const T& str)
{
return DEKHash(str.c_str());
}
};부 릉 필 터 는 다음 과 같이 구체 적 으로 실 현 됩 니 다.
#define _CRT_SECURE_NO_WARNINGS 1
template<class K = string,
class HashFunc1 = _HashFunc1<K>, class HashFunc2 = _HashFunc2<K>,
class HashFunc3 = _HashFunc3<K>, class HashFunc4 = _HashFunc4<K>,
class HashFunc5 = _HashFunc5<K>, class HashFunc6 = _HashFunc6<K>>
class BloomFilter
{
public:
BloomFilter(size_t size = 0)
{
_capacity = _GetNextPrime(size);
_bm.Resize(_capacity);// BitMap Resize
}
void Set(const K& key)
{
size_t index1 = HashFunc1()(key);
size_t index2 = HashFunc2()(key);
size_t index3 = HashFunc3()(key);
size_t index4 = HashFunc4()(key);
size_t index5 = HashFunc5()(key);
size_t index6 = HashFunc6()(key);
_bm.Set(index1 % _capacity);// index1 % _capacity， BitMap Set
_bm.Set(index2 % _capacity);
_bm.Set(index3 % _capacity);
_bm.Set(index4 % _capacity);
_bm.Set(index5 % _capacity);
_bm.Set(index6 % _capacity);
}
bool Test(const K& key)
{
// 0 ，
size_t index1 = HashFunc1()(key);
if (!_bm.Test(index1 % _capacity))
return false;
size_t index2 = HashFunc2()(key);
if(!_bm.Test(index2 % _capacity))
return false;
size_t index3 = HashFunc3()(key);
if(!_bm.Test(index3 % _capacity))
return false;
size_t index4 = HashFunc4()(key);
if(!_bm.Test(index4 % _capacity))
return false;
size_t index5 = HashFunc5()(key);
if(!_bm.Test(index5 % _capacity))
return false;
size_t index6 = HashFunc6()(key);
if(!_bm.Test(index6 % _capacity))
return false;
return true;
}
private:
BitMap _bm;
size_t _capacity;
};
void TestBloomFilter()
{
BloomFilter<> bf(50);
bf.Set("Scen");
bf.Set(" ");
bf.Set("http://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773181");
cout << "exist? " << bf.Test("Scen") << endl;
cout << "exist? " << bf.Test("Scenluo") << endl;
cout << "exist? " << bf.Test(" ") << endl;
cout << "exist? " << bf.Test("http://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773181") << endl;
cout << "exist? " << bf.Test("http://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773131") << endl;
}부 릉 필터 의 결함:
1. 오산 율 (False Positive) 은 그 중의 하나 이다.
저 장 된 요소 의 수량 이 증가 함 에 따라 오산 율 이 증가한다.그러나 원소 의 수량 이 너무 적 으 면 산열 표를 사용 하면 충분 하 다.그래서 우 리 는 여러 개의 해시 표 로 데 이 터 를 저장 했다.그러면 문제 가 또 생 겼 다. 우 리 는 좀 더 쓸 까, 아니면 좀 적 게 쓸 까?해시 시 계 를 많이 사용 하면 위의 문제 와 같이 해시 하나 에 500 M 이 필요 하 다. 그러면 많이 넣 을 수록 메모리 가 차지 하 는 것 이 아 닐 까?너무 적 으 면 오산 율 이 높 은 거 아니 야? 그 러 니까 적당 한 걸 로.나의 프로그램 실현 은 여섯 개의 해시 표를 얻 은 것 이다.
2. 현재 위치 가 0 이면 존재 하지 않 지만 1 이면 존재 하지 않 습 니 다.
일반 부 릉 필 터 는 디자인 만 지원 하고 삭 제 는 지원 되 지 않 습 니 다.인용 수 를 통 해 계산 할 수 있 지만 공간 낭비 가 크다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cacheasBitmap 연구true으로 설정하면 Flash가 실행될 때 객체의 내부 비트맵 표현이 캐시됩니다.이 캐시는 복잡한 벡터 내용을 포함하는 디스플레이 대상의 성능을 향상시킬 수 있습니다. 캐시된 비트맵이 있는 표시 대상의 모든 벡터 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
