매우 긴 문자열 목록에 대한 적절한 검색 / 검색 방법은 무엇입니까?
이것은 매우 드문 질문은 아니지만 여전히 선택을 실제로 설명하는 답을 찾을 수없는 것 같습니다.
매우 큰 문자열 목록 ( 정확히 SHA-256 해시 의 ASCII 표현 )이 있고 해당 목록 내에 문자열이 있는지 쿼리해야합니다.
이 목록에는 1 억 개가 넘는 항목이있을 수 있으며 항목의 존재 여부를 여러 번 반복해서 쿼리해야합니다.
크기를 감안할 때 모든 것을 HashSet<string>. 성능을 극대화하기위한 적절한 검색 시스템은 무엇입니까?
목록을 미리 정렬 할 수 있고, SQL 테이블에 넣을 수 있고, 텍스트 파일에 넣을 수는 있지만 내 응용 프로그램을 고려할 때 실제로 무엇이 가장 적합한 지 잘 모르겠습니다.
이들 또는 다른 검색 방법 중 성능 측면에서 확실한 승자가 있습니까?
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Security.Cryptography;
namespace HashsetTest
{
abstract class HashLookupBase
{
protected const int BucketCount = 16;
private readonly HashAlgorithm _hasher;
protected HashLookupBase()
{
_hasher = SHA256.Create();
}
public abstract void AddHash(byte[] data);
public abstract bool Contains(byte[] data);
private byte[] ComputeHash(byte[] data)
{
return _hasher.ComputeHash(data);
}
protected Data256Bit GetHashObject(byte[] data)
{
var hash = ComputeHash(data);
return Data256Bit.FromBytes(hash);
}
public virtual void CompleteAdding() { }
}
class HashsetHashLookup : HashLookupBase
{
private readonly HashSet<Data256Bit>[] _hashSets;
public HashsetHashLookup()
{
_hashSets = new HashSet<Data256Bit>[BucketCount];
for(int i = 0; i < _hashSets.Length; i++)
_hashSets[i] = new HashSet<Data256Bit>();
}
public override void AddHash(byte[] data)
{
var item = GetHashObject(data);
var offset = item.GetHashCode() & 0xF;
_hashSets[offset].Add(item);
}
public override bool Contains(byte[] data)
{
var target = GetHashObject(data);
var offset = target.GetHashCode() & 0xF;
return _hashSets[offset].Contains(target);
}
}
class ArrayHashLookup : HashLookupBase
{
private Data256Bit[][] _objects;
private int[] _offsets;
private int _bucketCounter;
public ArrayHashLookup(int size)
{
size /= BucketCount;
_objects = new Data256Bit[BucketCount][];
_offsets = new int[BucketCount];
for(var i = 0; i < BucketCount; i++) _objects[i] = new Data256Bit[size + 1];
_bucketCounter = 0;
}
public override void CompleteAdding()
{
for(int i = 0; i < BucketCount; i++) Array.Sort(_objects[i]);
}
public override void AddHash(byte[] data)
{
var hashObject = GetHashObject(data);
_objects[_bucketCounter][_offsets[_bucketCounter]++] = hashObject;
_bucketCounter++;
_bucketCounter %= BucketCount;
}
public override bool Contains(byte[] data)
{
var hashObject = GetHashObject(data);
return _objects.Any(o => Array.BinarySearch(o, hashObject) >= 0);
}
}
struct Data256Bit : IEquatable<Data256Bit>, IComparable<Data256Bit>
{
public bool Equals(Data256Bit other)
{
return _u1 == other._u1 && _u2 == other._u2 && _u3 == other._u3 && _u4 == other._u4;
}
public int CompareTo(Data256Bit other)
{
var rslt = _u1.CompareTo(other._u1); if (rslt != 0) return rslt;
rslt = _u2.CompareTo(other._u2); if (rslt != 0) return rslt;
rslt = _u3.CompareTo(other._u3); if (rslt != 0) return rslt;
return _u4.CompareTo(other._u4);
}
public override bool Equals(object obj)
{
if (ReferenceEquals(null, obj))
return false;
return obj is Data256Bit && Equals((Data256Bit) obj);
}
public override int GetHashCode()
{
unchecked
{
var hashCode = _u1.GetHashCode();
hashCode = (hashCode * 397) ^ _u2.GetHashCode();
hashCode = (hashCode * 397) ^ _u3.GetHashCode();
hashCode = (hashCode * 397) ^ _u4.GetHashCode();
return hashCode;
}
}
public static bool operator ==(Data256Bit left, Data256Bit right)
{
return left.Equals(right);
}
public static bool operator !=(Data256Bit left, Data256Bit right)
{
return !left.Equals(right);
}
private readonly long _u1;
private readonly long _u2;
private readonly long _u3;
private readonly long _u4;
private Data256Bit(long u1, long u2, long u3, long u4)
{
_u1 = u1;
_u2 = u2;
_u3 = u3;
_u4 = u4;
}
public static Data256Bit FromBytes(byte[] data)
{
return new Data256Bit(
BitConverter.ToInt64(data, 0),
BitConverter.ToInt64(data, 8),
BitConverter.ToInt64(data, 16),
BitConverter.ToInt64(data, 24)
);
}
}
class Program
{
private const int TestSize = 150000000;
static void Main(string[] args)
{
GC.Collect(3);
GC.WaitForPendingFinalizers();
{
var arrayHashLookup = new ArrayHashLookup(TestSize);
PerformBenchmark(arrayHashLookup, TestSize);
}
GC.Collect(3);
GC.WaitForPendingFinalizers();
{
var hashsetHashLookup = new HashsetHashLookup();
PerformBenchmark(hashsetHashLookup, TestSize);
}
Console.ReadLine();
}
private static void PerformBenchmark(HashLookupBase hashClass, int size)
{
var sw = Stopwatch.StartNew();
for (int i = 0; i < size; i++)
hashClass.AddHash(BitConverter.GetBytes(i * 2));
Console.WriteLine("Hashing and addition took " + sw.ElapsedMilliseconds + "ms");
sw.Restart();
hashClass.CompleteAdding();
Console.WriteLine("Hash cleanup (sorting, usually) took " + sw.ElapsedMilliseconds + "ms");
sw.Restart();
var found = 0;
for (int i = 0; i < size * 2; i += 10)
{
found += hashClass.Contains(BitConverter.GetBytes(i)) ? 1 : 0;
}
Console.WriteLine("Found " + found + " elements (expected " + (size / 5) + ") in " + sw.ElapsedMilliseconds + "ms");
}
}
}
결과는 매우 유망합니다. 단일 스레드로 실행됩니다. 해시 셋 버전은 7.9GB RAM 사용량에서 초당 1 백만 회를 약간 넘는 조회를 기록 할 수 있습니다. 어레이 기반 버전은 더 적은 RAM (4.6GB)을 사용합니다. 둘 사이의 시작 시간은 거의 동일합니다 (388 초 대 391 초). 해시 세트는 조회 성능을 위해 RAM을 교환합니다. 둘 다 메모리 할당 제약으로 인해 버킷 화되어야했습니다.
어레이 성능 :
해싱 및 추가에 307408ms 소요
해시 정리 (일반적으로 정렬)에 81892ms 소요
562585ms에서 30000000 개 요소 (예상 30000000 개) 발견 [초당 55,000 개 검색]
====================================
해시 셋 성능 :
해싱 및 추가에 391105ms 소요
해시 정리 (일반적으로 정렬)에 0ms 소요
74864ms [초당 40 만 검색]에서 30000000 요소 (예상 30000000) 발견
시간이 지남에 따라 목록이 변경되면 데이터베이스에 저장합니다.
목록이 변경되지 않으면 정렬 된 파일에 넣고 모든 쿼리에 대해 이진 검색을 수행합니다.
두 경우 모두 Bloom 필터 를 사용하여 I / O를 최소화합니다. 그리고 문자열 사용을 중지하고 4 개의 ulong으로 이진 표현을 사용합니다 (객체 참조 비용을 피하기 위해).
여유 공간이
16GB (2 * 64 * 4 / 3 * 100M, Base64 인코딩 가정
) 이상인 경우 옵션은 Set & ltstring>을 만들고 만족하는 것입니다. 물론 바이너리 표현을 사용하면 7GB 미만에 들어갈 수 있습니다.
David Haney의 대답은 메모리 비용이 그렇게 쉽게 계산되지 않는다는 것을 보여줍니다.
를 사용하면 <gcAllowVeryLargeObjects>훨씬 더 큰 배열을 가질 수 있습니다. 256 비트 해시 코드의 ASCII 표현을 구현하는 사용자 지정 구조체로 변환하지 않는 이유는 무엇 IComparable<T>입니까? 다음과 같이 표시됩니다.
struct MyHashCode: IComparable<MyHashCode>
{
// make these readonly and provide a constructor
ulong h1, h2, h3, h4;
public int CompareTo(MyHashCode other)
{
var rslt = h1.CompareTo(other.h1);
if (rslt != 0) return rslt;
rslt = h2.CompareTo(other.h2);
if (rslt != 0) return rslt;
rslt = h3.CompareTo(other.h3);
if (rslt != 0) return rslt;
return h4.CompareTo(other.h4);
}
}
그런 다음 약 3.2GB를 차지하는 이러한 배열을 만들 수 있습니다. Array.BinarySearch로 쉽게 검색 할 수 있습니다 .
물론 사용자의 입력을 ASCII에서 해당 해시 코드 구조 중 하나로 변환해야하지만 이는 충분히 쉽습니다.
성능면에서 이것은 해시 테이블만큼 빠르지는 않지만 데이터베이스 조회 또는 파일 작업보다 확실히 빠를 것입니다.
생각해 보면 HashSet<MyHashCode>. 에서 Equals메서드 를 재정의해야 MyHashCode하지만 정말 쉽습니다. 내가 기억하는 HashSet것처럼 항목 당 24 바이트 의 비용 이 들며 더 큰 구조체의 추가 비용이 발생합니다. 당신이 있다면 그림 5 육기가바이트, 총은을 사용합니다 HashSet. 더 많은 메모리이지만 여전히 가능하며 O (1) 조회를 얻습니다.
이 답변은 문자열 메모리를 응용 프로그램에 반영하지 않습니다. .NET에서 문자열은 1 문자 == 1 바이트가 아닙니다. 각 문자열 개체에는 개체 데이터에 대해 상수 20 바이트가 필요합니다. 그리고 버퍼에는 문자 당 2 바이트가 필요합니다. 따라서 문자열 인스턴스의 메모리 사용량 추정치는 20 + (2 * Length) 바이트입니다.
수학을 좀 해봅시다.
- 100,000,000 개의 고유 한 문자열
- SHA256 = 32 바이트 (256 비트)
- 각 문자열의 크기 = 20 + (2 * 32 바이트) = 84 바이트
- 필요한 총 메모리 : 8,400,000,000 바이트 = 8.01GB
그렇게 할 수는 있지만 .NET 메모리에 잘 저장되지 않습니다. 목표는이 모든 데이터를 메모리에 한 번에 저장하지 않고도 액세스 / 페이징 할 수있는 양식으로로드하는 것입니다. 이를 위해 Lucene.net디스크에 데이터를 저장하고 지능적으로 검색하는 것을 사용합니다. 검색 가능한 각 문자열을 색인에 기록한 다음 색인에서 문자열을 검색합니다. 이제이 문제를 처리 할 수있는 확장 가능한 앱이 있습니다. 유일한 제한은 디스크 공간입니다 (테라 바이트 드라이브를 채우려면 많은 문자열이 필요함). 또는 이러한 레코드를 데이터베이스에 넣고 쿼리합니다. 이것이 데이터베이스가 존재하는 이유입니다. RAM 외부에서 사물을 유지하는 것입니다. :)
최대 속도를 얻으려면 RAM에 보관하십시오. 데이터 구조에 필요한 오버 헤드는 모두 3GB에 불과합니다. A HashSet<byte[]>는 잘 작동합니다. 오버 헤드와 GC 압력을 낮추려면 <gcAllowVeryLargeObjects>를 켜고 단일 byte[], 및 HashSet<int>사용자 지정 비교 자와 함께 인덱싱을 사용합니다.
속도와 낮은 메모리 사용량을 위해 디스크 기반 해시 테이블에 저장하십시오. 단순성을 위해 데이터베이스에 저장하십시오.
무엇을하든 문자열이 아닌 일반 바이너리 데이터로 저장해야합니다.
해시 세트는 데이터를 버킷 (배열)으로 분할합니다. 64 비트 시스템에서 어레이의 크기 제한은 2GB 이며 약 2,000,000,000 바이트입니다.
문자열은 참조 유형이고 참조는 8 바이트 (64 비트 시스템 가정)를 사용하므로 각 버킷은 문자열에 대한 약 250,000,000 (2 억 5 천만) 참조를 보유 할 수 있습니다. 필요한 것보다 훨씬 더 많은 것 같습니다.
즉, Tim S.가 지적했듯이 참조가 해시 세트에 맞더라도 문자열 자체를 유지하는 데 필요한 메모리가있을 가능성은 거의 없습니다. 데이터베이스가 이것에 훨씬 더 적합 할 것입니다.
대부분의 언어로 된 대부분의 컬렉션은 이러한 종류의 규모에 맞게 설계되거나 최적화되지 않았기 때문에 이러한 종류의 상황에서주의해야합니다. 이미 확인 했으므로 메모리 사용량도 문제가 될 것입니다.
여기서 확실한 승자는 어떤 형태의 데이터베이스를 사용하는 것입니다. SQL 데이터베이스 또는 적절한 NoSQL 데이터베이스가 많이 있습니다.
SQL 서버는 이미 많은 양의 데이터를 추적하고 인덱싱하며 해당 인덱스에서 검색 및 쿼리하도록 설계 및 최적화되어 있습니다. 그것은 당신이하려는 일을 정확하게 수행하도록 설계되었으므로 실제로 가장 좋은 방법이 될 것입니다.
성능을 위해 프로세스 내에서 실행되고 결과적인 통신 오버 헤드를 절약 할 임베디드 데이터베이스 사용을 고려할 수 있습니다. Java의 경우 해당 목적을 위해 Derby 데이터베이스를 추천 할 수 있습니다. C #에 해당하는 항목을 충분히 알지 못하지만 적절한 데이터베이스가 존재한다고 생각합니다.
(클러스터형 인덱싱 된) 테이블의 모든 레코드를 덤프하고 (가급적이면 문자열 표현이 아닌 해당 값을 사용 (2)) SQL에서 검색을 수행하는 데 시간이 걸릴 수 있습니다 (1). 이진 검색을 처리하고 캐싱을 처리하며 목록을 변경해야하는 경우 작업하기 가장 쉬운 방법 일 것입니다. 그리고 쿼리하는 것이 직접 만드는 것보다 빠르거나 빠를 것이라고 확신합니다.
(1) : 데이터를로드하려면 SqlBulkCopy 개체를 살펴보십시오. ADO.NET 또는 Entity Framework 와 같은 항목 은 행 단위로 데이터를로드 할 때 너무 느려집니다.
(2) : SHA-256 = 256 비트이므로 binary (32)가 수행합니다. 현재 사용중인 64 자의 절반에 불과합니다. (또는 유니 코드 숫자 = P를 사용하는 경우 1/4 ) 그런 다음 현재 일반 텍스트 파일에 정보가있는 경우 여전히 char (64) 방식으로 이동하고 다음을 사용하여 테이블의 데이터를 덤프 할 수 있습니다. bcp.exe. 데이터베이스가 더 커지고 쿼리가 약간 느려집니다 (더 많은 I / O가 필요하고 캐시가 동일한 양의 RAM에 대한 정보의 절반 만 보유 함).하지만 그렇게하는 것은 매우 간단합니다. 결과가 마음에 들지 않으면 자신의 데이터베이스 로더를 작성할 수 있습니다.
세트가 상수이면 큰 정렬 된 해시 목록을 만듭니다 (원시 형식, 각각 32 바이트). 디스크 섹터 (4KB)에 맞도록 모든 해시를 저장하고 각 섹터의 시작도 해시의 시작이되도록합니다. 메모리에 쉽게 들어갈 수있는 특수 인덱스 목록의 모든 N 번째 섹터에있는 첫 번째 해시를 저장합니다. 이 인덱스 목록에서 이진 검색을 사용하여 해시가 있어야하는 섹터 클러스터의 시작 섹터를 확인한 다음이 섹터 클러스터 내에서 다른 이진 검색을 사용하여 해시를 찾습니다. N 값은 테스트 데이터로 측정하여 결정해야합니다.
편집 : 대안은 디스크에 자신의 해시 테이블을 구현하는 것입니다. 테이블은 열린 주소 지정 전략을 사용해야하며 프로브 시퀀스는 가능한 한 동일한 디스크 섹터로 제한되어야합니다. 빈 슬롯은 특수 값 (예 : 모두 0)으로 표시되어야하므로이 특수 값은 존재 여부를 쿼리 할 때 특별히 처리되어야합니다. 충돌을 피하기 위해 테이블은 값으로 80 % 이상 채워서는 안됩니다. 따라서 32 바이트 크기의 1 억 항목이있는 경우 테이블에 최소 100M / 80 % = 1 억 2500 만 개의 슬롯이 있어야하며 크기가 있어야합니다. 125M * 32 = 4GB. 2 ^ 256 도메인을 125M으로 변환하는 해싱 함수와 멋진 프로브 시퀀스 만 생성하면됩니다.
접미사 트리를 사용해 볼 수 있습니다 .이 질문 은 C #에서 수행하는 방법에 대해 설명합니다.
또는 다음과 같은 검색을 시도 할 수 있습니다.
var matches = list.AsParallel().Where(s => s.Contains(searchTerm)).ToList();
AsParallel은 쿼리의 병렬화를 생성하므로 속도를 높이는 데 도움이됩니다.
- 해시를 UInt32 [8]로 저장
2a. 정렬 된 목록을 사용합니다. 두 해시를 비교하려면 먼저 첫 번째 요소를 비교하십시오. 그들이 같으면 두 번째 것을 비교하는 식입니다.
2b. 접두사 트리 사용
우선 리소스 소비를 최소화하기 위해 데이터 압축을 사용하는 것이 좋습니다. 캐시 및 메모리 대역폭은 일반적으로 최신 컴퓨터에서 가장 제한된 리소스입니다. 이를 어떻게 구현하든 가장 큰 병목 현상은 데이터를 기다리고 있습니다.
또한 기존 데이터베이스 엔진을 사용하는 것이 좋습니다. 그들 중 대부분은 내장 압축 기능이 있으며 모든 데이터베이스는 사용 가능한 RAM을 사용합니다. 괜찮은 운영 체제를 가지고 있다면 시스템 캐시는 가능한 한 많은 파일을 저장합니다. 그러나 대부분의 데이터베이스에는 자체 캐싱 하위 시스템이 있습니다.
어떤 db 엔진이 당신에게 가장 좋을지 정말 말할 수 없습니다. 개인적으로 저는 종종 성능이 좋고 인 메모리 및 파일 기반 데이터베이스로 사용할 수 있으며 투명한 압축으로 빌드 된 H2를 사용합니다.
일부 사용자는 데이터를 데이터베이스로 가져오고 검색 색인을 작성하는 데 일부 사용자 지정 솔루션보다 시간이 더 오래 걸릴 수 있다고 말했습니다. 사실 일 수도 있지만 수입은 일반적으로 매우 드문 일입니다. 빠른 검색이 가장 일반적인 작업 일 가능성이 높으므로 빠른 검색에 더 관심이 있다고 가정하겠습니다.
또한 SQL 데이터베이스가 안정적이고 매우 빠른 이유는 NoSQL 데이터베이스를 고려하는 것이 좋습니다. 몇 가지 대안을 시도해보십시오. 어떤 솔루션이 최고의 성능을 제공하는지 알 수있는 유일한 방법은 벤치마킹하는 것입니다.
또한 목록을 텍스트로 저장하는 것이 타당한 지 고려해야합니다. 목록을 숫자 값으로 변환해야 할 수도 있습니다. 공간을 덜 사용하므로 쿼리 속도가 빨라집니다. 데이터베이스 가져 오기는 상당히 느릴 수 있지만 쿼리는 훨씬 빨라질 수 있습니다.
정말 빠른 속도를 원하고 요소가 다소 불변하고 정확한 일치가 필요한 경우 바이러스 스캐너처럼 작동하는 것을 빌드 할 수 있습니다. 항목과 관련된 알고리즘을 사용하여 잠재적 요소의 최소 수를 수집하도록 범위를 설정하고 검색 기준을 찾은 다음 RtlCompareMemory를 사용하여 검색 항목에 대해 테스트하면서 해당 항목을 반복합니다. 항목이 상당히 연속적이면 디스크에서 항목을 가져와 다음과 같이 비교할 수 있습니다.
private Boolean CompareRegions(IntPtr hFile, long nPosition, IntPtr pCompare, UInt32 pSize)
{
IntPtr pBuffer = IntPtr.Zero;
UInt32 iRead = 0;
try
{
pBuffer = VirtualAlloc(IntPtr.Zero, pSize, MEM_COMMIT, PAGE_READWRITE);
SetFilePointerEx(hFile, nPosition, IntPtr.Zero, FILE_BEGIN);
if (ReadFile(hFile, pBuffer, pSize, ref iRead, IntPtr.Zero) == 0)
return false;
if (RtlCompareMemory(pCompare, pBuffer, pSize) == pSize)
return true; // equal
return false;
}
finally
{
if (pBuffer != IntPtr.Zero)
VirtualFree(pBuffer, pSize, MEM_RELEASE);
}
}
이 예제를 수정하여 항목으로 가득 찬 큰 버퍼를 가져 와서 반복합니다. 그러나 관리되는 코드는 갈 길이 아닙니다 .. 가장 빠른 것은 항상 실제 작업을 수행하는 호출에 더 가깝기 때문에 커널 모드 액세스 권한이있는 드라이버가 곧바로 C로 빌드되는 것이 훨씬 빠릅니다 ..
첫째, 문자열이 실제로 SHA256 해시라고 말합니다. 그 관찰 100 million * 256 bits = 3.2 gigabytes은 메모리에 전체 목록을 맞게 할 수 있도록 메모리 효율적인 데이터 구조를 사용하는 가정.
가끔 오탐을 용서하면 실제로 그보다 적은 메모리를 사용할 수 있습니다. 블룸 필터 참조 http://billmill.org/bloomfilter-tutorial/
그렇지 않으면 정렬 된 데이터 구조를 사용하여 빠른 쿼리를 수행합니다 (시간 복잡도 O (log n)).
자주 쿼리하고 빠른 결과가 필요하기 때문에 데이터를 메모리에 저장하고 싶다면 Redis를 사용해보세요. http://redis.io/
Redis는 오픈 소스, BSD 라이선스, 고급 키-값 저장소입니다. 키에는 문자열, 해시, 목록, 집합 및 정렬 된 집합이 포함될 수 있으므로 데이터 구조 서버 라고도 합니다.
세트 데이터 유형 http://redis.io/topics/data-types#sets
Redis 세트는 정렬되지 않은 문자열 모음입니다. O (1)에서 구성원의 존재 여부를 추가, 제거 및 테스트 할 수 있습니다 (Set에 포함 된 요소 수에 관계없이 일정 시간).
그렇지 않으면 디스크에 데이터를 저장하는 데이터베이스를 사용하십시오.
A plain vanilla binary search tree will give excellent lookup performance on large lists. However, if you don't really need to store the strings and simple membership is what you want to know, a Bloom Filter may be a terric solution. Bloom filters are a compact data structure that you train with all the strings. Once trained, it can quickly tell you if it has seen a string before. It rarely reports.false positives, but never reports false negatives. Depending on the application, they can produce amazing results quickly and with relatively little memory.
Insta의 접근 방식 과 유사한 솔루션을 개발 했지만 약간의 차이점이 있습니다. 실제로는 그의 청크 배열 솔루션과 매우 유사합니다. 그러나 단순히 데이터를 분할하는 대신 내 접근 방식은 청크 인덱스를 작성하고 적절한 청크에만 검색을 지시합니다.
인덱스가 작성되는 방식은 해시 테이블과 매우 유사하며 각 버킷은 이진 검색으로 검색 할 수있는 정렬 된 배열입니다. 그러나 저는 SHA256 해시의 해시를 계산하는 데 별 의미가 없다고 생각했기 때문에 대신 값의 접두사를 사용합니다.
이 기술의 흥미로운 점은 인덱스 키의 길이를 확장하여 조정할 수 있다는 것입니다. 긴 키는 더 큰 인덱스와 더 작은 버킷을 의미합니다. 내 8 비트 테스트 케이스는 아마도 작은 편일 것이다. 아마도 10-12 비트가 더 효과적 일 것입니다.
이 접근 방식을 벤치마킹하려고했지만 빠르게 메모리가 부족하여 성능 측면에서 흥미로운 것을 볼 수 없었습니다.
C 구현도 작성했습니다. C 구현은 지정된 크기의 데이터 세트도 처리 할 수 없었지만 (테스트 머신에는 4GB의 RAM 만 있음) 다소 더 많은 것을 관리했습니다. (이 경우 대상 데이터 세트는 실제로 그다지 문제가되지 않았습니다. 테스트 데이터가 RAM을 가득 채웠습니다.) 실제로 데이터를 처리 할 수있을만큼 빠르게 데이터를 처리 할 수있는 좋은 방법을 찾지 못했습니다. 성능 테스트를 참조하십시오.
이 글을 쓰는 것을 즐겼지만 전반적으로 C #으로 메모리에서 이것을 시도해서는 안된다는 주장에 찬성하는 증거를 제공한다고 말하고 싶습니다.
public interface IKeyed
{
int ExtractKey();
}
struct Sha256_Long : IComparable<Sha256_Long>, IKeyed
{
private UInt64 _piece1;
private UInt64 _piece2;
private UInt64 _piece3;
private UInt64 _piece4;
public Sha256_Long(string hex)
{
if (hex.Length != 64)
{
throw new ArgumentException("Hex string must contain exactly 64 digits.");
}
UInt64[] pieces = new UInt64[4];
for (int i = 0; i < 4; i++)
{
pieces[i] = UInt64.Parse(hex.Substring(i * 8, 1), NumberStyles.HexNumber);
}
_piece1 = pieces[0];
_piece2 = pieces[1];
_piece3 = pieces[2];
_piece4 = pieces[3];
}
public Sha256_Long(byte[] bytes)
{
if (bytes.Length != 32)
{
throw new ArgumentException("Sha256 values must be exactly 32 bytes.");
}
_piece1 = BitConverter.ToUInt64(bytes, 0);
_piece2 = BitConverter.ToUInt64(bytes, 8);
_piece3 = BitConverter.ToUInt64(bytes, 16);
_piece4 = BitConverter.ToUInt64(bytes, 24);
}
public override string ToString()
{
return String.Format("{0:X}{0:X}{0:X}{0:X}", _piece1, _piece2, _piece3, _piece4);
}
public int CompareTo(Sha256_Long other)
{
if (this._piece1 < other._piece1) return -1;
if (this._piece1 > other._piece1) return 1;
if (this._piece2 < other._piece2) return -1;
if (this._piece2 > other._piece2) return 1;
if (this._piece3 < other._piece3) return -1;
if (this._piece3 > other._piece3) return 1;
if (this._piece4 < other._piece4) return -1;
if (this._piece4 > other._piece4) return 1;
return 0;
}
//-------------------------------------------------------------------
// Implementation of key extraction
public const int KeyBits = 8;
private static UInt64 _keyMask;
private static int _shiftBits;
static Sha256_Long()
{
_keyMask = 0;
for (int i = 0; i < KeyBits; i++)
{
_keyMask |= (UInt64)1 << i;
}
_shiftBits = 64 - KeyBits;
}
public int ExtractKey()
{
UInt64 keyRaw = _piece1 & _keyMask;
return (int)(keyRaw >> _shiftBits);
}
}
class IndexedSet<T> where T : IComparable<T>, IKeyed
{
private T[][] _keyedSets;
public IndexedSet(IEnumerable<T> source, int keyBits)
{
// Arrange elements into groups by key
var keyedSetsInit = new Dictionary<int, List<T>>();
foreach (T item in source)
{
int key = item.ExtractKey();
List<T> vals;
if (!keyedSetsInit.TryGetValue(key, out vals))
{
vals = new List<T>();
keyedSetsInit.Add(key, vals);
}
vals.Add(item);
}
// Transform the above structure into a more efficient array-based structure
int nKeys = 1 << keyBits;
_keyedSets = new T[nKeys][];
for (int key = 0; key < nKeys; key++)
{
List<T> vals;
if (keyedSetsInit.TryGetValue(key, out vals))
{
_keyedSets[key] = vals.OrderBy(x => x).ToArray();
}
}
}
public bool Contains(T item)
{
int key = item.ExtractKey();
if (_keyedSets[key] == null)
{
return false;
}
else
{
return Search(item, _keyedSets[key]);
}
}
private bool Search(T item, T[] set)
{
int first = 0;
int last = set.Length - 1;
while (first <= last)
{
int midpoint = (first + last) / 2;
int cmp = item.CompareTo(set[midpoint]);
if (cmp == 0)
{
return true;
}
else if (cmp < 0)
{
last = midpoint - 1;
}
else
{
first = midpoint + 1;
}
}
return false;
}
}
class Program
{
//private const int NTestItems = 100 * 1000 * 1000;
private const int NTestItems = 1 * 1000 * 1000;
private static Sha256_Long RandomHash(Random rand)
{
var bytes = new byte[32];
rand.NextBytes(bytes);
return new Sha256_Long(bytes);
}
static IEnumerable<Sha256_Long> GenerateRandomHashes(
Random rand, int nToGenerate)
{
for (int i = 0; i < nToGenerate; i++)
{
yield return RandomHash(rand);
}
}
static void Main(string[] args)
{
Console.WriteLine("Generating test set.");
var rand = new Random();
IndexedSet<Sha256_Long> set =
new IndexedSet<Sha256_Long>(
GenerateRandomHashes(rand, NTestItems),
Sha256_Long.KeyBits);
Console.WriteLine("Testing with random input.");
int nFound = 0;
int nItems = NTestItems;
int waypointDistance = 100000;
int waypoint = 0;
for (int i = 0; i < nItems; i++)
{
if (++waypoint == waypointDistance)
{
Console.WriteLine("Test lookups complete: " + (i + 1));
waypoint = 0;
}
var item = RandomHash(rand);
nFound += set.Contains(item) ? 1 : 0;
}
Console.WriteLine("Testing complete.");
Console.WriteLine(String.Format("Found: {0} / {0}", nFound, nItems));
Console.ReadKey();
}
}
'Program Club' 카테고리의 다른 글
| Python은 키 목록이 사전에 있는지 확인합니다. (0) | 2020.11.16 |
|---|---|
| jQuery promise를 사용하여 3 개의 비동기 호출을 어떻게 연결합니까? (0) | 2020.11.16 |
| 데이터베이스가없는 Rails 모델 (0) | 2020.11.16 |
| C ++ 게터 / 세터 코딩 스타일 (0) | 2020.11.16 |
| 루비에서 문자열을 숫자와 연결 (0) | 2020.11.16 |