在 C++ 程序中显示进程完成的百分比

Question

我正在制作一组 C++ 库作为我的数据结构作业的一部分，其中包括向量的自定义实现、排序算法、堆栈等。我应该在运行ning 时间工作排序算法、冒泡排序、选择排序、快速排序等，它们是我的库的一部分。

现在给定10^6数量级的算法测试数据集。我运行对一个2*10^6个元素的数据进行冒泡排序，程序用了大约138分钟才运行，而在这段时间里，我不知道我的排序算法是不是是否正常工作，或者是否正常工作。我想为排序函数添加另一个功能，即它们可以显示完成排序的百分比，我认为这是可能的，因为像冒泡排序这样的算法是确定性的。

我需要在启动过程后立即显示一条消息：

Bubble sort under progress. Done: 17%

这个百分比由算法决定。考虑具有 10000 个元素的冒泡排序示例。如果你看一下冒泡排序算法（参考这里：https://en.wikipedia.org/wiki/Bubble_sort），它有 2 个循环，并且在主循环的每次迭代之后，一个元素被固定到它在排序数组中的正确位置。所以经过 1 次迭代后，百分比应该增加 0.01%。

虽然这个百分比计算有一个问题，在这种情况下，百分比增加的时间不断减少，但这样就可以了。

另外，这个数字应该在需要的时候在同一个地方增加。但我不知道如何实施它。

Answer 1

对于冒泡排序的特殊情况，您可以用您拥有的元素数量除以 100。如果您有 552 个元素，那么您将得到 5。（使用整数很有意义）。然后，在你的循环中有一个计数器。如果计数器是 5 的倍数（到目前为止，您已经对 5 个元素进行了排序），那么您可以将百分比增加 1 并打印出来。至于打印它以便百分比出现在现场而不是打印在下面，你可以打印退格！要么，要么尝试使用 ncurses 库，尽管这可能有点矫枉过正。最后，执行此操作的另一种方法可能是使用 linux 样式的进度条，长度为 50 个字符或类似的东西。

Answer 2

您可以将通用类型的回调函数传递给您的冒泡排序函数，并以合理的间隔调用该函数。

这会影响性能，但无论如何，当您使用冒泡排序时，这不应该是一个问题。

首先我们需要一些包括：

#include <iostream>
#include <vector>
#include <random>
#include <chrono>

然后是 bubblesort 函数，我基本上是从维基百科中获取的：https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort

template <typename T, typename Func>
void bubblesort(std::vector<T> &v, Func callback) {
    size_t const len = v.size();
    size_t n = v.size();
    while(n > 0) {
        size_t newn = 0;
        for(size_t i = 1; i <= n-1; ++i) {
            if (v[i - 1] > v[i]) {
                std::swap(v[i-1], v[i]);
                newn = i;
            }
        }
        n = newn;
        callback(100-static_cast<int>(n*100/len));
    }
}

只要在一个元素中完成排序，我们就会调用给定的回调函数（或在对象上使用 operator()）。

我们传递的参数是我们已经走了多远的整数百分比。请注意，由于整数运算，您不能使用 n*100/v.size() 更改运算顺序，否则它始终会导致 0，因为 n 始终小于 v.size();

using namespace std::chrono; //to avoid the horrible line becoming even longer

int main() {
    std::vector<int> vec; 

    /* fill vector with some data */
    std::mt19937 generator(static_cast<unsigned long>(duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count())); //oh god
    for(int i = 0; i < 100000; ++i) {
        vec.push_back(static_cast<int>(generator()));
    }

对于初始化，我们创建一个随机数生成器并使用当前时间作为种子。然后我们将一些元素放入向量中。

    char const *prefix = "Bubble sort under progress. Done: ";
    int lastp = -1;
    bubblesort(vec, [&lastp,prefix](int p){
        //if progress has changed, update it
        if(p != lastp) {
            lastp = p;
            std::cout << "\r" << prefix << p << "%" << std::flush;
            /*std::flush is needed when we don't start a new line
              '\r' puts the cursor to the start of the line */
        }
    });

    std::cout << "\r" << prefix << "100%" << std::endl;
    //make sure we always end on 100% and end the line
}

现在是核心部分：我们将 C++ lambda 函数作为回调传递给我们的 bubblesort 函数。然后，我们的 bubblesort 函数将使用百分比值调用此 lambda 并将其写入屏幕。

瞧，我们得到了一些整洁的输出：

https://youtu.be/iFGN8Wy9T3o

结束语：

您当然可以将 lamda 函数集成到 sort 函数本身中，但是我不推荐这样做，因为您会失去很多灵活性。但这是一个由您决定的设计选择 - 如果您不需要灵活性，只需对其进行硬编码。

百分比不是很准确，事实上，知道您处于 20%（以及达到该水平需要多长时间）并不能告诉您达到 100% 所需的时间，因为很可能是，向量的最后 20% 已排序（因此可以使用 bubblesort - O(n) 快速排序），但其余 80% 是随机的，并采用 O(n^2) 进行排序. 事实上，它告诉你的只是你正在取得进步，但这就是你一开始想要的，所以我想这没关系。

如果您想要更准确的百分比，请像这样调整您的程序：

#include <iomanip>
/* ... */
callback(10000-static_cast<int>(n*10000/len));
/* ... */
std::cout.fill('0'); //to fill leading zero of p%100
std::cout << "\r" << prefix << p/100 << "." << std::setw(2) << p%100 << "%" << std::flush;

如果您决定改用浮点值，请记住清除先前输出中的剩余字符 -“\r”仅重置光标位置，但不会清除该行。

使用 std::cout.precision(3); 以获得固定精度或在消息后写一些空格以清除之前的运行。

在 C++ 程序中显示进程完成的百分比

Show the percentage of process completion in a C++ program

c++

algorithm

io

function

percentage

结束语：