最佳HashSet初始化(Scala | Java)

Question

我正在写一个人工智能来解决" 生命迷宫 "之谜.尝试将状态存储为a HashSet会减慢一切.没有一组探索状态,运行它会更快.我相当自信我的节点(状态存储)实现了equals,hashCode并且测试显示HashSet不会添加重复状态.我可能需要重新修改这个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设置

Answer 1

好的,首先,请更换

override def hashCode(): Int =

同

override lazy val hashCode: Int = 

因此,grid.height*grid.width每次需要访问哈希码时,都不会计算()浮点功率.这应该会大大加快速度.

然后,除非你以某种方式依赖具有紧密哈希码的close单元格,否则不要重新发明轮子.使用scala.util.hashing.MurmurHash3.seqHash或某些来计算你的哈希值.这应该会使你的哈希速度增加20倍左右.(仍然保持懒惰的val.)

然后,您只需要从所需的集合操作中获得开销.现在,除非你有很多0x0网格,否则你正在耗尽绝大多数时间等待math.pow给你一个结果(并冒着一切变得危险,Double.PositiveInfinity或者0.0,取决于值的大小,这会产生什么哈希冲突会进一步降低速度.)