Quick Sort の最良値が O( N * log N ) になるのは、理解できると思う。 で、最悪値が O( N^2 ) になるのも(書き込んでいるぐらいだから)理解できると思う。 と言う事は、このアルゴリズムはこの2つの間のどこかの計算量になり、どうなるかは「与えられたデータに強く依存する」と言う事だ。
Quick Sort は決して O( N * log N ) のアルゴリズムではない。単に「係数」部が非常に軽いので、O( N * log N )である事が保証されている他のアルゴリズムを、平均値では追い抜いているのに過ぎない。最悪値比較をすれば、O( N * log N )が保証されている merge sort に負ける。
車輪の再発明をさせろ (スコア:4, すばらしい洞察)
ライブラリが無い環境でどうしていいか分からなくなる。
コードは書けるけど、アルゴリズムが無いと何もできない子になる。
一度Cとかのなにもない環境でやらせないとダメ。
無いものは作るというハングリー精神が無くなる。
#最近はPythonでしか書いてないなぁ…
#10行でWebサーバが書けるのには感動。
Re: (スコア:3, 興味深い)
学生の雇用面接（@US）をすると、いろいろなアルゴリズムや技術の名前は知っているのだけれど、それをブラックボックスとしてしか理解していない人が驚くほどいるんですよね。ちょっと話すと色々知っているし、レジュメを見てもいろんなものを作っているように見える。でもちょっと掘り下げるとすぐに馬脚を表して、がっかり。そういう人は確かに典型的に Java, そして perl や Python 止まりで C はできるけれどそれほど得意じゃない。そういう感じ。最近立て続けに、The Perils of JavaSchools [joelonsoftware.com] とNYUの先生の記事を読んで、なるほどそういう背景があったのか、ポンっと膝を叩く気分でした。
こっちの期待しているのは車の運転の仕方を知っている人ではなくて、車を作れる人なんだけどな。
Re: (スコア:2, 興味深い)
私が面接をした範囲では、quick sort を O( N * log N ) のアルゴリズムだと思い込んでいる、と言うあたりが馬脚の基本ですね。
# 逆にそこをつついてくる面接を受けた事もあります。
# 多分、あそこの面接官は本当に技術力があったんだろうな。
fjの教祖様
Re: (スコア:1)
最悪計算量が O(n^2) とかいう話？
それとも，ピボット選択がどうとか，分割後の要素数が閾値以下になったらとか実装に関わる話？
はたまた，並列計算で O(log n) に近づけられるとかそういうこと？
Re:車輪の再発明をさせろ (スコア:3, 参考になる)
Quick Sort の最良値が O( N * log N ) になるのは、理解できると思う。
で、最悪値が O( N^2 ) になるのも(書き込んでいるぐらいだから)理解できると思う。
と言う事は、このアルゴリズムはこの2つの間のどこかの計算量になり、どうなるかは「与えられたデータに強く依存する」と言う事だ。
Quick Sort は決して O( N * log N ) のアルゴリズムではない。単に「係数」部が非常に軽いので、O( N * log N )である事が保証されている他のアルゴリズムを、平均値では追い抜いているのに過ぎない。最悪値比較をすれば、O( N * log N )が保証されている merge sort に負ける。どの方法も(ランダムアルゴリズムを利用する方法でさえも)平均値を良くする以上の効果は無い。つまり、ここに述べられている『実装』の話を全部ぶち込んでも、Quick Sort の数学的な側面は変わらない。並列処理をしても変化するのは結果が出るまでの総時間だけで、計算量は変わりません。もっと言うと、並列処理をするために「データを分配する」段階が O( N ) になるので O( log N )とは、とても呼べません。
# で、分配しない、共有メモリ型にすると、メモリ参照が衝突する。その頻度がO(N)が
# 最悪値保証されてしまう。
# 衝突頻度を下げるために Cache を入れると「Cache 読み込みの段階で」O(N)が保証される。
# と言うわけで、O(N)を切るソート方式はありえないのだよ。
## 厳密な証明は面倒なのでやらないが。
実装レベルでの改良方法を一杯言ってくる人はいます。いろいろ独創的なものを持ってくる人も含めて(最初に一発 table sort を入れる、ってのは面白かった)。
その結果「係数がどんなに小さくなっても、計算量評価の際には無視する」という大前提を理解しているかどうかが判る。
# 「係数が小さいから、この項は次数が大きいけど無視しよう」という判断は、
# ・N の範囲が本当に制約されている事
# ・インターフェース的にきれいに分かれていて、
# Nが万が一でかくなったときにも対処できる事
# という2つの前提が成立しない限り、やってはいけない。で、このセンスは教えられる。
# もし、その前の段階の「計算量」の話が判っているのならば。
fjの教祖様
Re:車輪の再発明をさせろ (スコア:1)
ああ，なるほど．単純に (n * log n) を n で割ってしまいました．
よく考えたら，仮に「データを分配する」処理を無視できたとしても，
(※ 計算開始時に既にデータが無限個の計算ノードに分散しているなど)
計算量 O(log n) にはならないですね．
再帰回数 O(log n) は並列化しても減りそうにないので，
再帰 1 回当たりの計算量を O(1) にしなければ全体の計算量 O(log n) にならないが，
全ノードへのブロードキャスト O(log n) などの操作が含まれているだけでアウトですからね…．
> # と言うわけで、O(N)を切るソート方式はありえないのだよ。
最初から昇順に並んだデータに対し，
隣接要素を 1 個ずつ比較して結果がソートされているか確かめる，
というだけでも O(n) 必要ですね．
Re: (スコア:0)
>というだけでも O(n) 必要ですね．
比較するという手段が必須であれば、の話。
比較しないソート方法に対しては、その前提は崩れる。
#まあそれが汎用的かと言われればなかなか‥。
Re:車輪の再発明をさせろ (スコア:1)
(与えられたデータの各要素が大小関係の二分木のどこに属するかを決める必要があるから)
比較に基づかないビンソートや基数ソートなどでも O(n) は切らないですよね？
O(n) の前提が崩れるっていうのは近似アルゴリズムの話ですか？
Re:車輪の再発明をさせろ (スコア:1)
> 比較するという手段が必須であれば、の話。
比較しなくてもデータを読むだけでO(n)必要なので...。
O(n)より速くするには最初からソートされたデータ構造(二分検索ツリ、AVLツリー、RBツリー)を使えば良い訳です。時間のかかることは出来るだけしないようにする。部分を速くするよりも、それを使わなくする、という大局的な視点で見るのも重要。そのためにはプロファイリングが重要。
Best regards, でぃーすけ
Re: (スコア:0)
クイックソートやハッシュや双方向リストや平衡木みたいなメジャーなものは
どんな人でも知っていて当然だけど、その他大勢のアルゴリズムについては無数
にあるので、全部覚えるなんてできるはずがない。（逆に覚えようとすると
単なるアルゴリズムマニアに成り下がってしまう。）
もちろん多くのアルゴリズムを知っているべきであるというのは強く共感するし、
実際に優秀なプログラマーの多くは比較的多くのアルゴリズムを知っていると
思うけれども、暗記しているアルゴリズムの個数とプログラマーの能力とは比例
するわけではないでしょう。
Re:車輪の再発明をさせろ (スコア:2, すばらしい洞察)
あー、そういうことをいう「試験官」にプログラマーとして有能な奴はいない。テストとは「コスト」と「エラー率」との戦いだ、という事を念頭においていない証拠であり、それ自体プログラマーとして無能な証拠だから。
もちろん、個数と単純に比例はしませんがソートというトピックに対して、1つしか方法が出てこない人は確実に無能です。
# いや、名前は出てこなくてもいいんですよ。「ほら、こういう風にするやつ」でも。
大事なのは、「比較する能力がある」事。そのために「2つ以上述べられる」事。そしてそれぞれの pros/cons が比較できる事です。
ただ、大抵の場合ちゃんと2つ以上述べられる人にソートというテーマを与えると、quick sort と merge sort が出てきて、必要要件に応じてどちらを使うかをパシッと述べる事ができる。これができない人は quick sort しか出てこない。そしてほぼ確実に quick sort を O( N * log N )だと思い込んでいる。
# で、ここでこのネタをばらしていると言う事は、実はもうそろそろ次のネタが
# 見つかったという事なんで、ここを丸暗記したってだめだよ (^o^)。
fjの教祖様