2

我正在编写一个人工智能来解决“生命迷宫”难题。尝试将状态存储到 aHashSet会减慢一切。在没有一组探索状态的情况下运行它会更快。我相当有信心我的节点（状态存储）实现了 equals 并且hashCode测试显示 aHashSet不会添加重复状态。我可能需要重新设计该hashCode功能，但我相信减慢它的速度是HashSet重新散列和调整大小。

我尝试将初始容量设置为一个非常大的数字，但它仍然非常慢：

 val initCapacity = java.lang.Math.pow(initialGrid.width*initialGrid.height,3).intValue()
 val frontier = new QuickQueue[Node](initCapacity)

这是快速队列代码：

class QuickQueue[T](capacity: Int) {

val hashSet = new HashSet[T](capacity)
val queue = new Queue[T]
    //methods below

有关更多信息，这里是哈希函数。我将网格值以字节为单位存储在两个数组中，并使用元组访问它：

override def hashCode(): Int = {
  var sum = Math.pow(grid.goalCoords._1, grid.goalCoords._2).toInt
  for (y <- 0 until grid.height) {
     for (x <- 0 until grid.width) {
        sum += Math.pow(grid((x, y)).doubleValue(), x.toDouble).toInt
     }
     sum += Math.pow(sum, y).toInt
  }
  return sum
}

关于如何设置HashSet不会减慢速度的任何建议？也许另一个关于如何记住探索状态的建议？

PS 使用java.util.HashSet，即使设置了初始容量，也需要 80 秒 vs < 7 秒 w/o

4

2 回答 2

6

好的，首先，请更换

override def hashCode(): Int =

和

override lazy val hashCode: Int =

所以每次需要访问散列码时都不需要计算 ( grid.height*grid.width) 浮点幂。这应该会大大加快速度。

然后，除非您以某种方式依赖具有紧密哈希码的紧密单元，否则不要重新发明轮子。使用scala.util.hashing.MurmurHash3.seqHash或类似的东西来计算你的哈希。这应该将您的哈希速度提高 20 倍左右。（仍然保留懒惰的 val。）

然后，您只有所需的集合操作的开销。现在，除非您有很多 0x0 网格，否则您将花费​​绝大多数时间等待 math.pow 给您一个结果（并且冒着一切风险变成Double.PositiveInfinityor 0.0，这取决于值的大小，这将创建哈希冲突会进一步减慢速度）。

于 2013-02-05T20:00:43.410 回答
2

请注意，以下假设您的所有对象都是不可变的。在使用散列时，这是一个合理的假设。

此外，您应该在应用优化之前分析您的代码（例如使用 JDK 附带的免费 jvisualvm）。

快速记忆hashCode

计算哈希码通常是一个瓶颈。通过为每个对象只计算一次哈希码并存储结果，您可以将哈希码计算的成本降至最低（在对象创建时一次），但会增加空间消耗（可能适中）。为了实现这一点，将 thedef hashCode变成lazy valor val。

快速实习equals

hashCode一旦消除了成本，计算equals就会成为问题。equals一般来说，对于收集领域和深层结构来说，成本特别高。

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

于 2013-02-05T20:38:47.573 回答