이 코드가 너무 느리게 실행되는 이유는 무엇입니까?

나는이 코드에 심각하게 난처 해하며 gprof를 실행했으며 프로그램이 약 8000 번 실행되는 contains() 함수에서 40 %의 시간을 보낸다는 것을 알았습니다. 프로그램 자체는 실행하는 데 총 15 초가 걸립니다. 누구나 왜 그렇게 오래 걸릴지 또는 그 밖의 무엇이 될 수 있는지 알 수 있습니까?이 코드가 너무 느리게 실행되는 이유는 무엇입니까?

// Check a list to see if it contains a tile object at x,y 
bool contains(std::list<struct Tile>* list, int x, int y){ 
    std::list<struct Tile>::iterator it; 
    for(it = list->begin(); it != list->end(); it++){ 
    if((*it).x == x && (*it).y == y){ 
     return true; 
    } 
    } 
    return false; 
}

출처

2014-01-06 dakillakan

목록은 검색하기에 효율적이지 않습니다. 왜 벡터를 사용하지 않습니까? –

음, 목록은 얼마 동안 있니? 선형 검색은 특히 효율적이지는 않습니다 (링크 된 목록에서 얻는 것만 큼 좋을 것입니다). –

'struct'를 드롭하면 그냥 'Tile'됩니다. 깨끗해. –

std::vector을 사용하면 캐시 친화적이기 때문에 트래버스하는 것이 약 100 배 빠릅니다. 벡터 push_back에는 목록과 마찬가지로 O (1) 난이도 상각이 있습니다. 벡터는 중간 삽입에 좋지 않습니다. 또한 std::map 및 std::unordered_map은 빠른 검색을 위해 설계되었습니다.

출처

2014-01-06 00:52:55

나는 당신의 일반적인 전제에 동의하지만 100 배는 될 것 같지 않다. 캐시 라인 (x86)은 64 바이트입니다. 'T'가 단지 8 바이트 일지라도 주 메모리 가져 오기의 최대 8 배가 필요합니다 ... –

@OliCharlesworth : x86 가정뿐만 아니라 캐시에서 아무것도 시작하지 않는다고 가정합니다. 8 바이트 데이터 가정을 감안할 때 우리는 캐시에 머물고있는 값이 8 배가되는 것을 감안할 때 - 어떤 액세스 패턴과 데이터 크기에 대해서 - 많은 주 메모리 페치를 피할 수있을뿐만 아니라 어떤 투기 적 프리 페칭 .... –

@TonyD : 그렇습니다. (캐시를 초과하는 매우 큰 데이터 세트의 경우, 점근 비율 차이는 8x로 향하는 경향이 있습니다 ...) –

이 코드가 너무 느리게 실행되는 이유는 무엇입니까?

답변

관련 문제