Алгоритмы очереди

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

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

РЕДАКТИРОВАТЬ: очередь должна быть общей, позволяющей помещать в очередь произвольные типы данныхВот мой тестовый код (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 хранит много, много элементов в каждом распределении. Однако вы выделяете и освобождаете индивидуально для каждого элемента. Вот почему ваша очередь такая медленная.

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Я предлагаю вам попробовать boost :: round_buffer . Если размер по умолчанию задан достаточно высоким, это приведет к выделению только одной памяти за время его жизни.