オフラインリアルタイムどう書く E22 の実装例(Go で 腕力)

オフラインリアルタイムどう書く E22 の実装例(Go で 腕力)
問題 : http://nabetani.sakura.ne.jp/hena/orde22numord/
解答リンク集 : https://qiita.com/Nabetani/items/99e38a39165e1905b415

で。

ナイーブな実装を go で書いてみた。

実装

package e22

import (
    "fmt"
    "sort"
    "strconv"
    "strings"
)

func impl(m int, n int, b int, x int) int {
    values := make([]string, 0, n-m+1)
    for i := m; i <= n; i++ {
        values = append(values, strconv.FormatInt(int64(i), b))
    }
    sort.Strings(values)
    val, _ := strconv.ParseInt(values[x-1], b, 32)
    return int(val)
}

func solve(src string) string {
    split := strings.Split(src, ",")
    fmt.Println(split)
    m, _ := strconv.Atoi(split[0])
    n, _ := strconv.Atoi(split[1])
    b, _ := strconv.Atoi(split[2])
    x, _ := strconv.Atoi(split[3])
    return strconv.Itoa(impl(m, n, b, x))
}

テスト

package e22

import (
    "testing"
)

func TestE22(t *testing.T) {
    var tests = []struct {
        name  string
        input string
        want  string
    }{
        {"0", "2,15,3,8", "14"},
        {"1", "6,8,8,1", "8"},
        {"2", "6,6,5,1", "6"},
        // 中略
        {"36", "66097362,104618756,16,32740764", "98838125"},
    }
    ch := make(chan struct{}, len(tests))
    for _, test := range tests {
        go func(name, input, want string) {
            got := solve(input)
            if got != want {
                t.Errorf("%v: solve(%q)=%q, want %q\n", name, input, got, want)
            }
            ch <- struct{}{}
        }(test.name, test.input, test.want)
    }
    for range tests {
        <-ch
    }
}

実装の方はシングルスレッドで、テストの方で goルーチンを使ってみた。
結果、 118秒。まあそんなもんか。
テストで goルーチンを使わないと 244秒。倍しか違わない。
C++ で OpenMP を使わない実装( see https://qiita.com/Nabetani/items/cbf55992627452a9be67 )が2分半から3分ちょっとなので、go の方がちょと遅い感じ。

とはいえ。
C++ の方は vector<array<char,32>> なので、速くて当たり前か。

しかし。 string を [32]byte に変えた実装

実装2

package e22

import (
    "sort"
    "strconv"
    "strings"
)

func toBytes(n, b int) [32]byte {
    var s [32]byte
    var m [32]byte
    i := 0
    for 0 < n {
        m[i] = byte((n % b) + 1)
        n /= b
        i++
    }
    for j := 0; j < i; j++ {
        s[j] = m[i-j-1]
    }
    s[i] = 0
    return s
}

func toNum(c [32]byte, b int) int {
    r := 0
    for pos := 0; 0 != c[pos]; pos++ {
        r *= b
        r += int(c[pos]) - 1
    }
    return r
}

type NumsSlice [][32]byte

func (s NumsSlice) Len() int {
    return len(s)
}

func (s NumsSlice) Less(i, j int) bool {
    sa := s[i]
    sb := s[j]
    for pos := 0; ; pos++ {
        a := sa[pos]
        b := sb[pos]
        if a < b {
            return true
        }
        if b < a {
            return false
        }
    }
}

func (s NumsSlice) Swap(i, j int) {
    tmp := s[i]
    s[i] = s[j]
    s[j] = tmp
}

func impl(m int, n int, b int, x int) int {
    values := NumsSlice(make([][32]byte, 0, n-m+1))
    for i := m; i <= n; i++ {
        values = append(values, toBytes(i, b))
    }
    sort.Sort(values)
    val := toNum(values[x-1], b)
    return int(val)
}

func solve2(src string) string {
    split := strings.Split(src, ",")
    m, _ := strconv.Atoi(split[0])
    n, _ := strconv.Atoi(split[1])
    b, _ := strconv.Atoi(split[2])
    x, _ := strconv.Atoi(split[3])
    return strconv.Itoa(impl(m, n, b, x))
}

の方が遅く、シングルスレッドで 340秒なのであった。ぐぬぬ。
やっぱり C++ の方が速い模様。