Queue Алгоритмы

Question

Я пытаюсь сделать связанную на основе очереди списка для быстрых операций, теперь это то, что у меня есть:

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; 
    } 
}; 

Довольно просто, что теперь я имею проблему с функцией сброса() , Кажется, что уходит слишком много времени, освобождая все узлы в очереди (7 секунд). Итак, вопрос в том, что может быть лучшим алгоритмом? Я попытался понять реализацию MSVC std :: deque, но код настолько громоздкий для меня, чтобы понять.

EDIT: Очередь должна быть общей, позволяя помещать произвольные типы данных. Вот мой код тестирования (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

Вы создаете связанный список. Реализация deque хранит много и много элементов в каждом распределении. Однако вы выделяете и освобождаете отдельно для каждого элемента. Вот почему ваша очередь настолько медленная.

В дополнение к этому в интерфейсе очереди Standard говорится, что вы должны использовать полный тип Allocator, а не шаблон, хотя реальность выполнения требований распределителя Standard заключается в том, что он должен быть шаблоном в любом случае.

Answer 2

Как было предложено другими людьми, распределение памяти/открепление является самой большой проблемой производительности здесь.

Предлагаю вам попробовать boost::circular_buffer. Если размер по умолчанию установлен достаточно высоким, он будет вызывать только одно распределение памяти за время его существования.

Answer 3

Вы не можете сделать это, изменив алгоритмы push/pop/clear, потому что 95% времени идет на выделение и освобождение узлов. Но есть некоторые вещи, которые вы могли бы сделать:

1) Используйте какой-то пул памяти для узлов. Вы можете использовать распределитель пула (boost :: pool_alloc - хороший, если вы не хотите его реализовать), или вы можете использовать кеш внутреннего узла в классе очереди. Поэтому вместо удаления узлов вы просто подталкиваете его к кешу узла, а при создании узлов вы выталкиваете их из кеша.

2) Храните несколько элементов в одном узле. Например, если у вас есть 8 элементов в одном узле, вам нужно только выделить/dealloc один раз каждые 8 ​​нажатий/всплывающих окон. Конечно, это требует немного более сложного кода; в дополнение к указателям на головные и хвостовые узлы, вам также понадобятся индексные переменные для обоих из них, чтобы отслеживать, сколько элементов фактически используется.

Answer 4

Мне пришлось вытащить все материалы Allocator, чтобы его скомпилировать (под g ++ 4.40), но он запускается в кратчайшие сроки. Даже если я нажимаю 100 раз больше элементов, для заполнения очереди требуется всего полсекунды, а для ее очистки - полсекунды. Вы пробовали использовать новые и удалять?