オフラインリアルタイムどう書く 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++ の方が速い模様。