差分
スリープソート
,'''スリープソート'''([[英語]]:sleep sort)とは、究極の[[ソート]][[アルゴリズム]]である。
==概要==
アメリカの巨大掲示板群である[[4chan]]のプログラミング板にて「Genius sorting algorithm: Sleep sort」というスレッドが立てられた<ref>https://dis.4chan.org/read/prog/1295544154</ref>。[[2ちゃんねる]]風に訳すと「ちょwwwすごいソートアルゴリズム思いついたwwwww」といった感じである。
<source lang="bash">
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
</source>
あまりの凄さに全米が驚いた。
スリープソートは数学的概念を覆し、精度方向に[[スケーラブル]]であり、個々が独立しているため超並列も可能である、など様々な特徴を持っている。
このスリープソートを[[半導体]]で実装し、1クロックを1スリープとし、[[GPU]]の[[シェーダー]]ばりに超並列とすれば爆速ではないかなど様々な議論を呼んだ。
初期実装における難点は数値しか扱えないことであったが、[[コンピューター]]内部では全てを数値として表すため不可能はなく、後に登場した実装ではあらゆる[[データ]]をソートできるようなものも登場している。
ちなみに2007年に日本人で同様のアプローチで「[[ショットガンソート]]」と名付けてほぼ同様の[[アルゴリズム]]を実装した方がいる<ref>http://tockri.blog78.fc2.com/blog-entry-44.html</ref>。
==主な実装==
スリープソートの発想の画期的さと実装の容易さから瞬く間に様々な[[プログラミング言語]]による実装が登場した。
==関連項目==
*[[ソート]]
==参考文献==
{{reflist}}
{{stub}}
==概要==
アメリカの巨大掲示板群である[[4chan]]のプログラミング板にて「Genius sorting algorithm: Sleep sort」というスレッドが立てられた<ref>https://dis.4chan.org/read/prog/1295544154</ref>。[[2ちゃんねる]]風に訳すと「ちょwwwすごいソートアルゴリズム思いついたwwwww」といった感じである。
<source lang="bash">
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
</source>
あまりの凄さに全米が驚いた。
スリープソートは数学的概念を覆し、精度方向に[[スケーラブル]]であり、個々が独立しているため超並列も可能である、など様々な特徴を持っている。
このスリープソートを[[半導体]]で実装し、1クロックを1スリープとし、[[GPU]]の[[シェーダー]]ばりに超並列とすれば爆速ではないかなど様々な議論を呼んだ。
初期実装における難点は数値しか扱えないことであったが、[[コンピューター]]内部では全てを数値として表すため不可能はなく、後に登場した実装ではあらゆる[[データ]]をソートできるようなものも登場している。
ちなみに2007年に日本人で同様のアプローチで「[[ショットガンソート]]」と名付けてほぼ同様の[[アルゴリズム]]を実装した方がいる<ref>http://tockri.blog78.fc2.com/blog-entry-44.html</ref>。
==主な実装==
スリープソートの発想の画期的さと実装の容易さから瞬く間に様々な[[プログラミング言語]]による実装が登場した。
==関連項目==
*[[ソート]]
==参考文献==
{{reflist}}
{{stub}}