Wie gestalte ich einen neuesten kürzlich gebrauchten Cache?

Question

Wie gestalte ich einen neuesten kürzlich gebrauchten Cache?

Angenommen, Sie haben einige Artikel besucht. Sie müssen eine Datenstruktur entwerfen, um diese Elemente zu halten. Jeder Artikel ist mit der neuesten besuchten Zeit verbunden.

Überprüfen Sie ihn jedes Mal, wenn Sie einen Artikel besuchen, in der Datenstruktur. Wenn der Artikel im Cache war, aktualisieren Sie seine Besuchszeit. Ansonsten fügen Sie es in den Cache ein. Die Cache -Größe wird behoben, wenn sie voll ist, löschen Sie das älteste Element.

Meine Lösung:

1. Verwenden Sie eine Karte <elements, Vieittime>

2. Initalizion: Sortieren Sie die Karte mit F (Visitgtime) mit absteigender Reihenfolge. O (NLG N)

3. Wenn ein Artikel besucht wird, suchen Sie ihn in der Karte mit O (LG N).

4. Wenn es in der Karte war, aktualisieren Sie die Zeit O (1). Sortieren Sie die Karte O (LG N).

5. Wenn nicht, fügen Sie es in die Karte ein und sortieren Sie sie dann. O (LG N)

6. Wenn Kartengröße> feste Größe festgelegt ist, löschen Sie das letzte Element O (1).

Eine andere Lösung:

1. Verwenden Sie Hashtable <item, VisittTime>

2. Sortieren Sie es o (n lgn).

3. Wenn ein Artikel besucht wird, suchen Sie ihn im Talbe mit O (1).

4. Wenn es in der Tabelle war, aktualisieren Sie die Zeit O (1). Sortieren Sie die Tabelle O (n lg n).

5. Wenn nicht, setzen Sie es in die Tabelle ein und sortieren Sie sie. O (n lg n)

6. Wenn Tabellengröße> Festgröße festgelegt ist, löschen Sie das letzte Element O (1).

Gibt es bessere Lösungen? An) ?

Answer 1

Wenn Sie eine doppelt verknüpfte Liste verwenden, erhalten Sie die Einfügung von O (1) (nach der Suche), o (1) Löschung, o (n) Suche.

Angenommen, Sie setzen neue Elemente vorne ein:

Wenn der Cache nicht voll ist, fügen Sie einfach vorne hinzu (o (1)).

Wenn Sie ein Element aktualisieren müssen, finden Sie es (o (n)), entfernen Sie ihn aus der verknüpften Liste (o (1)) und fügen Sie dann nach vorne (o (1)) hinzu.

Wenn Sie das älteste zum Einfügen eines neuen Elements löschen müssen, löschen Wenn das Element noch nicht im Cache ist, also o (n)].

Eine verknüpfte Liste kann Ihnen auch gleichzeitig geben, da die Suche Sie im letzten Element hinterlässt.

Answer 2

Pythons LRU -Cache hat o (1) Einfügung, Löschung und Suche. Sein Design verwendet eine doppelt verknüpfte Liste von Einträgen (ältesten ältesten zu Neuen) und eine Hash-Tabelle, um einen bestimmten Link zu lokalisieren.

Hier ist eine vereinfachte (aber schnelle) Version in weniger als 40 Zeilen von sehr einfachem Python. Es sollte nicht schwer sein, Pythons Lösung in C ++ zu übersetzen:

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))

Answer 3

Sie können es in Java mit dem machen java.util.linkedhashset. Es handelt sich um eine Hash -Tabelle, die mit einer verknüpften Liste in Verbindung gebracht wird, die die Reihenfolge bewahrt, in der die Elemente eingefügt wurden. Sie sollten (erwartete) konstante Zeitaufnahmen, Einfügungen und Umzüge erhalten, wenn die wichtigste Ausbreitung gut funktioniert.

Möglicherweise möchten Sie sich auch ansehen WeaChasMap Dies implementiert einen automatisierten Mechanismus, bei dem Elemente Müll gesammelt werden können.

Answer 4

Verwenden Sie zwei Sammlungen, die dieselben Daten teilen. Haben Sie einen Hashtable und eine Liste. Verwenden Sie Hashtable, um zu überprüfen, ob das Element existiert, und um es in der Liste zu finden (Wert der Hash -Karte ist Listen -Iterator). Verwenden Sie die Liste, um die Reihenfolge zwischen den Elementen zu verwalten. Synchronisieren Sie zwei Sammlungen (beim Entfernen von Elementen aus der Liste entfernen Sie das entsprechende Element aus Hashtable). List Iterator muss so sein, dass es sich nicht ändert, wenn Sie das Element in die Liste verlegen.

Bearbeiten: STD :: List Iterator ist während der Addition und des Löschens von Elementen gültig, vorausgesetzt, dass der Iterator mit sehr Elementen nicht entfernt wird. Siehe letzte Zeilen im Abschnitt Kapazität und Zuteilung in Wikipedia.

Answer 5

Sie müssen den Behälter nicht wirklich sortieren. Fügen Sie einfach die Elemente zur Karte oder zum Vektor hinzu und suchen Sie sie linear, um den benötigten Element (oder den ältesten Element) zu finden.

Dann wird es sein O(n).

Answer 6

Sich ansehen Boost :: multi_index. Eines der Beispiele, die es zeigt, ist eine MRU -Liste.