如何有效CPU增加項目的唯一項目

-1

序言名單：這個問題應該是中性語言，它是關於算法，但是爲了更學術的問題，因爲這是我最喜歡的語言，我會寫的例子在C++。如何有效CPU增加項目的唯一項目

試想以下結構簡單：

struct Item 
{ 
    char Char; 
    std::string String; 
};

現在，我有這些項目的清單，說std::vector<Item> list。我想要的是創建一個函數，允許我將項目添加到此列表中，但是如果該項目已經在列表中，則跳過。所以它只包含每個項目一次。這使我想到的最簡單的實現：

void AppendItem(Item item) 
{ 
    // Check if the item is in the list and if yes, exit the function 
    foreach (Item x, list) 
    { 
     // Compare char first, because comparing 2 chars is as CPU complex as comparing 2 numbers 
     if (item.Char != x.Char) 
      continue; 
     // Now we can compare the strings, which is relatively complex operation 
     if (item.String == x.String) 
      return; 
    } 
    // There clearly isn't any such item in a list, so let's add it 
    list.push_back(item); 
}

到目前爲止，它看起來是一個愚蠢的問題，這實際上是。但現在它變得更有趣。

想象已經有列表中的2000項，我要添加更多的1000。我不知道這1000箇中的任何一個是否已經在列表中。

如果我遞歸地使用這個啞函數，我會導致循環每個項目2000 + N（N爲0 - 999）* 1000。給定字符串比較的實現，這非常慢。即使在我的i7 CPU上也很慢。

有沒有更聰明的算法，我該如何做到這一點？只要CPU吃得少，我甚至可能會犧牲一些RAM。

來源

2015-11-26 Petr

downvote的原因是什麼？ – Petr

幾乎每一種語言都有所舉辦唯一的值優化列表。在C++中，您可以使用std::set而不是列表。在C＃中，您將使用HashSet。在JavaScript中你可以使用一個對象...

在你的問題你正在做每個元素的O（N）查找，一個集或唯一列表將至少做一個O（log（N））這是快很多倍。

來源

2015-11-26 18:55:40

恩，實際上我根本不用stdlibs。我只是用它們以最常見的方式表達我的問題。我對理論解決方案更感興趣。爲什麼std :: set更高效？它在背景上做了什麼，它更好？ – Petr

@Petr您可以使用高效的查找算法來查看值是否在集合中，而不是掃描它。許多選項存在不同的折衷。如果你想了解更多信息，你可以閱讀哈希，BTrees等等。 – btilly

在C++ 11中，'std :: unordered_set'可能會更快，因爲它基於哈希表，所以平均需要* O（1）*，vs * O（log N）*平衡最差情況時間在'std :: set'中搜索樹。 – stgatilov

-1

所以你一定要添加這些1000個項目都是獨一無二的彼此之間？

如果是這樣，那麼一種可能是首先檢查的項目將被添加（不在列表中的話），然後暫時將它們保存在一個單獨的列表。之後你連接兩個列表。

另一個優化將繼續以某種方式排序列表中一樣基於項目的字符串數據成員的字母順序排列。這樣您就可以使用二進制搜索算法等搜索方法來加速檢查唯一性的過程。

來源

2015-11-26 19:01:31 Jupiter

不，如我的問題所述：我不知道這1000個是否已經在列表中。 – Petr

哦，我明白了。對不起。第二部分有用嗎？ – Jupiter

我不知道，可能它可以工作，但哈希表查找聽起來更有希望。只是供參考，我沒有downvote你的答案，我仍然感激它，即使它並沒有真正幫助我:) – Petr

如何有效CPU增加項目的唯一項目

回答

相關問題