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

.
我为双端队列运行这个简单的基准测试： 

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

快速堆栈
3.01085 快速堆栈 2.9934 快速堆栈
3.02536 快速
堆栈 3.00937

结果以秒为单位，我在 Intel i5 3570k（默认时钟）上运行代码。我使用了具有所有可用优化的 VS2010 编译器。我知道我的 FastStack 有很多限制，但是在很多情况下，可以使用它以及何时可以提供很好的提升！（我在一个项目中使用了它，与 std::queue 相比，我的速度提高了 2 倍）。
所以现在我的问题是：
C++ 中是否还有其他每个人都在使用但没人知道的“抑制剂”？
编辑：我不想冒犯，我只是好奇你是否知道一些像这样的未知“加速”。

4

2 回答 2

23

你在比较苹果和橘子。出队是双端的，这要求它在内部与您实现的简单堆栈有很大不同。尝试运行你的基准测试std::stack<int, std::vector<int> >，看看你是怎么做的。std::stack 是一个容器适配器，如果你使用向量作为底层容器，它应该几乎和你自己的实现一样快。

不利的一面是 std::stack 实现没有办法让您预先设置大小，因此在您知道最大大小需要的情况下，最初会慢一些它必须重新分配几次。在那之后，它几乎是一样的。

于 2012-10-02T15:26:48.620 回答
15

如果您知道在任何给定时间将在堆栈中的最大元素数量，您应该使用std::vector您预先保留容量的 a。即使您不知道容量，对于堆栈，您应该使用std::vector会增长几次（增长时比预分配向量成本更高）但永远不会缩小的堆栈，因此一段时间后它将停止分配内存。

性能问题在于，std::deque它将根据需要分配块，并在不再需要它们时释放它们（遵循一些策略），所以如果你std::deque经常填充和清除，就会不断地分配和释放。

于 2012-10-02T15:26:29.603 回答