7

事前に割り当てられた配列を使用するスタックの「自家製」バージョンと比較すると、標準の std deque が非常に遅いことがわかりました。
これは私のスタックのコードです: 

template <class T>
class FastStack
{    
public:
    T* st;
    int allocationSize;
    int lastIndex;

public:
    FastStack(int stackSize);
    FastStack();
    ~FastStack();

    inline void resize(int newSize);
    inline void push(T x);
    inline void pop();
    inline T getAndRemove();
    inline T getLast();
    inline void clear();
};

template <class T>
FastStack<T>::FastStack()
{
    lastIndex = -1;
    st = NULL;
}

template <class T>
FastStack<T>::FastStack(int stackSize)
{
    st = NULL;
    this->allocationSize = stackSize;
    st = new T[stackSize];
    lastIndex = -1;
}

template <class T>
FastStack<T>::~FastStack()
{
    delete [] st;
}

template <class T>
void FastStack<T>::clear()
{
    lastIndex = -1;
}

template <class T>
T FastStack<T>::getLast()
{
    return st[lastIndex];
}

template <class T>
T FastStack<T>::getAndRemove()
{
    return st[lastIndex--];
}

template <class T>
void FastStack<T>::pop()
{
    --lastIndex;
}

template <class T>
void FastStack<T>::push(T x)
{
    st[++lastIndex] = x;
}

template <class T>
void FastStack<T>::resize(int newSize)
{
    if (st != NULL)
        delete [] st;
    st = new T[newSize];
}

.
deque のこの簡単なベンチマークを実行します。 

std::deque<int> aStack;
int x;

HRTimer timer;
timer.Start();

for (int i = 0; i < 2000000000; i++)
{
    aStack.push_back(i);
    x = aStack.back();
    if (i % 100 == 0 && i != 0)
        for (int j = 0; j < 100; j++)
            aStack.pop_back();
}

double totalTime = timer.Stop();
stringstream ss;
ss << "std::deque " << totalTime;
log(ss.str());

.
ベクトルをコンテナーとして std スタックを使用する (「Michael Kohne」が提案したように)

std::stack<int, std::vector<int>> bStack;
int x;

HRTimer timer;
timer.Start();

for (int i = 0; i < 2000000000; i++)
{
    bStack.push(i);
    x = bStack.top();
    if (i % 100 == 0 && i != 0)
        for (int j = 0; j < 100; j++)
            bStack.pop();
}

double totalTime = timer.Stop();
stringstream ss;
ss << "std::stack " << totalTime;
log(ss.str());

.
そして、私の FastStack と同じもの: 

FastStack<int> fstack(200);
int x;

HRTimer timer;
timer.Start();

for (int i = 0; i < 2000000000; i++)
{
    fstack.push(i);
    x = fstack.getLast();
    if (i % 100 == 0 && i != 0)
        for (int j = 0; j < 100; j++)
            fstack.pop();
}

double totalTime = timer.Stop();
stringstream ss;
ss << "FastStack " << totalTime;
log(ss.str());

.
4 回実行した後の結果は次のとおりです。
deque 15.529
deque 15.3756
deque 15.429
deque 15.4778

スタック 6.19099
スタック 6.1834
スタック 6.19315
スタック 6.19841

FastStack 3.01085
FastStack 2.9934
FastStack 3.02536
FastStack 3.00937

結果は秒単位で表示され、Intel i5 3570k (デフォルト クロック) でコードを実行していました。利用可能なすべての最適化を備えた VS2010 コンパイラを使用しました。私の FastStack には多くの制限があることは知っていますが、それを使用できる状況や、素晴らしいブーストを提供できる状況はたくさんあります! (std::queue と比較して 2 倍の速度が得られる 1 つのプロジェクトで使用しました)。
だから今私の質問は：
誰もが使用しているが、誰も知らない C++ の「阻害剤」は他にありますか?
編集:私は攻撃的になりたくありません。このような未知の「高速化」を知っているかどうか知りたいだけです。

4

2 に答える 2

23

あなたはリンゴとオレンジを比較しています。デキューは DOUBLE-ENDED であるため、実装した単純なスタックとは内部的にかなり異なる必要があります。代わりにベンチマークを実行してみて、std::stack<int, std::vector<int> >どうなるか見てみましょう。std::stack はコンテナー アダプターであり、ベクターを基になるコンテナーとして使用する場合、自家製の実装とほぼ同じ速度になるはずです。

1 つの欠点は、std::stack の実装にはサイズを事前に設定する方法がないことです。そのため、必要な最大サイズがわかっている状況では、最初は少し遅くなります。数回再割り当てする必要があります。その後は、ほとんど同じになります。

于 2012-10-02T15:26:48.620 に答える
15

特定の時点でスタック内にある要素の最大量がわかっている場合は、std::vector事前に容量を予約する を使用する必要があります。容量がわからない場合でも、スタックの場合はstd::vector、数回成長する (成長時に事前に割り当てられたベクターよりもコストが高くなる) が縮小しないため、しばらくするとメモリの割り当てが停止するスタックを使用する必要があります。

パフォーマンスの問題はstd::deque、必要に応じてブロックを割り当て、必要がなくなったときに割り当てを解除することです (いくつかの戦略に従って) std::deque。

于 2012-10-02T15:26:29.603 に答える