使用std :: map與std :: string鍵vs int鍵的代價？

Question

我知道個人地圖查詢最多需要log（N）時間。但是我想知道，我看到很多使用字符串作爲映射鍵的例子。將std :: string作爲關鍵字關聯到map而不是int的性能成本是多少？

std::map<std::string, aClass*> someMap; VS std::map<int, aClass*> someMap;

謝謝！

Answer 1

除了比較已經提到的字符串的時間複雜性之外，字符串鍵還會在每次將項添加到容器時導致額外的內存分配。在某些情況下，例如高度並行的系統，全局分配器互斥可能成爲性能問題的來源。

一般而言，您應該選擇最適合您情況的替代方案，並且僅根據實際性能測試進行優化。很難判斷哪些是瓶頸。

Answer 2

成本差異將與比較兩個字符串與比較兩個字符串之間的成本差異相關聯。

比較兩個字符串時，您必須取消引用指向第一個字符的指針，並對它們進行比較。如果它們相同，則必須比較第二個字符，依此類推。如果你的字符串有一個很長的公共前綴，這可能會使進程變慢一點。儘管如此，它不可能像比較整數一樣快。

Answer 3

成本是理所當然可以在實時O（1）時間比較ints，而字符串在O（n）time（n是最大共享前綴）進行比較。而且，字符串的存儲消耗比整數更多的空間。 除了這些明顯的差異之外，沒有主要的性能成本。

Answer 4

漸近性能的分析算法正在研究必須執行的操作以及它們添加到方程中的成本。爲此，您需要首先了解執行的操作，然後評估其成本。

在平衡二叉樹中搜索關鍵字（哪些地圖碰巧是）需要O(log N)複雜的操作。這些操作中的每一個意味着比較匹配的關鍵字並且如果關鍵字不匹配則跟隨適當的指針（子）。這意味着總成本與這兩個操作的成本成正比。以下指針是恆定時間操作O(1)，並且比較密鑰取決於密鑰。對於整數密鑰，比較很快O(1)。比較兩個字符串是另一個故事，它需要的時間與參與O(L)串的大小（這裏我特意用L作爲長度字符串參數，而不是更常見的N的。

當你總結所有費用高達你得到使用整數作爲鍵的總成本是O(log N)*(O(1) + O(1))等效於O(log N)（O(1)被隱藏在不斷的O符號默默隱藏。

如果使用字符串作爲鍵，總成本爲O(log N)*(O(L) + O(1))恆定時間操作得到隱藏n通過更昂貴的線性操作O(L)並且可以轉換成O(L * log N)。也就是說，在由字符串鍵入的映射中查找元素的成本與存儲在映射中的元素數的對數乘以用作鍵的字符串的平均長度成比例。

請注意，大O符號最適合用作分析工具，以確定算法在問題規模增長時的行爲方式，但它掩蓋了許多對原始性能非常重要的事實。

作爲最簡單的示例，如果將密鑰從通用字符串更改爲1000個字符的數組，則可以將該成本隱藏在從符號中刪除的常量內。比較1000個字符的數組是一個持續的操作，只需要很長時間。使用漸近符號，就像O(log N)操作一樣，使用整數。

許多其他隱藏成本也是如此，因爲創建元素的成本通常被認爲是恆定時間操作，僅僅因爲它不依賴於問題的參數（查找塊的成本的內存不依賴於你的數據集，而是依賴於算法分析範圍之外的內存碎片，獲得malloc內部鎖的代價，以保證兩個進程不會嘗試返回相同的塊的內存取決於鎖的爭用，這取決於它本身的處理器數量，進程和它們執行多少內存請求......，這同樣超出了算法分析的範圍）。當用大O符號閱讀成本時，你必須意識到它的真正含義。

Answer 5

首先，我懷疑在一個真實的應用程序中，不管你是否有字符串鍵或int鍵都有明顯的區別。分析你的應用程序會告訴你它是否重要。

如果這非常重要，你可以改變你的關鍵是這樣的（未經測試）：

class Key { 
public: 
    unsigned hash; 
    std::string s; 

    int cmp(const Key& other) { 
     int diff = hash - other.hash; 
     if (diff == 0) 
      diff = strcmp(s, other.s); 
     return diff; 
} 

現在你正在做的兩個字符串的哈希一個int比較。如果哈希值不同，字符串肯定是不同的。如果哈希值相同，則由於Pigeonhole Principle，您仍然需要比較字符串。

Answer 6

簡單的例子，只需訪問兩個具有相同鍵數的映射中的值 - 一個int鍵另一個具有相同int值的字符串需要8倍的字符串長度。