爲什麼這段代碼運行得如此緩慢？

我被這段代碼嚴重困擾了，我運行了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倍......） –

爲什麼這段代碼運行得如此緩慢？

回答

相關問題