C++ contenedor que le permite ordenar los artículos por el último acceso?

Question

¿Existe tal cosa? o ¿alguien podría recomendar cómo podría implementar tal contenedor?

básicamente tengo un std :: map que usa un entero de 64 bits como clave y un tipo de datos personalizado como el elemento que lo contiene.

Necesito ser capaz de eliminar periódicamente los elementos que no se han accedido en un momento de la manera más óptima. ¿Alguien tiene alguna sugerencia para esto?

aplausos

Answer 1

Una idea: mantener un std::deque que obtiene un iterador en el elemento del mapa empujado hacia el frente cada vez que accede al mapa. A continuación, puede ver fácilmente la deque para decir qué elementos se han usado más recientemente.

Algunos bocetos en C++ (sin verificación de errores, el objetivo es demostrar que el deque se actualiza al acceder al mapa, y luego puede recortar el mapa).

class MyMap { 
    typedef std::map<int64_t, void *> Map; 
    Map m_map; 
    std::deque<Map::iterator> m_recentlyUsedItems; 

public: 
    void *getItem(int64_t key) { 
    Map::iterator it = m_map.find(key); 
    if (it == m_map.end()) { 
     return 0; 
    } 
    m_recentlyUsedItems.push_front(it); 
    return it->second; 
    } 

    void removeAllButMostRecentlyUsedItems(int n) { 
    std::deque<Map::iterator> it = m_recentlyUsedItems.begin(); 
    advance(it, n); 
    std::deque<Map::iterator> it2 = it; 
    for (; it2 != m_recentlyUsedItems.end(); ++it2) { 
     m_map.erase(*it2); 
    } 
    m_recentlyUsedItems.erase(it, m_recentlyUsedItems.end()); 
    } 
}; 

Answer 2

Utilice una cola de prioridad que se coloca el elemento menos utilizado recientemente (LRU) a la cabeza de la cola. Cuando se accede a un elemento, quítelo y vuelva a insertarlo contra la marca de tiempo actual. Cuando desee caducar elementos, simplemente elimínelos del encabezado de la cola.

Debo señalar que no puede usar el estándar priority_queue, ya que no es compatible con la eliminación aleatoria. Tendrás que usar las funciones de montón junto con un vector.

Debo señalar que la actualización de un elemento en el acceso será costosa (O (N) para encontrar el elemento para eliminar).

EDITAR: No tenga en cuenta esta respuesta. Al reconsiderar, no es la mejor manera de hacerlo. (Además, vea los comentarios.)

Answer 3

Si sólo necesita saber qué elementos se accede de manera que se pueden eliminar, entonces es probable que podría tomar un mapa de índice de múltiples y almacenar el último valor clave de acceso como alternativa.

Si desea utilizar esa idea para aumentar el rendimiento, puede implementar su propio contenedor. El enfoque más fácil significaría hacer una estructura de datos que se conoce como auto-sorting list. En realidad, esto significa que cada operación de acceso hace que el elemento al que acceda a su lista sea su nueva cabeza. En este caso, los elementos a los que se accede con frecuencia residirían cerca del principio, lo que daría como resultado un mejor tiempo de búsqueda.

Por supuesto, hay variaciones. Las listas ordenadas automáticamente no son muy eficientes y existen muchas otras estructuras de datos similares que en realidad son mejores.

Answer 4

He implementado un tipo de sonido similar que he llamado DynamicCache. Básicamente almacena los datos en una lista ordenada por la fecha de creación. Esto podría cambiarse fácilmente a la última fecha de acceso. El objetivo de mi caché es almacenar en caché los elementos de la base de datos que no cambian muy a menudo. Almacena en caché los elementos durante 5 minutos y luego los elimina para volver a leerlos cuando se acceda a ellos.

La búsqueda de caché utiliza un mapa que almacena la clave y un iterador en la lista. La búsqueda usa el mapa para buscar los datos en la lista, luego, antes de devolver el elemento, elimina todos los elementos anteriores del final de la lista. Si un artículo no está en la memoria caché, se llama a una fábrica para proporcionar los datos.

Este enfoque debe usar una lista para almacenar los datos, ya que los iteradores en el mapa siempre deben ser válidos, si utiliza un deque los iteradores podrían invalidarse después de una inserción. La lista usa una estructura para almacenar los datos, la clave, la hora en que se creó (no se accedió por última vez) y finalmente si los datos existen.

struct Record 
{ 
    KeyT key; 
    DataT data; 
    time_t createTime; 
    bool exists; 
}; 

Si los datos son estáticos y se desea preservar la accedido más recientemente, entonces usted podría agregar un miembro de tiempo de acceso a la estructura, y mover el elemento a la parte superior de la lista cada vez que se accede.

Aquí está mi código, parece un poco complicado, pero esto se debe principalmente a los parámetros de la plantilla y al bloqueo del escritor lector.

#include "BWThread/BWReadersWriterLock.h" 

#include <list> 
#include <map> 
#include <ctime> 
#include <memory> 
#include <boost/scoped_ptr.hpp> 

/** 
* This is a Generic Cache implementation. 
* 
* To implement a cache using this class create a new class 
* derived from CacheFactory and implement the lookup method. 
* If the datasource supports updating implement update and 
* remove method. 
* 
* EG 
* typedef NameCache DynamicCache<int, BWString>; 
* NameCacheFactory : NameCache::Factory 
* { 
* public: 
* virtual bool lookup(int, BWString *); 
* }; 
* 
* NameCache cache(new NameCacheFactory, "<cache name>"); 
* 
* -------------------------------------------------------- 
* Implementation note: 
* This class uses a list as an efficient way to remove stale items from 
* the cache. The map stores a key and an iterators to the data in the list. 
* The list and the map are updated together. 
*/ 

template <class KeyT, class DataT> 
class CacheFactory 
{ 
public: 
    virtual ~CacheFactory() {} 

    // Lookup the data for from the data source. 
    // Return true if the data is found. 
    virtual bool lookup(const KeyT & key, DataT * data) = 0; 

    // Update or insert the data in the data source. 
    // Return true if the data can be updated. 
    // Returning false means the cache is not updated either. 
    virtual bool update(const KeyT & key, const DataT & data) { return false; } 

    // Remove the data in the data source. 
    // Return true if the data can be deleted weather it exists or not. 
    // Returning false means the cache is not updated either. 
    virtual bool remove(const KeyT & key) { return false; } 
}; 


template <class KeyT, class DataT> 
class DynamicCache 
{ 
public: 
    typedef CacheFactory<KeyT, DataT> Factory; 

    DynamicCache(Factory * f, const std::string & name, time_t t = (5 * 60)) : 
     factory(f), timeout(t), lastClean(std::time(0)), lock(name + " DynamicCache") {} 

    /* 
    * Lookup a key in the cache, the cached version is returned if it is 
    * present and the value is not old. If the value is old or is not 
    * present then use the factory to create it and insert the value in the 
    * cache for future lookups. If the factory cannot create it cache this 
    * fact too so we will ignore future lookups. Afterwards any entries in 
    * the cache longer than timeout are removed. 
    * 
    * This is the main method and entry point for the cache. All locking is 
    * performed inside the child methods. 
    */ 
    bool lookup(const KeyT & key, DataT * data, time_t now = std::time(0)) 
    { 
     bool found = false; 
     FindStatus status = find(key, data, now); 

     switch(status & EntryStatus) { 
     case Found: 
      found = true; 
      break; 
     case Create: 
      found = build(key, data, now); 
      break; 
     } 
     if (status & CleanRequired) { 
      cleanOldEntries(now); 
     } 
     return found; 
    } 

    bool update(const KeyT & key, const DataT & data, time_t now = std::time(0)) 
    { 
     if (factory->update(key, data)) 
     { 
      Record record; 
      record.key = key; 
      record.createTime = now; 
      record.data = data; 
      record.exists = true; 

      BWReadersWriterLock::WriteLockGuard guard(lock, __FILE__, __LINE__); 

      updateEntry(key, record); 
      return true; 
     } 
     return false; 
    } 

    bool remove(const KeyT & key, time_t now = std::time(0)) 
    { 
     if (factory->remove(key)) 
     { 
      Record record; 
      record.key = key; 
      record.createTime = now; 
      record.exists = false; 

      BWReadersWriterLock::WriteLockGuard guard(lock, __FILE__, __LINE__); 

      updateEntry(key, record); 
      return true; 
     } 
     return false; 
    } 

    /** 
    * Return the size of the cache (only really useful for unit testing). 
    */ 
    size_t size() const 
    { 
     BWReadersWriterLock::ReadLockGuard guard(lock, __FILE__, __LINE__); 

     return map.size(); 
    } 

    Factory * getFactory() 
    { 
     return factory.get(); 
    } 
private: 
    // Cache record 
    struct Record 
    { 
     KeyT key; 
     DataT data; 
     time_t createTime; 
     bool exists; 
    }; 

    // Find and Clean status 
    // CleanRequired is part of this so that searching the cache and finding 
    // stale items in the cache can be automic (use a single readlock). 
    enum FindStatus { 
     None, 
     Found, 
     Create, //Add 
     NotExist, 
     EntryStatus=Found|Create|NotExist, 
     CleanRequired = 8 
    }; 

    typedef std::list<Record> List; 
    typedef typename List::iterator Iterator; 
    typedef std::map<KeyT, typename Iterator> Map; 


    // 
    // The following methods all use and require explicit locking. 
    // 

    FindStatus find(const KeyT & key, DataT * data, time_t now) 
    { 
     BWReadersWriterLock::ReadLockGuard guard(lock, __FILE__, __LINE__); 

     Iterator itr = getEntry(key); 
     if (isValid(itr) && !isOld(itr, now)) { 
      if (itr->exists) { 
       *data = itr->data; 
       return FindStatus(Found | cleanRequired(now)); 
      } 
      else { 
       return FindStatus(NotExist | cleanRequired(now)); 
      } 
     } 
     return FindStatus(Create | cleanRequired(now)); 
    } 

    bool build(const KeyT & key, DataT * data, time_t now) 
    { 
     Record record; 
     record.key = key; 
     record.createTime = now; 
     record.exists = factory->lookup(key, &record.data); 

     BWReadersWriterLock::WriteLockGuard guard(lock, __FILE__, __LINE__); 

     if (record.exists) { 
      *data = record.data; 
     } 

     updateEntry(key, record); 
     return record.exists; 
    } 

    void cleanOldEntries(time_t now) 
    { 
     BWReadersWriterLock::WriteLockGuard guard(lock, __FILE__, __LINE__); 

     lastClean = now; 
     time_t old = now - timeout; 

     typename List::reverse_iterator itr = list.rbegin(); 
     while(!list.empty() && list.back().createTime < old) { 
      removeEntry(getEntry(list.back().key)); 
     } 
    } 

    // 
    // The following methods don't use locking but require the calling 
    // method to already have aquired a lock. 
    // 

    Iterator getEntry(const KeyT & key) 
    { 
     typename Map::const_iterator itr = map.find(key); 
     if (itr != map.end()) { 
      return map.find(key)->second; 
     } 
     return list.end(); 
    } 

    bool updateEntry(const KeyT key, const Record & record) 
    { 
     Iterator itr = getEntry(key); 
     if (isValid(itr)) { 
      removeEntry(itr); 
     } 

     insertEntry(record); 
     return record.exists; 
    } 

    bool isValid(Iterator itr) const 
    { 
     typename List::const_iterator constItr(itr); 
     return constItr != list.end(); 
    } 

    bool isOld(Iterator itr, time_t now) const 
    { 
     // isOld or time_t has wrapped 
     return ((itr->createTime + timeout) < now) || (now < itr->createTime); 
    } 

    Iterator insertEntry(const Record & record) 
    { 
     list.push_front(record); 
     Iterator itr = list.begin(); 
     map.insert(typename Map::value_type(record.key, itr)); 
     return itr; 
    } 

    void removeEntry(Iterator itr) 
    { 
     map.erase(itr->key); 
     list.erase(itr); 
    } 

    FindStatus cleanRequired(time_t now) const 
    { 
     return (lastClean + timeout) < now ? CleanRequired : None; 
    } 

    List list; 
    Map map; 
    time_t timeout; 
    time_t lastClean; 
    boost::scoped_ptr<CacheFactory<KeyT, DataT> > factory; 
    mutable BWReadersWriterLock lock; 
}; 

Answer 5

Voy a proponer una idea singularmente diferente.

El problema de óptimo es que es difícil entenderlo. Especialmente: ¿desea paralizar la operación de recuperación para obtener una limpieza más rápida? La limpieza típica generalmente se realiza durante el "tiempo de inactividad" cuando la velocidad no es tan importante; por otro lado, es posible que desee recuperar rápidamente (para acceder en bucles, etc.)

Allí propongo que antes de intentar lujo construcciones, simplemente almacena la última hora accedida a lo largo de tu artículo en el mapa. Luego, la limpieza simplemente consiste en verificar cada elemento en el mapa y eliminar los que ya no desea.

Answer 6

Aquí hay un boceto de cómo se podría hacer, utilizando una lista para almacenar los elementos accedidos más recientemente en orden. La lista se actualiza en tiempo constante, por lo que no hay una sobrecarga significativa por encima del acceso al mapa (a diferencia de otras respuestas que requieren una búsqueda lineal en cada acceso). Mantuve la interfaz muy básica y no la he probado a fondo.

template <typename KEY, typename VALUE> 
class Container 
{ 
public: 
    void Set(const KEY& key, const VALUE& value) 
    { 
     typename Map::iterator it = map.find(key); 
     if (it == map.end()) 
     { 
      list.push_front(it); 
      it = map.insert(std::make_pair(key, std::make_pair(value, list.begin()))).first; 
      list.front() = it; 
     } 
     else 
     { 
      it->second.first = value; 
      Accessed(it); 
     } 
    } 

    const VALUE* Get(const KEY& key) 
    { 
     typename Map::iterator it = map.find(key); 
     if (it == map.end()) 
      return 0; 

     Accessed(it); 
     return &it->second.first; 
    } 

    void Expire(std::size_t new_size) 
    { 
     while (list.size() > new_size) 
     { 
      map.erase(list.back()); 
      list.pop_back(); 
     } 
    } 

private: 
    // Needed to resolve the semicircular dependency on nested iterator types. 
    struct MapIterator; 

    typedef std::list<MapIterator> List; 
    typedef std::map<KEY, std::pair<VALUE, typename List::iterator> > Map; 

    struct MapIterator : Map::iterator 
    { 
     MapIterator(const typename Map::iterator& it) : Map::iterator(it) {} 
    }; 

    void Accessed(typename Map::iterator it) 
    { 
     list.erase(it->second.second); 
     list.push_front(it); 
     it->second.second = list.begin(); 
    } 

    Map map; 
    List list; 
}; 

Answer 7

También puede utilizar linked_hash_map de MCT library. De hecho, su documentación contiene una receta para este uso.