我stable_sort用来排序一个大的vector.
排序大约需要几秒钟（比如 5-10 秒），我想向用户显示一个进度条，显示到目前为止已经完成了多少排序。
但是（即使我要编写自己的排序程序）我怎么知道我已经取得了多少进展，还有多少要走？
我不需要它是精确的，但我需要它是“合理的”（即合理的线性，不是伪造的，当然也不是回溯）。
问问题
1243 次
7 回答
7
标准库排序使用用户提供的比较函数，因此您可以在其中插入一个比较计数器。quicksort/introsort 或 mergesort 的比较总数将非常接近 log 2 N * N（其中 N 是向量中的元素数）。这就是我要导出到进度条的内容：比较次数 / N*log 2 N
由于您使用的是合并排序，因此比较计数将是一个非常精确的进度衡量标准。如果实现花费时间在比较运行之间置换向量，它可能会略微非线性，但我怀疑您的用户会看到非线性（无论如何，我们都习惯于不准确的非线性进度条:)）。
根据数据的性质，快速排序/引入排序会显示出更多的差异，但即使在这种情况下，也总比没有好，您总是可以根据经验添加一个捏造因素。
比较类中的一个简单计数器几乎不会花费您任何费用。就我个人而言，我什至不会费心锁定它（锁会影响性能）；它不太可能进入不一致的状态，并且无论如何进度条不会因为它获得不一致的进度数字而开始辐射蜥蜴。
于 2012-12-16T04:57:15.137 回答
1
将向量分成几个相等的部分，数量取决于您想要的进度报告的粒度。分别对每个部分进行排序。然后开始合并std::merge。您可以在对每个部分进行排序后以及每次合并后报告您的进度。您需要进行试验以确定与合并相比应计算部分排序的百分比。
编辑：
我自己做了一些实验，发现与排序相比，合并微不足道，这就是我想出的功能：
template<typename It, typename Comp, typename Reporter>
void ReportSort(It ibegin, It iend, Comp cmp, Reporter report, double range_low=0.0, double range_high=1.0)
{
double range_span = range_high - range_low;
double range_mid = range_low + range_span/2.0;
using namespace std;
auto size = iend - ibegin;
if (size < 32768) {
stable_sort(ibegin,iend,cmp);
} else {
ReportSort(ibegin,ibegin+size/2,cmp,report,range_low,range_mid);
report(range_mid);
ReportSort(ibegin+size/2,iend,cmp,report,range_mid,range_high);
inplace_merge(ibegin, ibegin + size/2, iend);
}
}
int main()
{
std::vector<int> v(100000000);
std::iota(v.begin(), v.end(), 0);
std::random_shuffle(v.begin(), v.end());
std::cout << "starting...\n";
double percent_done = 0.0;
auto report = [&](double d) {
if (d - percent_done >= 0.05) {
percent_done += 0.05;
std::cout << static_cast<int>(percent_done * 100) << "%\n";
}
};
ReportSort(v.begin(), v.end(), std::less<int>(), report);
}
于 2012-12-16T05:07:18.537 回答
0
最简单的方法：对一个小向量进行排序并假设 O(n log n) 复杂度推断时间。
t(n) = C * n * log(n) ⇒ t(n 1 ) / t(n 2 ) = n 1 /n 2 * log(n 1 )/log(n 2 )
如果排序 10 个元素需要 1 μs，那么 100 个元素将需要 1 μs * 100/10 * log(100)/log(10) = 20 μs。
于 2012-12-16T04:55:35.307 回答
0
稳定排序基于归并排序。如果您编写了自己的合并排序版本（忽略一些加速技巧），您会看到它由 log N 次传递组成。每次传递都以 2^k 个排序列表开始并生成 2^(k-1) 个列表，当它将两个列表合并为一个时排序完成。因此，您可以使用 k 的值作为进度的指示。
如果您要运行实验，您可以使用比较对象来计算所进行的比较次数，并尝试查看所进行的比较次数是否是 n log n 的某个合理可预测的倍数。然后，您可以通过计算完成的比较次数来跟踪进度。
（请注意，对于 C++ 稳定排序，您必须希望它找到足够的存储来保存数据的副本。否则成本会从 N log N 变为可能 N (log N)^2，并且您的预测也会很远乐观的）。
于 2012-12-16T04:59:56.397 回答
0
选择一小部分索引并计算反转。您知道它的最大值，并且您知道完成后该值为零。因此，您可以将此值用作“progressor”。您可以将其视为熵的度量。
于 2012-12-16T05:11:08.160 回答
0
快速排序基本上是
- 使用枢轴元素对输入进行分区
- 递归排序最小部分
- 使用尾递归对最大部分进行排序
所有工作都在分区步骤中完成。您可以直接进行外部分区，然后在完成最小部分时报告进度。所以在上面的 2 和 3 之间会有一个额外的步骤。
- 更新进度条
这是一些代码。
template <typename RandomAccessIterator>
void sort_wReporting(RandomAccessIterator first, RandomAccessIterator last)
{
double done = 0;
double whole = static_cast<double>(std::distance(first, last));
typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
while (first != last && first + 1 != last)
{
auto d = std::distance(first, last);
value_type pivot = *(first + std::rand() % d);
auto iter = std::partition(first, last,
[pivot](const value_type& x){ return x < pivot; });
auto lower = distance(first, iter);
auto upper = distance(iter, last);
if (lower < upper)
{
std::sort(first, iter);
done += lower;
first = iter;
}
else
{
std::sort(iter, last);
done += upper;
last = iter;
}
std::cout << done / whole << std::endl;
}
}
于 2012-12-16T19:31:49.350 回答
0
我花了将近一天的时间来弄清楚如何显示 shell 排序的进度，所以我将在这里留下我的简单公式。给定一组颜色，它将显示进度。它正在将颜色从红色混合到黄色，然后再到绿色。当它被排序时，它是数组的最后一个位置是蓝色的。对于 shell 排序，它每次通过数组的迭代次数是相当比例的，因此进度变得非常准确。（Dart/Flutter 中的代码）
List<Color> colors = [
Color(0xFFFF0000),
Color(0xFFFF5500),
Color(0xFFFFAA00),
Color(0xFFFFFF00),
Color(0xFFAAFF00),
Color(0xFF55FF00),
Color(0xFF00FF00),
Colors.blue,
];
[...]
style: TextStyle(
color: colors[(((pass - 1) * (colors.length - 1)) / (log(a.length) / log(2)).floor()).floor()]),
它基本上是一个交叉乘法。一个手段数组。(log(a.length) / log(2)).floor() 表示向下取整 log2(N)，其中 N 表示项目数。我用数组大小、数组编号和颜色数组大小的几种组合对此进行了测试，所以我认为这很好。
于 2020-06-18T21:11:20.790 回答