Trie dans un cache LRU

**Kromagg** · 08/11/2008, 15h32

Bonjour à tous

Je réalise un cache LRU afin de gérer mes ressources. Voici le code de ces 2 classes pour vous aider :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
template<typename T>
    class _NaosExport_ Resource
    {
    private:
 
        /// Nom de la ressource.
        Ogre::String mName;
 
        /// Instance de l'objet contenu dans la ressource.
        shared_ptr<T> mObject;
 
        /// Indique quand la resource a été utilisé pour la dernière fois (pour le cache LRU).
        time_t mLastTimeUsed;
 
    public:
 
        /**
         * Constructeur par défaut utilisé pour créer une ressource dont l'objet interne est NULL.
         */
        Resource() {}
 
        /**
         * Constructeur à partir d'un objet.
         */
        Resource(const Ogre::String& _name, shared_ptr<T> _object = shared_ptr<T>()):
        mName(_name),
        mObject(_object),
        mLastTimeUsed(time(NULL))
        {}
 
        /**
         * Destructeur.
         */
        ~Resource() {}
 
        /**
         * Retourne l'instance de l'objet de la ressource.
         * @Retour      shared_ptr sur l'objet.
         */
        shared_ptr<T> getObject() const
        {
            return mObject;
        }
 
        /**
         * Retourne le nom de la ressource.
         */
        Ogre::String getName() const
        {
            return mName;
        }
 
        /**
         * Met à jour la dernière fois où la resource a été utilisée.
         */
        void updateTimeLastUsed()
        {
            mLastTimeUsed = time(NULL);
        }
 
        /**
         * Compare la fréquence d'utilisation de cette ressource avec une autre.
         * @Param       _rhs : ressource avec laquelle comparer.
         * @Retour      True si cette ressource à une utilisation moins récente que l'autre.
         */
        bool operator < (const Resource<T>& _rhs) const
        {
            return mLastTimeUsed < _rhs.mLastTimeUsed;
        }
    };

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
namespace Naos
{
    /** Cette classe représente un cache LRU (Last Recent Used) de ressource et permet
        donc de gérer le nombre maximal de ressources voulu.
        @Note
            Dans ce cache on utilise 2 conteneurs : un std::list et std::map. Pourquoi ?
            On utilise un std::list pour conserver l'ordre des ressources dans le cache en fonction
            des utilisations qui en sont faites.
            On utilise un std::map pour faciliter la recherche des ressources dans le cache. De
            plus un std::map fourni une complexité logarithmique pour la recherche d'éléments comparé
            à une compléxité linéaire pour un std::list.
    */
    template<class T>
    class _NaosExport_ ResourceLRUCache
    {
    private:
 
        typedef typename std::list<Resource<T> >             ResourceCache;
        typedef typename std::list<Resource<T> >::iterator   ItResourceCache;
 
        typedef typename std::map<Ogre::String, ItResourceCache>              ResourceIndex;
        typedef typename std::map<Ogre::String, ItResourceCache>::iterator    ItResourceIndex;
 
    private:
 
        /// Taille maximale du cache LRU.
        size_t mMaxSize;
 
        /// Cache de resource.
        ResourceCache mResourceCache;
 
        /// Index des ressource dans le cache
        ResourceIndex mResourceIndex;
 
    public:
 
        /**
         * Constructeur par défaut.
         * @Param       _maxSize : taille maximale du cache en nombre de ressource.
         */
        ResourceLRUCache(size_t _maxSize):
        mMaxSize(_maxSize)
        {}
 
        /**
         * Destructeur
         */
        ~ResourceLRUCache(void)
        {
            mResourceCache.clear();
            mResourceIndex.clear();
        }
 
        /**
         * Ajoute une ressource dans le cache.
         * @Param       _resource : resource à ajouter.
         */
        void addResource(const Resource<T>& _resource)
        {
            ItResourceIndex it = mResourceIndex.find(_resource.getName());
 
            // Si la ressource est déjà présente dans le cache on la déplace au début de ce dernier.
            if(it != mResourceIndex.end())
            {
                mResourceCache.erase((*it).second);
                mResourceCache.push_front(_resource);
 
                mResourceIndex.erase(it);
                mResourceIndex[_resource.getName()] = mResourceCache.begin();
            }
            else
            {
                // Si le cache est plein.
                if(mResourceCache.size() == mMaxSize)
                {
                    // On retire la dernière ressource du cache c'est-à-dire celle utilisée le moins récemment.
                    Resource<T> resourceToRemove = mResourceCache.back();
                    Ogre::String resourceName = resourceToRemove.getName();
                    mResourceIndex.erase(resourceName);
                    mResourceCache.pop_back();
                }
 
                mResourceCache.push_front(_resource);
                mResourceIndex[_resource.getName()] = mResourceCache.begin();
            }
        }
 
        void removeResource(const Ogre::String& _resourceName)
        {
            ItResourceIndex it = mResourceIndex.find(_resourceName);
 
            if(it != mResourceIndex.end())
            {
                mResourceCache.erase((*it).second);
                mResourceIndex.erase(it);
            }
        }
 
        Resource<T> getResource(const Ogre::String& _resourceName)
        {
            ItResourceIndex it = mResourceIndex.find(_resourceName);
 
            if(it != mResourceIndex.end())
            {
                return (*(*it).second);
            }
            else
            {
                return Resource<T>();
            }
        }
 
        bool isResourceInCache(const Ogre::String& _resourceName) const
        {
            return mResourceIndex.find(_resourceName) != mResourceIndex.end();
        }
    };
}   // Naos.

Maintenant j'utilise ce cache dans un manager de base. A chaque fois que je créer une ressource je l'insert dans mon cache s'il elle n'existe pas, et ma ressource ce trouve donc au début de mon cache (pas besoin de trie). Maintenant si la ressource que je veux créer existe déjà dans mon cache je la retourne simplement, tout en mettant un jour son dernier temps d'utilisation (Resource::updateLastTimeUsed())
Dans ce cas il faut que je dise à mon cache de remettre en ordre les ressources par rapport au temps. Si par exemple la ressource demandée se trouve au milieu du cache il faut la remettre au début. Je pensais donc faire dans la classe ResourceLRUCache une méthode qui ferait ca pour moi avec un std::sort(mResourceCache.begin(), mResourceCache.end(). Seulement j'ai peur que mes itérateurs du conteneur ResourceIndex (qui pointent vers une ressource dans le cache ResourceCache) ne soient plus valide et donc qu'ils ne désignent plus la bonne resource.

Avez-vous une solution ?

**loufoque** · 08/11/2008, 23h29

Pas besoin de faire un tri pour déplacer un élémént se trouvant au milieu au début.
Avec des listes doublement chaînées, cela se fait en temps constant, sans allocation mémoire ni rien.

Typiquement pour un cache de ce genre, tu veux donc une liste doublement chaînée intrusive dont les nœuds sont dans un tableau de taille fixe.

**Kromagg** · 09/11/2008, 13h53

Ok merci bien

**Médinoc** · 09/11/2008, 14h05

Je ne suis pas sûr qu'on ait besoin que la liste soit doublement chaînée: En effet, la seule insertion possible dans le cas du LRU est en tête de liste, donc un chaînage simple peut suffire...

**Kromagg** · 09/11/2008, 14h20

Oui mais si une ressource que je veux charger est déja présente dans le cache il faut que je la remette au début de celui-ci (pour dire qu'elle vient d'être utilisée) et que je la supprime de sa position actuelle dans le cache (milieu ou autre)

**Médinoc** · 09/11/2008, 14h24

Oui, mais tu n'auras à déplacer l'élément que lorsque tu l'auras trouvé dans le cache, donc à ce moment-là tu auras encore un pointeur vers l'élément précédent (ou mieux, un pointeur vers le pointeur qui indiquait l'élément trouvé).
http://www.developpez.net/forums/d62...e/#post3675588

**Kromagg** · 09/11/2008, 14h57

Envoyé par Médinoc

Oui, mais tu n'auras à déplacer l'élément que lorsque tu l'auras trouvé dans le cache, donc à ce moment-là tu auras encore un pointeur vers l'élément précédent (ou mieux, un pointeur vers le pointeur qui indiquait l'élément trouvé).

Ok mais une fois ma ressource trouvée puis retourner, je dois mettre à jour mon cache. Je remonte donc ma ressource au tout début de mon cache. Et la j'ai peur que mon itérateur ,pour cettre ressource, qui est enregistré dans mon std::map ne pointe plus vers la bonne ressource.

**Médinoc** · 09/11/2008, 15h15

Je pense que ça pointera toujours dessus, puisque l'emplacement de la structure elle-même ne changera pas. Seuls changeront les pointeurs dessus.

**loufoque** · 09/11/2008, 21h21

Tout dépend comment tu accèdes aux éléments se trouvant en cache.
Personnellement, je ne parcours pas le cache, j'utilise une table.

Trie dans un cache LRU

C++

Discussions similaires

Partager

Partager