快速存儲桶實現

在圖類中，我需要處理具有整數值（主要是1-1000）的節點。在每一步我想從圖中刪除一個節點及其所有鄰居。另外我想始終以最小值的節點開始。我想長約如何做到這一點在最快的方式，決定執行以下操作：快速存儲桶實現

該圖使用adjancency列表存儲
有一個巨大的陣列std::vector<Node*> bucket[1000]其價值
最低的非空桶的索引總是存儲和保持跟蹤關閉
我可以採摘指數的隨機元素找到最小值的節點非常快，或者如果桶已經是空的增長指數
刪除選定的節點這個桶可以在O（1）中清楚地完成，問題是爲了移除鄰居，我需要首先搜索所有鄰居節點的桶桶[鄰居的值]，這不是很快。

有沒有更有效的方法呢？

我想過使用類似std::list<Node*> bucket[1000]的東西，併爲每個節點分配一個指向其「列表元素」的指針，以便我可以從O（1）中的列表中刪除該節點。這可能與stl清單，顯然它可以用一個正常的雙鏈表完成，我可以手工執行？

來源

2012-03-08 Listing

在普通的C數組中使用STL容器感覺很奇怪。是的，這個評論是無關緊要的。 – 2012-03-08 13:24:10

從矢量和列表中移除元素的相對速度是'k * O（n）'和'K * O（1）'。 'n'，'k'和'K'的值也很重要。如果'n'平均爲「小」，則矢量可以非常快。 – 2012-03-08 13:26:27

輸出是什麼？一個近似最小權重控制集？ – 2012-03-08 13:39:49

我最近爲使用存儲桶的優先級隊列實現做了類似的事情。

我做的是使用哈希表（unordered_map），這樣，你不需要存儲1000個空向量，你仍然得到O（1）隨機訪問（一般情況下，不能保證）。現在，如果你只需要一次存儲/創建這個圖類，它可能並不重要。在我的情況下，我需要創建每秒數百次的優先級隊列，並且使用哈希映射造成了巨大的差異（由於我只在實際擁有該優先級的元素時創建了無序集，因此不需要初始化1000個空的散列集）。散列集和映射在C++ 11中是新的，但現在已經在std :: tr1中可用，或者可以使用Boost庫。

我可以在你的&我的用例之間看到的唯一區別是你還需要能夠移除相鄰節點。我假設每個節點都包含一個指向它的鄰居的指針列表。如果是這樣，刪除鄰居應採取k * O(1)與k鄰居的數量（同樣，一般O（1），不保證，最壞的情況是O（n）在一個unordered_map /集合）。您只需遍歷每個相鄰節點，獲取其優先級，即可爲哈希映射提供正確的索引。然後你在優先權映射到的散列集中找到指針，這個搜索通常是O（1），並且一般去除元素也是O（1）。總而言之，我認爲你對做什麼有一個很好的想法，但我相信使用散列映射/集合會加快你的代碼的速度（取決於具體的用法）。對我而言，unordered_map<int, unordered_set>與vector<set>的實施速度提高了約50倍。

來源

2012-03-08 13:44:32 Darhuuk

謝謝，這看起來很有希望。我會嘗試這一點，並將其與我目前的解決方案進行比較:-)。 – Listing 2012-03-08 13:48:48

這是我會做的。節點結構：

struct Node { 
    std::vector<Node*>::const_iterator first_neighbor; 
    std::vector<Node*>::const_iterator last_neighbor; 
    int value; 
    bool deleted; 
};

串聯的鄰接表，並把它們放在一個std::vector<Node*>，以降低存儲管理開銷。我正在使用軟刪除，所以更新速度並不重要。

按值排序指向節點的指針到具有counting sort的另一個std::vector<Node*>。將所有節點標記爲未刪除。

按排序順序遍歷節點。如果正在考慮的節點已被刪除，請轉到下一個節點。否則，將其標記爲已刪除並遍歷其鄰居並將其標記爲已刪除。

如果節點連續存儲在內存中，那麼你就可以在該結構的最後一個額外的前哨淋巴結的成本忽略last_neighbor，因爲一個節點的last_neighbor是後節點的first_neighbor。

來源

2012-03-08 13:55:38

這也是一個不錯的方法，問題（我不得不承認我在這個問題中省略了這個問題）是我有時想要改變刪除內某些節點的值，而不必重新排序列表。將所有節點存儲到地圖時，這可能更容易。 – Listing 2012-03-08 14:05:20

我對此有點奇怪，因爲每個節點對標準貪婪算法的吸引力取決於剩下多少鄰居。如果值只能增加，我會使用一個單級單調優先級隊列（基本上是一個插入式雙向鏈表）。否則，我會使用侵入式優先隊列。不幸的是，STL基本上不能提供侵入式數據結構（儘管你可能會看到Boost.Intrusive）。 – 2012-03-08 14:12:51

謝謝，我一定會那樣做的。 – Listing 2012-03-08 14:18:38

快速存儲桶實現

回答

相關問題