Comment implémenter un cache le plus récemment utilisé

Quelle serait la meilleure façon de mettre en œuvre une plus récemment utilisés cache d'objets?

Ici sont les exigences et les restrictions...

Objets sont stockés en tant que clé/valeur de l'Objet/Objet paires, de sorte que l'interface serait un peu comme table de hachage get/put
Un appel à "obtenir" serait la marque de l'objet en tant que le plus récemment utilisé.
À tout moment, la moins récemment utilisée objet peut être supprimé du cache.
Des recherches et des purges doit être rapide (Comme dans la table de hachage rapide)
Le nombre d'Objets peuvent être de taille importante, les recherches dans les listes ne sont pas assez bonnes.
La mise en œuvre doit être faite à l'aide de JavaME, donc il y a peu de possibilités pour l'utilisation de la troisième partie du code ou soignée de la bibliothèque de classes à partir de la norme de bibliothèques Java. Pour cette raison, je suis à la recherche de plus pour l'algorithmique réponses, plutôt que de recommandations de hors-la-peg solutions.

source d'informationauteur izb

21

Java Collections offrent LinkedHashMap hors de la boîte, qui est bien adapté à la construction de caches. Vous n'avez probablement pas présente dans Java ME, mais vous pouvez obtenir le code source ici:

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

Si vous ne pouvez pas simplement copier-coller, le regardant devrait vous obtenir a commencé la mise en œuvre de l'un pour les inclure dans votre application mobile. L'idée de base est juste d'inclure une liste liée par les éléments de la carte. Si vous gardez cela à jour chaque fois que quelqu'un ne put ou get, vous pouvez efficacement l'accès aux voies de commande et l'utilisation de la commande.

Les documents contiennent des instructions pour la construction d'un MRU Cache en remplaçant la removeEldestEntry(la Carte.D'entrée) méthode. Tout ce que vous avez à faire est de faire une classe qui étend la classe LinkedHashMap et remplacer la méthode comme suit:
```
private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}
```
Il y a aussi un constructeur qui vous permet de spécifier si vous voulez que la classe pour stocker les choses dans l'ordre par insertion ou par l'usage, de sorte que vous avez un peu de souplesse pour votre éviction politique:
```
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)
```
Passer vrai pour une utilisation d'ordre et faux pour la commande d'insertion.
7

Un ConcurrentLinkedHashMap est difficile à construire, en raison de la verrouiller. Une LinkedHashMap avec une serrure est simple, mais pas toujours performant. Une version simultanée de tenter de réduire la quantité de verrouillage, soit par verrouillage de fractionnement ou, idéalement, faire des TAS opérations de verrouillage très bon marché. Si le CAS des opérations ne deviennent chères, alors même seau division peut être utile. Comme un LRU exige écrit pour chaque opération d'accès, et utilise une liste à double liaison, ce qui est très difficile à mettre en œuvre avec pur CAS d'opérations. J'ai tenté, mais j'ai besoin de continuer à mûrir mon algorithme. Si vous recherchez ConcurrentLinkedHashMap, vous allez voir ma page de projet...

Si Java ME ne supporte pas le CAS des opérations, je m'attends à être vrai, alors de base de synchronisation est tout ce que vous pouvez faire. C'est probablement assez bon avec un LHM, étant donné que je n'ai vu que des problèmes de performance à haute nombre de threads sur le côté serveur. Donc +1 pour les réponses ci-dessus.
2

Pourquoi mettre en place quelque chose de déjà mis en œuvre? Utilisation Ehcache.

Cependantsi les bibliothèques de tiers sont totalement hors de question, je suppose que vous êtes à la recherche pour mettre en œuvre une structure de données qui ressemble à quelque chose comme ceci:
- Est fondamentalement une HashMap (s'étend HashMap<Object, Object> si vous voulez)
- Chaque valeur de la Carte des points d'un objet dans une liste triée, basées sur ce qui est le plus utilisé.
- Objets récemment utilisés sont ajoutés à la tête de la liste - O(1)
- Purge le moins récemment utilisé un moyen de tronquer la fin de la liste - O(1)
- Encore vous donne la Carte des recherches, mais conserve encore récemment utilisé des éléments de la première...
0

Une autre approche peut être de prendre un coup d'oeil à la section 5.6 dans Java de la Simultanéité dans la Pratique par Brian Goetz: "la Construction d'un système efficace, évolutive cache de résultat". Jetez un oeil à la Memoizer, bien que vous pourriez avoir à le personnaliser à vos besoins.

Que d'un côté, ce que je ne peut pas comprendre est pourquoi Java ne dispose pas d'un ConcurrentLinkedHashMap hors de la boîte. Cette structure de données serait très utile pour la construction d'un cache.

Vous devez vous connecter pour publier un commentaire.