双端与队列速度 [英] Deque vs Queue Speed

问题描述

我正在处理 LeetCode 上的一个问题(此处).当我完成这个问题时，我想出了:

I was working on a problem on LeetCode (Here). When I finished the problem, I came up with:

class MovingAverage {
    std::deque<int> numsToAverage;
    int maxSize;
    int currentTotal;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        currentTotal = 0;
    }

    double next(int val) 
    {
        currentTotal += val;
        numsToAverage.push_back(val);

        if (numsToAverage.size() > maxSize)
        {
            currentTotal -= numsToAverage[0];
            numsToAverage.pop_front();
        }

        return (double)currentTotal / (double)numsToAverage.size();
    }
};

后来，我看到另一个解决方案与我的非常相似，但使用了队列.出于好奇，我只将双端队列交换到队列，然后从第 18 个百分点(双端队列)跳到第 56 个百分点(队列).这是队列代码:

Afterwards, I saw that another solution was very similar to mine but used a queue. Out of curiosity, I swapped only the deque to a queue and I jumped from the 18th percentile (deque) to the 56th percentile (queue). Here's the queue code:

class MovingAverage {
    std::queue<int> numsToAverage;
    int maxSize;
    int currentTotal;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        currentTotal = 0;
    }

    double next(int val) 
    {
        currentTotal += val;
        numsToAverage.push(val);

        if (numsToAverage.size() > maxSize)
        {
            currentTotal -= numsToAverage.front();
            numsToAverage.pop();
        }

        return (double)currentTotal / (double)numsToAverage.size();
    }
};

我的问题特别为什么?我检查了std::队列，它默认为双端队列！为什么它会因为它是一个队列而更快?我唯一的猜测是它在某些地方缓存该值?但同时，一个队列，默认是一个双端队列！插入/删除时间简直再好不过了！

My question is specifically why? I checked std::queue and it defaults to a deque! Why on earth would it be faster just because it's a queue? My only guess is that it's caching that value some where? But at the same time, a queue, by default IS a deque! The insertion/deletion time literally can't be better!

(旁注，我没有考虑 size == 0 的情况，因为这个问题没有测试它.事实上，如果你把它交给 0，他们的代码会猛烈地破碎)

(Side note, I don't account for the case where size == 0 because the question doesn't test for it. In fact, their code violently shatters if you hand it 0)

推荐答案

这是一个有根据的猜测:

Here is an educated guess:

• 内存控制器具有预取惯用性"，可奖励连续的、升序的内存访问，但按降序访问则速度较慢.

• Memory controllers have a prefetch "handedness" that rewards consecutive, ascending memory accesses but is slower for accesses in descending order.

因此，用作 FIFO 容器的双端队列具有在一侧推送和在另一侧弹出的首选方向.

Accordingly, deques used as a FIFO container have a preferred direction for pushing on one side and popping on the other.

很可能，您的双端队列代码使用了最不受欢迎的方向.但是队列实现已经优化为在其最受青睐的方向上使用底层双端队列.

Likely, your deque code uses the least favored direction. But the queue implementation is already optimized to use the underlying deque in its most favored direction.

有一个简单的方法来检验这个假设(假设这些是非保证的实现细节).在您的双端队列代码中，切换 push_back -->push_front 和 pop_front -->pop_back.如果假设是正确的，deque 代码应该和队列实现一样快:-)

There is an easy way to test this hypothesis (given that these are non-guaranteed implementation details). In your deque code, switch push_back --> push_front and pop_front --> pop_back. If the hypothesis is correct, the deque code should speed-up to just as fast as the queue implementation :-)

这篇关于双端与队列速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！