まじかんと雑記

使はれてゐない最も小さい数字を選ぶやり方は、ジョブ番号が無駄に大きくなるのを防いでくれるけれども、計算量的にはあまり効率は良くない。空いてゐる番号を配列の中から探す場合、時間計算量はジョブの数に比例する。空いてゐる番号がない場合、n 個のジョブを追加するのに O(n²) の時間がかかる。空いてゐる番号をヒープに覚えさせておけばジョブの数の対数にまで計算量を抑へられるが、果たしてそこまでやる価値があるだらうか。

Bash-5.1.8 は、使はれてゐるジョブ番号の最大値の次の自然数をジョブ番号として選ぶ様になってゐる。このやり方は、より小さいジョブ番号が空いてゐる場合でも再利用されないといふ点では非効率だが、償却時間計算量は定数になる。ただし、番号が最大のジョブが終了しない限り番号が再利用されないので、同時に実行されるジョブの数が有限でもジョブ番号が無限に増えていく可能性がある。