이봐, 지금은 구조체 목록을 가지고 있는데, std :: list sort 메서드를 사용하여 새 개체를 추가 할 때마다이 목록을 정렬합니다. 모든 프레임 (전체 게임)을 반복하고 있기 때문에 어떤 것이 더 빠를 지 알고 싶습니다. std :: multimap for this 또는 std :: list, .std :: list or std :: multimap
본인은이 사건에 대해 사용해야하는 귀하의 의견을 듣고 싶습니다.
std::multimap 아마, 더 빠른 것입니다 작업 않습니다 반면 목록의 삽입 및 정렬은 O (n log n)입니다.
사용 패턴에 따라 vector 초로 정렬하는 것이 더 나을 것입니다. 한 번에 많은 항목을 삽입 한 다음 읽기 및 쓰기가 인터리브되지 않은 경우 - vector, std::sort 및 std::binary_search을 사용하면 성능이 향상됩니다.
+1''을 인용하기 위해 +1 ('deque'라고 말할 수도 있었지만 더 좋을 수도 있음)하지만, 키/값 쌍인 것처럼 보이지 않기 때문에 여기에'multiset'을 제안 할 것입니다. –
std :: vector를 사용하여 여러 항목을 삽입하더라도 std :: set보다 성능이 더 좋아지지는 않습니다. 정렬에 항상 O (n log n)이 있기 때문입니다 (목록의 n 항목) 그리고 n 개의 항목을 가진 집합에 k 개의 항목을 삽입하는 것은 O (k log n)이 될 것이고, 이는 k가 n보다 훨씬 작은 경우 더 낫다. – MKroehnert
@MKroehnert : 그래서 인터리브되지 않은 읽기 및 쓰기에 대해 이야기했습니다. 즉, K는 N과 비교하여 의미가있을 것입니다. 또한 '벡터'는지도와 비교할 때 공간 효율성뿐만 아니라 참조의 지역성이 훨씬 뛰어납니다. 지도 내에서 진행해야하는 추가 역 참조는 이론상의 복잡성에서는 고려되지 않지만 실제 코드에는 영향을 미칩니다. Scott Meyers의 Effective STL Item 23 : 연관 컨테이너를 정렬 된 벡터로 대체하는 것을 고려하십시오. –
lower_bound 알고리즘을 사용하여 목록에 삽입 할 위치를 찾으십시오. http://stdcxx.apache.org/doc/stdlibref/lower-bound.html
편집 : 닐의 의견에 비추어,이 모든 시퀀스 컨테이너 (벡터, 양단 큐 등)이 삽입 당 O는 (로그 n)와 같이
이lower_bound는 선형 검색 시간 때문에 목록에서 제대로 수행되지 않습니다. 그렇지 않으면 +1. –
@Billy ONeal : 아니요, 참조를 확인하십시오. 그것은 O (log n)입니다. 아마도 이진 검색을 사용합니다. –
랜덤 액세스 반복기를 사용하는 경우에만 (log n)입니다. List는 양방향 반복자 만 제공하여 선형으로 만듭니다. 대수적 인 비교 숫자가되지만 여전히 선형 적으로 목록을 횡단해야합니다. –
일반적으로 컨테이너 반복은 다른 반복보다 많은 시간이 걸릴 수 있습니다. 따라서 컨테이너에 계속 추가하고 반복 할 경우 주로 반복적으로 발생하는 것을 피하는 컨테이너를 선택해야합니다. 메모리를 재 할당하고 원하는 방식으로 빠르게 삽입합니다.
list와 multimap은 요소를 추가하는 것만으로 코드를 재 할당 할 필요가 없으므로 (주로 벡터를 사용할 수있는 것처럼) 삽입하는 데 걸리는 시간이 가장 큰 문제입니다. 목록의 끝에 추가하는 것은 O (1)이고 멀티 맵에 추가하는 것은 O (log n)가됩니다. 그러나 멀티 맵은 요소를 정렬 된 순서로 삽입하고 목록을 정렬하려면 O (n log n)의 목록을 정렬하거나 정렬 된 방식으로 요소를 삽입해야합니다 O (n)이 될 lower_bound와 같은 것입니다. 두 경우 모두, 목록을 사용하는 것이 (최악의 경우에는) 훨씬 더 나쁠 수 있습니다.
일반적으로 컨테이너를 정렬 된 순서로 유지 관리하고 컨테이너를 생성하고이를 한 번 정렬하는 대신 지속적으로 컨테이너에 추가하는 경우 집합과 맵은 정렬되도록 설계되어 있으므로 더 효율적입니다. 물론 항상 그렇듯이 성능에 대해 정말로 신경 쓰는 경우 특정 응용 프로그램을 프로파일 링하고 어떤 것이 더 잘 작동하는지 보는 것이 당신이해야 할 일입니다. 그러나이 경우 멀티 맵이 더 빠를 것이라는 보장은 거의 없다고 말할 수 있습니다 (특히 요소가 많은 경우).
알고리즘 적으로 일반적으로 한 컨테이너에서 반복하는 것이 길다. 실제로는 캐시 고려 사항 때문에 배열과 같은 구조체 ('vector'와'deque')가 훨씬 더 효율적입니다. –
키/값 쌍 std::set 또는 std::multiset이 필요하지 않은 경우 std::multimap을 사용하는 것이 좋습니다.
std::set에 대한
참조 : http://www.cplusplus.com/reference/stl/set/
참조 std::multiset에 대한 : http://www.cplusplus.com/reference/stl/multiset/
편집 : 사용하는 것보다 std::(multi)set 또는 std:(multi)map 같은 용기를 사용하는 것이 일반적으로 더 나은 (이 전 불분명처럼 보인다) std::list 그리고 요소를 삽입 할 때마다 나중에 정렬합니다. 왜냐하면 std::list은 컨테이너 중간에 요소를 삽입하는 데별로 도움이되지 않기 때문입니다.
목록의 경우 선형 삽입 시간이 있더라도 하나씩 삽입하는 것은 O (n^2) 이상임을 유의하십시오. 모두 삽입하고 한 번 정렬하는 것이 좋습니다. –
O (log n)의 삽입을 n 배로하여 정렬과 동일한 O (n log n)를 얻을 수 있기 때문에 실제로는 사실이 아닙니다. – MKroehnert
@MKroehnert - 목록은 로그 삽입을 허용하지 않습니다. –
목록은 최후의 수단입니다.이 주제에 대한 제 생각은 http://punchlet.wordpress.com/2009/12/27/letter-the-fourth/ –
을 참조하십시오. 사물? 반복 할 때마다 반복 하시겠습니까? 분을 추출 하시겠습니까? 이미 병목 현상이 있습니까? 목록이 얼마나 큽니까? – fabrizioM
목록에서 항목을 찾으려면 어떻게합니까? –