Quelle structure de données dois-je utiliser pour cette stratégie de mise en cache?

Je travaille sur une application .NET 4.0, qui effectue un calcul assez cher sur deux doubles retournant un double. Ce calcul est effectué pour chacun de plusieurs milliers d' articles . Ces calculs sont effectués dans un Tasksur un thread threadpool.

Certains tests préliminaires ont montré que les mêmes calculs sont effectués encore et encore, donc je voudrais mettre en cache n résultats. Lorsque le cache est plein, je voudrais jeter l' élément le moins souvent utilisé récemment. ( Edit: je me suis rendu compte que le moins souvent n'a pas de sens, car lorsque le cache est plein et que je remplacerais un résultat par un nouveau calculé, celui-ci serait le moins souvent utilisé et immédiatement remplacé la prochaine fois qu'un nouveau résultat est calculé et ajouté au cache)

Afin de mettre en œuvre cela, je pensais à utiliser un Dictionary<Input, double>(où Inputserait une mini-classe stockant les deux valeurs doubles d'entrée) pour stocker les entrées et les résultats mis en cache. Cependant, je devrais également garder une trace du moment où un résultat a été utilisé la dernière fois. Pour cela, je pense que j'aurais besoin d'une deuxième collection stockant les informations dont j'avais besoin pour supprimer un résultat du dicton lorsque le cache était plein. Je crains que le fait de conserver constamment cette liste triée ait un impact négatif sur les performances.

Y a-t-il une meilleure façon (c'est-à-dire plus performante) de faire cela, ou peut-être même une structure de données commune que je ne connais pas? Quels types de choses dois-je profiler / mesurer pour déterminer l'optimalité de ma solution?

Si vous souhaitez utiliser un cache d'expulsion LRU (expulsion la moins récemment utilisée), alors une bonne combinaison de structures de données à utiliser est probablement:

• Liste liée circulaire (comme file d'attente prioritaire)
• dictionnaire

C'est pourquoi:

• La liste chaînée a un temps d'insertion et de retrait O (1)
• Les nœuds de liste peuvent être réutilisés lorsque la liste est pleine et qu'aucune allocation supplémentaire ne doit être effectuée.

Voici comment l'algorithme de base devrait fonctionner:

Les structures de données

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

1. L'entrée est reçue
2. Si le dictionnaire contient la clé
   • renvoyer la valeur stockée dans le nœud et déplacer le nœud au début de la liste
3. Si le dictionnaire ne contient pas la clé
   • calculer la valeur
   • stocker la valeur dans le dernier nœud de la liste
   • si le dernier n'a pas de valeur, supprimez la clé précédente du dictionnaire
   • déplacer le dernier nœud à la première position.
   • stocker dans le dictionnaire la paire de valeurs de clé (entrée, nœud).

Certains avantages de cette approche sont, la lecture et la définition d'une valeur de dictionnaire approche O (1), l'insertion et la suppression d'un nœud dans une liste chaînée est O (1), ce qui signifie que l'algorithme approche O (1) pour la lecture et l'écriture de valeurs vers le cache, et évite les allocations de mémoire et les opérations de copie de mémoire de bloc, ce qui le rend stable d'un point de vue mémoire.

Cela semble demander beaucoup d'efforts pour un seul calcul étant donné la puissance de traitement dont vous disposez sur le PC moyen. En outre, vous aurez toujours les frais du premier appel à votre calcul pour chaque paire de valeurs uniques, donc 100 000 paires de valeurs uniques vous coûteront toujours le temps _n * 100 000 au minimum. Considérez que l'accès aux valeurs dans votre dictionnaire deviendra probablement plus lent à mesure que le dictionnaire s'agrandit. Pouvez-vous garantir que la vitesse d'accès à votre dictionnaire compensera suffisamment pour fournir un rendement raisonnable par rapport à la vitesse de votre calcul?

Quoi qu'il en soit, il semble que vous devrez probablement envisager de trouver un moyen d'optimiser votre algorithme. Pour cela, vous aurez besoin d'un outil de profilage, tel que Redgate Ants, pour voir où se trouvent les goulots d'étranglement et pour vous aider à déterminer s'il existe des moyens de réduire certains des frais généraux que vous pourriez avoir concernant les instanciations de classe, les traversées de liste, la base de données accès, ou quoi que ce soit qui vous coûte tellement de temps.

Une pensée est pourquoi ne mettre en cache que les résultats n? Même si n est 300 000, vous n'utiliserez que 7,2 Mo de mémoire (plus tout ce qui est supplémentaire pour la structure de la table). Cela suppose bien sûr trois doubles 64 bits. Vous pouvez simplement appliquer la mémorisation à la routine de calcul complexe elle-même si vous ne craignez pas de manquer d'espace mémoire.

L'approche avec la deuxième collection est très bien. Il doit s'agir d'une file d'attente prioritaire qui permet de trouver / supprimer rapidement des valeurs min et également de modifier (augmenter) les priorités dans la file d'attente (cette dernière partie est la plus difficile, non prise en charge par la plupart des implémentations de file d'attente prio simples). La bibliothèque C5 possède une telle collection, on l'appelle IntervalHeap.

Ou bien sûr, vous pouvez essayer de créer votre propre collection, quelque chose comme a SortedDictionary<int, List<InputCount>>. ( InputCountdoit être une classe combinant vos Inputdonnées avec votre Countvaleur)

La mise à jour de cette collection lors de la modification de votre valeur de comptage peut être implémentée en supprimant et en réinsérant un élément.

Comme indiqué dans la réponse de Peter Smith, le modèle que vous essayez de mettre en œuvre s'appelle la mémorisation . En C #, il est assez difficile d'implémenter la mémorisation de manière transparente sans effets secondaires. Le livre d'Oliver Sturm sur la programmation fonctionnelle en C # donne une solution (le code est disponible en téléchargement, chapitre 10).

En F #, ce serait beaucoup plus facile. Bien sûr, c'est une grande décision de commencer à utiliser un autre langage de programmation, mais cela peut valoir la peine d'être considéré. Surtout dans les calculs complexes, cela rendra plus de choses plus faciles à programmer que la mémorisation.