다양한 C++ 사전 구현 (지도, 사전, 벡터 등)에 대한 보고서를 작성하고 있습니다.std :: map의 메모리 할당
std :: map을 사용한 삽입 결과는 성능이 O (log n)임을 보여줍니다. 성능에도 일관된 스파이크가 있습니다. 나는 이것을 일으키는 것이 확실하지 않다. 나는 그들이 메모리 할당에 의한 것이라고 생각하지만, 이것을 증명할 수있는 문헌/문서를 찾지 못했습니다.
누구나이 문제를 해결하거나 올바른 방향으로 나를 가리킬 수 있습니까?
건배.
당신이 맞습니다 : 그것은 O (log n) 복잡도입니다. 그러나 이것은 맵의 정렬 된 특성 (일반적으로 이진 트리 기반) 때문입니다.
http://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.html 참고 사항 삽입시 참고 사항이 있습니다. 최악의 경우는 O (log n)이고 amortized O (1)는 삽입 위치를 암시 할 수있는 경우입니다.
지도는 일반적으로 이진 트리를 기반으로하며 성능을 유지하기 위해 균형을 조정해야합니다. 관찰하고있는로드 스파이크는 아마도이 균형 조정 프로세스에 해당합니다.
처음에는 스파이크가 나무 회전으로 인해 발생한다고 생각했지만 50,000 개의 항목이지도에 삽입 될 때까지 스파이크가 발생하지 않았습니다. 이 숫자 이후에 스파이크는 그 후 약 25,000 개의 항목마다 일관되게 발생하며 각 항목의 크기는 일정합니다. –
나는 늦게 대답하고 있지만 유용 할 수있다 : 최소한의 조작으로 각 삽입시 밸런싱을 수행 할 수있다. 그래서 내 생각에 스파이크는 엘리먼트에 미리 할당 된 메모리의 양이 증가 할 때 수행되는 재 할당이다. 에 도달했습니다. – Gui13
경험적 접근법은 STL의 경우 꼭 필요한 것은 아닙니다. 표준이 std :: map 삽입과 같은 최소한의 연산 복잡성을 명확히 지시 할 때 실험을하는 것은 의미가 없습니다.
실험을 계속하기 전에 최소한의 복잡성 보장을 알고 있으므로 표준을 읽어 보시기 바랍니다. 물론 테스트 할 STL 구현에 버그가있을 수 있습니다. 하지만 인기있는 STL은 꽤 잘 디버깅 된 생물이며 널리 사용되기 때문에 의심 스럽습니다.
올바르게 기억하면 std :: map은 균형 잡힌 빨강 - 검정 나무입니다. 일부 스파이크는 std :: map이 기본 트리가 균형을 잡아야한다고 결정할 때 발생할 수 있습니다. 또한, 새로운 노드가 할당 될 때, OS는 할당 부분 동안 몇몇 스파이크에 기여할 수있다.
std :: map의 GCC 구현은 사실 적색 - 검은 색 트리입니다. 나는 MS VS가 붉은 색 검정 나무를 사용한다고 생각하지만, 100 % 확실하지는 않습니다. 스파이크는 트리의 재조정 일 가능성이 큽니다. – paxos1977
이 동작은 구현에 크게 의존한다고 생각합니다. STL은 사용 방법 만 구현해야하는 방식을 지정하지 않았기 때문입니다. – mmmmmmmm
@restevens - 맞지 않습니다. STL의 작동 방식에 대한 정의가 있습니다 (즉, 각 유형의 컨테이너에 대한 실적이 얼마나 큰지). – ChrisW
@rstevens : 그건 잘못되었습니다. STL 컨테이너는 서로 다른 작업의 복잡성에 대한 보장 측면에서 정의됩니다. –