 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Jean-Marc Desperrier
Guest
|
 Posted: Tue Jun 07, 2005 12:51 pm Post subject: Implementer un cache en c++/STL |
 |
|
Bonjour,
Je suis à la rechercher d'une implémentation de cache limité en taille
efficace en C++/STL plutôt que de réinventer la roue en faisant moi-même.
Pour être précis, je veux parler d'un container qui stocke des éléments
indexé par une clé, avec accès par la clé, sur lequel je fixe une taille
limite, les éléments les plus anciens/moins souvent accédés étant
supprimés une fois cette taille atteinte.
Vous avez des références ?
L'accès par la clé doit être de préférence rapide, mais il faut voir
quels compromis il y a entre cette vitesse d'accès, et le temps pour
savoir quel est l'élément le plus ancien/moins accédés, et combien de
listes on stocke.
|
|
| Back to top |
|
 |
kanze@gabi-soft.fr
Guest
|
| Posted: Wed Jun 08, 2005 6:47 am Post subject: Re: Implementer un cache en c++/STL |
|
|
Jean-Marc Desperrier wrote:
| Quote: | Je suis à la rechercher d'une implémentation de cache limité
en taille efficace en C++/STL plutôt que de réinventer la roue
en faisant moi-même.
Pour être précis, je veux parler d'un container qui stocke des
éléments indexé par une clé, avec accès par la clé, sur lequel
je fixe une taille limite, les éléments les plus anciens/moins
souvent accédés étant supprimés une fois cette taille
atteinte.
Vous avez des références ?
L'accès par la clé doit être de préférence rapide, mais il
faut voir quels compromis il y a entre cette vitesse d'accès,
et le temps pour savoir quel est l'élément le plus
ancien/moins accédés, et combien de listes on stocke.
|
Il n'y a pas de collection aussi compliquée dans la STL. La
solution évidente, c'est un std::map auquel on joint un
std::list; chaque fois qu'on accède à un élément du map, on
l'enlève de la liste, et on le remet en tête. Quand le nombre
d'éléments devient trop grand, on supprime ceux en queue de la
liste. Le seul problème, c'est de rétrouver rapidement l'élément
dans la liste quand on y accède dans le map ; à la rigueur, ce
qu'on stocke dans le map, c'est des struct { List::iterator,
ElemType } (et on met à jour la partie List::iterator à chaque
accès). Mais j'avoue que chaque fois que je me suis trouvé
confronté à un problème pareil, je me suis servi d'une liste
invasive, dont les liens se trouvaient dans l'objet même. Ce qui
permet d'enlever l'objet de la liste sans autre chose que
l'objet même.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
|
|
| Back to top |
|
|
Marc Boyer
Guest
|
| Posted: Wed Jun 08, 2005 7:48 am Post subject: Re: Implementer un cache en c++/STL |
|
|
Jean-Marc Desperrier wrote:
| Quote: | Je suis à la rechercher d'une implémentation de cache limité en taille
efficace en C++/STL plutôt que de réinventer la roue en faisant moi-même.
|
Ce qui est amusant, c'est que je fais à peut prêt la même chose
en ce moment.
| Quote: | Pour être précis, je veux parler d'un container qui stocke des éléments
indexé par une clé, avec accès par la clé, sur lequel je fixe une taille
limite, les éléments les plus anciens/moins souvent accédés étant
supprimés une fois cette taille atteinte.
|
Un problème déjà, c'est que suivant la politique (FIFO/LFU),
la "bonne" structure de donnée pour stocker les infos de
conservation/effacement dans le cache sont très différents.
Pour FIFO, une list ou une dequeu sont assez évident.
Pour une LFU, ça se discute.
Pour une FIFO, on stocke les éléments eux-même dans une map,
puis on utilise une FIFO (dequeu,list) qui contient des iterateurs
sur map pour gérer l'ordre. On se base sur la bonne propriété
des map que les opérations n'invalident pas les itérateurs.
Pour une LFU, je stoquerais dans la map les élements + leurs
nombres d'accès. A côté, une liste/dequeu/vecteur triée
d'itérateur sur les éléments de la map, avec comme critère de
tri bien sur le nb d'accès.
Marc Boyer
--
Je ne respecte plus le code de la route à vélo depuis une double fracture
due au fait que j'étais le seul à le respecter.
|
|
| Back to top |
|
|
Jean-Marc Desperrier
Guest
|
| Posted: Wed Jun 08, 2005 10:11 pm Post subject: Re: Implementer un cache en c++/STL |
|
|
[email]kanze (AT) gabi-soft (DOT) fr[/email] wrote:
| Quote: | Il n'y a pas de collection aussi compliquée dans la STL.
|
Ca me semble pourtant un besoin assez courant et générique, il n'y a
rien dans Boost non plus ?
| Quote: | solution évidente, c'est un std::map auquel on joint un
std::list; [...]. Le seul problème, c'est de rétrouver rapidement l'élément
dans la liste quand on y accède dans le map ;
[...] j'avoue que chaque fois que je me suis trouvé
confronté à un problème pareil, je me suis servi d'une liste
invasive, dont les liens se trouvaient dans l'objet même.
|
Ca parait nickel ! J'avais un faible pour les solutions type LFU au
départ, mais en réfléchissant un peu plus les cas dégénérés peuvent
devenir franchement catatrophiques.
|
|
| Back to top |
|
|
Fabien LE LEZ
Guest
|
| Posted: Wed Jun 08, 2005 11:06 pm Post subject: Re: Implementer un cache en c++/STL |
|
|
On Thu, 09 Jun 2005 00:11:10 +0200, Jean-Marc Desperrier
<jmdesp (AT) alussinan (DOT) org>:
| Quote: | Il n'y a pas de collection aussi compliquée dans la STL.
Ca me semble pourtant un besoin assez courant et générique
|
Vider un conteneur est aussi un truc très courant, et pourtant la STL
ne propose aucune solution directe. Il faut faire soit-même la
fonction
template <class T> void ViderConteneur (T& t)
{
t.erase (t.begin(), t.end());
}
|
|
| Back to top |
|
|
Loïc Joly
Guest
|
| Posted: Wed Jun 08, 2005 11:36 pm Post subject: Re: Implementer un cache en c++/STL |
|
|
Fabien LE LEZ a écrit :
| Quote: | On Thu, 09 Jun 2005 00:11:10 +0200, Jean-Marc Desperrier
[email]jmdesp (AT) alussinan (DOT) org[/email]>:
Il n'y a pas de collection aussi compliquée dans la STL.
Ca me semble pourtant un besoin assez courant et générique
Vider un conteneur est aussi un truc très courant, et pourtant la STL
ne propose aucune solution directe. Il faut faire soit-même la
fonction
template <class T> void ViderConteneur (T& t)
{
t.erase (t.begin(), t.end());
}
|
Ah ?
Table 67—Sequence requirements (in addition to container)
________________________________________________
expression return type assertion/note
pre/postcondition
a.clear() void erase(begin(), end())
post: size() == 0.
________________________________________________
Ou alors tu voulais parler de l'astuce avec swap ?
--
Loïc
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Thu Jun 09, 2005 8:12 am Post subject: Re: Implementer un cache en c++/STL |
|
|
Jean-Marc Desperrier wrote:
| Quote: | kanze (AT) gabi-soft (DOT) fr wrote:
Il n'y a pas de collection aussi compliquée dans la STL.
Ca me semble pourtant un besoin assez courant et générique, il
n'y a rien dans Boost non plus ?
|
Pas à ce que je sache. Il n'y a pas de map bi-directionnel
non-plus.
La bibliothèque standard ne peut pas fournir des solutions tout
faites pour tous les problèmes. Son rôle, c'est plutôt de fornir
des mechanismes de base qui peuvent servir à implémenter des
solutions à des problèmes divers.
| Quote: | solution évidente, c'est un std::map auquel on joint un
std::list; [...]. Le seul problème, c'est de rétrouver
rapidement l'élément dans la liste quand on y accède dans le
map ; [...] j'avoue que chaque fois que je me suis trouvé
confronté à un problème pareil, je me suis servi d'une liste
invasive, dont les liens se trouvaient dans l'objet même.
Ca parait nickel ! J'avais un faible pour les solutions type
LFU au départ, mais en réfléchissant un peu plus les cas
dégénérés peuvent devenir franchement catatrophiques.
|
En plus, c'est beaucoup plus difficile à implémenter:-). Pour
qu'il soit efficace, il faut bien gerer l'aspect time ; les
utilisations anciennes ne compte pas autant que les utilisations
récentes. Il faut donc un espèce de côte affaiblissant : tu y
ajoutes une constante à chaque utilisation, à des intervales
fixes, tu en soustrais une constante à tous les éléments, et
quand il faut supprimer, tu supprimes celui dont la côte est la
plus basse. (À la place des intervales fixes, je suppose qu'on
pourrait utiliser des accès : a chaque dizième accès, par
exemple. Voir même à chaque accès.)
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Thu Jun 09, 2005 8:31 am Post subject: Re: Implementer un cache en c++/STL |
|
|
Marc Boyer wrote:
| Quote: | Jean-Marc Desperrier wrote:
Je suis à la rechercher d'une implémentation de cache limité
en taille efficace en C++/STL plutôt que de réinventer la
roue en faisant moi-même.
Ce qui est amusant, c'est que je fais à peut prêt la même
chose en ce moment.
Pour être précis, je veux parler d'un container qui stocke
des éléments indexé par une clé, avec accès par la clé, sur
lequel je fixe une taille limite, les éléments les plus
anciens/moins souvent accédés étant supprimés une fois cette
taille atteinte.
Un problème déjà, c'est que suivant la politique (FIFO/LFU),
la "bonne" structure de donnée pour stocker les infos de
conservation/effacement dans le cache sont très différents.
Pour FIFO, une list ou une dequeu sont assez évident.
Pour une LFU, ça se discute.
|
Dans les deux cas, tu as besoin de deux collections, une indexée
par la clé, et l'autre pour gerer l'ordre de suppression.
Dans le cas d'un FIFO, il te faut les deux en permanance. Dans
le cas LFU, ça dépend ; on pourrait envisager de ne créer la
deuxième collection qu'en cas de besoin.
| Quote: | Pour une FIFO, on stocke les éléments eux-même dans une map,
puis on utilise une FIFO (dequeu,list) qui contient des
iterateurs sur map pour gérer l'ordre. On se base sur la bonne
propriété des map que les opérations n'invalident pas les
itérateurs.
|
C'est une solution. En fait, comme j'ai dit, j'ai souvent mis
l'implémentation de la liste dans l'objet.
| Quote: | Pour une LFU, je stoquerais dans la map les élements + leurs
nombres d'accès. A côté, une liste/dequeu/vecteur triée
d'itérateur sur les éléments de la map, avec comme critère de
tri bien sur le nb d'accès.
|
Pourquoi pas un map d'itérateurs comme deuxième collection
aussi ?
Sinon, si les cas de suppression ne sont pas si fréquent, ou
pourrait envisager de ne créer, ou au moin ne trier la deuxième
collection que quand on veut supprimer. D'autant plus qu'on n'a
pas besoin de trier complètement ; on doit pouvoir se servir de
std::partial_sort ou std::nth_element.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
|
|
| Back to top |
|
|
Joaquín M López Muñoz
Guest
|
| Posted: Fri Jun 10, 2005 6:48 am Post subject: Re: Implementer un cache en c++/STL |
|
|
Jean-Marc Desperrier wrote:
| Quote: | kanze (AT) gabi-soft (DOT) fr wrote:
Il n'y a pas de collection aussi compliquée dans la STL.
Ca me semble pourtant un besoin assez courant et générique, il n'y a
rien dans Boost non plus ?
|
Veuillez regarder sur
http://boost-consulting.com/boost/libs/multi_index/doc/examples.html#example9
por un exemple de container cache en utilisant
Boost.MultiIndex. L'exemple emploie des "hashed indices" pour
la récupération rapide des eléments: Ces index ne sont pas
disponibles encore (début en Boost 1.33), mais on peut
les substituer par des "ordered indices", qui resemblent
à des maps de STL.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
