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