1

私が知っている b-tree や rb-tree などのデータ構造は、同じキーを探し続けても変わりません。頻繁に使用されるキーの検索を高速化するために、実行時に最適化されるデータ構造を探しています。今、私はこのような単純な実装を持っています:

ValueType MyNaiveMap::get(KeyType key) {
  innerMap.addFreq(key);
  if (key == mostFreqUsedKey1) {
    return val1;
  } else if (key == mostFreqUsedKey2) {
    return val2;
  }
  else {
    return innerMap.get(key);
  }
}

キーは常にint私のケースにあります。

アップデート：

ハッシュマップについて言及するのを忘れていました。マップが非常に大きなサイズになる可能性があるため、ランタイムで O(n) 複雑なサイズ変更を回避しようとしていました。

4

2 に答える 2

2

事前に合計サイズがわかっている場合、またはサイズ変更による O(n) 個の挿入 (ただし、平均的なケースでは O(1) 償却される) が問題ない場合は、ハッシュ テーブルが最適なオプションだと思います。サイズ変更時にテーブル全体をコピーするという 1 回限りのヒットは、インクリメンタル サイズ変更を使用して複数の操作に分散することもできます。

メモリを浪費しているように感じるかもしれない衝突を避けるために、ハッシュテーブルを部分的に空にしておく必要があります。しかし、ツリーベースのマップでは、通常、アイテムごとに少なくとも 1 つの追加ポインターがあり、これもかなりの量のメモリを「浪費」します。また、ハッシュ テーブルを使用すると、どれだけ空にしておくかを微調整して、パフォーマンスとメモリを部分的に交換することができます (またはその逆)。

しかし、最近アクセスしたキーを検索するために最適化されたツリーベースのデータ構造もあります: splay treeです。ローテーションを使用して、最近使用されたキーをルートの近くに保持しながら、挿入と検索のために O(log n) の償却された最悪のケースを維持します。(その「償却された」ビットは重要です。一部の操作はまだ O(n) である可能性があります)。

于 2013-01-22T19:57:57.393 に答える
1

最も X 回使用された値/キーを内部的に追跡できます。最初にチェックするこれらの値のクイック キャッシュを用意します (より大きなデータ ツリーをチェックする前に)。アイテムがアクセス/表示された回数を追跡します。ビューで、そのアイテムがリストの最後のアイテムよりも多く表示された場合、ミニ リストでの配置を把握できます。このように、このクイック ルックアップに新しいアイテムを追加するかどうかを確認するには、最後の値をチェックして、それを置き換える必要があるかどうかを確認するだけで済みます。

上位のルックアップ値を定期的に並べ替えます。

于 2013-01-22T19:13:11.223 に答える