为什么这段代码运行得如此缓慢？

我被这段代码严重困扰了，我运行了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

虽然我同意你的一般前提，但100x似乎不太可能。高速缓存行（在x86上）是64个字节。即使'T'只有8个字节，那最多只需要8倍的存储器提取量...... –

@OliCharlesworth：和x86的假设一样，假设什么都没有在缓存中开始。考虑到8字节的数据假设，我们讨论的高达8倍的值保留在高速缓存中，对于某些访问模式和数据大小，可以避免大量主存取，以及连续内存使用可以更好地处理任何推测预取.... –

@TonyD：是的，这很公平。（尽管对于超过缓存的非常大的数据集，我猜渐近比率差异趋向于8倍......） –

为什么这段代码运行得如此缓慢？

回答

相关问题