追記:殺せましたこんにちは。ISUCON7本戦に「百万円ドリブン」の一員として参加しました。三人で,二人はサークルのメンバーです。集中のあまり美味しいお昼のクッキーと珈琲は逃してしまいました。悔しかったのでBigint周りで試行錯誤をした結果について述べます。具体的には、Bigintと__float128について述べます。率先してやってくれました。Bigintを一旦文字列に変換してから先頭から15文字をとるという実装になっていました。遅いのも容易に理解できます。これは改善しなければなりませんね。改善案Go言語ではBigintはuint(符号なし64bit整数)の配列として表現されています。その配列の上位2つのuintからその数字を近似して計算する方法です。111112222233333444445555559037072617328607232と近似します。計算すれば分かることですが、桁が増えても上位2つのみを用いればよいことに変わりはありません。上位2つを用いて近似することにより、桁数オーダーだった部分を改善することが出来ます。BigIntを一つも使わなくてもよくなり、大幅な改善が見込めますね。計算し、最後に10の指数で戻せばよいです。.........なーんてことは無かった...。そもそもfloat64は15.9桁までしか整数との1対1対応を保証してくれません。今回必要な桁は15桁、かなりギリギリです。log10したり演算をすると、微妙に2桁程度合わないのです...。ISUCON中ずっと「あと2桁!!あと2桁なんや...!!」って叫んでいました。本質的に精度が微妙に足りないのです。このあと僕は迷走してしまい、ISUCONは敗北を期しました。こたえ15桁全てを合わすことは到底不可能でも、それが何桁かどうかは精度の問題なしにすぐに計算できます。よって、桁数を計算しもとのBigIntからその10の桁数分で除算するという方法がとれます。本質的にはBigIntをStringに変換する処理がBigInt除算の処理に変わります。bigintを実装から全て消し去り心の平穏を取り戻したいものです。精度の高いものを使えばbigintを使わなくても実装できるはずです。float64までしかありません。擬似的に4倍精度を達成する枠組みです。用いれば上手くできそうです。そのインターフェースとコンパイルフラグ等をgo言語でシュッと記述すると簡単に二つを繋ぐことができます。以下にCとGoのコードを載せます。uint64(o_res)}はい。bigintを殺せました。ベンチを回しましょう...。...まとめBigIntを殺そうとしたが結局BigIntを完全に殺すことはできなかった。初期実装の段階では上記の改善のみでよさそうです。この後、更に高速化してもう一度この部分がネックになってきた場合には、除算を上位の3つのuintのみで行えばよいですね。この実装であれば実質BigIntを殺したといっても過言ではないのでかなり満足です。月別アーカイブはてなブログをはじめよう!CHY72さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。