4

以前に評価された位置のハッシュ テーブルを利用して (うまくいけば) 検索時間を短縮するチェス プログラムを作成しています。唯一の問題は、ArrayList を使用してハッシュ値を格納していることと、格納した位置の数に基づいてルックアップ時間が長くなることです。現在のサイズに依存しないルックアップ時間を持つハッシュ テーブルを取得するにはどうすればよいですか? （すみません、私はJavaの初心者です。Objective Cは本当に私のものです）

編集：問題があれば、私は Zobrist 高速ハッシュ技術を使用しています。いくつかの試行に基づいて、大量の時間を費やすのはハッシュ キーの生成ではないと判断しました。ハッシュ方法は非常に高速で、速度への影響はほとんどわかりません。

4

3 に答える 3

5

The standard Java HashMap is pretty good and already available to you, but if you want the screamingly fastest map in Java use Trove ( http://trove4j.sourceforge.net/html/overview.html ) which is filled with data structures that are optimized for performance.

于 2013-01-09T02:31:18.503 に答える
4

最初の予備的な注意：チェスの専門用語では、転置テーブルという用語は「ハッシュテーブル」よりも一般的であり、Googleでより良い検索結果を提供します。

これを念頭に置いて、転置テーブルと汎用ハッシュテーブル（JavaMapなど）の間には重要な違いがあります。

マップは、新しい値が挿入されたときに既存のエントリが削除されないことを保証する連想配列です。通常、これはあなたが望むものですが、チェスエンジンを書くとき、古いエントリを削除または上書きしないと、すぐにメモリが不足します。

対照的に、転置テーブルはキャッシュであり、最新のエントリのみが含まれます。これは、現在の位置のハッシュ値によってアドレス指定される単純な固定サイズの配列として実装できます。キーを計算するためのよく知られた非常に効率的な方法は、Zobristハッシュです（質問ですでに言及しています）。このキーは、配列にインデックスを付けるために使用されます。新しいエントリが追加されると、既存のエントリが上書きされます。

アイデアを説明するためのいくつかの擬似コードを次に示します。

// the transposition table entry
class TTEntry {
  long hashKey; // should be at least 64-bit to be safe

  // other information, e.g.:
  Move move;
  int distance;
  // ...
}

TTEntry[] ttable = ... // the more memory, the better

Entry getTTEntry(Board board) {
  long hashKey = board.getHashKey();
  int index = hashKey % ttable.length;
  return ttable[index];
}

void store(Board board) {
  Entry entry = getTTEntry(board);
  entry.hashKey = board.getHashKey();
  entry.move = ...;
  entry.distance = ...;
}

void probe(Board board) {
  Entry entry = getTTEntry(board);
  if (entry.hashKey == hashKey) {
    // entry found
    // ... do something with entry.move and entry.distance
  }
}

使用したとのことですArrayListが、保存されている位置の数に応じてルックアップ時間が長くなりました。上記の例の手法を使用する場合、それは決して起こり得ません。検索された位置の数に依存しないだけでなく、HashMap内部がはるかに複雑な、よりも高速になります。

于 2013-01-14T23:12:37.710 に答える
2

java.util.HashMapあなたの最善の策です。キー ルックアップはO(1)(償却) されており、非常に優れた汎用 HashMap です。

それが最適であると言っているわけではありません。方法を知っていて、多くの時間/決定がある場合は、特別なケースにより適したカスタムハッシュマップ実装を設計できます。しかし、通常の HashMap は間違いなく開始する場所です。後でいつでも最適化できます。

于 2013-01-09T02:23:22.040 に答える