시간과 공간에 가장 적합한 것은 블룸 필터, 해시 테이블 또는 사전입니까?

Question

고정 길이 (8-char)의 4000 문자열을 C#에 저장해야하지만, 항목 추가 및 검색 시간과 관련하여 가장 좋은 공간은 무엇입니까? 블룸 필터, 해시 테이블 또는 사전? 아무도 도와 줄 수 있다면 제발

Answer 1

C#의 사전은 해시 테이블을 사용하여 구현되므로이 질문에 C#에서는 실제로 두 가지 데이터 구조 만 있습니다. 따라서 우리는 Dictionary와 HashTable을 모두 해시 테이블이라고 부릅니다. 그중 하나를 사용한다면 여기에 설명 된대로 유형 안전성과 성능으로 인해 사전이 필요할 것입니다. Why is Dictionary preferred over hashtable? 그러나 사전은 해시 테이블을 사용하여 구현되므로 큰 차이가 없습니다.

하지만 진짜 질문은 해시 테이블 (사전) 대 블룸 필터입니다. 누군가는 이전에 관련 질문 인 What is the advantage to using bloom filters?을 요청했습니다. 그들은 또한 블룸 필터의 Wikipedia 페이지에 링크합니다. 이것은 매우 유익합니다. https://en.wikipedia.org/wiki/Bloom_filter 짧은 답변은 블룸 필터가 작고 빠릅니다. 그러나 그들은 이것과 관련된 비용이 있습니다 : 그들은 완전히 정확하지 않습니다. 해시 테이블에서 원래 문자열은 항상 정확한 비교를 위해 저장됩니다. 먼저 값을 해시하면 테이블의 어느 부분을 볼 수 있는지 알려줍니다. 일단 테이블을 들여다 보면 그곳에있는 값을 찾고있는 값과 비교합니다. 블룸 필터에서는 여러 해시를 사용하여 위치 집합을 계산합니다. 모든 위치에 1이 있으면 문자열을 찾은 것으로 간주합니다. 즉, 원래 삽입되지 않은 문자열이 "발견"될 수 있습니다. 테이블이 너무 작 으면 실제로 시도한 모든 문자열이 Bloom 필터에 표시 될 포화 점에 도달 할 수 있습니다. 삽입 할 문자열의 수를 알기 때문에이를 피하기 위해 테이블의 크기를 적절하게 조정할 수 있습니다.

관련 크기를 살펴 보겠습니다. 숫자가 깔끔하게 나오게하려면 정확히 4096 개의 문자열이 있다고 가정합니다. 상대적으로 콜리 전 (collision) 해시 테이블을 사용하려면 최소한 테이블 수가 문자열 수만큼 커야합니다. 그래서 현실적으로 (32 비트 (4 바이트) 포인터라고 가정),이 경우 4096 * 4 바이트 = 16K의 테이블과 4096 * (4 + 4 + 8) = 64K의 테이블을 볼 수 있습니다. 리스트 노드 (다음 포인터 + 문자열 포인터)와 문자열. 그래서 총계로 약 80K가 될 것입니다. 아마도 C#을 사용할 대부분의 상황에서별로 메모리가 아닙니다.

블룸 필터의 경우 크기 계산시 목표로하고 싶은 오류율을 결정해야합니다. 1 %의 오류율에 대해 이야기 할 때, Bloom 필터에 삽입되지 않은 100 개의 문자열 중 1 개는 존재하는 것으로 잘못 표시됩니다. 삽입 된 문자열은 항상 삽입 된 것으로 올바르게 표시됩니다. 방정식 m = -n * ln (p)/(ln (2)^2)을 사용하여 최소 크기를 계산하여 특정 오류율을 얻을 수 있습니다. 그 방정식에서, m은 테이블 내의 슬롯의 수이고, p는 에러율이고, n은 삽입 될 문자열의 수이다. 따라서 p를 0.01 (1 % 오류)로 설정하면 약 9.6 * 4096 비트 = 9.6 * 512 바이트 = 4.8K가됩니다. 이는 분명히 상당히 작습니다. 그러나 실제로 1 %는 오류율이 높습니다. 그래서 현실적으로 우리는 0.0001 %와 비슷한 것을 찾아야합니다. 28.8 * 4096b 비트 = 28.8 * 512 바이트 = 14.4K가됩니다. 분명히 이들 중 하나는 해시 테이블에 대해 계산 한 80K보다 훨씬 작습니다. 그러나 해시 테이블의 오류율은 0으로 분명히 1 % 또는 0.0001 % 미만입니다.

실제로 상황에 따라 약간의 속도와 약간의 시간을 얻는 데 대한 정확성을 잃어 버리는 것의 보완이 가치가 있는지 여부는 여러분에게 달려 있습니다. 현실적으로 두 옵션 중 어느 것도 현실 세계의 대부분을 충분히 작고 빠르지는 않습니다.

Answer 2

.NET 1.0의 System.Collections.Hashtable은 .NET 2.0에서 소개 된 System.Collections.Generic.Dictionary와 완전히 동일합니다.

키와 값 유형을 지정하여 유형이 안전하므로 사전을 사용하는 것이 좋습니다. Hashtable은 객체 유형 만 사용하므로 데이터를 검색 할 때마다 문자열로 다시 캐스팅해야합니다.

Answer 3

사전은 한 유형에서 다른 유형으로의 매핑을 나타내는 추상 데이터 유형입니다. 사전의 구현이 무엇인지는 지정하지 않습니다. 해시 테이블, 균형 이진 검색 트리, 건너 뛰기 목록 또는 다른 많은 구조 중 하나에 의해 뒷받침 될 수 있습니다. 사전이 한 유형의 요소를 다른 유형과 연관시키기 때문에 아마 여기서는 적합하지 않습니다. 당신은 이것을하지 않고 있습니다 - 당신은 요소를 저장하는 것에 관심이 있습니다 - 그래서 이것은 아마도 부적절 할 것입니다. 블룸를 필터링

는 요소가 확실히 세트 하지,하지만 뭔가 이 세트인지 확실히 당신에게 말할 수 있는지 여부를 확인하기위한 좋은 확률 데이터 구조입니다. 불필요한 네트워크 읽기를 피하기 위해 분산 시스템에서 일반적으로 사용됩니다. 각 컴퓨터는 데이터베이스에있는 항목의 블룸 필터를 저장할 수 있으며 필터가 항목을 제외하면 원격 시스템에 쿼리하지 않아 불필요한 네트워크 호출을 걸러 낼 수 있습니다. 오탐 (false positive)은 아마도 거래 차단 자 (deal-breaker)이기 때문에 당신이하려는 일에별로 좋지 않습니다.

해시 테이블은 원하는 데이터 구조입니다. 그것은 요소의 빠른 검색과 삽입을 지원하며, 좋은 구현으로 극도로 메모리를 효율적으로 사용할 수 있습니다. 그러나 요소를 정렬 된 순서로 저장하지 않으므로 응용 프로그램에 따라 문제가 될 수 있습니다.

정렬 된 순서를 원할 경우 고려해야 할 다른 두 가지 구조가 있습니다. 첫 번째는 균형 이진 검색 트리으로, 빠른 검색과 삭제를 지원하고 요소를 정렬 된 순서로 저장합니다. 많은 좋은 구현이 있습니다. 사실상 모든 좋은 프로그래밍 언어는 구현과 함께 제공됩니다. 다른 하나는 이며 매우 빠른 검색과 액세스를 지원하며 정렬 된 순서를 유지합니다. 문자열의 분포에 따라 공간이 비효율적 일 수도 있지만 찾고자하는 것이 맞을 수도 있습니다.

희망이 도움이됩니다.