我應該使用哪種數據結構

我想弄清楚用於這個問題的最佳數據結構。我正在使用字符串鍵實現鍵值存儲。這些值經常被添加，通常只會被查找1或2次。最初我使用了std::map，但是我發現性能並不理想，因爲添加密鑰和重新平衡紅黑樹的開銷，掩蓋了搜索值的時間減少。目前我正在使用修改的單鏈表。它使用包含c字符串（const char *）的結構，字節長度和存儲的值。當我想用鍵找到一個值時，我遍歷列表並比較鍵的大小，如果它們匹配，我使用memcmp來檢查這些字符串是否相同。如果它們相同，我將返回該值。我能夠通過std::map使用此方法實現約10倍的更高性能。但是，我需要使其效率提高約2倍。任何人都可以推薦一個更好的數據結構類型，對於這個問題？我應該使用哪種數據結構

來源

2011-02-10 Skyler Saleh

有多少個元素？鑰匙的平均尺寸是多少？ – 2011-02-10 19:10:09

在沒有任何實際問題知識的情況下，很難找到快速解決方案。特別是，您的數據集有多大，真實數據存儲在哪裏（存儲在容器中還是其他地方？）。您需要對容器執行哪些其他操作？你需要從容器中刪除元素嗎？

作爲對其他問題之一的評論，您聲明密鑰需要在std::unordered_map中複製...如果密鑰已經存儲在其他地方，我會建議您使用地圖，但避免複製字符串。使用指針作爲鍵，和一個自定義比較提領，並在結果操作：

// Assuming that the data is stored in std::string somewhere else 
struct custom_compare { 
    bool operator()(std::string* lhs, std::string* rhs) const { 
     return lhs!=rhs && (lhs->size() < rhs->size() || lhs->compare(*rhs) < 0); 
    } 
}; 
std::map< std::string*, data, custom_compare > mymap;

通過存儲指針而不是實際的字符串這將需要擺脫複製。自定義比較器基本上和列表中實現的一樣快，並且樹會平衡內容，允許O（log n）查找。根據集合的大小（如果有很多元素），那麼這將是對線性搜索的改進，而如果大小很小，那麼線性搜索會更好。另外，根據數據的多樣性，您可能想要遵循線性搜索，但會根據某些快速計算的標準劃分搜索空間，並且同時儘可能均勻地分割該集合。例如，您可以使用線性搜索，但不是保留單個列表，而是根據密鑰長度保留不同的列表。

如果標準實際上是基於字符串的內容（字母，而不是大小），那麼您近似了一個trie的定義。如果你得到一個已經實現了一個庫的庫，或者你願意花費這麼多時間來完成這個工作，那麼一個庫特里可能是這種查找的最快容器之一，因爲它將「大小」變量從元素與字符串的長度。

來源

2011-02-10 19:24:26

也許某種散列表？爲你的密鑰使用一個好的散列算法會大大加快你的搜索時間。您的插入時間會稍微減慢，但如果您的散列函數良好，希望不會太多。

來源

2011-02-10 18:30:56 Ben

@RTS：用`std :: unordered_map`（哈希表）替換`std :: map`（rbtree）並測試應該相當容易。我對代碼中的`std :: unordered_map`性能非常滿意。 – Blastfurnace 2011-02-10 18:45:17

@Blastfurnance：我已經試過std :: unordered_map和std :: tr1 :: unordered_map，這些在我的用例中比我的鏈表解決方案慢。由於他們需要密鑰數據的副本，所以在鏈接列表中，我可以複製字符串指針。 – 2011-02-10 18:52:59

std::vector應該比鏈表快得多，在push_back()也要快得多，因爲大部分時間都不需要內存分配。

來源

2011-02-10 18:35:20 antonakos

您將它作爲您的一個標籤......爲什麼不使用Trie？插入應該很快，由於字符重疊，內存使用可能會減少，並且查找速度很快。

來源

2011-02-10 18:39:12

我應該使用哪種數據結構

回答

相關問題