キューアルゴリズム

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秒）。 問題は、より良いアルゴリズムは何でしょうか？私はstd :: dequeのMSVCの実装を理解しようとしましたが、コードはわかりやすいものです。

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

あなたはリンクリストを作成しています。両端キュー実装では、各割り当てに多数の要素が格納されます。ただし、各要素に対して個別に割り当ておよび割り当て解除を行います。これがあなたのキューが遅い理由です。

さらに、スタンダードのキューインターフェイスでは、テンプレートではなく完全なアロケータタイプを使用する必要があると言われていますが、スタンダードのアロケータ要件を満たすことの現実は、テンプレートでなければならないということです。

Answer 2

で、メモリの割り当て/割り当て解除は、ここでは最大のパフォーマンスの問題です。

私はあなたがboost::circular_bufferを試すことをお勧めします。既定のサイズが十分に高く設定されている場合、そのメモリはその存続期間中に1つだけ割り当てられます。

Answer 3

プッシュ/ポップ/クリアアルゴリズムを変更することで、95％の時間がノードの割り当てと割り当て解除になるので、あまりできません。しかし、あなたができることがいくつかあります：

1）ノードのための何らかの種類のメモリプールを使用します。プールアロケータ（boost :: pool_allocは自分自身を実装したくない場合には良い方法です）を使用することも、キュークラスの内部ノードキャッシュを使用することもできます。ノードを削除するのではなく、ノード・キャッシュにプッシュし、ノードを作成するときにはキャッシュからポップします。

2）1つのノードに複数のアイテムを格納します。たとえば、1つのノードに8つの項目がある場合、8回のプッシュ/ポップごとに1回だけalloc/deallocを実行する必要があります。もちろんこれには少し複雑なコードが必要です。ヘッドノードとテールノードへのポインタを持つことに加えて、実際に使用されているアイテムの数を追跡するために、両方のインデックス変数が必要になります。

Answer 4

私はすべてのアロケータのものを（g ++ 4.40で）コンパイルするために取り出しなければなりませんでしたが、まったく時間がかかりません。 100倍以上の要素をプッシュしても、キューを埋めるのに約0.5秒かかり、それをクリアするのに0.5秒しかかかりません。あなたは新しいを使用して削除しようとしましたか？