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, すばらしい洞察)
例えば、便利なアルゴリズムや制御構造が揃ってるlispを使ってアルゴリズムに弱くなるかっていうとそんなことないだろう。
Javaの問題は、便利な道具が揃ってることじゃなくて簡単にソースが見れないのと、ライブラリの利用者と製作者を分けるような姿勢が問題なんじゃないかって気がする。
似たようなので、Windowsの世界もそうかな。OSのことを語られるのにあーなんじゃないかこーなんじゃないかって内部構造を想像して終わらない議論になってて、まるで占い師か経済学者の議論を見ているような気分になることがある。
Re: (スコア:0)
Re: (スコア:0)
飾りなのは実装（含む言語）であって、アルゴリズムがキモだよ。
Re: (スコア:0)
(そういう意味ではLinuxでCの世界と同じくらいにソースは浴びれる)
んだけど、
いっぽう「分けるような姿勢」のほうは本当に頭が痛いですね。
いや、それもJava言語自体にそういう姿勢が有るわけじゃないんだが、
今時Javaを採用するような(クソ)企業の中では、
そういう姿勢が横行してるのは事実だね。
Re: (スコア:0)
>いっぽう「分けるような姿勢」のほうは本当に頭が痛いですね。
ライブラリのソースが誰でも手に入るので、製作者としての立場で
ライブラリを拡張するのも自由です。
クローズドソースならともかく、オープンソースなライブリで利用者と製作者を
分けることの問題はどこにあるのだろうか？
むしろ、単に使うだけならたいした知識も不要で、お客さん扱いされていることに喜ぶべきです。
Re:車輪の再発明をさせろ (スコア:1, すばらしい洞察)
>分けることの問題はどこにあるのだろうか？
同じようにソースを公開してても、そのソースを見たり修正してみる人間の割合はコミュニティによって大きく異なる。なぜなら、ソースがあるかどうかというのはただの前提条件にすぎなくて、コミュニティにハックかそれに類似した文化があるかどうかもまた重要だから。そして、そういう文化が自然と高い教育効果を生むのだと思う。
Cみたいに、実装がちらちらと時には大っぴらに見えて、不満があったらちょろっとハック可能っていうのは、企業ユースでは危険の種かもしれないけど、教育効果という点ではポイントが高い。
Re: (スコア:0)
(クソ)企業には、そんなことをさせない規約なり文化なりが有ります。
ライセンス的に不味い場合(LGPLとか)も当然そうですが、
そうでなくても
「ソースなんか見てる暇があったらコード書け」
といわれるのがオチです。
つまり「学習してない低レベルのコードを」書けと言ってるのですね。
まあ、そんなクソコードでも
美味しい美味しいといって食べてくれる顧客が
居るから成り立つボロイ商売です。
Re: (スコア:0)
占い師は議論なんてしません。罵り合うだけです。
＃…経済学者も？
Re: (スコア:0)
あちらではeconomistと一つの単語で事足りるのに、なぜか日本では二つの単語を使って分けないとならない。
経済学者の方の議論は無駄に小難しいし抽象的過ぎて意味不明に見えるもんでしょうけど、一応まじめにやってますよ。
Re:車輪の再発明をさせろ (スコア:3, 興味深い)
学生の雇用面接（@US）をすると、いろいろなアルゴリズムや技術の名前は知っているのだけれど、それをブラックボックスとしてしか理解していない人が驚くほどいるんですよね。ちょっと話すと色々知っているし、レジュメを見てもいろんなものを作っているように見える。でもちょっと掘り下げるとすぐに馬脚を表して、がっかり。そういう人は確かに典型的に Java, そして perl や Python 止まりで C はできるけれどそれほど得意じゃない。そういう感じ。最近立て続けに、The Perils of JavaSchools [joelonsoftware.com] とNYUの先生の記事を読んで、なるほどそういう背景があったのか、ポンっと膝を叩く気分でした。
こっちの期待しているのは車の運転の仕方を知っている人ではなくて、車を作れる人なんだけどな。
Re:車輪の再発明をさせろ (スコア:2, 興味深い)
私が面接をした範囲では、quick sort を O( N * log N ) のアルゴリズムだと思い込んでいる、と言うあたりが馬脚の基本ですね。
# 逆にそこをつついてくる面接を受けた事もあります。
# 多分、あそこの面接官は本当に技術力があったんだろうな。
fjの教祖様
Re:車輪の再発明をさせろ (スコア:2, 参考になる)
クイックソートは『平均』nlognだと教えてはいるのですが、細かい背景をすっ飛ばしてnlognだけ暗記するアンポンタンがおおくて、すみません。
P.S。「quicksortは最悪時O(n^2)」よりも、「quicksortは最良時O(nlogn)」のほうが結構頭からすっかり抜けている落とし穴かも。ちゃんとクイックソートを理解していれば、その場で考えて「最良時もnlognだ」と分かるんですが。
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の教祖様
Re:車輪の再発明をさせろ (スコア:2, 興味深い)
ので、お手軽言語だって教えておく意味は十分あると思うよ。
Re:車輪の再発明をさせろ (スコア:2, すばらしい洞察)
ここで得た経験を足がかりにして，応用を利かせられれば良いと思いますが．
特に最近の大学のプログラミング実習は，実用性を中心に考えるのではなくて
取っかかりを掴ませるところに主眼を置いている気がします．
とりあえず誰でも出来るような簡単なところからスタートして動かしてみて，
それで面白がってやる気を起こした学生は，面白がってもっと上を目指すでしょうし，
つまらんと思った学生は逃げていきます．
Re:車輪の再発明をさせろ (スコア:2, すばらしい洞察)
Re: (スコア:0)
>近年減少気味の受講者数を増やせそうな
>お手軽な言語とカリキュラム しか 教えなくなっていると主張。
と、「だけ」では駄目ということの様ですね。
まあ原理をきちんと学ばせないと潰しも応用も利かない技術者の出来上がりですから。
#時代の変化に対応できなくなること必至。それは不幸だな。
どこかのエライ人曰く (スコア:0)
ってことですか?
Re:車輪の再発明をさせろ (スコア:1)
std::vectorを知らなくて、自前で可変長配列をがんばって作ってた覚えが。
std::mapを知らなくて、自前で二分木をがんばって作ってた覚えが。
Re:車輪の再発明をさせろ (スコア:1, すばらしい洞察)
何もないどころか、Cもライブラリ充実しまくりだと思うんですが…。
# そんな僕はASM派。
Re: (スコア:0)
Workframeがあるとなんでもできるような気がするが、Write Once Run Anywhereとは随分遠いところへ来てしまったような気がする。
純javaだけで喰っていけるようには一生なれないだろうな。