編集可能

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

いつもの。
16
Pin@appbrew @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 @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
潮流に導かれしバリスタ @fumieval

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

2013-01-27 11:12:58
潮流に導かれしバリスタ @fumieval

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

2013-01-27 11:18:47
Pin@appbrew @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 @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
しょぼっち @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
残りを読む(119)

コメント

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