1

我正在寻找一种高性能的数据结构，它的行为类似于一个集合，其中的元素将始终是一个整数数组。数据结构只需要实现这个接口：

trait SetX {
  def size:Int
  def add(element:Array[Int])
  def toArray:Array[Array[Int]]
}

该集合不应包含重复项，这可以使用 Arrays.equals(int[] a, int[] a2) 来实现 - 即数组的值不能相同。

在创建它之前，我对将有多少元素有一个粗略的想法，但需要调整大小行为以防万一超出最初的想法。元素的长度总是相同的，我知道在创建时是什么。

当然，我可以使用 Java HashSet（当然是包装数组），但这是在紧密循环中使用的，而且速度太慢。我看过 Trove 并且效果很好（通过使用数组但提供 TObjectHashingStrategy）但我希望由于我的要求非常具体，因此可能有一种更快/更有效的方法来做到这一点。

有没有人遇到过这个或知道我如何能做到这一点？

上面的特征是 Scala，但我对 Java 库或代码非常满意。

我真的应该说我在做什么。我基本上是在一个紧密的循环中生成大量 int 数组，最后我只想看到唯一的数组。我永远不必从集合或其他任何东西中删除元素。只需将大量 int 数组添加到集合中，最后取出唯一的数组。

4

4 回答 4

1

查看前缀树。您可以在数组生成期间立即遵循树结构。在生成结束时，如果生成的数组已经存在于集合中，您将得到答案。前缀树将比普通哈希集消耗更少的内存。

如果您正在生成数组并且它们等价的机会并不小，我怀疑您只是从非常有限的范围内获取数字。它也将简化前缀树的实现。

我确信正确的实现会比使用任何集合实现来保持实体数组更快。

这个方案的缺点是你需要自己实现数据结构，因为它会和代码的逻辑深度集成。

于 2013-10-11T18:12:53.653 回答
0

在不知道有多少数据或您是否执行的读取多于写入的情况下：

您可能应该尝试（即基准测试）数组数组或特殊包装数组数组的幼稚情况（即具有数组和数组的缓存哈希码的复合对象）。一般来说，在小型数据集上循环遍历数组并没有多少节拍（例如，枚举的 HashMap 实际上可能比循环遍历要慢）。

如果您拥有大量数据并且愿意做出一些妥协，您可能会考虑使用布隆过滤器，但听起来您没有太多数据。

于 2013-10-11T16:23:49.300 回答
0

如果您想要高性能，请编写自己的：

称它为 ArraySetInt。

集合通常被实现为树或哈希表。

如果你想要一个基于数组的集合，这会减慢添加，可能会删除，但会加速迭代，内存使用率低。等等

先看看ArrayList是怎么实现的。删除对象并将其替换为原始 int。

然后将 add() 重命名为 put() 并将其更改为按插入排序的类型。使用 System.arraycopy() 插入。使用 Arrays.binsearch() 查找插入位置以及元素是否已经存在一步。

于 2013-10-11T16:43:08.493 回答
0

我会选择一些经典的解决方案，通过提供更快equals和hashCode. hashCode可以简单地缓存，并且可以equals利用它在不同数组的情况下快速拒绝。

我会避免Arrays.hashCode，因为它使用愚蠢的乘数 (31)，这可能会导致不必要的碰撞。对于非常快equals的情况，您可以使用密码学并说当且仅当它们的SHA-1相等时两个数组才相等（您将是第一个发现冲突的人：D）。

ArrayWrapper相当简单，应该比使用更快，因为它永远不必TObjectHashingStrategy查看数据本身（更少的缓存未命中），并且它具有最快和最好hashCode的equals.

您还可以寻找一些CompactHashSet实现，因为由于更好的内存局部性，它可以更快。

于 2013-10-12T09:36:15.653 回答