2

「 MazeofLife」パズルを解くためのAIを書いています。状態を保存しようとすると、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

詳細については、ハッシュ関数を参照してください。グリッド値をバイト単位で2つの配列に格納し、タプルを使用してアクセスします。

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、初期容量が設定されている場合でも、設定なしの場合は7秒未満であるのに対して80秒かかります

4

2 に答える 2

6

さて、最初に、交換してください

override def hashCode(): Int =

と

override lazy val hashCode: Int =

grid.height*grid.widthしたがって、ハッシュコードにアクセスする必要があるたびに（）浮動小数点パワーを計算する必要はありません。それは物事を非常にスピードアップするはずです。

次に、近いハッシュコードを持つ近いセルに何らかの形で依存しない限り、車輪の再発明を行わないでください。または何かを使用scala.util.hashing.MurmurHash3.seqHashして、ハッシュを計算します。これにより、ハッシュがさらに20倍ほど高速化されます。（それでも怠惰な値を維持します。）

そうすれば、必要な設定操作からのオーバーヘッドだけが得られます。現在、0x0グリッドがたくさんない限り、math.powが結果を出すのを待つ時間の圧倒的大部分を使い果たしています（そして、値の大きさに応じて、すべてがDouble.PositiveInfinityまたはになるリスクがあります。0.0物事をさらに遅くするハッシュ衝突）。

于 2013-02-05T20:00:43.410 に答える
2

以下は、すべてのオブジェクトが不変であることを前提としていることに注意してください。これは、ハッシュを使用する場合の正しい仮定です。

また、最適化を適用する前にコードのプロファイルを作成する必要があります（たとえば、JDKに付属している無料のjvisualvmを使用してください）。

高速なメモ化hashCode

ハッシュコードの計算は通常、ボトルネックです。オブジェクトごとに1回だけハッシュコードを計算し、その結果を保存することで、スペース消費量の増加（おそらく中程度）を犠牲にして、ハッシュコード計算のコストを最小限に抑えることができます（オブジェクトの作成時に1回）。これを実現するには、をまたはにdef hashCode変換します。lazy valval

高速インターンequals

コストをhashCode削減すると、コンピューティングequalsが問題になります。equals一般に、収集フィールドや深層構造には特に費用がかかります。

インターンすることでコストを最小限に抑えることができequalsます。これは、ファクトリメソッドを介してクラスの新しいオブジェクトを取得することを意味します。ファクトリメソッドは、要求された新しいオブジェクトがすでに存在するかどうかを確認し、存在する場合は、既存のオブジェクトへの参照を返します。このタイプのすべてのオブジェクトがこのように構築されていると主張する場合、それぞれの個別のオブジェクトのインスタンスは1つだけであり、オブジェクトIDと同等になることがわかります。これは、安価な参照比較です（Scalaで）。equalseq

于 2013-02-05T20:38:47.573 に答える