オフラインリアルタイムどう書く E31 の実装例( Go, C++ )

問題の名前 : ぐるぐる数
問題 : http://nabetani.sakura.ne.jp/hena/orde31rotnum/
実装リンク集 : https://qiita.com/Nabetani/items/d139d5ef70aa23c2d038

次回のイベントは 4/6
see https://yhpg.doorkeeper.jp/events/88379

で。

ナイーブな実装を Go と C++ で。

# Go

```go:go
package main

import (
	"encoding/json"
	"fmt"
	"io/ioutil"
	"os"
	"strconv"
	"strings"
	"time"
)

func isGuru(b, i int32) bool {
	prev := int32(-1)
	for {
		num := i % b
		if 0 <= prev && prev != num && prev != (num+1)%b {
			return false
		}
		i = (i - num) / b
		if i == 0 {
			return true
		}
		prev = num
	}
}

func impl(b, x, y int32) int32 {
	c := int32(0)
	for i := x; i <= y; i++ {
		if isGuru(b, i) {
			c++
		}
	}
	return c
}

func solveSlow(src string) string {
	vals := strings.Split(src, ",")
	b, e0 := strconv.Atoi(vals[0])
	x, e1 := strconv.ParseInt(vals[1], b, 32)
	y, e2 := strconv.ParseInt(vals[2], b, 32)
	if e0 != nil || e1 != nil || e2 != nil {
		panic(fmt.Sprint(e0, e1, e2))
	}
	count := impl(int32(b), int32(x), int32(y))
	return fmt.Sprint(count)
}

func bytesFromFile(fn string) []byte {
	f, err := os.Open(fn)
	if err != nil {
		panic(err)
	}
	defer f.Close()
	b, err := ioutil.ReadAll(f)
	if err != nil {
		panic(err)
	}
	return b
}

type testDataType struct {
	Number   int    `json:"number"`
	Src      string `json:"src"`
	Expected string `json:"expected"`
}

type dataType struct {
	EventID  string         `json:"event_id"`
	EventURL string         `json:"event_url"`
	TestData []testDataType `json:"test_data"`
}

func runTest(list []testDataType) {
	for _, t := range list {
		start := time.Now()
		actual := solveSlow(t.Src)
		tick := time.Now().Sub(start).Seconds()
		result := func() string {
			if actual == t.Expected {
				return "ok"
			}
			return "***NG***"
		}()
		fmt.Printf("%2d:%s solve(%q)=%q, want %q ( %.3f sec )\n", t.Number, result, t.Src, actual, t.Expected, tick)
	}
}

func main() {
	data := dataType{}
	json.Unmarshal(bytesFromFile(os.Args[1]), &data)
	start := time.Now()
	runTest(data.TestData)
	tick := time.Now().Sub(start).Seconds()
	fmt.Printf("total : %.2f sec\n", tick)
}
```

実行は `go run slow.go data.json` みたいな感じで。

随所で `int32` と書いているのは、`int` よりもたぶん速いから。手元の環境では `int` は 64bit なので、落ちるコードに差が出てくる。

この実装で、手元の環境で 75秒ぐらい。
goルーチンを活用すれば半分ぐらいにはなるはずだけど、何もしていない。

# C++

こちらは、[cielavenir さんの記事]( https://qiita.com/cielavenir/items/c950594d7c4038dc640f )を参考にして、OpenMP を入れてみた。

```c++:c++17
// clang++ -O2 -std=c++17 -Wall -Xpreprocessor -fopenmp -lomp  3.cpp

#include <iomanip>
#include <iostream>
#include <numeric>
#include <regex>
#include <sstream>
#include <string>

int is_guru(int b, int i) {
  auto prev{-1};
  for (;;) {
    auto num = i % b;
    if (0 <= prev && prev != num && prev != (num + 1) % b) {
      return 0;
    }
    i = (i - num) / b;
    if (i == 0) {
      return 1;
    }
    prev = num;
  }
}

std::string solve(std::string const &src) {
  auto regex = std::regex(R"(^([^\,]+)\,([^\,]+)\,([^\,]+))");
  std::smatch m;
  std::regex_match(src, m, regex);
  auto b = std::stoi(m[1]);
  auto x = std::strtol(m[2].str().c_str(), nullptr, b);
  auto y = std::strtol(m[3].str().c_str(), nullptr, b);
  int count = 0;
#pragma omp parallel for reduction(+ : count)
  for (int i = x; i <= y; ++i) {
    count += is_guru(b, i);
  }
  return std::to_string(count);
}

void test(std::string const &src, std::string const &expected) {
  auto actual{solve(src)};
  auto okay{actual == expected};
  std::cout << (okay ? "ok" : "**NG**") << " " << src << " " << actual << " "
            << expected << std::endl;
}

int main() {
  /*0*/ test("4,1313,3012", "12");
  /*1*/ test("10,100,110", "0");
  /*2*/ test("36,zoo,zyz", "0");
  /*3*/ test("4,1300000,2222221", "0");
  // 中略
  /*68*/ test("2,101001011010110000110101,110101110001110110110101", "3240321");
}
```

Go の実装とロジックは同じ。
というか、Go の実装を移植しただけ。
入力のパースで正規表現を使ってみた。`std::split` とかあると嬉しいんだけどなぁ。
「中略」のところを略さないで実行して、手元のマシンで、10秒弱。OpenMP 様々。