珠玉のプログラミングを読んだ

GWには普段はやらないことをやろうと思い、数年前に流し読みだけして積んであった、珠玉のプログラミングという本を読みました。 www.amazon.co.jp

かなり古い本なのですが、富豪的プログラミングに慣れてしまっている自分にとっては、アルゴリズムの大切さや、パフォーマンス・チューニングの勘所を再認識する、とても良い機会となりました。

今回は本文中の擬似コードをGoで実装し、その効果を確認してみたいと思います。

お題

n要素のint配列xを入力とし、配列xの連続した要素でその和が最大になるものをみつけ、
その和を出力とする。

例えば以下の様な配列があった時、最大となるのはx[2..6]の和で187です。

|31|-41|59|26|-53|58|97|-93|-23|84|

これをいくつかのアルゴリズムで実装します。事前に、各処理から呼び出す max を定義しておきます。

func max(comp ...int) int {
    i := 0
    for _, c := range comp {
        if c > i {
            i = c
        }
    }
    return i
}

実装

O(n³) な実装

一番シンプルに実装すると

0 ≦ i ≦ j < nを満たす全てのi, j のペアについて x[i..j] の和を計算し、それらのうち最大のものを返却する、と言った感じになるかと思います。

具体的な実装は以下です。計算量は O(n³) です。

func cubed(list []int) int {
    maxsofar := 0
    len := len(list)
    for i := 0; i < len; i++ {
        for j := i; j < len; j++ {
            sum := 0
            for k := i; k <= j; k++ {
                sum += list[k]
                maxsofar = max(maxsofar, sum)
            }
        }
    }
    return maxsofar
}

O(n²) な実装

上記アルゴリズムを少し改良します。 x[i..j] の和は、その前までの x[i..j - 1] の和にx[j]を加えるだけなので、最後のループは必要無さそうです。という訳で削ります。

これで計算量は O(n²) となりました。

func squared(list []int) int {
    maxsofar := 0
    len := len(list)
    for i := 0; i < len; i++ {
        sum := 0
        for j := i; j < len; j++ {
            sum += list[j]
            maxsofar = max(maxsofar, sum)
        }
    }
    return maxsofar
}

O(n log n) な実装

アルゴリズムの定番、二分木 x リニアサーチな実装にして、計算量を O(n log n)にします。配列を a、bに分割し、それぞれの計算を再帰的に行います。注意点としては a、b両方にまたがる領域(ここでは c と呼びます)の考慮が必要となるところです。 cを計算するときには、分割する左側の配列は、aの最後の要素を含む配列の中で、要素の和が最大となるものを使用します。

func nlogn(list []int) int {
    return maxsum3(0, len(list)-1, list)
}

func maxsum3(l, u int, list []int) int {
    if l > u {
        return 0
    }
    if l == u {
        return max(0, list[l])
    }
    m := (l + u) / 2
    lmax, sum := 0, 0
    for i := m; i >= l; i-- {
        sum += list[i]
        lmax = max(lmax, sum)
    }

    rmax, sum := 0, 0
    for i := m + 1; i <= u; i++ {
        sum += list[i]
        rmax = max(rmax, sum)
    }

    return max(lmax + rmax, maxsum3(l, m, list), maxsum3(m + 1, u, list))
}

O(n) な実装

個人的には目からウロコでしたが、これを線形(O(n))で実装する方法があります。配列の開始位置x[0]から終端のx[n-1]まで、つねにそこまでの配列の和の最大値を記録しながら走査するアルゴリズムです。

func linear(list []int) int {
    len := len(list)
    maxsofar := 0
    maxend := 0
    for i := 0; i < len; i++ {
        maxend = max(maxend + list[i], 0)
        maxsofar = max(maxsofar, maxend)
    }

    return maxsofar
}

シンプルかつ、非常に強力な実装ですね！

確認

テストコード

var list []int

func init() {
    var i int
    flag.IntVar(&i, "num", 0, "num")
    flag.Parse()
    fmt.Println("list num =", i)

    rand.Seed(time.Now().UnixNano())
    list = rand.Perm(i)
}

func BenchmarkCubed(b *testing.B) {
    for i := 0; i < b.N; i++ {
        cubed(list)
    }
}

func BenchmarkSquared(b *testing.B) {
    for i := 0; i < b.N; i++ {
        squared(list)
    }
}

func BenchmarkNlogn(b *testing.B) {
    for i := 0; i < b.N; i++ {
        nlogn(list)
    }
}

func BenchmarkLinear(b *testing.B) {
    for i := 0; i < b.N; i++ {
        linear(list)
    }
}

$ go test -bench . -num=10
list num = 10
BenchmarkCubed-5         1000000              1093 ns/op
BenchmarkSquared-5       5000000               256 ns/op
BenchmarkNlogn-5         5000000               309 ns/op
BenchmarkLinear-5       20000000                83.3 ns/op

$ go test -bench . -num=100
list num = 100
BenchmarkCubed-5            2000            838238 ns/op
BenchmarkSquared-5        100000             22884 ns/op
BenchmarkNlogn-5          300000              4729 ns/op
BenchmarkLinear-5        2000000               834 ns/op

$ go test -bench . -num=1000
list num = 1000
BenchmarkCubed-5               2         775887991 ns/op
BenchmarkSquared-5          1000           2182157 ns/op
BenchmarkNlogn-5           20000             64348 ns/op
BenchmarkLinear-5         200000              8250 ns/op

期待通りの動作をしているようです。

最後に

O(n log n) の実装までは割りとスムーズに理解できましたが、最後の O(n) のそれは、理解するのに少し時間がかかりました。

ことWeb開発で言うと、パフォーマンスのボトルネックはネットワークやディスクI/O等になることが多く、 CPUやMemoryマターな問題に対して、アルゴリズムを駆使して解決する、みたいなケースはあまり多くないかもしれません。

しかし、エンジニアと名乗るからにはこの辺のスキルもきっちり抑えて置いたほうがよいなあと改めて思いました。日々是学習ですね (^^;)

技術備忘記

日々調べたこととかとりとめなく

Goでアルゴリズムのお勉強