3

我的问题很像上一篇文章Optimal HashSet Initialization (Scala | Java)，我想在其中使用HashSet加速（目前我正在使用Set）但HashSet没有表现出它的（恒定时间）优势。

对于提到的解决方案：

您可以通过实习来最小化equals的成本。这意味着您通过工厂方法获取类的新对象，该方法检查请求的新对象是否已经存在，如果存在，则返回对现有对象的引用。如果您断言这种类型的每个对象都是以这种方式构造的，那么您就知道每个不同对象只有一个实例，并且 equals 等效于对象标识，这是一种廉价的引用比较（Scala 中的 eq）。

但是，我不太确定检查的有效方法是什么

请求的新对象是否已经存在

对于大型对象（例如带有 hashmap 参数的案例类对象，一些其他对象结构......等）

通过比较这些复杂的领域中的每一个并没有给出太多的性能优势，不是吗？或者如果是，还有其他方法吗？

另外，我也很困惑如何制作

equals 等同于对象标识，这是一种廉价的引用比较（Scala 中的 eq）。

在代码中。

我认为上面提到的意图技术基本上是一个对象缓存。因此，我参考了Java中小的不可变对象的缓存策略一文中提到的技术？. 但是，我仍然看不到大型对象的有效方法是什么。

为方便起见，我引用了帖子中的缓存技术（Java 中）并指出了///我的想法和问题：

private static final int N_POINTS = 10191; 
private static final Point[] POINTS = new Point[N_POINTS];

public static Point of(int x, int y, int z) {
    int h = hash(x,y,z); ///  I can use hash code of each complicated field to construct the value
    int index = (h & 0x7fffffff) % N_POINTS;
    Point p = POINTS[index];
    if (p != null && p.x == x && p.y == y && p.z == z) /// Not working for large objects?
       return p;
    return POINTS[index] = new Point(x,y,z);
}

总而言之，为大型对象实施有效缓存策略的最佳实践是什么，以便我可以HashSet在 Scala 中利用？

谢谢，

4

1 回答 1

4

实习的目标是使equals方法能够使用引用相等来实现：（ this eq that或this == that在 Java 中）。很明显，与比较某些字段集的更传统的方法相比，此实现将具有最佳的运行时特性。 equals

这种比较仅在每个“唯一对象”只有一个实例时才有效，该实例由对象的某些字段集确定。

实习生只有在实习生操作的前期成本可以完全被由equals驱动的（可能很多）调用的最小成本所抵消的情况下才有效HashMap。

正如您所指出的，这种实习可能需要一种可能成本高昂的缓存机制：存在运行时开销（执行检查）和内存开销（缓存大小）。

  • 最直接的缓存方式是使用HashMap, 和传统的equals. hashCode应该懒惰；缓存它的结果，因此不需要重新计算。可能需要考虑线程问题。

  • 实现这种缓存的一种方法是使用trie，可能在每个节点上使用哈希表实现，并且每个“级别”对应于对象中的一个字段（第一级 - 字段 1、第二级、字段 2 等...) 用于“用于建立唯一性的字段集”。

还有其他可行的方法来实现这样的缓存。请原谅我避免进一步讨论此类问题，并请允许我提出避免处理该问题的方法。

选项 1：不缓存

声明：通过使用快速散列（并在内部缓存它）、“传统”实现以及从 a or足够的最小大小开始，您可能会获得足够有效的结果equalsHashMapHashSet

理想情况下，哈希表中的冲突很少，调用次数equals最少。

选项 2：将多个字段映射为一个唯一字段String

[此方法假定“唯一定义对象的字段”是不可变的。如果这不是真的，可以进行适当的调整来补偿。]

构建并缓存private unique: String与唯一对象实例相对应的 a。例如，对于一些简单的对象，以下内容可能是唯一的：

“用于建立唯一性的字段集”的字符串值的串联，以逗号分隔。

了解您的对象/字段特征将有助于确定如何创建这样一个唯一的字符串。

有了这样一个值，我们可以避免单独的实习生/缓存equals机制，并通过同时实现hashCode 这个unique字符串来保留很多好处：

def equals(thatObj: Any) = thatObj match {
    case that : MyType => unique.equals(that.unique)
    case _             => false
  }

def hashCode() = unique.hashCode

选项 2 的替代方案：

[编辑：Rüdiger Klaehn 提供了这个链接，它提供了令人信服的证据来避免 String.intern() ]

使用String.intern并调整equals以利用它：

private val unique = buildUnique().intern

def equals(thatObj: Any) = thatObj match {
    case that : MyType => unique.eq(that.unique) // In Java: unique == that.unique
    case _             => false
  }
于 2013-08-05T04:02:43.503 回答