常量大小優先級隊列 - 先插入或先刪除？

我正在使用priority_queue來存儲迄今在K-最近鄰居搜索中找到的K個最近點。當我發現一個點比隊列頂部的點更接近時，我想彈出頂部元素並推送新元素。常量大小優先級隊列 - 先插入或先刪除？

if(point < pq.top()){ 
    pq.pop(); 
    pq.push(point); 
}

一般情況下，它是更有效的流行，然後再插入，或者是更有效地插入，然後再彈出？

來源

2011-05-01 Null Set

什麼容器類是您使用備份的priority_queue？ – onitake 2011-05-01 01:45:15

@onitake矢量。 – 2011-05-01 01:46:50

@Null Set：那麼答案不言而喻？瞭解VECTOR'的'的行爲，如果插入，然後再彈出，你有* *勢，迫使底層'VECTOR'重新分配，而如果你彈出，然後再插入，你不知道。除此之外你還問什麼？ – ildjarn 2011-05-01 01:55:08

如果您使用std::priority_queue作爲您的優先級隊列類，默認情況下，標準容器類std::vector用於其基礎容器類。

一般來說，它是到push比pop第一第一效率較低。

理由一

在priority_queue推送元件將envoke vector::push_back如果它超過它的電流容量可以潛在重新分配基礎緩衝區。

理由二

priority_queue ::彈出

當您從 priority_queue流行的元素，它調用 pop_heap算法，以保持priority_queues堆屬性，然後電話成員函數底層容器對象的pop_back 到刪除的元素。

priority_queue ::推

當按下一個元素 priority_queue，它調用構件函數底層容器對象的push_back，然後調用 push_heap算法保持priority_queues堆屬性。

假設現在有在優先級隊列Ñ元件。

如果push第一，算法push_heap被稱爲兩次，以調整N + 1和N + 1元件，分別。

如果pop第一，算法push_heap被稱爲兩次，以調整Ñ和Ñ元件，分別。

除了

如果你實現自己的優先級隊列，這可能是一個性能金丹。既然你已經與頂級檢查值，我想知道，如果你可以直接交換與頂部的元素，而不必調用推送/彈出從而繞過堆調整算法。雖然可能不太實際。

來源

2011-05-01 02:06:26

realloc + memcpy操作對於FIXED SIZE隊列不會有問題。 – corlettk 2011-05-01 02:13:05

@corlettk，對。但實際上，當使用std :: priority_queue時，它可能無法修復。 – 2011-05-01 02:16:44

一旦priority_queue達到K的大小，它將在K和K + 1或K-1和K之間擺動，具體取決於我選擇的順序。重新分配成本應該只發生一次。 – 2011-05-01 02:28:22

@NullSet，

你實現K-近鄰搜索，所以我要去假定性能是一個大問題。

如果是這樣，，只是使用標準隊列的一個技巧，看看你是否可以用數組備份它（我在這裏我沒有自己的深度）......我猜這個固定大小，隨機訪問結構將比該向量更有效。然後，如果你的隊列仍然是一個經過驗證的性能瓶頸，那麼我會看看基於btree（或者甚至是rbtree）的優先級隊列接口的滾動式我自己的實現。

你走多遠這是真的取決於你的最大K。如果ķ足夠小的標準載體支持優先級隊列將被織補的近等爲 - 快 - 作爲最有效的解決方案可能的。訣竅是觀察正在運行的程序的ACTUAL性能，以便找出那些可能爲您的努力提供最佳性能改進的「改進機會」。

是啊，我是一個算法的賽車迷......它說明了什麼？

乾杯。基思。

來源

2011-05-01 02:32:50 corlettk

我可能最終只是自己實現它。我真正想在這裏做的操作是用新節點替換堆的頂部並冒泡。 – 2011-05-01 02:38:16

常量大小優先級隊列 - 先插入或先刪除？

回答

相關問題