슈퍼 하이 퍼포먼스 C/C++ 해시 맵(표, 사전)
원시 키(int, 긴 키)를 고성능 해시 맵 데이터 구조의 구조 값에 매핑해야 합니다.
제 프로그램에는 수백 개의 지도가 있고, 각 지도에는 기껏해야 수천 개의 엔트리가 있습니다.입니다. 의 "" 또는 "새롭게" 또는 "새롭게" 처리되는 을 상상해 보십시오. 수백만 개의 맵을 처리하는 것을 상상해 보십시오.add ★★★★★★★★★★★★★★★★★」delete1번
C 또는 C++의 어떤 라이브러리가 이 사용 사례에 적합한 데이터 구조를 가지고 있습니까?아니면, 어떻게 직접 만드는 것을 추천하시겠습니까?감사합니다!
Google Sparse Hash(또는 C11 버전 Google Sparse Hash-c11)를 사용해 보고, 고객의 요구에 적합한지 확인해 보는 것을 추천합니다.메모리 효율이 뛰어난 실장과 속도에 최적화된 실장 기능을 갖추고 있습니다.오래 전에 벤치마크를 실시했습니다만, 속도 면에서는 최고의 해시 테이블 실장이었습니다(단점은 있었지만).
카슈슈는 매우 효율적입니다.저자의 상세한 벤치마크는 https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/이며, 또한 카슈끄지가 다른 많은 해시 라이브러리를 능가한다는 것을 보여준다.
C 또는 C++의 어떤 라이브러리가 이 사용 사례에 적합한 데이터 구조를 가지고 있습니까?아니면, 어떻게 직접 만드는 것을 추천하시겠습니까?감사합니다!
LGPLd Judy 어레이를 확인해 주세요.나 자신을 사용한 적은 없지만, 몇 번인가 나에게 광고되었다.
STL 컨테이너(std::hash_map 등)를 벤치마킹할 수도 있습니다.플랫폼/실장 및 소스 코드 튜닝(동적 메모리 관리에는 가능한 한 많은 비용이 소요됨)에 따라서는 충분한 퍼포먼스를 얻을 수 있습니다.
또, 최종 솔루션의 퍼포먼스가 솔루션의 코스트를 웃돌고 있는 경우는, 모든 것을 플레인 어레이에 격납할 수 있는 충분한 RAM을 탑재한 시스템을 발주할 수 있습니다.인덱스별 액세스 성능은 타의 추종을 불허합니다.
추가/삭제 조작은 get 조작보다 훨씬(100배) 빈도가 높습니다.
이는 먼저 알고리즘 개선에 주력해야 한다는 것을 암시합니다.데이터가 읽기보다 쓰기만 한다면, 왜 데이터를 쓰겠습니까?
쓰세요.boost::unordered_map (오류)tr1을 사용하다그런 다음 코드를 프로파일링하고 코드가 병목 현상인지 확인합니다.그 때 보다 빠른 대체품을 찾기 위해 당신의 요구 사항을 정밀하게 분석할 것을 제안합니다.
Android 소스(따라서 Apache 2 라이센스가 있음)에서 제공됨
https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils
hashmap.c를 보고 include/cutils/cutils/sublicmap.h를 선택합니다.스레드 안전성이 필요 없는 경우 뮤텍스 코드를 삭제할 수 있습니다.실장 예는 libcutils/str_parms.c에 있습니다.
기타 컨테이너 템플릿의 해시 테이블을 사용해 보십시오.그것의.closed_hash_map★★★★★★★★★★★★★★★★★★★★★★★★★★★★와 거의 같은 속도입니다.dense_hash_map값에 ), 그.
먼저 libmemcache와 같은 기존 솔루션이 고객의 요구에 적합한지 확인합니다.
그렇지 않으면...
해시맵이 당신의 요구에 대한 확실한 답변인 것 같습니다.키에 근거한 o(1) 룩업을 제공합니다.오늘날 대부분의 STL 라이브러리는 일종의 해시를 제공합니다.플랫폼이 제공하는 것을 사용합니다.
해당 부품이 완료되면 솔루션을 테스트하여 기본 해시 알고리즘이 필요에 따라 충분한 성능을 발휘하는지 확인해야 합니다.
그렇지 않은 경우, 인터넷상에서 찾을 수 있는 적절한 고속 해싱 알고리즘을 조사해야 합니다.
- 좋은 옛 소수 곱셈 알고
- http://www.azillionmonkeys.com/qed/hash.html
- http://burtleburtle.net/bob/
- http://code.google.com/p/google-sparsehash/
이 방법으로 충분치 않은 경우 테스트한 STL 컨테이너와 위의 해시 알고리즘 중 하나에서 발생한 문제를 수정하는 해시 모듈을 직접 롤링할 수 있습니다.반드시 결과를 어딘가에 게시하십시오.
오, 그리고 흥미로운 건 네가 지도를 여러 개 가지고 있다는 거야...어떤 맵에 속하는지를 구별하고 모든 키 값의 쌍을 하나의 거대한 해시에 추가하기 위해 사용되는 높은 비트를 가진 64비트 num으로 하여 키를 단순화할 수 있습니다.기본 소수 해싱 알고리즘에서 10만 개 정도의 기호가 완벽하게 작동하는 해시를 본 적이 있습니다.
수백 개의 맵과 비교하여 솔루션의 성능을 확인할 수 있습니다.기억 프로파일링 관점에서 보면 그게 더 나을 것 같아이 연습을 하게 되면 결과를 어딘가에 게시해 주세요
해시 알고리즘보다 메모리의 계속적인 추가/삭제(회피할 수 있는가)와 CPU 캐시 사용 프로파일이 애플리케이션 성능에 더 중요하다고 생각합니다.
행운을 빌어요
우타쉬를 추천합니다.포함시키기만 하면 됩니다.#include "uthash.h"그런 다음 a를 추가합니다.UT_hash_handle구조물에서 키 역할을 할 필드를 하나 이상 선택합니다.퍼포먼스에 대해서 한 말씀 드리겠습니다.
멀티스레드 프로그램이 있는 경우 인텔 스레드 빌딩 블록 라이브러리에서 유용한 해시 테이블을 찾을 수 있습니다.예를 들어 tbb::concurrent_unordered_map은 std::unordered_map과 동일한 api를 가지지만 주요 함수는 스레드 세이프입니다.
또한 Facebook의 바보같은 라이브러리도 보세요. 그것은 고성능 동시 해시 테이블과 스킵 리스트를 가지고 있습니다.
http://incise.org/hash-table-benchmarks.html gcc는 매우 좋은 구현입니다.단, 매우 나쁜 표준 결정을 존중해야 합니다.
재해시가 발생하면 모든 반복기는 비활성화되지만 개별 요소에 대한 참조 및 포인터는 유효한 상태로 유지됩니다.실제 리해시가 발생하지 않으면 변경되지 않습니다.
http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/
이는 기본적으로 표준에서 구현은 링크된 목록에 기반해야 한다고 명시되어 있음을 의미합니다.오픈 어드레싱이 방지되어 퍼포먼스가 향상됩니다.
구글 스파스는 오픈 어드레싱을 사용하고 있다고 생각합니다만, 이러한 벤치마크에서는 고밀도 버전만이 경쟁사보다 우수합니다.그러나 sparse 버전은 메모리 사용률에서 모든 경쟁 제품보다 우수합니다.(또한 고원, 순수 직선 wrt 개수의 요소가 없습니다)
언급URL : https://stackoverflow.com/questions/3300525/super-high-performance-c-c-hash-map-table-dictionary
'programing' 카테고리의 다른 글
| Java에서 명령줄 인수를 해석하려면 어떻게 해야 합니까? (0) | 2022.07.18 |
|---|---|
| 대신 프로펠러 값을 기반으로 데이터 또는 계산된 속성을 사용하십시오.Vue JS (0) | 2022.07.18 |
| instance of와 Class.isAssignableFrom(...)의 차이점은 무엇입니까? (0) | 2022.07.17 |
| TypeScript를 사용하여 Vue 컴포넌트를 프로그래밍 방식으로 생성합니다. (0) | 2022.07.17 |
| v-model이 jQuery 트리거 이벤트의 변경 사항을 감지하지 못함 (0) | 2022.07.17 |