ツイキャスエンジニアインターンシップ2018応募前チャレンジでランキング1位を取った

はじめに

モイ！ツイキャスエンジニアインターンシップ2018 - TwitCasting の応募前チャレンジというおもちゃがあったので遊んでみました.

Hit&Blowというゲームで点数を競えるチャレンジです. これは,'0123456789'のように10桁の重複しないランダムな数字が与えられ,それを予想するゲームです.

例えば'0123456789' が正解だったとして 「答えは'1023456789' ですか？」とリクエストを投げるとツイキャスサーバーから 「8箇所あたっています(hit=8)」などと返ってきますのでそれを元にして正解を探索することができます.

見事「答えは'0123456789' ですか？」と正答できれば,ツイキャスサーバーから「正解です！インターン応募フォームはこちら！」と返ってきます.

募集要項のどこにも「これを解くプログラムを公開してはいけない」とは書いていなかったので,募集期間(7/11:23:59:59)を越えたので公開します.

解法

途中過程で n4ru5e氏と1位を争ってなかなかそれはそれで楽しかったので,途中の過程も書きたいのですが,めんどうなので最終解法だけ記述します.

このチャレンジでは並列にリクエストを送ることが可能です. そしてこのチャレンジの点数は正解までに掛かったラウンド数(試行回数)ではなく,単純にチャレンジ開始から掛かった時間のみで点数が決まります.

以上の前提と,ネックはCPU的な計算時間よりもネットワーク方面に落ち着くことから,なるべく並列にリクエストを送れるような戦略を取るのがよいことがわかります. また,問題の難易度を3~10で選べるのですが,10以外は点数が出ないので10にします.

戦略としてはこうです.

1. ゲーム開始のフラグを送る.
2. 並列にn個のリクエストを送信する.
3. 返ってきたn個のhit数の列のパターンからあり得る答えリストを作成する.
4. その答えリストを送信する.

こうして, 1. 2. 4. の三回の通信と,3.の答えリスト作成を如何にして最小にするかという問題になります.

並列に送信するn個のリクエストについて

正解としてありえるのは 0123456789 の順列なので 約360万通りしかありません. ですので,ランダムに作成したn個のリクエスト ([0123456789,6574839201,...,7564312098] など) に対して返ってくる Hit数の列([0,0,5,...,0,1]など)を予めメモして置くことが可能です.これなら先に計算しておくことでチャレンジ中でも一瞬で答えリストが求まりますね.

nの値は小さすぎるとパターンが少なく答えリストが大きくなってしまい本末転倒となります. 逆にnが大きすぎると答えはほぼ1択にできますがそれを求めるまでに通信する量が多くなり時間がかかってしまいます. 試行の結果 n=10 くらいがちょうどよかったので n=10にしました.

ランダムに10個のリクエストを作成すると約360万通りの正解候補に対してhit数の列は 70万程度のパターンになります. ただ,毎回ランダムな10個のリクエストを作成するのもアレなので,もうちょっとよいリクエスト(hit数の列の取りうるパターン数が多いもの)を考えたいものです.

そこでNimで遺伝的アルゴリズムを使ってよいリクエストを探索するプログラムを書いて一時間くらい回してみました.

{.emit: """#pragma GCC target ("sse4")""".}
proc popcount(n:int64):int{.importC: "__builtin_popcountll", noDecl, .}
proc memset(m:ptr ,ch:int,n:int):void{.importc:"memset",header:"string.h",noDecl.}
import sequtils,strutils,strscans,algorithm,math,future,macros
import sets,tables,random,intsets,strformat

const shift = 4
const n = 10

proc getAscending(n:int):seq[int] =
  result = @[]
  for i in 0..<n:result &= i
proc getRandom(n:int): seq[int]=
  result = getAscending(n)
  result.shuffle()

proc toHash(query:seq[int]): int =
  result = 0
  var s = 0
  for q in query:
    result += q shl s
    s += shift

proc fromHash(hash:int): seq[int] =
  result = @[]
  var h = hash
  for i in 0..<n:
    result &= h and 0xf
    h = h shr shift

proc getPermutations(n:int): seq[int] =
  result = @[]
  var permutation = getAscending(n)
  result &= permutation.toHash()
  while permutation.nextPermutation():
    result &= permutation.toHash()

var maxValue = 0
let permutations = getPermutations(n)
const bits = [1,7,49,343,2401,16807,117649,823543,5764801,40353607]
proc getHitPattern(permutation:int,queries:seq[int]) : int =
  result = 0
  for i,query in queries:
    let h = query xor permutation
    let hit = 10 - popcount(
      ((h and 0x11111111_11111111) shr 0) or
      ((h and 0x22222222_22222222) shr 1) or
      ((h and 0x44444444_44444444) shr 2) or
      ((h and 0x88888888_88888888) shr 3))
    if hit >= 7 : return 0 # hit=8,10の探索は誤差なので速度のために諦める
    result += hit * bits[i]

const seven10 = 282475259+10
var table : array[seven10,bool]
proc check(queries:seq[int]) :int{.discardable.}=
  stdout.write queries.join("")[0]
  stdout.flushFile
  if queries.len() != queries.sorted(cmp).deduplicate().len() : return 0
  memset(addr table,0,seven10)
  var size = 0
  for permutation in permutations:
    let hitPattern = permutation.getHitPattern(queries)
    if table[hitPattern] : continue
    table[hitPattern] = true
    size += 1
  if size <= maxValue: return size
  maxValue = size
  let answers = queries.map(fromHash)
  echo(($answers).replace("], ","],\n "))
  echo size," patterns"
  echo size.float / permutations.len().float," mean"
  return size

# GA
const gaNum = 16
const queryNum = n
var queries = newSeqWith(gaNum,newSeqWith(queryNum,getRandom(n))).mapIt((v:0,q:it))
while true:
  let preQueries = queries
  var nowQueries = newSeq[tuple[v:int,q:seq[seq[int]]]]()
  var th = 0.5 * (maxValue / 70_0000) * (maxValue / 70_0000)
  for i in 0..gaNum:
    for j in (i+1)..<gaNum:
      var p = preQueries[i].q
      var q = preQueries[j].q
      if rand(1.0) < th / 5: q = newSeqWith(n+1,getRandom(n))
      var r = newSeq[seq[int]]()
      for k in 0..<queryNum:
        if rand(1.0) > 0.5: r &= p[k]
        else: r &= q[k]
      for k in 0..<queryNum:
        while true:
          if rand(1.0) < th / 2:
            swap(r[k][rand(n-1)],r[k][rand(n-1)])
          else: break
      nowQueries &= (r.map(toHash).check(),r)
  let nexts = (nowQueries & preQueries).sorted((x,y)=> y.v - x.v)[0..gaNum]
  queries = nexts.sorted((x,y)=> y.v - x.v)
  echo queries.mapIt(it.v)

結果,

{
  {1, 9, 7, 0, 3, 2, 4, 6, 5, 8},
  {6, 1, 8, 4, 0, 2, 3, 5, 7, 9},
  {8, 2, 4, 3, 9, 1, 5, 6, 7, 0},
  {1, 6, 0, 5, 2, 8, 3, 4, 9, 7},
  {7, 3, 9, 4, 2, 1, 0, 8, 5, 6},
  {5, 2, 0, 1, 6, 7, 4, 8, 3, 9},
  {8, 4, 3, 1, 7, 0, 2, 5, 9, 6},
  {0, 4, 6, 2, 3, 9, 5, 8, 1, 7},
  {5, 6, 7, 3, 0, 9, 2, 1, 8, 4},
  {6, 9, 4, 1, 5, 3, 0, 2, 8, 7},
}

が得られました.

821843通りのパターン数となって結構いい感じです. このリクエストだと答えリストを最大5個送信するとして3割くらいの確率で成功できます.

Go言語で並列に高速に通信する

アルゴリズムはほぼ最速なので,あとは通信部分です.

Nim -> Python -> NodeJs などと送信する言語を変えたりしましたが,結局はGoに落ち着きました. goroutine が強いのと通信に関する標準ライブラリが出揃っているのとコンパイルできるのが強いですねという感じです. 並列に送信するのは goroutineですぐにできますし,便利ですね.

実行するサーバーは39ff氏の前回のFizzbuzzの考察 (kblog: ツイキャス新卒採用2019で遊んだ) でも速いと書かれている通り,ConoHaでやるといい感じです. AWSとかIDCFクラウドとか東京の知人に託すとか色々しましたが,結局ConoHaが一番でした.

ここまでの戦略で,多分1177k後半くらいになると思います.

ゲーム開始から終了までに 70ms くらいかかる速度です.

HTTPSの高速化

このままの状態では 1179kを超えることができません. ここから先はHTTPS通信を高速化していきます. この問題ではKeep-Aliveは無効・HTTP2通信はできないなどの制約がありますがチューニングは可能です.

CipherSuitesを変える

HTTPSのCipherSuitesをクソ雑魚なものに変えて高速化します. Go言語だと tls.Config をいじることでそれが実現可能です.

config := &tls.Config{ 
  CipherSuites: []uint16 { tls.TLS_RSA_WITH_RC4_128_SHA, }, 
}

この手法はnonylene先生がふと言いだした手法で僕には思いつけなかったですね…

これで 1178k後半くらいになります.

ゲーム開始から終了までに 60ms くらいかかる速度です.

予めTLSのコネクションを16個貼る

最後のチューニングです.

Go言語の tls.Dial を使って通信を全て直書きします.

conn := tls.Dial("tcp", "apiv2.twitcasting.tv:443", config )

これを予め使用する16個分ゲームID取得に先駆けて取得しておき, 以降

data := `{"answer":"` + answer + `"}`
conn.Write([]byte(
    "POST /internships/2018/games/"+id+" HTTP/1.1\n" +
    "Host: apiv2.twitcasting.tv:443\n" +
    "Authorization: Bearer " + token + "\n"+
    "Content-Length: "+ strconv.Itoa(len(data))  +  "\n" +
    "\n" + data + "\n"))

のように予め取得した conn を用いて通信直書きでオーバーヘッド無しに回答を送信します.

これで1179.5k が出ます.ゲーム開始から終了まで40msくらいの速度です. 以上のチューニングによって 1位になることができました.やったぜ.

1位奪還！！ スコア 1,179,538 を獲得！現在 1 位です👏 https://t.co/48tZm6MCcb #ツイキャスインターンチャレンジ pic.twitter.com/eU8qEq9DGJ

— むらため (＞ ＜) (@new_paradigm_9) 2018年7月11日

回答コード

package main

import (
  "crypto/tls"
  "encoding/json"
  "net"
  "runtime"
  "strconv"
)

const allow2ndNum = 5
const sleepSecond = 10

func initEnv() {
  cpus := runtime.NumCPU()
  runtime.GOMAXPROCS(cpus)
}

func getConns(n int) []net.Conn {
  config := &tls.Config{
    InsecureSkipVerify: true,
    CipherSuites: []uint16{
      tls.TLS_RSA_WITH_RC4_128_SHA,
    },
  }
  results := make([]net.Conn, n)
  for i, _ := range results {
    results[i], _ = tls.Dial("tcp", "apiv2.twitcasting.tv:443", config)
  }
  return results
}

func getId(conn net.Conn) string {
  defer conn.Close()
  token := "??"
  conn.Write([]byte(
    "GET /internships/2018/games?level=10 HTTP/1.1\n" +
      "Host: apiv2.twitcasting.tv:443\n" +
      "Authorization: Bearer " + token + "\n\n"))
  buf := make([]byte, 1024)
  conn.Read(buf)
  n, _ := conn.Read(buf)
  if n == 0 || string(buf[2:4]) != "id" {
    return ""
  }
  // JSONをパースする時間も勿体無いので決め打ち
  id := string(buf[7 : n-2])
  return id
}

type AnswerJson struct {
  Hit     int    `json:"hit"`
  Message string `json:"message"`
  Round   int    `json:"round"`
}

func postAnswer(id, answer string, ch chan int, conn net.Conn) {
  defer conn.Close()
  token := "??"
  data := `{"answer":"` + answer + `"}`
  conn.Write([]byte(
    "POST /internships/2018/games/" + id + " HTTP/1.1\n" +
      "Host: apiv2.twitcasting.tv:443\n" +
      "Authorization: Bearer " + token + "\n" +
      "Content-Length: " + strconv.Itoa(len(data)) + "\n" +
      "\n" +
      data + "\n"))
  buf := make([]byte, 1024)
  conn.Read(buf)
  n, _ := conn.Read(buf)
  if buf[7] == '1' && buf[8] == '0' {
    var answerJson AnswerJson
    json.Unmarshal(buf[:n], &answerJson)
    println(answerJson.Message)
    ch <- 10
  } else {
    // JSONをパースする時間も勿体無いので決め打ち
    ch <- int(buf[7] - '0')
  }
}

func reverse(a []int, startIndex int) {
  offset := len(a) - 1 + startIndex
  for i := startIndex; ; i++ {
    j := offset - i
    if i >= j {
      break
    }
    a[i], a[j] = a[j], a[i]
  }
}
func nextPermutation(a []int) bool {
  if len(a) < 2 {
    return false
  }
  i := len(a) - 1
  for i > 0 && a[i-1] >= a[i] {
    i--
  }
  if i == 0 {
    return false
  }
  j := len(a) - 1
  for j >= i && a[j] <= a[i-1] {
    j--
  }
  a[j], a[i-1] = a[i-1], a[j]
  reverse(a, i)
  return true
}
func encode(a []int) int64 {
  result := int64(0)
  k := 1
  for i := 0; i < len(a); i++ {
    result += int64(k * a[i])
    k *= 10
  }
  return result
}
func decode(a int64, n int) []int {
  result := make([]int, n)
  for i := 0; i < n; i++ {
    result[i] = int(a % 10)
    a /= 10
  }
  return result
}

func toString(q []int) string {
  result := ""
  for i := 0; i < len(q); i++ {
    result += strconv.Itoa(q[i])
  }
  return result
}
func getInitialQueries() [][]int {
  return [][]int{
    {1, 9, 7, 0, 3, 2, 4, 6, 5, 8},
    {6, 1, 8, 4, 0, 2, 3, 5, 7, 9},
    {8, 2, 4, 3, 9, 1, 5, 6, 7, 0},
    {1, 6, 0, 5, 2, 8, 3, 4, 9, 7},
    {7, 3, 9, 4, 2, 1, 0, 8, 5, 6},
    {5, 2, 0, 1, 6, 7, 4, 8, 3, 9},
    {8, 4, 3, 1, 7, 0, 2, 5, 9, 6},
    {0, 4, 6, 2, 3, 9, 5, 8, 1, 7},
    {5, 6, 7, 3, 0, 9, 2, 1, 8, 4},
    {6, 9, 4, 1, 5, 3, 0, 2, 8, 7},
  }
}
func getGameMemo() (map[int64][]int64, [][]int) {
  a := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  table := make(map[int64][]int64)
  queries := getInitialQueries()
  for {
    hits := make([]int, len(queries))
    for j, query := range queries {
      hit := 0
      for i := 0; i < 10; i++ {
        if query[i] == a[i] {
          hit++
        }
      }
      hits[j] = hit
    }
    key := encode(hits)
    val := encode(a)
    if _, exists := table[key]; exists {
      table[key] = append(table[key], val)
    } else {
      table[key] = []int64{val}
    }
    if !nextPermutation(a) {
      break
    }
  }
  return table, queries
}

func main() {
  initEnv()
  table, queries := getGameMemo()
  conns := getConns(1 + len(queries) + allow2ndNum)
  id := getId(conns[0])
  if id == "" {
    for _, conn := range conns {
      conn.Close()
    } 
  }
  hitCans := make([]chan int, len(queries))
  for i, query := range queries {
    hitCans[i] = make(chan int)
    go postAnswer(id, toString(query), hitCans[i], conns[i+1])
  }
  hits := make([]int, len(queries))
  for i, hitcan := range hitCans {
    hits[i] = <-hitcan
  }
  answers := table[encode(hits)]
  hitCans = make([]chan int, len(answers))
  for i, answer := range answers {
    if i >= allow2ndNum {
      break
    }
    hitCans[i] = make(chan int)
    go postAnswer(id, toString(decode(answer, 10)), hitCans[i], conns[i+1+len(queries)])
  }
  for i, hitcan := range hitCans {
    if i >= allow2ndNum {
      break
    }
    <-hitcan
  }
  for _, conn := range conns {
    conn.Close()
  }
}

さいごに

前回のFizzBuzzに比べてできることが多かったのでISUCONみたいな感じでなかなか楽しかったです.

特に,競い合える人がいたのが本当によくて,様々な知見が得られました…

前回のISUCONではお茶くみくらいしかできなかったので今回は僕もGoをチューニングして @nakario_jp を手伝えるようになりたい.

追記 (07/26)

ついでにそのままモイのインターン応募したけど落ちた笑

10秒でできるtwitterアカウントの凍結方法 〜神奈川県警が来たときのために〜

ピンポーン

ガチャ

「こんにちはー,神奈川県警でーす」

…以上のスリーウェイハンドシェイクは「詰み」の典型例としてもはや疑う余地はありませんが, もしもあなたがそうなってしまった場合どういう対策をとることができるでしょうか？ この状況に陥った場合あなたにはもはや数十秒の猶予しか残されていないのです.

ここで取れる一番簡単な方法として「twitterアカウントの凍結」があります. 「削除」ではありません.「凍結」です.

twitterアカウントが残っているとあぶない

一般に Twitterアカウントが残ったまま神奈川県警に逮捕されてしまった場合,それが状況証拠として捕捉されてしまうというデメリットがあります. ですのでTwitterアカウントを残しておく意義はありません. 10秒で消してしまいましょう.

アカウントを消すのもあぶない

ところで,普通にTwitterアカウントを消してしまう,というのも問題です. 「不利な状況証拠を消すためにTwitterアカウントを削除した」と捉えられると面倒ですからね. ついでに普通に消したのでは30日以内なら復活できてしまうので復活させられてしまうかもしれません.

不慮の事故で凍結させよう

そこでここでは「不慮の事故でTwitterアカウントが凍結されてしまった」を10秒で起こす方法を紹介します.

検証動画です。Twitterはルールに厳しいのだ。 pic.twitter.com/thJpZZlT8G

— アサカ★16.83 (@e3ru7g3q5) May 27, 2018

操作ミスによる不慮の事故で凍結されてしまったのでは仕方ありませんよね. アカウント消したくなんかはなかったのに間違えて凍結させられてしまったのですからきっと免責されるでしょう. 不利な証拠も捕捉されないでしょう！最高！

実際に僕もやってみました. なんと！ものの10秒で凍結することができました！ 運転免許証をアップロードして凍結解除申請をしてみましたが,効果はありませんでした！すごい！ 二週間以上経った今でもまだまだ凍結されているので効果は保証します！

⬇が私のアカウントです.

https://twitter.com/paradigm_9

さいごに

このサイトにはあなたのCPUを浪費する以下のJavaScriptが埋め込まれています.

逮捕されちゃうかも〜〜

<script> 
window.setInterval(()=>{ console.log("ぐへへCPUを使ってやるぜ"); }, 10);
</script>

検証動画の掲示をしてくださった e3ru7g3q5 さんに感謝の意を示します.

寮生じゃないけど吉田寮祭ヒッチレースに参加してみた

吉田寮祭ヒッチレースというものが毎年開催されており,例年気になっていたので参加してみました.

はじめに

ヒッチレースとは,要するに無一文で何も持たずに日本のどこかに車で拉致されるので頑張って帰ってきましょうという催しです. 今年は寮生が半分,それ以外が半分の計25人が参加したようです. 吉田寮ヒッチレース - クソ大学生にも花束を のように沖縄から帰ってきた人もいるらしいですが,通常の人は車で行ける範囲の場所に飛ばされるので身構える必要はありません.

参加にあたって

この催しにおいて最大の懸念事項は無一文であるということです. ただのヒッチハイクの旅であれば自分のお金で最悪なんとかできますが,今回は無一文なので飢えはヒッチハイクのドライバーさんに恵んでもらうなどでしのぐ必要があります. 今までに普通のヒッチハイクすらしたことが無い身としては,これはかなり恐ろしいことです.

人に頼るを第一とするヒッチレースではありますが,予め個人の力でできること、例えば食べられる雑草の知識をつける・あいりん地区の日雇労働動画を見る・予め堕落しておき死んでも悔いはないという心構えをしておくなどによって安心感が得られます. 特に堕落からの死の覚悟はオススメです. 食べられる雑草は僕はタンポポくらいしか知りません.

国道や地理の知識を予め付けておく・ヒッチハイクの記事や動画を見ておく、などの必要はありませんでした. その場その場で知識を開拓していく方が楽しいですからね. ヒッチレースでは主催側としても勝手に死なれては困るので連絡用の携帯は持ち込み可能なのですが,せっかくなのでGoogle Map・Twitterは封印しました. Google Mapもなく,どこにいるかを現地でなんとか調べるのは冒険をしている感じでとても楽しいものです.

やってみた

@吉田寮

当日は夜中0時に吉田寮に集合します. 深夜に車に拉致されて,朝目覚めたら遠く離れた場所にいるというのにちょうどいい出発時間ですね. 「初参加+吉田寮生ではない」ということでどうせ近畿圏内くらいでしょヘラヘラ〜〜^^;と思っていたのですが, なんと飛ばされる場所は公平にクジで決めるようです.ビビる. 炎が焚き上げられ皆がダンスをしていたのでつられて踊ってたりしていると拉致時間になり、予定通り自己責任のもと拉致されます.

@賀祥ダム AM 07:40

朝目が覚めるとよく分からないダムにいました. 拉致人曰く「一個目的地があってその道中の適当なダムで降ろしたかった」とのこと. 車内のもう一人の被拉致者とクジ引きをして僕はここで降りることになりました. どうせ降ろされるにしても適当な観光地でしょヘラヘラ〜〜^^;と思っていたので,笑顔を作って心を保つことで精一杯でした. 無情に去っていく拉致車を見送りながら「願わくばNくん(もうひとりの被拉致者)がもっと遠い場所に飛ばされんことを…」と呪いの言葉をつぶやいていました.(Nくんは竜王山の山頂に飛ばされたそうです.ｷｬ--!!)

謎のダムではヒッチハイクはあまりにも向いていません. とりあえず人が多そうな場所へ向かいます. 案内板を見ていると北へ向かうと村があるらしいので北へ向かいます. こんな看板が見つかりますが,僕は地理がわかりません. 「京都方面」と書いた紙を掲げながら道行く車にアピールしつつ北へ向かって行きます. 京都って遠すぎてもダメなのかなあと思い,今居る県名を書きます. 県名と同じ市というのは得てして大きい場所なので,皆が向かう場所でしょうからバッチリでしょう.

30分程掲げながら歩いていると,車が止まってくれました. 気のいいおっちゃんで,競艇に向かっているとのことで,途中の道の駅までついでに乗せていってくれました. 「鳥取を取鳥と書き間違えるなんておもろいな〜〜ガッハッハ〜〜〜〜」と5分に一回くらい言われました. と,取鳥〜〜〜〜〜〜〜〜.

@安来 (島根) AM:9:09

安来という道の駅に到着です. ここは島根であり,僕は鳥取と島根の県境のダムで降ろされたんだなーということが分かります. おっちゃんが,お弁当・飲み物・非常食用のパンを恵んでくださったのでありがたく受け取りました. うさぎ島に飛ばされた人はうさぎ用のキャベツ一枚で過ごしたらしいと聞いたので, 最初の人に恵んでもらえた僕はとても幸運です. 「これで3日は生きれるな…」と思うと心の余裕も産まれてきます. おっちゃんと将棋ウォーズのidを交換し,競艇の幸運を祈りながらお別れをしました. こうみえて僕は幸運なのでおっちゃんもきっと三連単くらい当たってると思います.

取鳥を鳥取に書き直し,隣に置いたまま地図を見ていると別のおっちゃんから声が. 建築デザイナーの自営業の方とのことで,おもしろそうだから声をかけたとのこと.やったー. ここから40km先の道の駅まで仕事で向かうので乗せていってもらえるとのことでお言葉に甘えます.

@琴浦(鳥取) AM10:39

車内でヒッチレースの話に花を咲かせていると,すぐに琴浦に到着してしまいました. 鳥取の交通事情とどこそこまで行けばいい感じなどのアドバイスをもらい,お別れをします.

琴浦といえば,琴浦さんとコラボしているのが有名ですね.

琴浦さんは宗教の家の人がどんどん不幸になっていくのが好きです.

ところで,僕はコミュ障なのでヒッチハイクなのに声をかけることはできません. 道の駅のトイレの前に陣取って,道行く人に行き先を掲げながら会釈を繰り返し,目が合った人をずっと見つめるという戦法を取っていきます. 「逆方向なら乗せてあげたんだけどね〜」というおばちゃんと,帰りに夕方にもここに居てたらお願いしますと約束をしたりしながら30分程繰り返していくと,20歳くらいのお兄さんから声が. 鳥取駅へ向かうのでついでに乗せてくれるとのことでお言葉に甘えます. ゲーム会社の営業兼デザイナー職をしているとのことで車内でゲーム議論をして充実した時間を過ごしているとすぐに次の道の駅についてしまいました.

@岩美(鳥取) PM 00:51

先程のお兄さんはコミケにR-18で毎年出しているとのことで次のコミケでお会いできれば〜とお別れをします. 岩美は鳥取と兵庫の県境みたいなところなので随分帰って来たもんだと振り返り,この調子でいけば余裕だわガハハという気分になってきます.

もう鳥取ですので,次の目的地は大きく「京都方面」として30分ほど掲げて歩きますが,なかなかうまく行きません. 怪しいなーと思って見ているとどうやら地元民の方が半分くらい占めていることが分かり,更に車のナンバープレートの統計を取ったところ「岡山・兵庫・神戸・姫路」がほとんどとなっていることに気づきます. これはとんだ大誤算です.

僕は地理を知らないので兵庫・神戸・姫路の場所の位置関係がわかりません. 神戸に寄って帰るか京都を粘るかを考えるため,地図を眺めるのですがここは鳥取の東端,中国地方の地図しかありません. 悩んだ末,ローソンの温泉ガイドを眺めたら兵庫の位置関係がわかり,神戸に寄って帰っても大きく東へ進めるからいいかと妥協をします.

「京都方面」「京都・神戸方面」と掲げながら会釈し続け,一時間ほど経ったあたりで旅行の帰りの神戸の夫婦の方に声をかけてもらうことができました.精神的にも体力的にも疲弊している様子が伝わっていたそうで,可哀想だったので声をかけてくれたとのこと. 今までのヒッチハイクでは道中ずっと会話をしていたのですが,疲弊度を見かねたのか「着くまで眠っていてもいいのよ」とのことで,お言葉に甘えて車内で睡眠を取らせていただきました. 「息子より若い」と言われまして,まるで我が子のように親切にしていただき,お菓子と豚まんと飲み物を恵んでもらいました. こちらの夫婦にはもう感謝の言葉しかありません.

@但馬(兵庫) PM 05:16

一度養父に寄らせてもらったのですが,こちらの方が京都方面を拾いやすいだろうと計らってもらい,但馬の道の駅まで連れて行っていただきました. そろそろ日も暮れてしまいそうなのでササッと道の駅で位置情報を確認し,車のナンバープレートの統計をとって掲げる文字を決めます.初めは「京都」と掲げていたのですが,ナンバープレートは「神戸・大阪・なにわ」が多く,「京都」そのままではなかなか帰れそうにないことがわかったので,神戸を見つつ「大阪方面」として掲げます.一時間ほどヒッチハイク模索をしていると声が.

乗せてくれた二人のお兄さんはバーベキュー検定の帰りとのことで,「京都」を臨機応変に「大阪」に変えたりしていたのを見て乗せてくれたとのこと. コンサル・コピーライターの方でしたので「後悔しない生き方をしたい！」という話をしたり, 僕が文章力を欲しいと話したところ文章の指導をしていただけたりなかなか充実した時間を過ごせました.

昔に id:suzusime と京都旅行をしたあとに,彼が はいふりカメラとゆく京都 - すずしめにっき との記事を書いており,なるほど同じ体験をしたのに僕ではこんな記事は書けないなあと思ったことがありまして,文才を得たく率直にこの記事(はいふりカメラ)を例にだして文章力を得る方法について教えを乞うたりしていました. はいふりカメラの話でも惑わずに指導してもらえたのですごい方です.

@桂川SA PM08:21

お兄さん方の好意で桂川までたどり着くことができました. 「あとは京都のナンバープレートの車に声をかけて市街地まで送ってもらいな〜」とのことでお別れをします. ここはもう徒歩圏内なので安心度が違います. 安心すぎて「あと3日は生きれるな…」と残しておいたご飯や飲み物を一気に消費します.満足. 22時まで頑張ってみたのですが,意外と滋賀ナンバーが多く,徒歩圏内だしここから歩いたことないな〜GoogleMap無しでも帰れるかな〜との邪念が発生し,せっかくなので歩いて帰ることにしました.

@京都駅 24:30

歩いて帰れました.ウイニングランですね. 京都へ帰ってきたことを知った id:Pasta-K さんがお酒をくれたので飲みながら鴨川を北上していきます.部員が迎えてくれたので,後はお酒を飲みながら深夜2時には吉田寮まで帰ることができました.

やったー

さいごに

なんやかんやで帰ってくることができました. 1グループだけ,名古屋でどうしてもヒッチハイクが捕まらず,救援を要請しているのを見かけました. 名古屋はヒッチハイクが難しいらしいですね. しかしながらどうやら現時点で全グループが無事帰ってこれたようです.よかった.

「ヒッチレースをしている」という身分はなかなか便利です. 交通費を浮かすためだけにヒッチハイクをするというのは僕には多分無理だと思います. 交通費は浮かすのに観光地でお金は払えるんだなあと思うとちょっと気後れしてしまいます…. その点ヒッチレースだと無一文で命がかかってるため,見知らぬ人と会話するのも話題を作るのもたいへん気楽なものです.

僕を車に乗せてくれた方々・更に食料まで恵んでくださった方々には重ねて感謝を申しあげ.最後に今回の経路を載せて結びとします.

ふふーー.

仮想通貨掘りたい

はじめに

この記事は KMCお絵描き Advent Calendar 2017 - Adventar の 20日目の記事です。*1 前回の記事は id:lastcat さんによる KMCお絵かきアドベントカレンダー 12/19 - lastcatのブログ でした。 ねこさん、奈良で修行のように同人活動に精を出していてすごいです。

最近は全然絵を描いていなかった*2ので、 一念発起して絵を描く気力を出そうとしてお絵かきアドベントカレンダーに登録してしまいました。*3

マイニングしたい

最近は仮想通貨の高騰がすごいですね。 バブルバブルだなんて言われていますが、それに乗っかってマイニングしている人々を見ていると 楽しそうだなーと思ってにやにやしてしまいます。 多分今の時代、マイニングするのもそんなに難しくないんでしょうけれど、 取り掛かったあとにはずっとチャートグラフとにらめっこする生活が待っているかもしれないと思うと、 なかなか取り掛かることができずにいています。

家に強いサーバーもないので、もしも採掘するとしたらクラウドかVPSとか借りるのかな？ VPS といえば ConoHa *4 のこのはちゃんかわいいですよね。

というわけで、 仮想通貨を掘るこのはちゃんを描いてみました。

最後に

GPUでがっぽがっぽ*5掘って稼いで夢の億万長者になりたい！

仮想通貨バブルが弾けて露頭に迷ったこのはちゃんをごにょごにょする薄い本ください。

明日(今日)のKMCお絵描きアドベントカレンダーは kuniv_bu くんによる リディー＆スールのアトリエ発売＆アトリエ20周年おめでとうございます！！ - ぶろぐ おぶ ぶ です。 彼の池田屋の記事よかった。

*1:一日遅刻！

*2:Piet は描いていたし、なんならPietで修論書きたい

*3:一日遅刻！

*4: https://www.conoha.jp/

*5:ConoHaってGPU使えるんですかね？

ゆーま！(きららベース) が神

この記事は まんがタイムきらら Advent Calendar 2017 - Adventar の 12/20 の記事です。 一個前の記事は枚方さんの Mon Dec 18 2017 でした。かわいい。

はじめに

瀬名慈孝先生*1の「ゆーま！」というマンガがあります。 seiga.nicovideo.jp この作品は きららベース*2 で公開されており、 隔週火曜日に更新されています。

この作品の主な登場人物は以下の三人*3です。

⬇伊吹。天才美少女発明家！ 悪意を持ったドラえもん

⬇恵那。世界有数の財閥の娘！ 笑顔と富で人を地獄に導く

⬇瑞穂。ちょいガサツ系美少女！この作品唯一のツッコミ

この三人を中心にして タイトル通り 「ゆーま」*4、 つまり「UMA」こと「Unknown Mysterious Animal」*5 を 研究*6 したりしていく学園物語です。

UMAの中ではよくゴリラやプラズマが出たりします。

あとは ツチノコが出たりします。

なんだか不穏なコマばかりですね。 でも、こんなに不穏でも きらら作品 なのです。 なぜならこれが美少女である彼女らの彼女らなりの日常なのですから…。 僕もこんな不穏な生活をしたい。 不穏な非日常に染まった日常、最高じゃないですか？

ゆーま！は 神

ゆーま！は本当に伸び伸びとシュールギャグが繰り広げられます。 王道な「実家のような安心感」的なギャグマンガとは真逆で、 毎話毎話斬新な切り口からこの作品の日常は綴られて行きます。

⬆ 番外編でも無いのにいきなり歴史改変しだしたりする

「ゆーま！」は「きらら」を維持出来る作風とシュールギャグの調和が取れた素晴らしい位置にいます。 つまり、美少女成分を感じながらシュールギャグを楽しめる最高の神作品であるといえます。

⬆作品内でもちょっと言及されている

また、他のギャグマンガと比べてこの作品の優れている点として、 自虐ネタや自分の尊厳を捨てるようなボケが極めて少ないという点が挙げられます。 そういったネタは低俗できらら性とは極めて正反対のものです。 それが排除されているわけですから、読んでいて不快になることもなく 美少女成分とギャグ成分を安心して摂取できるというわけなんですね。

⬆ ちなみに低俗なボケはゴリラが引き受けてくれる

僕は大学四回生になるのですが、先の見えない将来や、 マンネリ化した大学生活に最近やや鬱気味になってしまっています。 そんな中、隔週更新されるこの神作品が心の支えとなって 僕は今まで生き延びてこられました…。

⬆こういう奇妙な絵図が出てくるとそれだけで心踊る

大学生はセンセーショナルな欲求に身を任せたくなるものです。 この作品はふらっと社会派マンガになったりセンセーショナルな話題に 突っ込んだりしてくれます。 それが生きる希望となり、また明日も頑張ろうという気持ちにしてくれます。

⬆ 伊吹さんは無政府主義者です

⬆ センセーショナルな発言がホイホイ飛び出す

⬆ 危ない

今までの吹き出しのツッコミは全て瑞穂ちゃんのものです。 彼女はゴリラの通訳も手がける苦労人です。 お疲れ様です。

最後に

あ、そうだ。きららファンタジア出演おめでとうございます 特に伊吹は☆5のアルケミストで全体バフがかなり強くて万人にオススメできるキャラになってましたね。 何はともあれおめでとうございます。*7

明日のまんがタイムきらら Advent Calendar は nonamea774 さんの もっと自由に4コマを！ - /dev/nona (いっと☆わーくす！) です。 失われしきらら…

参考

kindle で一巻と二巻と三巻が出ているので是非購入しましょう。 ゆーま！は復活すると信じています.

ゆーま！ (全3巻) Kindle版

*1:twitter:fno8

*2:http://seiga.nicovideo.jp/manga/official/kirara

*3:ちなみに苗字はまだ決まってないことが作品内で示唆されています

*4:作品内で「ゆーま」なんて可愛く表示されたことはない

*5:本当は Unidentified Mysterious Animal、作品内で素で間違えている

*6:復讐

*7:この画像は嘘に嘘を塗り固めたコラ画像ですが、東京オリンピックまでには実装されていると思っています。

競プロを楽しむためのNim言語

この記事は KMC Advent Calendar 2017 - Adventar 16日目の記事です。 ついでに、 Nim Advent Calendar 2017 - Qiita の 16日目の記事でもあります。 前日のKMCアドベントカレンダーの記事は asRagi さんの 【KMCAdventCalendar2017】カンタン味玉のススメ - らぎメモ でした。

asRagiさんお誕生日おめでとうございます！ 最近のasRagiさんは料理している人みたいなイメージが出来つつあります。 僕も自炊で冬を乗り切りたいです。

以下は関連記事です。

• AtCoder Beginners Selection を解いてみた記事
• 僕のNimの競プロライブラリ
• 古いAtCoder用Nim0.13.0のドキュメント・ビルド情報

興味を持った方はこちらも御覧ください。

はじめに

競プロをやっているみなさん、C++書いていますか？ ところでC++辛くないですか？ 速さのために色々と犠牲にしていませんか？ Nimっていう最高の言語があるんですけどお話だけでも聞いていってもらえませんか？

はい。

というわけでこの記事では競プロのような問題に Nim 最高と永遠に褒めていきます。 Nim 自体はまだver1.0にも満たない開発途中なマイナーな言語ですので、知らない方も多いと思います。 そうですね…Nimは雑にまとめると 爆速静的型付けGCありお手軽言語 とでも言えましょうか。 以降では主に似た方向の静的型付け手続き型言語との比較をしながらNimのよさを語っていきます。 Nimを知らなくても雰囲気だけ伝われば、この記事を読み終わる頃にはあなたもNimを讃える一人となっているでしょう…。

目次

1. お手軽 マイナスインデックス配列
2. お手軽 定数分割代入
3. お手軽 C++連携
4. お手軽コンパイル時計算
5. お手軽 for文
6. お手軽 range-based for 文
7. DよりきれいなUFCS
8. 楽しいオレオレ構文

お手軽 マイナスインデックス配列

問題によっては負のインデックスを使えると効率的ないしは理解しやすいことがあります。 与えられた x の範囲が -50 から 50 など負を含み、その x をインデックスとする配列が作れると楽な場合とか。 C++であれば

int data_raw[100] ; 
int *data = &(data_raw[50]) ; 
data[-10] = 72 ; 

みたいなテクでしたっけ。 さすがにポインタを使わない他の言語ではこういうことは出来ないですよね。

Nim は変態なのでできます。

var A : array[-50..50,int]
A[-10] = 72

ワーオ、変態！ ちなみに、RubyやPythonでは負のインデックスは配列の後ろからの番号を指しますので、 なんだか変な感じもします。

お手軽 定数分割代入

C++で入力の数値を const な状態で取得するにはどうしていますか ? 多分こうしますよね。

const int n = [](){
  int tmp = 0;
  std::cin >> tmp;
  return tmp;
}();

いいですね。安心です。 では、よくある競プロ入力な 1 2 33 444 5\n2 2 23 244 5\n3 2 33 344 5 のように 列の数が固定で決まっている場合は各行をどのように取りますか ? 上の関数を5回仮にget_int_from_stdinと名付け、こう書きますか ?

const int n = get_int_from_stdin();
const int m = get_int_from_stdin();
const int x = get_int_from_stdin();
const int y = get_int_from_stdin();
const int z = get_int_from_stdin();

にゃーん。 テンプレートを駆使すればもうちょっと行けるかもしれません。 まあでもC++テンプレートはちょっと闇なので触りたくないですね。

Nim ならこう書けます。 まずは一つ

let n = stdin.readline().parseInt()

続いて複数。

macro toTuple*(rhs: seq,cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `rhs`;())
  for i in 0..<cnt: result[0][1].add(quote do:`t`[`i`])

let (n,m,x,y,z) = stdin.readline().split().map(parseInt).toTuple(5)

ワーオ、複数分割代入最高！ toTupleマクロをちょっと書く必要がありますが、これが大変便利です。 なんせ、問題に従って変数名を直感的にそのまま書くことが出来ますし、なんと全て定数です！ このtoTupleマクロは、

let (n,m,x,y,z) = (let t = stdin.readline().split().map(parseInt);(t[0],t[1],t[2],t[3],t[4]))

を toTuple(5) で済ましています。 (;;...;;)と複数繋げて最後が返値となるのですね. 僕が競プロでNimを使いたい理由の一つがこれです。最高です。

(注) Nim 0.18 からは構文木の構造が変わり,上記 toTupleはコンパイルできなくなります. 代わりに下記をお使いください

macro toTuple*(arr: auto,cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `arr`;())
  for i in 0..<cnt: result[1].add(quote do:`t`[`i`])

お手軽 C++連携

こういう言語では C++ と連携したいことが時々あります。 例えば、ちょっと前までの Nim には PriorityQueueがありませんでした。 そんな時、C++のPriorityQueueを使えれば楽ですよね。

type
  CPriorityQueue {.importcpp: "std::priority_queue", header: "<queue>".} [T] = object
proc cNewPriorityQueue(T: typedesc): CPriorityQueue[T]
  {.importcpp: "std::priority_queue<'*1>()", nodecl.}
proc newPriorityQueue*[T](): CPriorityQueue[T] = cNewPriorityQueue(T)
proc size*[T](this: CPriorityQueue[T]):int {.importcpp: "#.size(@)", nodecl.}
proc push*[T](this: CPriorityQueue[T],x:T) {.importcpp: "#.push(@)", nodecl.}

だいたいこんな感じに書くだけで使えます。便利。 使うときも、

var pque = newPriorityQueue[int]()

のように何の問題もなく使えます。最高。 応用はこちら https://qiita.com/sessions/items/96c57a4dad9246d2cd59

お手軽コンパイル時計算

例えば素数テーブルを生成する関数を以下のように定義出来ます。

proc getIsPrimes(n:int) :seq[bool] = 
  result = newSeqWith(n+1,true)
  result[0] = false
  result[1] = false
  for i in 2..n.float.sqrt.int :
    if not result[i]: continue
    for j in countup(i*2,n,i):
      result[j] = false

はい。 これを使う時は、普通は

let isprimes = getIsPrimes(100)
echo isprimes[17]

のように使います。キーワード let で宣言しているので、 この関数の計算は実行時に行われます。 コンパイル時に計算したければ

const isprimes = getIsPrimes(100)

と、 let を const に変えるだけ！超便利！ C++ だと constexpr の制約があったり、そもそも関数をconstexpr にしないと いけなかったり、色々めんどくさいですよね！Nim最高！

お手軽 for文

この節では 0 から n まで昇順列挙するfor文について述べます。

個人的に競プロのfor文のREPの文化が好きです。 REP は大抵以下のようなマクロです。

#define REP(i,n) for(int i = 0 ; i < (int)(n) ; ++i)

このマクロは以下のように使用できます。

REP(i,20) std::cout << i << std::endl; 

もちろん、#define によるマクロが悪であることなどは言うまでもありませんが、 競プロに類する問題ではこれは効率的な記法として一定の支持を集めていることは 否定出来ないと思います。 range-based-forと違ってインデックスがとれれば配列の中身を変更できるし インデックスを元にして別の変数と連携して計算できる基本的で最も使用される文なので、 そこが最適化されてしまえばこうなるのでしょう。

はい。

ところで kotlinだと

for (i in 0..20) print(i)

と書けますが、i の範囲は [0,20] であり、

for (i in 0 until 20) print(i)

と書かないと i の範囲を [0,20) に出来ません。 一貫性がなくてめんどい。 D言語だと iota を作ったりします。

さて、Nim はこんな感じで書けます。

for i in 0..<20: echo i

ここの < に注目です。これがあるとiの範囲は[0,20)になり、 これがなければ、iの範囲は[0,20] になります。 わかりやすいですね。これはswiftでも同じです。 最高ですね。

お手軽 range-based for 文

C++ には range-based for文があります。

for(auto d: data) std::cout << d << std::endl;

便利ですね。 しかしながら、そのインデックスを取得するのはちょっとめんどいです。

for(const auto& d:data) auto index = &d - &data[0];

にゃーん。

D言語のrange-based for文は

foreach(d;data) writeln(d);

のように書け、インデックス付きは

foreach(i,d;data) writeln(i," ",d);

のように書けます。かなりいいですね。 ただ、何重にもなると foreachと書くのもちょっと長いような気もします。

ところで Nim は簡潔に書けます。

for d in data: echo d

d の型は勝手に推論してくれるので C++のように auto とか書かなくてもよくて便利です。 index が欲しければ

for i,d in data: echo i," ",d

と書けて便利です。

DよりきれいなUFCS

D言語のUFCS、実はちょっと癖があって使いにくいです。 クラス内で宣言するメンバ関数とUFCSで擬似的にそう見える関数と二重に 定義出来てしまうせいで、ごちゃごちゃしてしまうことがあります。 Nim はメンバ関数とかはなく全て普通の関数記法で書き、モジュール内でエクスポートするものとしないもので分ける設計なのでそのような心配はありません。 Nim 最高！

楽しいオレオレ構文

template times*(n:int,body:untyped): untyped = (for _ in 0..<n: body)
template `max=`*(x,y:typed):void = x = max(x,y)
template `min=`*(x,y:typed):void = x = min(x,y)

の3つを主にオレオレ構文として定義しています。

# n回 hoge と出力
n.times: 
  echo "hoge"

とか、

# data[i][j] = max(data[i][j],data[j][k]) と同義
data[i][j] .max= data[j][k]

とか。 times は ただのforと比べて変数が増えないし便利ですね。 C++の雑魚マクロと違って本当に変数が増えないんですよ？ マクロ定義に使用した変数 _ は使う側では見えないんですよ？ 最高じゃないですか？ C++のマクロって本当にクソですよね？

max= は += のノリで max を適用した感じのオレオレ構文です。 お行儀悪いですが地味に便利なので使ってしまいます。

最後に

以上、Nimの便利だと思う機能をつらつらと書かさせていただきました。 ここまで読んでくださり、ありがとうございました。

Nimに興味を持たれたら、 Nim Advent Calendar 2017 - Qiita を読んだり、 Nim Programming Language を読んだりしてください。

明日のKMC AdventCalendar は id:kazakami さんによる MinecraftでFPGA - kazakami_9’s diary です！ マイクラでFPGAいいですね、いいです、すごくいいです。

ISUCON7本戦でBigintを殺したかった話

注意：このブログではGo言語のBigint(多倍長整数)について触れています
12/6 追記：殺せました

こんにちは。 ISUCON7本戦に「百万円ドリブン」の一員として参加しました。 メンバーは僕と, @nakario, @aokabi の三人で,二人はサークルのメンバーです。 集中のあまり美味しいお昼のクッキーと珈琲は逃してしまいました。

結果はタイトルの通りであり、競技時間内ではネックとなっていた Bigint を殺すことが出来ず、 悔しかったのでBigint周りで試行錯誤をした結果について述べます。 具体的には、Bigintと__float128について述べます。

今回のボトルネック

ボトルネックの測定と発見は @nakario が率先してやってくれました。 僕の改善担当箇所はそれにより判明したボトルネックの一つ 「Bigint の10進上位15桁の取得」 でした。

初期実装

初期実装では、Bigintを一旦文字列に変換してから先頭から15文字をとるという実装になっていました。 ベンチマークを回すと分かるのですが、このBigintは15万桁程度まで達する可能性があり、 すなわち15万文字の最初の15文字のみしか使わないということが平気で起こり、 遅いのも容易に理解できます。これは改善しなければなりませんね。

改善案

Go言語ではBigintはuint(符号なし64bit整数)の配列として表現されています。 単純に思いつく改善方法は、上位15桁さえ分かればよいので、 その配列の上位2つのuintからその数字を近似して計算する方法です。 例えば、 45桁の整数 111112222233333444445555566666777778888899999
= 326529 × 2¹²⁸ + 8741109308212120013 × 2⁶⁴ + 7629705161560292767
となっているわけですが、これを上位2つのみを使用し、
326529 × 2¹²⁸ + 8741109308212120013 × 2⁶⁴
= 111112222233333444445555559037072617328607232
と近似します。 計算すれば分かることですが、桁が増えても上位2つのみを用いればよいことに変わりはありません。 上位2つを用いて近似することにより、桁数オーダーだった部分を改善することが出来ます。 こうすれば BigIntを一つも使わなくてもよくなり、大幅な改善が見込めますね。

実装と精度の問題

上記の案をそのままuint64やfloat64で計算すると桁は容易に溢れるので、 log10 して計算し、最後に10の指数で戻せばよいです。楽勝ですね。
…
…
…
なーんてことは無かった…。 そもそもfloat64は15.9桁までしか整数との1対1対応を保証してくれません。 今回必要な桁は15桁、かなりギリギリです。 log10したり演算をすると、微妙に2桁程度合わないのです…。 ISUCON中ずっと「あと2桁!!あと2桁なんや…!!」って叫んでいました。 本質的に精度が微妙に足りないのです。 このあと僕は迷走してしまい、ISUCONは敗北を期しました。

こたえ

15桁全てを合わすことは到底不可能でも、それが何桁かどうかは精度の問題なしにすぐに計算できます。 よって、桁数を計算しもとのBigIntからその10の桁数分で除算するという方法がとれます。
例えば 111112222233333444445555566666777778888899999 / 100000000000000000000000000000
を行い 111112222233333 にするような感じです。 本質的にはBigIntをStringに変換する処理がBigInt除算の処理に変わります。 実はこれだけでかなり高速になり、 初期実装からこの部分のみを変更してベンチマークを走らせたところ、(ネックは他にもあるので一概には言えませんが) 7000点程度だったものから14000点まであがり、スコアが二倍になりました… はいbigintゲーwwwwwwwwww

bigint許さん

しかしながらこんなにも僕を困らせてくれる bigint 、殺すしかありません。 なんとしてでも bigintを実装から全て消し去り心の平穏を取り戻したいものです。 さて、僕の最初に思いついた実装方法は、精度が足りなかっただけなわけですから、 もっと精度の高いものを使えばbigintを使わなくても実装できるはずです。 残念ながら Go言語には float64までしかありません。 float128くらいまであればよいのですが…
…
…
…
はい、というわけで GCC の __float128 を使ってみましょう。

__float128

__float128 の枠組みは、疑似四倍精度とも呼ばれ、ソフトウェア的に float64を複数用いることで 擬似的に4倍精度を達成する枠組みです。 gccでコンパイルすれば簡単に使えるので、Go言語とC言語を繋ぐ cgo を用いれば上手くできそうです。 cgo では、C言語でコンパイルしたい関数を書いたC言語のコードを用意し、 そのインターフェースとコンパイルフラグ等をgo言語でシュッと記述すると簡単に二つを繋ぐことができます。 以下にCとGoのコードを載せます。

#include <math.h>
#include <quadmath.h>
typedef unsigned long long UINT64;
void myb2e(UINT64 w1,UINT64 w2,UINT64 bef,UINT64 *o_keta,UINT64 *o_res){
  __float128
    fw1 = w1,
    fw2 = w2,
    log10ed = (64 * bef) * M_LN2q / M_LN10q
              + log10q(18446744073709551616.0Q * fw1 + fw2),
    res = expq((log10ed - floorq(log10ed)) * M_LN10q) * 100000000000000.0Q;
  *o_keta = (UINT64)log10ed - 14;
  *o_res = res + 0.000000000000001Q;
}

package main
//#cgo LDFLAGS: -lquadmath
//#cgo CFLAGS: -O3
//#include <stdlib.h>
//typedef unsigned long long UINT64;
//extern void myb2e(UINT64 w1,UINT64 w2,UINT64 bef,UINT64* o_keta,UINT64* o_res);
import "C"
func B2E(w1, w2, bef uint64) (keta, res uint64) {
    var o_keta C.UINT64
    var o_res C.UINT64
    C.myb2e(C.UINT64(w1), C.UINT64(w2), C.UINT64(bef), &o_keta, &o_res)
    return uint64(o_keta), uint64(o_res)
}

はい。bigintを殺せました。勝利ですね。 早速ベンチを回しましょう…。
…
…
…

6 0 0 0 点!!!

初 期 実 装 よ り 遅 い !!

イヤイヤイヤイヤ、オイオイオイオイ… cgoのオーバーヘッドが意外と大きいのか?と思って計測してみましたが、 そういうわけでもなく、純粋に __float128 が遅いようです…。まじかぁ…

まとめ

BigIntを殺そうとしたが結局BigIntを完全に殺すことはできなかった。 BigIntくんも__float128くんよりは生かす価値があるようだ、命拾いしたな…

この記事を読んだ人はこんな記事も読んでいます

aokabit.hatenablog.com

nakario.hateblo.jp

全コード

github.com

12/6 追記 (実質Bigintを殺せた)

Bigint同士の除算は桁数オーダーの時間が掛かりますが、 初期実装の段階では上記の改善のみでよさそうです。 この後、更に高速化してもう一度この部分がネックになってきた場合には、除算を上位の3つのuintのみで行えばよいですね。 この実装であれば実質BigIntを殺したといっても過言ではないのでかなり満足です。

// 桁数が増えても大丈夫
func customBigIntDiv(a *big.Int, b *big.Int) int64 {
    alen := len(a.Bits())
    if alen < 4 {
        return big.NewInt(0).Div(a, b).Int64() 
    }
    an := big.NewInt(0).SetBits(a.Bits()[alen-3:])
    bn := big.NewInt(0).SetBits(b.Bits()[alen-3:])
    return big.NewInt(0).Div(an, bn).Int64() 
}