4

我正在编写一个使用 TreeMap 的 Java 程序，一旦有成千上万的整数字符映射，性能就会减慢到爬行。

我想知道是否有某种类型的排序集实现的实现，它可以使用 int 和 char 原语并具有类似“headMap”和“tailMap”函数的东西。

我目前正在看 Trove。我还研究了一个使用插入排序但不包括头和尾函数的链表的实现。我认为带有插入排序的链表会比树慢，不是吗？

4

9 回答 9

2

如果您正在寻找类似的替代品，TreeMap<Integer,Character>并且如果您的整数键很密集，那么数组将是最有效的。但它会是 achar[]而不是 anint[]因为你想char根据int-key 来查找。然后我读了一些关于“基因组”的东西？！假设你想用charAdenin、Gunin、Cytosin 和 Thymin 来表示（我不是这方面的专家）请记住，这char需要你每个 16 位 - 远远超过你需要四个不同的东西。也许你可以做类似的事情

...
public static final byte UNDEF = (byte)-1;
public static final byte ADENIN = 0;
public static final byte GUANIN = 1;
public static final byte CYTOSIN = 2;
public static final byte THYMIN = 3;
...
private byte[] genome = new byte[ 26000000 ]; // or which size ever
...

如果这仍然会占用太多内存，那将变得很棘手：假设您不需要该UNDEF值，您只需要 2 位来存储四个值，即一个可以存储您的序列，每个字节有四个值，最终需要大约 6.5 MB。但是对于这样的事情，你需要做一些摆弄......

于 2012-10-01T12:39:30.813 回答
1

如果我理解了这个问题，您需要一个保留键顺序的数据结构，即替换个人参考序列中的字符的位置。

我假设您通过增加仓位顺序来处理这些项目。

现在，由于 TreeMap 正在实现Red-Black Tree，它的基本操作具有对数复杂度。

如果您只需要按顺序迭代序列，那么每次插入都会严重影响性能。

如果我的假设是正确的，我会说您可以使用LinkedHashMap。

正如 javadoc 解释的那样：

此实现使其客户免于 HashMap（和 Hashtable）提供的未指定的、通常混乱的排序，而不会增加与 TreeMap 相关的成本。

这意味着您可以按照输入元素的相同顺序迭代元素，但基本操作与普通 HashMap 具有相同的复杂性，并且由于链表处理而导致性能下降。

你可以把它想象成一个 HashMap，它被一个按照插入顺序连接键的双链表遍历。

请注意，我没有解决您的序列是否适合记忆的事实。此外，请注意 LinkedHashMap 将比简单的 HashMap 占用更多内存。

于 2011-10-07T08:39:38.680 回答
0

要保存大量元素，最好使用B-Tree。这种结构在数据库中广泛用于保存索引。例如在 Oracle 和 MySQL 上，如果我没记错的话。看看JDBM3。还应该存在其他实现。

于 2013-10-11T07:14:16.240 回答
0

如果你只是想要一个更快的 Map 实现，你考虑过HashMap吗？这仍然使用对象，但如果最初创建（参见上一个链接中构造函数的第三种形式）具有足够大的容量，这将允许比TreeMap.

或者，如果您只对地图中类似 SortedSet 的行为感兴趣，则可以使用TreeSet获得更好的性能。

至于 Trove，我不熟悉它，但我怀疑你可以从 Java 提供的类中获得显着的性能增强，而不是诉诸 3rd 方库，只需一点额外的努力来检查你需要什么数据结构以及它们浪费了哪些额外的工作来提供您不需要的功能。

于 2011-10-06T17:30:03.673 回答
0

正如史蒂夫所写，使用分析器检查 TreeMap 是罪魁祸首可能是值得的。

其他几个选项是：

  • 使用HashMap大initialCapacity

  • 如果您的密钥集很密集，那么您可以使用int[]. 那将是最快的。

于 2011-10-06T17:33:52.267 回答
0

你看过 PriorityQueue 了吗？它有一些有用的方法，并根据您定义的比较器对元素进行排序。

于 2011-10-06T17:50:52.410 回答
0

如果您知道这是您的性能瓶颈和/或内存问题 - 那么我会考虑使用 trove TIntCharHashMap。过去，我使用 trove maps 非常成功地提高了性能并减少了内存消耗。

请注意，键不会被排序，但您可以int[]非常便宜地获得键，然后您可以对其进行排序。因此，如果您只是偶尔需要排序遍历，您可以根据需要对其进行排序。

如果您发现丑陋（或性能障碍），您可以将TIntCharHashMapand sorted包装int[]到您自己的排序映射中 - 您只需要自己维护不变量。

我发现 trove 不直接基于树的顺序维护映射/设置类有点不幸，但我感谢它提供的工具。

于 2014-10-06T03:11:59.227 回答
0

值得尝试Max Bolingbroke的类似B-Tree的解决方案。

于 2020-12-30T01:25:45.453 回答
0

一种适用于非常大的排序映射的技术是结合使用 SortedSet 来按排序顺序管理键，并使用 Map 来管理实际的键到值的映射。通过这种方式，您可以使用 headSet() 和 tailSet() 对键进行快速迭代，然后使用从集合返回的键来查找实际映射。

我没有证据证明为什么会这样，但根据我的经验，使用非常大的排序地图要快 10 倍。

于 2018-02-05T10:29:27.040 回答