algorithmes de file d'attente

Question

Je suis en train de faire une file d'attente sur la base de liste chaînée pour les opérations rapides, maintenant que ce que j'ai:

template< typename T, 
      template<typename> class Allocator = default_allocator 
> 
class fast_queue 
{ 
public: 
    typedef T element_type; 
    typedef T* element_ptr; 

private: 
    typedef struct e_node 
    { 
    element_type val; 
    e_node * next; 
    }node_type; 
    typedef node_type * node_ptr; 
    node_ptr parent; 
    node_ptr child; 
    int  m_size; 
    typedef Allocator<node_type> allocator_type; 

public: 
    fast_queue() 
    : parent(0) 
    , child(0) 
    , m_size(0) 
    { 
    } 

    ~fast_queue() { 
    this->clear(); 
    } 

    void push(element_type& i) 
    { 
    node_ptr n = allocator_type::alloc(); 
    n->val = i; 
    n->next = (node_ptr)0; 
    if(child) { 
    child->next = n; 
    } else { 
    parent = n; 
    } 
    child = n; 
    m_size++; 
    } 

    element_type pop() 
    { 
    element_type ret = parent->val; 
    node_ptr p = parent; 
    parent = parent->next; 
    m_size--; 
    allocator_type::dealloc(p); 
    return ret; 
    } 

    inline int size() const 
    { 
    return m_size; 
    } 

    inline bool empty() const 
    { 
    return (m_size == 0); 
    } 

    void clear() 
    { 
    while(!empty()) { 
    pop(); 
    } 
    child = 0; 
    } 
}; 

Assez simple, maintenant ce que je suis un problème avec est la fonction d'effacement() . Il semble prendre trop de temps à libérer tous les nœuds de la file d'attente (7 secondes). Donc la question est, quel pourrait être un meilleur algorithme? J'ai essayé de comprendre la mise en œuvre de std :: deque par MSVC, mais le code est si volumineux à comprendre pour moi.

EDIT: La file d'attente doit être générique, autorisant la mise en file d'attente de types arbitraires de données. Voici mon code d'essai (Windows)

DWORD time1 = timeGetTime(); 
fast_queue<int> queue; 

for(int i = 0; i < 100000; i++) { 
    queue.push(i); 
} 
queue.clear(); 
cout << "Test time: " << (int)(timeGetTime() - time1) << " milliseconds" << endl; 

Answer 1

Vous construisez une liste chaînée. L'implémentation de deque stocke beaucoup, beaucoup d'éléments dans chaque allocation. Vous, cependant, allouer et désallouer individuellement pour chaque élément. C'est pourquoi votre file d'attente est si lente. En plus de cela, l'interface de file d'attente de la norme indique que vous devez utiliser un type Allocator complet, pas un modèle, bien que la réalité de satisfaire aux exigences d'allocation de la norme est qu'elle doit être un modèle de toute façon.

Answer 2

Comme suggéré par d'autres personnes, l'allocation de mémoire/désallocation est le plus grand problème de performance ici.

Je suggère que vous essayez boost::circular_buffer. Si la taille par défaut est suffisamment élevée, cela ne provoquera qu'une allocation de mémoire au cours de sa durée de vie.

Answer 3

Vous ne pouvez pas faire grand-chose en changeant les algorithmes push/pop/clear, car 95% du temps va à l'allocation et à la désallocation des nœuds. Mais il y a certaines choses que vous pouvez faire:

1) Utilisez une sorte de pool de mémoire pour les nœuds. Vous pouvez utiliser un allocateur de pool (boost :: pool_alloc est bon si vous ne voulez pas implémenter le vôtre), ou vous pouvez utiliser un cache de nœud interne dans la classe de file d'attente. Ainsi, au lieu de supprimer des nœuds, vous devez simplement le placer dans le cache des nœuds et, lors de la création des nœuds, les extraire du cache.

2) Stocker plusieurs éléments dans un noeud. Par exemple, si vous avez 8 éléments dans un nœud, vous n'avez à allouer/dealloc qu'une fois tous les 8 push/pops. Bien sûr, cela nécessite un code légèrement plus compliqué; En plus d'avoir des pointeurs vers les nœuds tête et queue, vous aurez également besoin de variables d'index pour les deux afin de garder une trace du nombre d'éléments réellement utilisés.

Answer 4

Je devais enlever tout le matériel Allocator pour le compiler (sous g ++ 4.40), mais il s'exécute en un rien de temps. Même si je pousse 100 fois plus d'éléments, il suffit d'environ une demi-seconde pour remplir la file d'attente et une demi-seconde pour l'effacer. Avez-vous essayé d'utiliser new et delete?