堆棧和哈希聯合

我想寫一個數據結構，它是Stack和HashSet組合的快速推/流行/成員資格（我正在尋找恆定時間的操作）。想想Python的OrderedDict。堆棧和哈希聯合

我試了幾件事，我想出了以下代碼：HashInt和SetInt。我需要向源文件添加一些文檔，但基本上我使用帶有線性探測的散列將索引存儲在密鑰的向量中。由於線性探測總是將最後一個元素放在連續範圍的已填充單元格的末尾，因此pop（）無需複雜的刪除操作即可輕鬆實現。

我有以下問題：

數據結構消耗大量的存儲器（一些改進是顯而易見的：stackKeys比所需要的更大）。有些操作比我使用fastutil（例如：pop（），甚至在某些場景中使用push（））要慢一些。我嘗試使用fastutil和trove4j來重寫類，但是我的應用程序的整體速度減半了。

對於我的代碼，你會有什麼樣的性能改進？什麼開源庫/代碼你知道我可以試試嗎？

來源

2010-05-07 Alexandru

承認它，你只是想在同一句中使用散列和聯合;-) – fretje 2010-05-07 11:09:09

在標準API中沒有符合要求的類 - 也許是'java.util.concurrent.ConcurrentSkipListMap'？ – Jesper 2010-05-07 11:38:52

「按鍵的自然排序」。 ConcurrentSkipListMap不保留插入順序。但我正在研究'LinkedHashMap'。 – Alexandru 2010-05-07 11:45:24

你已經有了很好的實現。對我而言，唯一明顯的改進是，當你彈出時，你可以通過搜索來做更多的工作。您應該在堆棧中存儲不是密鑰本身，而是將的索引放入密鑰數組。當您想要查看最後一個項目時，這會讓您以較小的指針間接尋找快速彈出窗口。

除了這個之外，只需將堆棧大小設置爲LOAD_FACTOR *（堆數組大小），並且您應該儘可能快地執行實現，因爲您可以根據您的速度要求儘可能少地使用內存。

來源

2010-05-07 22:24:18

這是我期待的伎倆。我認爲將索引存儲在'stackKey'數組中會加快pop（）函數的速度。我明天會測試它。 – Alexandru 2010-05-08 00:52:59

它的工作原理很好：從最初的測試中（）改進了2倍，pop（）改進了4倍，push（）僅略微改進。最大的收益來自搜索（）中刪除的重定向。 – Alexandru 2010-05-08 14:34:53

我認爲你想要的是（幾乎）已經在庫中可用：LinkedHashSet是一個具有基礎雙向鏈表的哈希集（這使得它可迭代）。 LinkedHashMap甚至有一個removeEldestEntry，這聽起來非常類似於pop-method。

如何是一個天真的解決方案，比如性能：

class HashStack<T> {

private HashMap<T, Integer> counts = new HashMap<T, Integer>(); 
    private Stack<T> stack = new Stack<T>(); 

    public void push(T t) { 
     stack.push(t); 
     counts.put(t, 1 + getCount(t)); 
    } 

    public T pop() { 
     T t = stack.pop(); 
     counts.put(t, counts.get(t) - 1); 
     return t; 
    } 

    private int getCount(T t) { 
     return counts.containsKey(t) ? counts.get(t) : 0; 
    } 

    public boolean contains(T t) { 
     return getCount(t) > 0; 
    } 

    public String toString() { 
     return stack.toString(); 
    } 
}

來源

2010-05-07 13:59:19 aioobe

您的解決方案很好，但我已經使用fastutil實現了類似的解決方案，因爲fastutil使用原語可能會更快。我正在尋找HashTables和Stack儘可能使用單個表的組合。現在我的內存需求大約是插入密鑰的3倍，而我所擁有的並不是緩存，因爲我總是在兩張表中查找。 – Alexandru 2010-05-07 20:02:24

我會建議使用TreeSet<T>因爲它提供了保證O（log n）的成本來添加，刪除，並含有。

來源

2010-05-07 15:13:11

但這應該可以與攤銷恆定時間，不是嗎？ – aioobe 2010-05-07 21:31:13

堆棧和哈希聯合

回答

相關問題