R中用於OPTICS的優先級隊列的實現

我需要在R中構建一個優先級隊列，我將爲OPTICS聚類算法放置排序的種子對象（或對象的索引）。R中用於OPTICS的優先級隊列的實現

一種可能性是與該數組表示堆來實現它，並通過堆陣列中的每個插入物和減小鍵通話，並返回改變的陣列和在調用函數中重新分配它。在這種情況下，重新分配操作會使性能非常差，並且每次執行一次插入或減少操作時，需要將整個數組複製兩次，一次用於調用，另一次用於返回和重新分配。
另一種可能性是編寫函數內部的堆操作而不是調用它。這將導致代碼重複和繁瑣的代碼。
有沒有像訪問任何指針我們C
做我可以在R中的S3或S4類聲明用戶定義的函數？在這種情況下，我認爲對這些函數的調用在返回後仍然需要相同的重新分配（不像C++/Java類，對對象進行操作（對不對）可以在R中插入並提取一個對象在O(log(n))時間的隊列中？
是否有任何其他方式可以實現目標，即根據OPTICS算法中對象的可達性距離來維護基於優先級的插入和刪除種子，除了在每次插入之後進行顯式排序。

來源

2012-05-29 phoxis

[R5 classes]（https://github.com/hadley/devtools/wiki/R5）應該允許您在修改對象時避開副本。 –

您是否檢查過此討論：（http://www.mail-archive.com/[email protected]/msg108876.html） – nograpes

nograpes：隊列實現似乎對我沒有幫助。 Vincent Zoonekynd：看起來很有用，與C++/Java類更接近，需要詳細瞭解。 – phoxis

R5 classes 定義可變對象，以及非常相似的Java類：他們應該讓你避免副本當對象被修改。

來源

2012-05-29 21:36:17

請注意，您不僅需要優先級隊列。

它實際上也需要支持有效的更新。一個簡單的堆是不夠的，你需要同步一個hashmap來有效地查找對象以更新它們的值。然後，您需要修改更改位置的堆。

來源

2012-05-30 16:15:07

這正是我在設計算法時發現的。更新基本堆實現中的密鑰是O（n + lg（n）），這違背了使用堆進行O（lg（n））訪問的目的。你可以通過提供任何文檔/資源來闡明R的實現嗎？ – phoxis

對不起，我不使用'R'。我只知道OPTICS的ELKI實現，它包含一個相當先進的堆，可以按照OPTICS的需要更新，並且有一些懶惰堆構建/修復的技巧。例如，它似乎排隊多個「添加」操作，然後在實際需要時批量修復堆。您的平均堆將修復每個添加操作的堆。批量加載一個堆是O（n），增量修復它是O（n log n）。我不知道這是否也適用於部分散裝作業。 –

目前我只做了第一次迭代，因此我不需要懶堆修復。在我的情況下，我不是在堆中插入對象，而是將對象的索引從主數組插入到堆中，因此，存儲堆數組中對象索引位置的輔助索引數組沒有問題。 – phoxis

R中用於OPTICS的優先級隊列的實現

回答

相關問題