std :: vector 및 std :: list find_if 및 max_element 성능

Question

std::vector 및 std::list에 대해 테스트 한 코드의 성능에 대해 혼동스러워합니다. find_if과 max_element에이 두 가지의 차이점이 있습니까?

Answer 1

big-O 표기법의 경우 O (n)과 동일한 성능을 나타냅니다. (find_if은 요소가 더 빨리 발견되면 더 적을 수 있지만 두 컨테이너 모두 똑같이 적용됩니다.)

실제 벽 시계 시간의 관점에서 볼 때 벡터는 캐시 일관성 때문에 더 잘 수행됩니다. 모든 벡터 요소는 메모리에서 순차적이므로 액세스하면 CPU 캐시를보다 효율적으로 사용할 수 있습니다. 연결된 목록의 요소는 메모리에 흩어져있을 수 있으며 목록 링크를 따라 가야합니다.

Answer 2

두 알고리즘 모두 계산 복잡성 측면에서 O (n)이지만 벡터는 인접한 저장소 영역에 요소를 할당하므로 캐시 적중률이 높아질 가능성이 높습니다. 반면에리스트를 순회하는 것은 캐쉬 미스의 비율이 높아지는 경향이있는 흩어져있는 메모리 액세스 패턴을 포함합니다.

언제나 성과와 관련하여 결정을 내리기 전에 측정을 수행하십시오.

Answer 3

max_element의 경우 list 및 array의 모든 요소가 순회됩니다. 따라서 성능면에서 모두 O (n)입니다.

다시 find_if의 경우, 두 탐색 구조에 대해 순회가 선형 (O (n))이됩니다.

각기 다른 상수와의 차이가별로 없다고 생각하지 않습니다.