10

私はstable_sort大きなをソートするために使用していますvector。

並べ替えには数秒（たとえば、5〜10秒）かかります。これまでに行われた並べ替えの量を示す進行状況バーをユーザーに表示したいと思います。

しかし（自分で並べ替えルーチンを作成する場合でも）、自分がどれだけ進歩したか、そしてあとどれだけ残っているかをどのように知ることができますか？

正確である必要はありませんが、「合理的」である必要があります（つまり、適度に直線的で、偽造されておらず、確かにバックトラックされていない）。

4

7 に答える 7

7

標準ライブラリのソートでは、ユーザー提供の比較関数を使用するため、比較カウンターを挿入できます。クイックソート/イントロソートまたはマージソートの比較の総数は、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

クイックソートは基本的に

  1. ピボット要素を使用したパーティション入力
  2. 最小の部分を再帰的にソートする
  3. 末尾再帰を使用して最大の部分を並べ替える

すべての作業はパーティションステップで行われます。外側のパーティションを直接実行してから、最小の部分が完了したときに進行状況を報告することができます。したがって、上記の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

これを行う最も簡単な方法：小さなベクトルを並べ替え、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

安定ソートはマージソートに基づいています。独自のバージョンのマージソートを作成した場合（スピードアップのトリックを無視して）、ログNパスで構成されていることがわかります。各パスは2^kのソートされたリストで始まり、2 ^（k-1）のリストを生成し、2つのリストを1つにマージするとソートが終了します。したがって、進行状況の指標としてkの値を使用できます。

実験を実行する場合は、比較オブジェクトをインストルメント化して、行われた比較の数をカウントし、行われた比較の数がnlognの合理的に予測可能な倍数であるかどうかを確認します。次に、実行された比較の数を数えることにより、進行状況を追跡できます。

（C ++安定ソートでは、データのコピーを保持するのに十分なストアが見つかることを期待する必要があります。そうしないと、コストがN log NからおそらくN（log N）^ 2になり、予測もはるかに大きくなります。楽観的）。

于 2012-12-16T04:59:56.397 に答える
0

インデックスの小さなサブセットを選択し、反転をカウントします。あなたはその最大値を知っています、そしてあなたが終わったときあなたは値がゼロであることを知っています。したがって、この値を「プログレッサー」として使用できます。これは、エントロピーの尺度と考えることができます。

于 2012-12-16T05:11:08.160 に答える
0

シェルソートの進捗状況を表示する方法を理解するためにほぼ1日を費やしたので、ここに簡単な式を残します。色の配列が与えられると、進行状況が表示されます。赤から黄、そして緑へと色をブレンドしています。ソートされると、青色の配列の最後の位置になります。シェルソートの場合、配列を通過するたびの反復は非常に比例しているため、進行状況はかなり正確になります。（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 に答える