【またかよ】「Haskellでクイックソート」問題【何度目だ】

いつもの。
17
Pin📍AppBrew CTO @spinute

クイックソート何行だと思う? rubyが40行、c++が35行、haskellは5行だよ? 大きいのと小さいのにちぎる、空だったら終わる、それが本質でそれだけが必要最低限。 クイックソートのイデアは五行に収まるらしい

2013-01-27 00:18:27
Yoshi Yamaguchi @ymotongpoo

Haskellの凄さをクイックソートで語るクラスタを避けとけば間違いない

2013-01-27 11:05:29
Jun Furuse 🐫🌴 @camloeba

そのクイックソートは偽物です RT @spinute クイックソート何行だと思う? rubyが40行、c++が35行、haskellは5行だよ? 大きいのと小さいのにちぎる、空だったら終わる、それが本質でそれだけが必要最低限。 クイックソートのイデアは五行に収まるらしい

2013-01-27 11:05:35
Pin📍AppBrew CTO @spinute

@camloeba haskell歴二日目のヒヨッコが感動に昂ぶって書いた文章なのでご容赦、ご教示くださると嬉しいです。

2013-01-27 11:06:52
わたけん @wataken44

クイックソートはpivot適当に選んでいいからといって配列の最小値と最大値の間を選ばなかったら無限ループに陥って死ぬ

2013-01-27 11:08:54
Jun Furuse 🐫🌴 @camloeba

@spinute 簡単に言うと、クイックソートの本質である in place sort でないところがまずいです。そして実際遅すぎて実用になりません。クイックソートのような遅いソートアルゴリズムでしかないです。Haskell クイックソート 偽物 などで検索してください。

2013-01-27 11:12:37
ふみ (DJ Monad) @fumieval

Haskellのクイックソートはいわゆるミミック

2013-01-27 11:12:58
ふみ (DJ Monad) @fumieval

いや、セイレーンと呼ぶべきか

2013-01-27 11:17:17
ふみ (DJ Monad) @fumieval

クイックソートはHaskell界のローレライだったのだ…

2013-01-27 11:18:47
Pin📍AppBrew CTO @spinute

@camloeba なるほど、理由はまだわかったようなわからないようなですが、c++よりはひとまず確かに遅いようです。検索したら色々出てきたので読んでみます、ご指摘ありがとうございます。

2013-01-27 11:38:32
Jun Furuse 🐫🌴 @camloeba

プログラミングでの抽象化能力はあれば強力なんだけど、下手するとメモリ書き換えを基本とする今のコンピュータの本質から離れてしまった例を簡単に書けしかもそれになかなか気づけない。「クイックソート」はそういう「入門者殺し」の例だと私は思います

2013-01-27 11:42:22
Jun Furuse 🐫🌴 @camloeba

Haskell に限らず関数型プログラミングが出来る言語の多くの初心者向け本や情報がこの変なクイックソートを入門者殺しに使いはじめている。あんまり良くないことだと思います

2013-01-27 11:51:02
Pin📍AppBrew CTO @spinute

初心者あるあるだったわけだ 先は長いし、cもアセンブリもひいてはハード、アーキテクチャの振る舞いも忘れてはいけないし、可能なら相互に絡めて理解してみる必要があるわけですね

2013-01-27 11:51:07
Hideyuki Tanaka @tanakh

あれ、どこが変なんだろう。 RT @camloeba Haskell に限らず関数型プログラミングが出来る言語の多くの初心者向け本や情報がこの変なクイックソートを入門者殺しに使いはじめている。あんまり良くないことだと思います

2013-01-27 12:04:57
Hideyuki Tanaka @tanakh

なぜHaskellのコードでメモリを意識しないといけないんだろう。

2013-01-27 12:05:28
普通のC++使い、銀天すばる @SubaruG

Haskellで真面目にクイックソート書くと,一旦 STArray 辺りに落としてから普通に手続き型言語みたいなソートをすることになりますね.

2013-01-27 12:06:11
カル @nullkal

関数型プログラミング言語に効率を求めちゃだめだと思ってる。Haskellの入門書とかに書いてあるクイックソートって先頭の要素をピボットにしてる時点で実用的なものじゃないことは明白だし

2013-01-27 12:06:16
サム @sam_silf

クイックソートは初心者に教えちゃいかんだろう。配列で手一杯なところに再帰なんか詰め込んでみろ、一瞬で頭がパーンだ

2013-01-27 12:06:28
Hideyuki Tanaka @tanakh

in-placeな実装がかんたに作れるってのはquick sortの本質ではないと思う。実装選択の際の判断材料にはなると思うけど

2013-01-27 12:06:37
shobotch @dll7

バブルソートするの楽しい

2013-01-27 12:06:54
カル @nullkal

メモリ意識したいならC言語でポインタと戯れててください

2013-01-27 12:07:06
Hideyuki Tanaka @tanakh

偽物というのは、あまりにも語弊があるし、そっちのほうがよっぽど初心者を混乱させるし良くない。

2013-01-27 12:07:18
Masaki Hara @qnighy

どれそれ言語に効率を求めてはいけない、は言い過ぎ感ある

2013-01-27 12:07:33
サム @sam_silf

良くてバブルソートじゃないですかね・・・

2013-01-27 12:07:35
1 ・・ 6 次へ