2013-03-07 154 views
2

我很抱歉,神祕的標題。這裏是我的問題:如何實現以下算法?

class Item 
{ 
public: 
    double value; 
    void recomputeValue(); // after this, will probably increase a little, 
          // but never decrease. 
    std::list<Item*> neighbors; // relatively few items 
}; 

我想實現的過程,這將修剪這些物品到指定大小的列表:

void trimToNewSize(std::list<Item*>& items, int newSize); 

,需要加以實現的算法是:

while (size > newSize) 
{ 
    erase item with smallest value; 
    recomputeValue() for all its neighbors; 
} 

我已經考慮SOFAR 2點的方法:

1.堆

從所有值構造一個堆。堆是合適的,因爲它可以找到並刪除O(1)中的最小元素,並且可以在O(n)中構造。

每次刪除後,找到所有的鄰居在堆中,recomputeValue()並更新他們在堆位置。

所以我也做了堆數據結構的一些粗淺的研究上WikipediaBoost問題是,它似乎是堆不提供快速的方式來定位它元素。

2.哈希表

排序列表由值。構建一個哈希表,將指針Item *映射到指向鏈表中的迭代器。然後,每次我從列表中刪除頂部(最小)項目時,都會因爲哈希表而在列表中持續查找其所有鄰居。然後爲每個鄰居recomputeValue()更新其在列表中的位置以及散列表中的對應迭代器。

也許,如果我用一個有序skiplist,而不是一個鏈表哈希表需要將被淘汰。

我的新節目,所以我的方法可能是太天真了,複雜的,我歡迎任何建議。

總結我的問題:

  1. 有沒有在堆中進行快速查找,使#1可行的方法嗎?
  2. 是否有維護元素的順序,可以進行快速查找,這樣我可以做#2清潔的容器?
  3. 你會如何處理這個問題?
+0

作爲堆,總重計算後,我認爲這是構建新的堆'會比「更新舊堆快」。但這只是一個預感 – quetzalcoatl 2013-03-07 09:36:08

+0

我忘了提及,每個項目只有少數鄰居,所以只有少數重新計算會發生。 – 2013-03-07 09:37:30

+2

這是非常積極的事情,你正在做深入的研究。然而,你有沒有調查過「無關緊要」的零假設?你會有多少物品/鄰居?你現在增加了「少數鄰居」,對於FEW,例如O(N)或O(NlgN)等沒有真正的差別,甚至O()符號中缺少的常數因子可能比O ()因素本身! – quetzalcoatl 2013-03-07 09:40:29

回答

3

這看起來像一個普通的老工作std::map< double, Item * >。它給你作爲* items.begin()的最小元素,並重新計算鄰居,只是像做

typedef std::map< double, Item * > itemsByValue; 
itemsByValue items; 

class Item 
{ 
public: 
    double value; 
    void recomputeValue(); // after this, will probably increase a little, 
          // but never decrease. 
    std::list<itemContainer::iterator> neighbors; // relatively few items 
}; 

for (itemsByValue::iterator i = neighbors.begin(); 
     i != neighbors.end(); ++ i) { 
    Item &item = * neighbor; 
    items.erase(neighbor); 
    item.recomputeValue(); 
    items.insert(std::make_pair(item.value, & item)); 
} 
+0

謝謝!所以我應該使用散列表的替代方案? – 2013-03-07 09:42:42

+2

@MartinDrozdik Huh?我在哪裏提到了一個散列表?不幸的是'std :: unordered_multimap'沒有提供你需要找到一個插入點的'lower_bound'操作,所以樹是必需的。 – Potatoswatter 2013-03-07 09:43:50

+0

我在提到#2的問題。我正在使用QHashTable,但我想,這只是一個相當於std :: unordered_multimap。謝謝你的建議! – 2013-03-07 09:51:08