10周年のSPコンテンツ!
16
Pin @spinute
クイックソート何行だと思う? rubyが40行、c++が35行、haskellは5行だよ? 大きいのと小さいのにちぎる、空だったら終わる、それが本質でそれだけが必要最低限。 クイックソートのイデアは五行に収まるらしい
Yoshi Yamaguchi 🇯🇵 @ymotongpoo
Haskellの凄さをクイックソートで語るクラスタを避けとけば間違いない
Jun Furuse 🐫🌴 @camloeba
そのクイックソートは偽物です RT @spinute クイックソート何行だと思う? rubyが40行、c++が35行、haskellは5行だよ? 大きいのと小さいのにちぎる、空だったら終わる、それが本質でそれだけが必要最低限。 クイックソートのイデアは五行に収まるらしい
Pin @spinute
@camloeba haskell歴二日目のヒヨッコが感動に昂ぶって書いた文章なのでご容赦、ご教示くださると嬉しいです。
わたけん @wataken44
クイックソートはpivot適当に選んでいいからといって配列の最小値と最大値の間を選ばなかったら無限ループに陥って死ぬ
Jun Furuse 🐫🌴 @camloeba
@spinute 簡単に言うと、クイックソートの本質である in place sort でないところがまずいです。そして実際遅すぎて実用になりません。クイックソートのような遅いソートアルゴリズムでしかないです。Haskell クイックソート 偽物 などで検索してください。
ふみ @fumieval
Haskellのクイックソートはいわゆるミミック
ふみ @fumieval
いや、セイレーンと呼ぶべきか
ふみ @fumieval
クイックソートはHaskell界のローレライだったのだ…
Pin @spinute
@camloeba なるほど、理由はまだわかったようなわからないようなですが、c++よりはひとまず確かに遅いようです。検索したら色々出てきたので読んでみます、ご指摘ありがとうございます。
Jun Furuse 🐫🌴 @camloeba
プログラミングでの抽象化能力はあれば強力なんだけど、下手するとメモリ書き換えを基本とする今のコンピュータの本質から離れてしまった例を簡単に書けしかもそれになかなか気づけない。「クイックソート」はそういう「入門者殺し」の例だと私は思います
Jun Furuse 🐫🌴 @camloeba
Haskell に限らず関数型プログラミングが出来る言語の多くの初心者向け本や情報がこの変なクイックソートを入門者殺しに使いはじめている。あんまり良くないことだと思います
Pin @spinute
初心者あるあるだったわけだ 先は長いし、cもアセンブリもひいてはハード、アーキテクチャの振る舞いも忘れてはいけないし、可能なら相互に絡めて理解してみる必要があるわけですね
Hideyuki Tanaka @tanakh
あれ、どこが変なんだろう。 RT @camloeba Haskell に限らず関数型プログラミングが出来る言語の多くの初心者向け本や情報がこの変なクイックソートを入門者殺しに使いはじめている。あんまり良くないことだと思います
Hideyuki Tanaka @tanakh
なぜHaskellのコードでメモリを意識しないといけないんだろう。
普通のC++使い、銀天すばる @SubaruG
Haskellで真面目にクイックソート書くと,一旦 STArray 辺りに落としてから普通に手続き型言語みたいなソートをすることになりますね.
カル @nullkal
関数型プログラミング言語に効率を求めちゃだめだと思ってる。Haskellの入門書とかに書いてあるクイックソートって先頭の要素をピボットにしてる時点で実用的なものじゃないことは明白だし
サム @sam_silf
クイックソートは初心者に教えちゃいかんだろう。配列で手一杯なところに再帰なんか詰め込んでみろ、一瞬で頭がパーンだ
Hideyuki Tanaka @tanakh
in-placeな実装がかんたに作れるってのはquick sortの本質ではないと思う。実装選択の際の判断材料にはなると思うけど
しょぼっち @dll7
バブルソートするの楽しい
カル @nullkal
メモリ意識したいならC言語でポインタと戯れててください
Hideyuki Tanaka @tanakh
偽物というのは、あまりにも語弊があるし、そっちのほうがよっぽど初心者を混乱させるし良くない。
Masaki Hara @qnighy
どれそれ言語に効率を求めてはいけない、は言い過ぎ感ある
サム @sam_silf
良くてバブルソートじゃないですかね・・・
残りを読む(119)

コメント

Unagi @unagix 2013年1月27日
うわぁ。俺だけ何言ってるんだこれ。
SODA Noriyuki @n_soda 2013年1月28日
クイックソートを使うのは、最悪O(N^2)でも大抵は速いからなので、よくある場合(ほぼソートされた配列をソート)で最悪なコード(先頭要素をpivotにする)って、あまり示す意味がないような。これは遅いから普通は…と続けるならアリだけど
ichimal @ichimal 2013年1月29日
計算量=(時間計算量+空間計算量)。時間量が一緒だからって、空間量のオーダーの異なるアルゴリズムを同一視するのが意味不明なだけ。そしてin-place性は空間量オーダー決定の支配的要因。無視して良いわけがない。
ログインして広告を非表示にする
ログインして広告を非表示にする