14

最近使用されたオブジェクトのキャッシュを実装する最良の方法は何ですか?

要件と制限は次のとおりです...

  • オブジェクトはキー/値のオブジェクト/オブジェクトのペアとして保存されるため、インターフェースは Hashtable の get/put に少し似ています。
  • 「get」を呼び出すと、そのオブジェクトが最近使用されたものとしてマークされます。
  • いつでも、使用頻度の最も低いオブジェクトをキャッシュから削除できます。
  • ルックアップとパージは高速でなければなりません (Hashtable の高速のように)
  • オブジェクトの数が多い可能性があるため、リスト ルックアップは十分ではありません。
  • 実装は JavaME を使用して作成する必要があるため、サード パーティのコードや標準 Java ライブラリの適切なライブラリ クラスを使用する余地はほとんどありません。このため、私はオフザペグのソリューションの推奨ではなく、アルゴリズムの回答を探しています。
4

4 に答える 4

24

Java コレクションは、すぐに使用できるLinkedHashMapを提供します。これは、キャッシュの構築に適しています。おそらく Java ME にはこれがありませんが、ここでソースコードを取得できます。

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

単にコピーして貼り付けることができない場合は、それを見て、モバイル アプリに含めるための実装を開始する必要があります。基本的な考え方は、マップ要素を介してリンクされたリストを含めることです。誰かがプットまたは取得するたびにこれを更新しておくと、アクセス順序と使用順序を効率的に追跡できます。

removeEldestEntry(Map.Entry)ドキュメントには、メソッドをオーバーライドして MRU キャッシュを構築するための手順が含まれています。あなたが本当にしなければならないのは、LinkedHashMap次のようにメソッドを拡張してオーバーライドするクラスを作成することだけです:

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

また、クラスが挿入順または使用順で物事を格納するかどうかを指定できるコンストラクターもあるため、エビクション ポリシーにも多少の柔軟性があります。

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)

使用順序にはtrueを、広告掲載順序にはfalseを渡します。

于 2009-02-24T22:31:10.167 に答える
7

ConcurrentLinkedHashMap は、ロック要件のために構築が困難です。ロック付きの LinkedHashMap は簡単ですが、常にパフォーマンスが高いとは限りません。並行バージョンでは、ロックを分割するか、理想的には CAS 操作を作成してロックを非常に安価にすることにより、ロックの量を削減しようとします。CAS 操作のコストが高くなった場合は、同様にバケット分割が役立ちます。LRU はアクセス操作ごとに書き込みを必要とし、二重リンク リストを使用するため、これを純粋な CAS 操作で実装するのは非常に困難です。私はそれを試みましたが、アルゴリズムを成熟させ続ける必要があります。ConcurrentLinkedHashMap を検索すると、私のプロジェクト ページが表示されます...

Java ME が CAS 操作をサポートしていない場合 (これは本当だと思います)、基本的な同期しかできません。サーバー側のスレッド数が多い場合にのみパフォーマンスの問題が発生したことを考えると、LHM ではこれで十分でしょう。したがって、上記の回答に+1してください。

于 2009-02-25T01:10:15.433 に答える
2

なぜすでに実装されているものを実装するのですか？Ehcacheを使用します。

ただし、サードパーティのライブラリがまったく問題にならない場合は、次のようなデータ構造を実装しようとしていると思います。

  • 基本的には HashMap です (HashMap<Object, Object>必要に応じて拡張します)
  • Map の各値は、最も使用されているオブジェクトに基づいてソートされたリスト内のオブジェクトを指します。
  • 最近使用したオブジェクトがリストの先頭に追加されます -O(1)
  • 最も最近使用されていないものを削除するということは、リストの末尾を切り捨てることを意味します -O(1)
  • 引き続きマップのルックアップを提供しますが、最近使用したアイテムを最初に保持します...
于 2009-02-24T22:19:05.890 に答える
0

もう 1 つのアプローチは、Brian Goetz によるJava Concurrency in Practiceのセクション 5.6 を参照することです。「効率的でスケーラブルな結果キャッシュの構築」。目的に合わせてカスタマイズする必要があるかもしれませんが、Memoizer を見てください。

余談ですが、私が理解できないのは、Java に ConcurrentLinkedHashMap がすぐに使用できない理由です。このデータ構造は、キャッシュを構築するのに非常に役立ちます。

于 2009-02-24T22:58:22.830 に答える