LRU cache mise en œuvre dans Javascript

Ce:

https://github.com/monsur/jscache

Semble correspondre à votre cas bien que setItem (c'est-à-dire mis) soit O (N) dans le pire des cas, cela se produit si le cache est rempli lors de l'insertion. Dans ce cas, le cache est recherché pour purger les éléments expirés ou les articles les moins récemment utilisés. getItem est O (1) et l'expiration est traitée sur l'opération getItem (c'est-à-dire si l'élément expiré est expiré, le supprime et renvoie null).

Le code est assez compact pour être facilement compris.

PS Il pourrait être utile d'ajouter au constructeur l'option de spécifier le fillFactor , qui est fixé à 0,75 (ce qui signifie que lorsque le cache est purgé, sa taille est réduite au moins à 3 / 4ème de la taille maximale)

Cela vaut la peine d'être mentionné: https://github.com/rsms/js-lru

Les fonctions principales sont O (1) et le code est fortement commenté (avec l'art ASCII aussi!)

La mise en œuvre de monsur.com est O (n) lors de l'insertion uniquement parce qu'elle comporte des éléments qui expirent réellement au temps réel. Ce n'est pas un simple LRU. Si vous vous souciez simplement de maintenir les articles les plus récemment utilisés sans tenir compte du temps réel, cela peut se faire dans O (1). Une file d'attente, mise en œuvre sous la forme d'une liste doublement liée, est O (1) pour l'insertion ou la suppression à partir de la fin, et c'est tout ce que vous devriez avoir besoin d'un cache. En ce qui concerne la recherche, une carte de hachage, javascript qui facilite les pistes, devrait être bonne pour la recherche presque O (1) (en supposant que le moteur javascript utilise un bon hashmap, cela implique bien sûr). Vous avez donc une liste d'éléments liés avec une carte de hash indiquant les éléments. Manipulez les extrémités de la liste liée si nécessaire pour mettre de nouveaux articles et des objets demandés sur une extrémité et supprimer des éléments anciens de l'autre extrémité.

Ce n'est pas un cache LRU, mais j'ai ma propre implémentation de carte associée . Comme il utilise un objet JS en tant que magasin, il aura des caractéristiques de performance similaires (les objets wrapper et la fonction hash donnent une pénalité de performance).

À l'heure actuelle, la documentation est essentiellement inexistante , mais il existe une réponse SO connexe .

La méthode each() passera la clé actuelle, la valeur actuelle et un booléen indiquant s'il y a plus d'éléments en tant qu'arguments à la fonction callback.

Alternativement, la mise en boucle peut se faire manuellement via

 for(var i = map.size; i--; map.next()) { var currentKey = map.key(); var currentValue = map.value(); } 

Je suis conscient que c'est une question ancienne, mais en ajoutant un lien pour le futur référé. Consultez https://github.com/monmohan/dsjslib . Cela comporte une implémentation de cache LRU en plus de certaines autres structures de données. Ces caches (et celle-ci aussi) contiennent une liste doublement liée des entrées de cache dans l'ordre LRU, c'est-à-dire que les entrées se déplacent vers la tête lorsqu'elles sont accessibles et sont retirées de la queue lorsqu'elles sont récupérées (par exemple, par expiration ou parce que la limite de taille a été atteinte). Son O (1) car il ne s'agit que d'un nombre constant de manipulations de pointeurs.