为什么这个 C++ 双端队列代码在我解调时“效率较低”？

Question

这是我在 HackerRank 上研究这个问题的解决方案时遇到的一个问题。它基本上归结为以下内容：给定一个数组 A 和一个整数 K，问题要求您找到大小为 K 的 A 的每个连续子数组的最大值。还有一些额外的东西（对于每个测试用例，这个问题都会发生 T次，并且必须从输入中读取才能获得 A)，但这就是它的要点。

该站点会检查您的答案是否足够有效，即使您的代码最终产生了正确的输出，也可能会因超时而导致提交失败。现在，当您第一次进入代码区域时，有一些预定义的代码供您使用：

#include <iostream>
#include <deque> 
using namespace std;

void printKMax(int arr[], int n, int k){
    //Write your code here.
}

int main(){

    int t;
    cin >> t;
    while(t>0) {
        int n,k;
        cin >> n >> k;
        int i;
        int arr[n];
        for(i=0;i<n;i++)
            cin >> arr[i];
        printKMax(arr, n, k);
        t--;
    }
    return 0;
}

一切都很好，该站点已经为您的利益处理输入，并为您指明模块化方法。你所要做的就是解决连续子数组问题；我使用以下函数完成了它，该函数通过了所有测试用例：

void printKMax(int arr[], int n, int k){
    // Queue will store up to k elements (moving window)
    // Elements stored will be indices of the array. Indices allow to compare with loop iterator for removal of oldest element as window moves
    // Most recent elements are pushed to the back (so they take longer to be popped)
    std::deque<int> Q(k); 

    // Iterate over the first window
    int i; 
    for (i = 0; i < k; ++i) { 
        // A new element (arr[i]) to be added at the back invalidates all elements added before it that are no greater (if they are smaller, they cannot be a maximum; if they are equal, the new element is more recent). Those elements are popped
        // This guarantees that the values corresponding to Q's indices will be increasing (strictly) from back to front. In particular, the front will be the maximum
        while ((!Q.empty()) && arr[i] >= arr[Q.back()]) 
            Q.pop_back();
        Q.push_back(i); 
    }

    // Iterate, letting the window move
    for (; i < n; ++i) { 
        // Print the largest element (window has not moved yet), followed by a space
        cout << arr[Q.front()] << " "; 

        // Use indices to determine if oldest element has gone out of the window
        if (Q.front() <= i - k) Q.pop_front();

        // Add new element, like before
        while ((!Q.empty()) && arr[i] >= arr[Q.back()]) 
            Q.pop_back(); 
        Q.push_back(i); 
    } 

    // Print the maximum element of last window, and end the line 
    cout << arr[Q.front()] << endl; 
}

然而，回想起来，我认为我可以做得（稍微？）更好。对于每个测试用例，主循环中的输入处理 n 次以填充数组 arr，然后 printKMax 依次也循环 n 次以创建和滑动移动窗口。我想我可以将它们组合成一个循环，我想这应该更有效。我是用下面的代码完成的，它与以前基本相同，但将 printKMax 合并到main.c 中。这次我会省略评论。

int main(){

    int t;
    cin >> t;
    while(t>0) {
        int i = 0, n, k;
        cin >> n >> k;
        int arr[n];

        std::deque<int> Q(k);

        for (; i < k; ++i) {
            cin >> arr[i];
            while ((!Q.empty()) && arr[i] >= arr[Q.back()]) 
                Q.pop_back();
            Q.push_back(i); 
        }

        for (; i < n; ++i) {
            cout << arr[Q.front()] << " "; 

            if (Q.front() <= i - k) Q.pop_front();

            cin >> arr[i];
            while ((!Q.empty()) && arr[i] >= arr[Q.back()]) 
                Q.pop_back(); 
            Q.push_back(i); 
        } 

        cout << arr[Q.front()] << endl;

        t--;
        }
    return 0;
}

然而，这一次，由于时间限制，代码除了最简单的测试用例外都失败了。

我知道在实践中模块化是好的，但在这一点上，我的兴趣比其他任何事情都更“学术”。我是否遗漏了实际程序中的某些内容，或者这与我不知道的幕后运行方式有关吗？

---

编辑：正如 PaulMcKenzie 所建议的，我使用 g++ 来运行程序的两个版本，使用失败的测试用例之一作为输入。两者都运行良好并产生了相同的输出，但是有一个printKMax运行了 3.97 秒，而没有运行了 5.44 秒。它需要大约 37% 的时间。

Answer 1

您的第二个版本较慢，因为您正在交错输入和输出。

读取cin会导致任何缓冲的输出cout首先被刷新。这个想法是有一个用户需要看到你的提示。

既然你阅读和写作之间切换许多为每个测试的时间，它会导致很多I / O操作写入到控制台，它没有那么快。

请参阅：https : //www.geeksforgeeks.org/fast-io-for-competitive-programming/和https://en.cppreference.com/w/cpp/io/basic_ios/tie

你可以用 cin.tie(NULL);