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.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
kanze
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.
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
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.
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
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
Marc Boyer
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.
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.
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.
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.
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.
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.
Jean-Marc Desperrier
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 ?
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.
kanze@gabi-soft.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 ?
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.
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 ?
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.
Fabien LE LEZ
On Thu, 09 Jun 2005 00:11:10 +0200, Jean-Marc Desperrier :
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
Table 67Sequence requirements (in addition to container) ________________________________________________ expression return type assertion/note pre/postcondition
Table 67Sequence requirements (in addition to container)
________________________________________________
expression return type assertion/note
pre/postcondition
Table 67Sequence requirements (in addition to container) ________________________________________________ expression return type assertion/note pre/postcondition
Ou alors tu voulais parler de l'astuce avec swap ?
-- Loïc
kanze
Jean-Marc Desperrier wrote:
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.
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
Jean-Marc Desperrier wrote:
kanze@gabi-soft.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.
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
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.
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
Joaquín M López Muñoz
Jean-Marc Desperrier wrote:
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 ?
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
Jean-Marc Desperrier wrote:
kanze@gabi-soft.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 ?
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
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
