複数のスレッドを使って並列にソートする際に必要なスレッド数を計算する
複数のスレッドを用いて並行にソートするアルゴリズムをrubyのthreadで実装する - 計算機と戯れる日々に必要なスレッド数を一般化する
- 奇数のとき
- n(n-1)/2
- 偶数のとき
- (n/2)^2+(n/2-1)^2=n(n-2)/2+1
| 個数 | 実値 | n(n-1)/2 | n(n-2)/2+1 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0.5 | |||||||||||
| 2 | 1 | 1 | 1 | 1 | ||||||||||
| 3 | 3 | 3 | 2.5 | 1 | 1 | 1 | ||||||||
| 4 | 5 | 6 | 5 | 2 | 1 | 2 | ||||||||
| 5 | 10 | 10 | 8.5 | 2 | 2 | 2 | 2 | 2 | ||||||
| 6 | 13 | 15 | 13 | 3 | 2 | 3 | 2 | 3 | ||||||
| 7 | 21 | 21 | 18.5 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | ||||
| 8 | 25 | 28 | 25 | 4 | 3 | 4 | 3 | 4 | 3 | 4 | ||||
| 9 | 36 | 36 | 32.5 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | ||
| 10 | 41 | 45 | 41 | 5 | 4 | 5 | 4 | 5 | 4 | 5 | 4 | 5 | ||
| 11 | 55 | 55 | 50.5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
| 12 | 61 | 66 | 61 | 6 | 5 | 6 | 5 | 6 | 5 | 6 | 5 | 6 | 5 | 6 |
ちなみにソート個数を四個と六個の場合の図は以下。
すごいなあ。5クロックで計算できるってことだもんな。
しまった、偶数時は別に表にしなくても図から個数が計算できた。後で気がついた。
あとこれは網の目の結び目の個数と同じ。
