先日の並行和で順序依存があった問題を解決

2018/08/14 02:27:10

酢と塩 — ただの足し算だし順序依存ないだろと思っていたらそうでもなかった話 では float64 の並行和によって丸め誤差が発生して逐次処理と結果が異なってしまうという話をしました。

「当初逐次処理と結果が異なる」ことが悪だと思っていました。しかし冷静に考えると円周率の近似値を求めるという要求は満たしています。

同じ条件での返り値を保証する

コンピューターの性質を考えると丸め誤差は発生して当然です。ただし並行処理の順序により毎回返り値が変わってしまうのは大問題です。

並行処理内の結果は常に同一なのですから、後は部分和を足し合わせる順序を保証すれば、答えは常に同一になります・

<br/>type SumResult struct {
    Offset int
    Sum    float64
}
func compute(rectCount, workers int) float64 {
    sum := 0.0
    width := 1.0 / float64(rectCount)
    ch := make(chan SumResult)
    for i := 0; i &lt; workers; i++ {
        go func(ch chan SumResult, offset int) {
            sum := 0.0
            for i := offset; i &lt; rectCount; i += workers {
                mid := (float64(i) + 0.5) * width
                height := 4.0 / (1.0 + mid*mid)
                sum += height
            }
            ch &lt;- SumResult{
                Offset: offset,
                Sum:    sum,
            }
        }(ch, i)
    }
    // 部分和を足し合わせる順序を保証する
    results := make([]float64, workers)
    for i := 0; i &lt; workers; i++ {
        result := &lt;-ch
        results[result.Offset] = result.Sum
    }
    for _, n := range results {
        sum += n
    }
    return sum * width
}

これで rectCount と workers が同一なら毎回同じ答えが返るようになりました。処理速度も毎回結果が変わってしまう最速のものとほぼ同じです。

無駄な処理を省くテクニック

本を読み進めると載っていました。

前回のコードでは各 worker に割りあてる restCount の範囲を (それなりの処理で) 以下のように分割していました。

restCount = 10 worker = 4 の場合です。

しかし今回のように worker 数で for をステップしていくとそのような分割は必要がないようです。便利ですね。