一個TTL（生存時間）的驅除優先級隊列

-1

我需要一個數據結構，它滿足以下屬性： -一個TTL（生存時間）的驅除優先級隊列

獲得最大的在O（1）
插入在O（log n）的
刪除O中的最大值（log n）（O（log n）中的刪除ANY時的獎勵積分）
刪除僅在特定的TTL（生存時間）超過時才被調用。

操作4只需要最終一致，但有限的時間複雜度將是非常好的。

1,2和3是使用堆數據結構的標準優先級隊列。但是我自己並沒有實施驅逐線程，但我沒有看到任何實現方法4.我有兩個問題：

實現4的最佳方法是什麼？
在Java或其他基於JVM的lang中是否存在現有的實現，我可以直接使用而不必自己編寫驅逐策略？

來源

2017-01-27 Arunav Sanyal

你可能想看看這個http://stackoverflow.com/questions/3802370/java-time-based-map-cache-with-expiring-keys –

@ShubhamChaurasia - 感謝這篇文章，它非常接近我的使用案例。然而，儘管維持我自己的優先隊列，但這仍然無法解決我的使用案例。獲取最大值不是O（1）的併發散佈圖 –

只需清除？ PQ中的關鍵與TTL不同，對吧？如果是這樣，我只是推薦像你已經提到的標準PQ +額外驅逐（只是一個有序的數組/二叉樹，鍵：=時間到期）。理想情況下，您可以在驅逐線程中使用Fibonacci Heap＆only標誌項目進行刪除，然後只刪除重建期間在fib堆上調用deleteMIn時觸及的項目。但我認爲這不一定值得實施。 –

是的，一個標準的二進制堆將給你的要求，除了刪除任何O（log n）。

您可以實現具有O（1）get max，O（log n）插入，O（1）刪除max，O（log n）刪除任何內容的優先隊列skip list。（1）get max，O（1）插入，分期償還O（log n）刪除最大值。你可以實現O（log n）（再一次，分期付款）刪除任何一個額外的數據結構。

根據我的經驗，配對堆比跳過列表更容易實現。

對於驅逐通知，我會建議計算驅逐時間，並將其用作優先級隊列中的密鑰。然後，我使用定時器通知我什麼時候可以調用remove。

在程序啓動時，初始化一個nextRemovalTime值以保留下次應刪除項目。將初始值設置在將來。設置一個計時器，當時會通知你。
要將項目添加到隊列中，請通過將TTL添加到當前時間來計算到期時間。然後將該項目插入隊列中。
比較nextRemovalTime與隊列頭部物品的刪除時間。
如果隊列頭部的項目早於nextRemovalTime，則取消現有定時器，設置nextRemovalTime等於第一個節點應該被移除的時間，然後重新初始化定時器。

這裏的想法是，當計時器滴答時，會創建一個後臺線程，並刪除頂層項目。和其他任何時間已過期的項目。然後計算新的移除時間並重新初始化計時器。

該方法的缺點是優先級隊列數據結構必須能夠處理併發訪問。通常這是一個鎖，除非你有一個無鎖的併發優先級隊列。這不應該是一個問題，真的，除非隊列非常頻繁地被擊中。

另一種方法來做到這一點，如果你不擔心隊列增長過大，就是在添加新項目或刪除現有項目時檢查過期項目。也就是說，刀片變得：

while (queue.peek().expirationTime < currentTime) 
{ 
    queue.removeMax(); 
} 
queue.insert(newItem);

來源

2017-01-27 15:10:39

一個TTL（生存時間）的驅除優先級隊列

回答

相關問題