sleep sort に対する反応まとめ

水果子 @nogcci

@daisukekonno 普通のソートが対象の相対的な位置を決めるのに対して、#sleepsort は「あらかじめ（時間軸上での）絶対的な位置が決まっている」のが世界観を変えてくれるというか、決定論的なところが面白い。このプログラムが起動した時点でなるべき世界にしかならない。

Daisuke KONNO @daisukekonno

@nogcci たしかに。 #sleepsort はどこかハッシュテーブルに似ていると感じたのはそういうことか。データを比較して相対的に格納していくリストやツリーに対して、ハッシュ値によって絶対的な格納位置を決めていくのに似ている。

Seiya Yazaki @saiya_moebius

sleep sort http://bit.ly/miJHxE って実質上計算量 O(n) だけど、原理的には選択ソートと同じことをしてるので O(n^2) になる、のかな。まぁ実際にはデータ数が多くなるとスケジューラーの実装依存で計算量以前にバグったりしそうだが。

いつき @ityuki

メモリ空間の入れ替えを時間演算で行っていると言う点では斬新。原理はバケットソートに近い？プロセステーブルあふれと超高負荷環境下での失敗可能性が怖い RT @madogiwa 常識を覆すソートアルゴリズム！その名も"sleep sort"！http://bit.ly/m7A6qe

nogutetu @nogutetu

Sleep SortはO(n)って言っていいの?

Y. Negishi @negiyas

@nogutetu 違うかもしれないけどsleep sortはcounting sortのある実装なのでは? 　だとすると最大値が事前に分かっているという仮定の下にO(n)。　

Y. Negishi @negiyas

@negiyas @nogutetu 比較を用いたsortではO(n log n) (logの基数2)が下限なので、sleep sortはある意味すごい。

T. Onodera @gagzzi

@negiyas @nogutetu そして、sleepの実装は、大量のプロセスが眠りにくるとは想定してないだろうから、きっとinsertion sortくらいのもの使ってて、O(n^^2)かかるというオチ？w （まあ、OSによるのでしょうが）

r-west @rwest2112

タイマ関連を十分軽量にすれば、radixソートより時間は掛かってもCPU資源の節約になる場合ありかな。mを最大値としてCPU消費はnとn log mだよね？ / 常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Is… http://htn.to/H33fXR

不安の定量化 @____c____o____

sleep sortを教授に紹介したら、OS屋さんならではの指摘が在ったのでなるほどでした。けっきょくのところ待ち時間を無視しても計算量自体は短くならないのですという話でした。

Masaki Hara @qnighy

無理にこじつけるならば、sleep sortは、sortをスケジューリングに帰着する手法であり、そのsleepを二項ヒープで実装することで、heapsortになる。つまり、sleep sortはheapsortに至る途中のアイデアと見なせる。

Toshio Koide @effy55

sleep sortの計算量がすごいらしいけど、そもそもsleep命令がO(1)じゃないでしょとか言っちゃだめですかそうですか

こばやし @giwarb

うーん、sleep sort面白いなぁ。これを実用性がないとみるのはもったいないな…もっと考察できる。時間軸の概念は計算量にはないアイディアだし。

こばやし @giwarb

@giwarb sleep sortの場合時間経過を大小比較の肩代わりにしてるのがポイントになるわけだ。時間を使って計算するなんて概念は一般的な計算モデルにはなかったはず。ステップ数とは違う概念だからだ。