정수 식별자를 포인터로 변환

ID 값이 unsigned int입니다. Id를 포인터에 매핑해야합니다. 일정 시간.정수 식별자를 포인터로 변환

키 배포 :

ID는 UINT_MAX 0의 범위의 값을가집니다. 대부분의 키는 단일 그룹으로 묶이지 만 이상 치가 있습니다.

구현 :

은 내가 C++ 내선 hash_map 물건을 사용하는 방법에 대한 생각,하지만 난 키가 거대한 잠재력 범위가있을 때 성능이 너무 크지 않다 들었습니다.
나는 또한 일련의 체인 된 룩업 (반복적으로 C 덩어리로 범위를 세분하는 것에 해당)을 사용하려고 생각했습니다. 범위에 키가 없으면 해당 범위는 NULL을 가리 킵니다.

N = 주요 범위

(C = 16으로 분할하므로 16 개) 등급 0 = 0/16 N), N/16, 2 * (N/16)), .. .

레벨 1 ... = (C = 16로 그래서 16 개 * 16 조각을 나누어)

다른 사람이이 매핑을보다 효율적으로 구현할 수있는 방법에 대한 아이디어가 있습니까?

업데이트 :

일정으로, 난 그냥 크게 항목의 값의 번호로 영향을받지 각 키 조회를 의미했다. 나는 그것이 하나의 작전이어야한다는 것을 의미하지는 않았다.

출처

2009-08-27 jameszhao00

또한 메모리 사용을 최소화하십시오 (위의 체인 조회와 유사 함). 크기가 KEY_RANGE 인 배열을 제안하지 마십시오.) – jameszhao00

해시지도 (unordered_map)를 사용하십시오. 이것은 ~ O (1) 룩업 시간을줍니다. 당신은 "들었습니다"라고 나 빠졌지 만 시험해 보았고, 시험하고, 문제로 판단 했습니까? 그렇지 않은 경우 해시 맵을 사용하십시오.

코드가 완료되면 코드를 프로파일 링하고 조회 시간이 프로그램의 느린 주요 원인인지 확인하십시오. 기회는 그렇습니다.

출처

2009-08-27 05:14:49 GManNickG

당신은 일정한 시간을 갖지 않을 것입니다.

나는 아마 당신의 정수 값이 넓은, 당신은 64 비트 플랫폼을 사용할 수있는 32 비트 인 경우 B+Tree

출처

2009-08-27 05:15:19 Tom

해시 맵은 대부분 일정 시간입니다. – GManNickG

@ 그만 : 해시와 키에 따라 다릅니다. – kibibu

버킷 수와 – kibibu

를 사용하는 메모리의 32 기가 바이트 (40 억 포인터 당 8 바이트), 및 사용을 할당하는 것 편평한 배열. 그것은 일정한 검색 시간을 얻으려고 할 때만큼이나 가까울 것입니다.

출처

2009-08-27 05:17:40

사이드 노트 : 64 킬로바이트가 완전히 장식 된 머신이었던 시대에 자란 우리들에게는 이것이 * 가능 * 할 수 있다는 사실은 지금 당장은 꽤나 놀라운 일입니다. –

상수로, 방금 각 키 조회가 항목의 값 수에 크게 영향을받지 않는다는 것을 의미했습니다. 나는 그것이 하나의 작전이어야한다는 것을 의미하지는 않았다. – jameszhao00

일정 시간은 같은 시간에 얻은 숫자 값과 상관없이 선형 시간이라는 것을 설명합니다. – Tom

4GB의 RAM을 예약하고 단순히 포인터를 포인터로 옮길 수 있습니다. 그것은 확실히 일정한 시간입니다.

출처

2009-08-27 05:20:04 Zed

트리 기반 솔루션을 원하고 ID가 {0 ..n-1}이면 van Emde Boas tree이라는 매우 멋진 데이터 구조를 사용할 수 있습니다. 그러면 O (로그 로그 n)의 모든 작업이 수행되고 O (n) 공간이 사용됩니다.

출처

2009-08-27 05:35:53 ttvd

안녕하세요, 멋지 답니다 – kibibu

구현하기가 매우 힘듭니다 내 경험에 의하면 :)하지만 매우 인상적입니다. – ttvd

GMan은 unordered_map이 아마도 좋은 해결책이라고 제안합니다. 이 해시 맵에서 많은 수의 충돌이 염려되는 경우 데이터 클러스터링을 제거하는 해시 함수를 사용하십시오. 예를 들어, 바이트를 스왑 할 수 있습니다.

주목할 점은 이미 좋은 혈통을 가진 것보다 사용자 정의 데이터 구조를 디버깅하고 증명하는 데 더 많은 시간을 할애해야한다는 것입니다.

출처

2009-08-27 05:55:59 PinkTriangles

얼마나 많은 항목이 그러한지도에 있어야하며 얼마나 자주 변경됩니까?

모든 값이 프로세서의 캐시에 맞으면 미리 값 및 이진 검색을 사용하는 std::vector<std::pair<unsigned int,T*>>이 액세스가 O (N) 임에도 불구하고 가장 빠를 수 있습니다.

출처

2009-08-27 09:40:13 sbi

약 200,000 개의 항목이 검색됩니다. – jameszhao00

32 비트'int'와 32 비트 포인터를 사용하면 1.6MB가됩니다. 나는이 경험이 없지만 vEB 트리와 같은 것을 구현하기 전에, 해시 값이 매우 좋은 정수를 선택하고 이진 검색을 사용하여 정렬 된'std :: vector '가 어떻게 비교되는지 알아 내려고합니다. 'std :: unordered_map'을 성능 측면에서 살펴 보겠습니다. – sbi

정수 식별자를 포인터로 변환

답변

관련 문제