메모리 효율 std :: map 대체

Question

나는 약 2 천만 개의 항목을 저장하기 위해 std::map을 사용하고 있습니다. 컨테이너 오버 헤드없이 저장 한 경우 약 650MB의 메모리가 필요합니다. 그러나 그들은 std::map을 사용하여 저장되기 때문에 약 15GB의 메모리를 사용합니다 (너무 많음).

내가 std::map을 사용하는 이유는 x과 같거나 더 크거나 작은 키를 찾아야하기 때문입니다. 이런 이유로 sparsehash 같은 것이 작동하지 않습니다. (그걸 사용하기 때문에, 비교로 키를 찾을 수 없기 때문입니다.)

std::map (또는 일반적으로 주문한지도)을 사용하면 메모리 사용량이 줄어들 수 있습니다.

편집 : 쓰기 성능은 읽기 성능보다 더 중요합니다. 많이입니다. 아마도 ~ 10 개의 항목 만 읽지 만 읽을 항목을 모릅니다. 대신 나무의 (std::vector 생각) std::map과 동일한 인터페이스를 지원하지만, 정렬 된 연속 배열에 연동하는 :

Answer 1

은std::map이 아니 었습니다.

나는 동일한 데이터의 여러 부분을 표현하기 위해 3 개의 개별지도를 사용하고 있으며이를 1로 줄이면 메모리의 차이는 완전히 무시할 수 있다는 것을 깨달았다.

코드를 조금 더 살펴보면 실제로 비싼 구조체 (지도 요소 당)를 무료로 작성한 코드가 실제로 작동하지 않는다는 것을 깨달았습니다.

이제이 부분을 수정하면 < 1GB의 메모리가 필요합니다. :)

---

TL; DR : std::map의 부담이 전적으로 무시할 수있다. 문제는 내 것이 었습니다.

Answer 2

하나의 대안은 flat_mapBoost.Containers에서를 사용하는 것입니다. 또는 동일한 아이디어를 기반으로 자신의 솔루션을 손으로 롤업하십시오.

성능 특성은 백 엔드가 다르기 때문에 물론 다릅니다. 그것은 귀하의 경우에 사용할 수 있는지 여부를 평가하는 것은 귀하에게 달려 있습니다.

Answer 3

을 감안할 때 귀하의 요구 사항 :

1. 삽입 빠르게 할 필요가
2. 속도가 느려질 수 있습니다
3. 읽기 다시 읽어
4. 에만

하면 데이터를 다시 읽을 수있는 많은 요소가 있습니다

나는 typedef std::pair<uint64, thirty_six_byte_struct> element;으로 생각하고 std::list<element>으로 채 웁니다. 그것은 성능 측면에서 이기기가 어려울 것입니다.

다시 읽으려면 링크 된 목록을 탐색하고 그 중 하나가 필요할 때마다 확인하십시오. 그것은 O (N) 탐색입니다.하지만 말했듯이, 당신은 한 번만 그렇게 할 것입니다.

Answer 4

조회가 완료되기 전에 즉석에서 작성 하시겠습니까? 나중에 해당되는 경우지도가 필요하지 않으므로 std::vector과 일회성 정렬을 사용할 수 있습니다.

벡터에 정렬되지 않은 모든 항목을 삽입 할 수 있습니다. 단 한 번만 정렬하면됩니다 (O (N * log N) 및 std::map). 그런 다음 정렬 된 배열 (O (logN)은 std::map으로 표시됩니다.

특히 읽기 전에 요소 수를 알고 벡터 크기를 미리 예약 할 수 있다면 매우 잘 작동 할 수 있습니다. 또는 적어도 "상한"을 알고 실제로 필요한 것보다 조금 더 확보 할 것이지만 재 할당을 피하십시오.