「スリープソート」の版間の差分
imported>Administrator 編集の要約なし |
|||
| (同じ利用者による、間の1版が非表示) | |||
| 18行目: | 18行目: | ||
</source> | </source> | ||
<source lang="bash"> | |||
# example usage: | |||
# ./sleepsort.bash 5 3 6 3 6 3 1 4 7 | |||
</source> | |||
あまりの凄さに全米が震撼した。 | |||
スリープソートは数学的概念を覆し、精度方向に[[スケーラブル]]であり、個々が独立しているため超並列も可能である、など様々な特徴を持っている。 | スリープソートは数学的概念を覆し、精度方向に[[スケーラブル]]であり、個々が独立しているため超並列も可能である、など様々な特徴を持っている。 | ||
このスリープソートを[[半導体]]で実装し、1クロックを1スリープとし、[[GPU]]の[[シェーダー]]ばりに超並列とすれば爆速ではないかなど様々な議論を呼んだ。 | このスリープソートを[[半導体]]で実装し、1クロックを1スリープとし、[[GPU]]の[[シェーダー]]ばりに超並列とすれば爆速ではないかなど様々な議論を呼んだ。 | ||
| 35行目: | 40行目: | ||
{{reflist}} | {{reflist}} | ||
[[category: アルゴリズム]] | |||
[[category: 算数]] | |||
2018年10月31日 (水) 02:58時点における最新版
スリープソート（英語：sleep sort）とは、究極のソートアルゴリズムである。
概要[編集 | ソースを編集]
アメリカの巨大掲示板群である4chanのプログラミング板にて「Genius sorting algorithm: Sleep sort」というスレッドが立てられた[1]。2ちゃんねる風に訳すと「ちょwwwすごいソートアルゴリズム思いついたwwwww」といった感じである。
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
# example usage:
# ./sleepsort.bash 5 3 6 3 6 3 1 4 7
あまりの凄さに全米が震撼した。 スリープソートは数学的概念を覆し、精度方向にスケーラブルであり、個々が独立しているため超並列も可能である、など様々な特徴を持っている。 このスリープソートを半導体で実装し、1クロックを1スリープとし、GPUのシェーダーばりに超並列とすれば爆速ではないかなど様々な議論を呼んだ。
初期実装における難点は数値しか扱えないことであったが、コンピューター内部では全てを数値として表すため不可能はなく、後に登場した実装ではあらゆるデータをソートできるようなものも登場している。
ちなみに2007年に日本人で同様のアプローチで「ショットガンソート」と名付けてほぼ同様のアルゴリズムを実装した方がいる[2]。
主な実装[編集 | ソースを編集]
スリープソートの発想の画期的さと実装の容易さから瞬く間に様々なプログラミング言語による実装が登場した。