Microsoft MVP성태의 닷넷 이야기
.NET Framework: 433. C# - 간단한 HyperLogLog 자료 구조 테스트 [링크 복사], [링크+제목 복사],
조회: 20497
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일

C# - 간단한 HyperLogLog 자료 구조 테스트

재미있는 글이 하나 소개되었습니다. ^^

확률적 자료구조를 이용한 추정 - 유일한 원소 개수(Cardinality) 추정과 HyperLogLog 
; https://d2.naver.com/helloworld/711301

위의 글에 나온대로 "HyperLogLog는 매우 적은 메모리로 집합의 원소 개수를 추정할 수 있는 방법"입니다. 물론, 적은 메모리라는 장점을 위해 "정확성"을 희생하는 식인데요. 사실, '정확성'이 그다지 중요하지 않을때가 생각보다 많기 때문에 응용할 곳은 제법 많습니다.

예를 들어, 구글의 검색어에 대한 예상 결과 수를 보여주는 기능이 바로 그러한 사례 중의 하나입니다.

http://www.google.com/webhp?complete=1&hl=en 검색에 관해서
; https://www.sysnet.pe.kr/2/0/96

"ebay" 검색어를 포함한 웹 페이지 수가 10,000개로 대략 나오든지, 아니면 11,382개라고 정확하게 나오든지 사용자에게 크게 영향을 주는 것은 아닙니다. 하지만, 구현하는 입장에서 볼 때 그걸 정확하게 구하기 위해서는 적지 않은 오버헤드가 수반될 수 있습니다.




이론적인 설명은 "확률적 자료구조를 이용한 추정 - 유일한 원소 개수(Cardinality) 추정과 HyperLogLog" 글에서 너무나 잘해주고 있으므로 여기서는 C#으로 간단하게 실습하는 것을 소개하겠습니다.

일단, 검색해 보면 이미 ^^ C# 구현체가 있으니 이걸 사용하겠습니다.

HyperLogLog C# implementation 
; http://adnan-korkmaz.blogspot.kr/2012/06/hyperloglog-c-implementation.html

또한, 유일한 단어 수를 계산하는 것 대신 전체가 유일 항목임을 보증하는 임의의 GUID 수를 생성해서 테스트 해보았습니다.

HyperLogLog log = new HyperLogLog(0.01);
HashSet<string> dict = new HashSet<string>();

for (int i = 0; i < 100; i++)
{ 
    string txt = Guid.NewGuid().ToString();

    log.Add(txt);

    bool result = dict.Contains(txt);
    if (result == false)
    {
        dict.Add(txt);
    }
}

Console.WriteLine("CountFromHash: " + dict.Count());
Console.WriteLine("CountFromHyperLogLog: " + log.Count());

// 출력결과
CountFromHash: 100
CountFromHyperLogLog: 100

일단, 100개로 시작했을 때 HashSet으로 하든 HyperLogLog로 하든 계산된 수는 100으로 동일했습니다. 단지, 가끔 특정 GUID 조합에서는 Hash 코드가 치우치는 탓인지 HyperLogLog의 경우 98~99를 출력하기도 합니다.

수를 늘리면 점차로 차이가 뚜렷해지기 시작합니다.

==== 10,000개인 경우 ====

CountFromHash: 10000
CountFromHyperLogLog: 9976

==== 100,000개인 경우 ====

CountFromHash: 100000
CountFromHyperLogLog: 100638

100000000까지 늘리면 이제 (x64에서조차도) HashSet으로는 Out of memory로 인해 더 이상 테스트가 되지 않습니다. 반면 HyperLogLog에서는 놀라운 메모리 사용량을 보여줍니다.

==== 100,000,000개인 경우 ====

CountFromHash: OOM 발생
CountFromHyperLogLog: 101648822 (메모리 사용량: 4.8MB)

게다가 오차도 0.01%수준으로 괜찮은 정확도를 보여줍니다.

한 가지 재미있는 것이 있다면, HyperLogLog.Add 메서드에 전달된 object 인자를 별도의 getHashCode 메서드를 이용해 구한다는 것입니다.

public static uint getHashCode(string text)
{
    uint hash = 0;

    for (int i = 0, l = text.Length; i < l; i++)
    {
        hash += (uint)text[i];
        hash += hash << 10;
        hash ^= hash >> 6;
    }
    hash += hash << 3;
    hash ^= hash >> 6;
    hash += hash << 16;

    return hash;
}

이것을 .NET Framework의 Object.GetHashCode()로 치환해도 결과가 거의 비슷했습니다.

public static uint getHashCode(string text)
{
    return (uint)text.GetHashCode();
}

참고로, Hash 코드를 구하는 것에는 정답이 없습니다. 아래의 글에서도 이야기했었지만,

괜찮은 문자열 해시 함수?
; https://www.sysnet.pe.kr/2/0/1222

해시 함수는, 결국 해당 '업무 도메인'에서 사용되는 문자열 셋이 다르기 때문에 (가능하다면) 그에 따른 적절한 테스트를 해보고 선택하시는 것이 좋습니다.


(첨부 파일은 이 글의 테스트 코드를 포함하고 있습니다.)





[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]







[최초 등록일: ]
[최종 수정일: 7/25/2022]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 




... 46  47  48  49  50  51  52  53  54  [55]  56  57  58  59  60  ...
NoWriterDateCnt.TitleFile(s)
12439정성태12/4/202013751디버깅 기술: 176. windbg - 특정 Win32 API에서 BP가 안 걸리는 경우 (2) [1]
12438정성태12/2/202013722오류 유형: 688. .Visual C++ - Error C2011 'sockaddr': 'struct' type redefinition
12437정성태12/1/202013391VS.NET IDE: 155. pfx의 암호 키 파일을 Visual Studio 없이 등록하는 방법
12436정성태12/1/202013582오류 유형: 687. .NET Core 2.2 빌드 - error MSB4018: The "RazorTagHelper" task failed unexpectedly.
12435정성태12/1/202019668Windows: 181. 윈도우 환경에서 클라이언트 소켓의 최대 접속 수 (4) - ReuseUnicastPort를 이용한 포트 고갈 문제 해결 [1]파일 다운로드1
12434정성태11/30/202014405Windows: 180. C# - dynamicport 값의 범위를 알아내는 방법
12433정성태11/29/202013531Windows: 179. 윈도우 환경에서 클라이언트 소켓의 최대 접속 수 (3) - SO_PORT_SCALABILITY파일 다운로드1
12432정성태11/29/202014882Windows: 178. 윈도우 환경에서 클라이언트 소켓의 최대 접속 수 (2) - SO_REUSEADDR [1]파일 다운로드1
12431정성태11/27/202012177.NET Framework: 976. UnmanagedCallersOnly + C# 9.0 함수 포인터 사용 시 x86 빌드에서 오동작하는 문제파일 다운로드1
12430정성태11/27/202013286오류 유형: 686. Ubuntu - E: The repository 'cdrom://...' does not have a Release file.
12429정성태11/25/202013754디버깅 기술: 175. windbg - 특정 Win32 API에서 BP가 안 걸리는 경우
12428정성태11/25/202012096VS.NET IDE: 154. Visual Studio - .NET Core App 실행 시 dotnet.exe 실행 화면만 나오는 문제
12427정성태11/24/202013521.NET Framework: 975. .NET Core를 직접 호스팅해 (runtimeconfig.json 없이) EXE만 배포해 실행파일 다운로드1
12426정성태11/24/202011777오류 유형: 685. WinDbg Preview - error InitTypeRead
12425정성태11/24/202013199VC++: 141. Visual C++ - "Treat Warnings As Errors" 옵션이 꺼져 있는데도 일부 경고가 에러 처리되는 경우
12424정성태11/24/202013662VC++: 140. C++의 연산자 동의어(operator synonyms), 대체 토큰 [1]
12423정성태11/22/202014467.NET Framework: 974. C# 9.0 - (16) 제약 조건이 없는 형식 매개변수 주석(Unconstrained type parameter annotations)파일 다운로드1
12422정성태11/21/202012191.NET Framework: 973. .NET 5, .NET Framework에서만 허용하는 UnmanagedCallersOnly 사용예파일 다운로드1
12421정성태11/19/202011565.NET Framework: 972. DNNE가 출력한 NE DLL을 직접 생성하는 방법파일 다운로드1
12420정성태11/19/202011006오류 유형: 684. Visual C++ - MSIL .netmodule or module compiled with /GL found; restarting link with /LTCG; add /LTCG to the link command line to improve linker performance
12419정성태11/19/202012426VC++: 139. Visual C++ - .NET Core의 nethost.lib와 정적 링크파일 다운로드1
12418정성태11/19/202014572오류 유형: 683. Visual C++ - error LNK2038: mismatch detected for 'RuntimeLibrary': value 'MT_StaticRelease' doesn't match value 'MDd_DynamicDebug'파일 다운로드1
12417정성태11/19/202011780오류 유형: 682. Visual C++ - warning LNK4099: PDB '...pdb' was not found with '...lib(pch.obj)' or at '...pdb'; linking object as if no debug info
12416정성태11/19/202012934오류 유형: 681. Visual C++ - error LNK2001: unresolved external symbol _CrtDbgReport
12415정성태11/18/202013386.NET Framework: 971. UnmanagedCallersOnly 특성과 DNNE 사용파일 다운로드1
12414정성태11/18/202014652VC++: 138. x64 빌드에서 extern "C"가 아닌 경우 ___cdecl name mangling 적용 [4]파일 다운로드1
... 46  47  48  49  50  51  52  53  54  [55]  56  57  58  59  60  ...