堆栈和哈希联合

我想写一个数据结构，它是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

堆栈和哈希联合

回答

相关问题