Datenstruktur zum Entwerfen eines Caches mit effizientem Einfügen, Löschen und dem Abrufen des höchsten Werts

Question

Ich muss einen Cache mit normalen Cache-Operationen implementieren, zusammen mit der Möglichkeit des schnellen Abrufs des maximalen Elements aus dem Cache.

Können Sie bitte Datenstrukturen vorschlagen, um dies zu implementieren?

Ich dachte daran, Hash-Karte zusammen mit einer Liste zu verwenden, um das minimale Element zu erhalten.

Andere Ansätze mit höherer Komplexität vorschlagen.

Answer 1

Heap ist ideal für die schnelle Wiedergewinnung von max Element.

Answer 2

Es gibt einen Strukturtyp, den ich Exponential-Lookaside-Listen nenne, die häufig von OS verwendet werden, um freie Speicherbereiche zu verfolgen. Sie beginnen mit einem gewissen Basisgröße N (irgendwo zwischen 8 Bytes, und der Seitengröße des OS) und dann ein Array bauen (oder Stapel) von Listen:

[list N] 
[list N*2] 
[list N*4] 
[list N*8] 
... 

Und so weiter bis zu einem gewissen Maximum. Um sie beizubehalten, nehmen Sie einfach die Größe eines neuen Eintrags (S) und verwenden dann LOG2 (S/N) als Ihren Offset in das lists-Array, um zu bestimmen, welcher Liste der neue Chunk hinzugefügt werden soll. Wenn Sie Ihren größten Chunk freigeben (oder zurückgeben) müssen, scannen Sie einfach von der Liste mit der höchsten Größe nach unten, bis Sie die erste nicht leere Liste finden, und suchen Sie nach dem größten Chunk in dieser Liste.