これqsortは単なる一般的な並べ替えであり、実装に関する約束はありません。ライブラリがプラットフォームごとにどのように異なるかはわかりませんが、Mac OS X と Linux の実装がほぼ同じであると仮定すると、qsort実装は再帰的であるか、多くのスタックが必要ですか?
私は大きな配列 (数十万の要素) を持っており、スタックを忘却することなく並べ替えたいと考えています。または、大規模な配列に相当する提案はありますか?
7080 次
9 に答える
22
これは BSD のバージョンであり、著作権は Apple であり、OS X でいつか使用されたと思われます:
http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
Blindy が説明するように、再帰の深さの上限は小さいですが、再帰呼び出しです。
これは glibc のバージョンで、おそらく Linux システムでいつか使用されたものです。
http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c
再帰呼び出しではありません。呼び出し再帰の制限が小さいのとまったく同じ理由で、少量の固定量のスタックを使用してループ再帰を管理できます。
わざわざ最新バージョンを調べることはできますか? いいえ ;-）
数十万の配列要素の場合、再帰呼び出しの実装でさえ、20 レベル以上の深さで呼び出すことはありません。非常に限られた組み込みデバイスを除いて、深くないものの壮大なスキームでは、最初にソートするほど大きな配列を持つのに十分なメモリがありません。N が上に制限されている場合、 O(log N) は明らかに定数ですが、それ以上に、通常はかなり扱いやすい定数です。通常、「小さい」の 32 倍または 64 倍は「合理的」です。
于 2010-07-31T21:05:22.230 に答える
12
ご存知のように、再帰部分は深くログされています。再帰の 64 レベル (スタック合計の ~64*4=~256 バイト) では、サイズ ~2^64 の配列、つまり 147573952589676412928 である 64 ビット CPU でアドレス指定できる大きさの配列をソートできます。 64 ビット整数のバイト。あなたはそれを記憶に留めることさえできません！
大事なことを心配してください。
于 2010-07-31T20:50:37.100 に答える
10
はい、再帰的です。いいえ、おそらく大量のスタックを使用することはありません。試してみませんか？再帰はある種のボギーではありません - それは非常に多くの問題のための選択の解決策です.
于 2010-07-31T20:46:42.503 に答える
5
を適切に実装qsortすると、log2(N) レベルを超える再帰 (つまり、スタックの深さ) は必要ありません。ここで、N は、特定のプラットフォームでの最大の配列サイズです。この制限は、パーティショニングの良し悪しに関係なく適用されることに注意してください。つまり、再帰の最悪のケースの深さです。たとえば、32 ビット プラットフォームでは、再帰の深さが最悪の場合でも 32 を超えることはありませんqsort。
言い換えれば、特にスタックの使用法が気になる場合は、奇妙な低品質の実装を扱っていない限り、心配する必要はありません。
于 2010-07-31T21:21:31.597 に答える
2
この本を読んだことを覚えています。Cプログラミング： ANSIC仕様ではqsortの実装方法が定義されていないという最新のアプローチ。
そして、この本はqsort、実際には別の種類のソート、マージソート、挿入ソート、そしてバブルソートではない可能性があると書いています：P
したがって、qsort実装は再帰的ではない可能性があります。
于 2010-07-31T21:19:43.917 に答える
1
の最新の実装のほとんどは、qsort実際に Introsort アルゴリズムを使用していると思います。とにかく、適切に作成されたクイックソートはスタックを吹き飛ばすことはありません (最初に小さいパーティションをソートし、スタックの深さを対数成長に制限します)。
ただし、イントロソートはさらに一歩進んでいます。最悪の場合の複雑さを制限するために、クイックソートがうまく機能していないことがわかった場合 (再帰が多すぎるため、O(N 2 ) の複雑さになる可能性があります)、ヒープソートに切り替えます。 O(N log 2 N) の複雑さを保証し、スタックの使用も制限します。したがって、それが使用するクイックソートがずさんに書かれていても、ヒープソートへの切り替えはとにかくスタックの使用を制限します。
于 2010-07-31T21:06:22.513 に答える
1
クイックソートを使用すると、スタックは対数的に増加します。スタックを爆破するには、多くの要素が必要になります。
于 2010-07-31T20:51:48.880 に答える
0
大きな配列で失敗する可能性のあるqsort実装は、非常に壊れています。あなたが本当に心配しているなら、私はRTFSに行きmallocますmalloc.
于 2010-07-31T20:53:08.357 に答える
0
単純なクイックソート実装 (これは依然として qsort の一般的なオプションです) の最悪の場合のスペースの複雑さは O(N) です。小さい方の配列を最初に並べ替えるように実装が変更され、末尾再帰の最適化または明示的なスタックと反復が使用される場合最悪の場合のスペースを O(log N) に減らすことができます (ここでのほとんどの回答は既に書いています)。そのため、クイック ソートの実装が壊れておらず、不適切なコンパイラ フラグによってライブラリが壊れていなければ、スタックを爆破することはありません。ただし、たとえば、末尾再帰の削除をサポートするほとんどのコンパイラは、最適化されていないデバッグ ビルドではこの最適化を行いません。間違ったフラグでビルドされたライブラリ (つまり、独自のデバッグ libc をビルドする組み込みドメインなど、最適化が不十分) は、スタックをクラッシュさせる可能性があります。
ほとんどの開発者にとって、これは決して問題にはなりません (彼らは O(log N) スペースの複雑さを持つベンダー テスト済みの libc を持っています) が、潜在的なライブラリの問題に時々目を向けることは良い考えだと思います。
更新: これが私が意味する例です: libc (2000年以降) のバグで、一時配列を保持するのに十分なメモリがあるにもかかわらず、qsort 実装が内部的にマージソートに切り替わるため、qsort が仮想メモリのスラッシングを開始します。
http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html
于 2010-07-31T22:02:16.547 に答える