5

最近使用したキャッシュを設計するにはどうすればよいですか？

あなたがいくつかのアイテムを訪れたとしましょう。これらのアイテムを保持するためのデータ構造を設計する必要があります。各アイテムは、最後に訪問した時間に関連付けられています。

アイテムにアクセスするたびに、データ構造でそのアイテムを確認してください。アイテムがキャッシュにある場合は、その訪問時間を更新します。それ以外の場合は、キャッシュに挿入します。キャッシュサイズは固定されています。キャッシュサイズがいっぱいの場合は、最も古いアイテムを削除してください。

私の解決策：

  1. マップを使用<item、visitTime>

  2. 初期化：マップをf（visitTime）で降順に並べ替えます。O（nlg n）

  3. アイテムにアクセスした場合は、マップでO（lg n）を使用してアイテムを検索します。

  4. マップにある場合は、時刻O（1）を更新します。マップO（lg n）を並べ替えます。

  5. そうでない場合は、マップに挿入してから並べ替えます。O（lg n）

  6. マップサイズ>固定サイズの場合、最後の要素O（1）を削除します。

別の解決策：

  1. ハッシュテーブルを使用<item、visitTime>

  2. O（n lgn）で並べ替えます。

  3. アイテムが訪問された場合、O（1）を使用してタルブでアイテムを検索します。

  4. テーブルにある場合は、時刻O（1）を更新します。テーブルO（n lg n）を並べ替えます。

  5. そうでない場合は、テーブルに挿入してから並べ替えます。O（n lg n）

  6. テーブルサイズ>固定サイズの場合、最後の要素O（1）を削除します。

より良い解決策はありますか？の上） ？

4

6 に答える 6

4

二重リンクリストを使用すると、O（1）挿入（検索後）、O（1）削除、O（n）検索が行われます。

前面に新しいアイテムを挿入すると仮定します。

キャッシュがいっぱいでない場合は、前面に追加するだけです（O（1））。

アイテムを更新する必要がある場合は、アイテムを見つけて（O（n））、リンクリストから削除して（O（1））、先頭に追加します（O（1））。

新しいアイテムを挿入するために最も古いものを削除する必要がある場合は、終了要素（O（1））を削除し、先頭に挿入します（O（1））[注：この場合、最初にリストを検索して表示する必要がありますアイテムがまだキャッシュにない場合は、O（n）]。

リンクリストは、検索によって最後の要素が残るため、同時に表示することもできます。

于 2011-11-29T19:39:58.107 に答える
3

Python の LRU キャッシュには、O(1) の挿入、削除、および検索があります。その設計では、二重にリンクされたエントリのリスト (古いものから新しいものへと並べられます) とハッシュ テーブルを使用して、特定のリンクを見つけます。

これは、非常に基本的な Python の 40 行未満の単純化された (ただし高速な) バージョンです。Python のソリューションを C++ に翻訳するのは難しくありません。

class LRU_Cache(object):

    def __init__(self, original_function, maxsize=1000):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        self.head = [None, None, None, None]        # oldest
        self.tail = [self.head, None, None, None]   # newest
        self.head[NEXT] = self.tail

    def __call__(self, *key):
        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        mapping, head, tail = self.mapping, self.head, self.tail
        sentinel = object()

        link = mapping.get(key, sentinel)
        if link is sentinel:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                oldest = head[NEXT]
                next_oldest = oldest[NEXT]
                head[NEXT] = next_oldest
                next_oldest[PREV] = head
                del mapping[oldest[KEY]]
            last = tail[PREV]
            link = [last, tail, key, value]
            mapping[key] = last[NEXT] = tail[PREV] = link
        else:
            link_prev, link_next, key, value = link
            link_prev[NEXT] = link_next
            link_next[PREV] = link_prev
            last = tail[PREV]
            last[NEXT] = tail[PREV] = link
            link[PREV] = last
            link[NEXT] = tail
        return value

if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))
于 2011-11-29T19:59:08.790 に答える
1

同じデータを共有する2つのコレクションを使用します。1つのハッシュテーブルと1つのリストを用意します。ハッシュテーブルを使用して、アイテムが存在するかどうかを確認し、リスト内でそれを見つけます（ハッシュマップの値はリストイテレーターです）。リストを使用して、アイテム間の順序を維持します。2つのコレクションを同期します（リストからアイテムを削除するときは、対応するアイテムをハッシュテーブルから削除します）。リストイテレータは、リスト内でアイテムを再配置したときに変更されないようにする必要があります。

編集：std :: listイテレータは、要素の追加と削除の間中有効です。ただし、参照している要素のイテレータが削除されていない場合に限ります。ウィキペディアの「容量と割り当て」セクションの最後の行を参照してください。

于 2011-11-29T19:44:12.887 に答える
1

java.util.LinkedHashSetを使用して Java で実行できます。これは、アイテムが挿入された順序を保持するリンクされたリストと結合されたハッシュ テーブルです。キーの分散がうまく機能すれば、(予想される) 一定時間の検索、挿入、および削除を取得する必要があります。

要素をガベージ コレクションできる自動メカニズムを実装するWeakHashMapも参照してください。

于 2011-11-29T20:00:30.007 に答える
0

boost::multi_indexを見て ください。表示される例の1つは、MRUリストです。

于 2011-11-29T21:10:02.767 に答える
0

コンテナを実際にソートする必要はありません。マップまたはベクトルにアイテムを追加し、それを直線的に調べて、必要なアイテム（または最も古いアイテム）を見つけます。

その後、になりますO(n)。

于 2011-11-29T19:38:11.793 に答える