2

バックエンドから返されたデータには多くの参照データが含まれており、効率的にアクセスする必要があるため、(オブジェクトの id) => (オブジェクト自体) 型のルックアップを作成することを考えています。オブジェクトの ID は文字列として返されますが、ハッシュ キーとして整数の方が文字列よりも速いのでしょうか?

playerLookup = {};
for (var i = 0; i < players.length; i++) {
  var player = players[i];
  playerLookup[player.id] = player;
  // vs.
  playerLookup[parseInt(player.id)] = player;
}

jsperf テストhttp://jsperf.com/testasdfaによると、整数ルックアップは Chrome でかなり (~25%) 高速です。シナリオが適切にテストされているかどうかはわかりません。どう思いますか？

4

1 に答える 1

1

私の意見では、要素を見つける最速の方法はモジュラー ハッシュ テーブルを使用することです。

playerLookup を n 要素の配列にし、配列の各要素を -1 (またはビットがまだ設定されていないことを知らせる何らかの値) に設定します。

playerId を保存するときは、playerLookup[parseInt(player.id) % n]

この方法でハッシュ テーブルからアイテムを見つける作業の複雑さは 1 ですが、上記のメソッドの作業の複雑さは x です。ここで x = playerLookup.length (文字列または数値をキーとして使用しているかどうかに関係なく) .

ハッシュ テーブルを小さくするには、より小さい n を選択します。n が小さいほど、衝突が発生する可能性が高くなります。

衝突

衝突に対処するには、playerLookup の各要素を配列にします。すでに別のプレーヤーが含まれている場所で playerLookup に playerId を追加する場合は、このプレーヤーと一緒に新しいプレーヤーをリストします (つまり、両方が同じ場所にあるということです)。プレーヤーを検索し、ハッシュテーブルに複数のプレーヤーが含まれるスポットを見つけた場合は、プレーヤーが見つかるまでこの配列全体を反復します。この反復は、最初に考えた実装と同じ作業の複雑さになりますが、次の 2 つの利点があります。

  1. モジュラー ハッシュ テーブルのおかげで、発生する可能性も低くなります。

  2. それが発生した場合、繰り返し処理している配列は、平均して、実装した元の配列よりも n 倍小さくなります (n はモジュラス変数です)。

数学的な理由から (モジュラスによる)、n には素数を選択することをお勧めします。

于 2013-01-17T03:01:58.363 に答える