北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

自転車を買った

電動自転車を10年使っていたのだが、子供が小学生に上がるのに合わせて自転車を買うことにした。

今まで乗っていたのは YAMAHA の PAS 。今の家に引っ越してきたタイミングで、駅までの道が上り坂だったために、高いなあと思いつつ購入したもの。

YAMAHA PAS
YAMAHA PAS

電動自転車はめちゃくちゃ便利で、ほとんどの坂道をまったく汗をかかずに登ることができる。特に子供が生まれてからはこれがベストチョイスで、小学校に上がるまで快適に子供を乗せて走ることができた(小学生に上がると、自転車に乗せられなくなる)。電動でなければ、坂道のある場所へは歩いて行くなど、選択肢が大幅に狭められただろう。

と、電動自転車には大満足なのだが、それでも別の自転車が欲しくなったのには理由がある。それは、自転車を電車に載せて旅をしてみたいという強い思いがあったからである。所謂、輪行だ。自家用車を持っておらず、かつ、田舎産まれなので、電車で郊外へ行くのが元々好きだった。ただ、郊外の駅へ行ってもほとんどの場合は公共交通機関が充実しておらず、歩きでは行ける範囲も限定されている。自転車に乗れればいいのになあ、と思うことが多々あった。

そんなわけで、輪行ができる自転車を探していたのだが、どうせ買い替えるのならいいものが欲しいなあと思ってググって見つけたのが brompton である。

brompton

イギリスで作られた自転車で、愛好者が多いようで YouTube で検索すると大量に魅力的な動画が出てくる。 40 年の歴史があり、ほとんど構造が変わっていないというのも好感が持てる。代官山に専門店 BROMPTON JUNCTION TOKYO があったので、息子を連れて見に行ってそのまま購入した。

購入して予想通りだったこと

brompton の売りは簡単に畳んだり戻したりできることで、 YouTube の動画を見てるとステマじゃないかと思うくらいみんなめちゃくちゃ簡単に折り畳んでいる。いやー、さすがに自分はここまでできないだろうなあと半信半疑で買ったが、それは杞憂だった。本当によく設計された自転車で、気持ち良く畳んだり展開したりできる。これは本当に brompton にして良かったなあと思うポイントである。

後は、買う前から高価なので盗難心配だなあと思っていたのだけど、これもまったくその通りだった。 世界最強レベルの鍵 を買う、常に肌見放さず持ち歩く、などいろんな選択肢があったが、結局 盗難保険 に落ち着いた。保険について、自分は、人類が発明したリスクに対処するための道具であると考えており、盗難というリスクに立ち向かうには一番良い選択肢だと判断した。なので、鍵は それなりのもの を使っており、駐輪場にも躊躇なく停めている。

購入して予想外だったこと

予想通りだったことよりも予想外だったことのほうが多い。

まず、一番予想外だったのが、自転車を買い替えた一番の目的である輪行が、とても大変であることである。と言っても、これは買う前の自分の見積もりが甘過ぎた。普段、自分は 2kg あるゲーミングノート を肌見放さず持ち歩いている。 brompton もその感覚で、使うか使わないかよくわからなくても常に持ち歩こうと思っていたのだが、 2kg と 12kg (恐らくもっと重い) はさすがに違い過ぎた。もう、とにかくどうやって持っても大変なのである。肩紐を付けて担いでいるが、本体が足に当たって痛く進むだけでも大変だし、改札なんて通ろうものなら狭くてガツンガツンと色んなところがぶつかってしまう。持ち歩きは買った直後に諦めた(輪行をしたことがある人にとっては当たり前の事実だろう)。

そして、もう一つ予想外だったのが、 brompton に乗ること自体がめちゃくちゃ楽しいということである。今まで電動自転車に乗っていたので、輪行はできるけど乗り心地は妥協だなあと勝手に思っていたのだが、乗ってみると brompton の方が圧倒的に楽しいのである。電動自転車は乗り始めこそ楽(むしろ不自然に飛び出して気持ち悪いくらい)だが、漕ぎ始めると漕いでるんだか漕いでいないんだかわからず惰性で進んでいる感じを受ける。 brompton はそうではなく、漕ぎ始めはスムーズで、漕いだ分だけ力がダイレクトに自転車に伝わって力強く進むのを感じられる。当然、漕いだ分だけ疲れるのだが、即座にその成果が車速に反映されるので、とても心地良い疲労なのだ。これは、ダイエットに最適なのでは、と思う。実際、サイクリングはダイエットに良いと言われているし、自分もこの一ヶ月で 400km 近く走って体重も 1kg ほど落ちた。 brompton を買った時期がちょうど エルデンリング の発売時期と被っていたのだが、エルデンリングするよりサイクリングに行きたいと思える程度には brompton は乗っていて楽しい。

brompton の前に、年末に scanwatch を購入していたのも、偶然とは言え良かった。 scanwatch は pikmin bloom のために買ってそれはそれで歩数計として活躍していたのだが、 brompton を買ってからは心拍計として大活躍してくれている。 brompton に乗っているせいで、むしろ歩かなくなって歩数計としての役割は(そして pikmin bloom も)オワコンとなってしまった。毎日 10km 以上走っているが、歩数は 2,000 歩以下で Google fit から怒られる日々が続いている。

ロードバイクが欲しくなるのか

こうして毎日エクササイズ目的で自転車で走るようになると、実はロードバイクのほうがいいのではないかという疑問が湧いてくる。しかし、今のところその欲求はない。

まず第一に、あくまでも運動をしたいだけで、速く走ることには興味がないということが挙げられる。川沿いのサイクリングロードを走っているのでそもそもそんなにスピードを出せない(出すべきではない)し、公道も首都圏は車が多く、スピードを出してもそんなに楽しいとは思えない。楽しく運動できればよく、 brompton で目的を完全に達成している。

第二に、やはり輪行に強い思いがあるということが挙げられる。さすがに日常的に持ち歩くことは諦めたが、それでも週末は輪行を楽しんでいる。重くて大変ではあるが、普段は自転車に乗れない別の駅から自転車で移動できるのは楽しく、行動範囲が広がって便利でもある。折り畳み自転車で輪行してまったりと自分の行きたいところに行く(つまり、ポタリング)方が自分にはあっている。

サイクリングとジョギングの違い

大昔、ダイエットのために ジョギングもしていた 経験もあるので、サイクリングとの比較を書いておこう。結論としては、自分にはサイクリングの方が圧倒的にあっていると感じられる。理由は以下の通りだ。

まず、サイクリングの方がスピードが早く爽快感があり、飽きにくい。ジョギングをしていたころは、心拍数を有酸素運動の範囲に合わせてしまうとあウォーキングの人にも抜かれてしまうほど遅くなってしまい、走っている意味があるか疑問になるし、とても惨めな気持ちにもなった。

また、サイクリングの場合は遠出しても帰って来れる安心感があり、スピードが速いことも相まって気軽に距離を伸ばすことができる。平地の場合、自転車はスピードにさえ乗ってしまえば漕がなくても距離を稼ぐことができる。つまり、疲労困憊で休んでいても、進むことができる。ジョギングはそうも行かなくて、疲れて座り込んでしまうとまったく進まない。歩いたほうが楽ではあるが、それでも完全に休めているわけではない。遠出して体力が尽きたときの帰路の不安は、ジョギングの方が大きいと言える(もっとも、公共交通機関の近くを走っていればどうにでもなるし、タクシーという手もあるが)。

そして最期に、サイクリングの方が圧倒的に足への負担が少ないと言える。特に、ダイエットが必要な太っている人にはそれが顕著である。昔、ジョギングをしていたときには、久しぶりに走ると必ずひどい筋肉痛に悩まされた。しかし、自転車ではちょっと足が疲れてだるいなということはあるが、筋肉痛で歩くのに支障が出ることはない。

今後の展望

輪行はしたいものの、当初思っていたよりは重く、正直、どうしようかなあと思っているところではある。何度か電車に載せて慣れては来たので、一度泊りがけの輪行をしてはみたいなあと思っている。

そして、せっかく郊外の駅から自転車で遠出するなら、チェアリングもしてみたいなあと思い始めている。ただ、 brompton ✕チェアリングや brompton ✕コーヒーは完全に(特に中高年の)お約束らしく、天邪鬼な自分としてはそういう万人が通る道を歩んでしまうのはどうかなあとも思うのである。

まあ、まずは日々のサイクリングが体力づくりとしてとても効率的に作用しているので、これを続けていくことを考えるのが最優先だろう。

小数第四位までの小数を10000倍して整数に直せるのか

数値が小数第四位まで与えられるとする。例えば、 1234.5678 のような形式である。

それらの数値を使って計算をしたいのだが、何も考えないと計算機上ではこれらの数値は double 型などで保持され、誤差が発生することは有名だろう。

>>> 1001.0000 * 1.1000 == 1101.1000
False
>>> 1001.0000 * 1.1000
1101.1000000000001

誤差が発生するのは嫌なので、入力を 10000 倍して整数として扱いたくなる。例えば、 1234.567812345678 に変換したい。

しかし、この操作にも注意が必要である。 https://qiita.com/mod_poppo/items/910b5fb9303baf864bf7 で解説されている通り、 10000 倍したり、 int を取ったりするだけではうまくいかない。

>>> 1.2347 * 10000
12346.999999999998
>>> int(1.2347 * 10000)
12346

ということで、四捨五入することになる。

>>> int(1.2347 * 10000 + .5)
12347

ところで、 この四捨五入する方法は果たして万能なんだろうか 。答えから言うと、残念ながら万能ではなく、桁数が大きくなるとうまくいかなくなる。

>>> int(274877906944.1832 * 10000 + .5)
2748779069441833

int.5 を使ったナイーブな実装だからではという人もいるかもしれないが、 round を使っても別の値でうまく行かない。

>>> round(274877906944.1832 * 10000)  # うまくいった!
2748779069441832
>>> int(274877906944.1835 * 10000 + .5)  # うまくいった!
2748779069441835
>>> round(274877906944.1835 * 10000)  # 駄目じゃん・・・
2748779069441834

この差は浮動小数点を「丸める」という仕様がそもそも人によって変わるということに起因している1。以下の 8 年ほど前のエントリに詳しい。

http://blog.practical-scheme.net/shiro/20131229-flonum-rounding

こんな感じのスクリプトで調べると、整数部が 274877906943 では発生しないようだ。

for i in range(1, 10000):
    x = f"274877906943.{i:04d}"
    ans = 274877906943 * 10000 + i
    if int(float(x) * 10000 + .5) != ans:
        print(f"int NG: {x}")
    if round(float(x) * 10000) != ans:
        print(f"round NG: {x}")

この現象について、もう少し数学的に考えてみよう。 double のフォーマットは色々なところに書かれていると思うが、今回は以下を参考にした。

https://www.k-cube.co.jp/wakaba/server/floating_point.html

誤差の伝搬による限界

URL に書かれている内容によると、 double仮数部は 52bit あり、最高位の隠しビットを含めると 53bit で表現されていると言える。 52bit のうち整数部に n bit を使うとすると、小数に使えるのは 52 - n bit であり、一番細かい桁は 2^ {- 52 + n} ということになる。真の値から一番近い表現に丸められるとすると、誤差は最小位の桁の半分となるため  2 ^{-53 + n} となる。

10000 倍をしたときに、この誤差が \frac{10^ {-4}}{2} 未満であれば round したときに意図する値に丸められると言える。つまり 2 ^{-53 + n} \lt \frac{10^ {-4}}{2} が条件であり、解くと n \lt 52 - 4 \frac{\log 10}{\log 2} \lt 38.7... となる。

つまり、整数 bit が 39 以上だと問題が発生することがわかる。しかし、先の数 274877906944 は 2^ {39} = 549755813888 よりも小さく、これだけではうまく説明がつかない。

掛け算後の桁あふれによる限界

先程の計算では整数部が n bit であるとして計算したが、 10000 倍した後には整数部の bit 数は増えるはずで、これにより小数 bit が少なくなり、値を丸めるために誤差が発生すると考えられる。簡単のため 2\log _ 2 10000 桁ズレるものとしよう。これにより、小数 bit の最小桁は 52 - n - \log _ 2 10000 となり、この桁に丸めるために \frac{2^ {- 52 + n + \log _ 2 10000}}{2} = \frac{10000 \cdot 2^ {-52 + n}}{2} の誤差が新たに加わる。

先の誤差と合計すると、  10000 \cdot 2 ^{-53 + n} + \frac{10000 \cdot 2^ {-52 + n}}{2} = 10000 \cdot 2^ {-52 + n} であり、ここから先程と同様に不等式を作って解くと n \lt 51 - 4 \frac{\log 10}{\log 2} \lt 37.7... となり、整数 bit が 38 以上だと問題が起こることがわかる。このときの値は 2^ {38} = 274877906944 で、 10000 倍して round してもうまくいかない例で紹介した値と一致している。

うまく整数にできない例

実際に何が起こっているか、もう少し見てみよう。 Haskell では 274877906944.000710000 倍してうまく整数化することができない。

Prelude Data.Ratio> round $ 274877906944.0007 * 10000
2748779069440006

Rational有理数で正確にリテラルの値を表現できるので、これとの差をとってみると、この時点で真の値との誤差が 0.000029 程度あることがわかる。リテラルを見るだけでは想像がつかない、割と大きな値なのではないだろうか。

Prelude Data.Ratio> x = 274877906944.0007 :: Rational
Prelude Data.Ratio> y = 274877906944.0007 :: Double
Prelude Data.Ratio> d = toRational y - x :: Rational
Prelude Data.Ratio> fromRational d
-2.861328125e-5

ただ、ここまでであれば 10000 倍して小数点を四捨五入すれば元の数に戻るはずである。 10000 倍後の誤差は、悲しいことにちょうど 0.5 となる。

Prelude Data.Ratio> x = 2748779069440007 :: Rational
Prelude Data.Ratio> y = 274877906944.0007 * 10000 :: Double
Prelude Data.Ratio> d = toRational y - x :: Rational
Prelude Data.Ratio> fromRational d
-0.5
Prelude Data.Ratio> d
(-1) % 2

もう少し状況を見てみよう。 Double で表された元の値を見ると、このような有理数になっている。

Prelude Data.Ratio> y = 274877906944.0007 :: Double
Prelude Data.Ratio> toRational y
4503599627370507 % 16384

手元に HaskellDecimal パッケージがなかったので横着して Python で試してみると、この値は 10 進数で以下の通り。先程確認したとおり、真の値より 0.000029 少ない値だ。

>>> Decimal(4503599627370507) / Decimal(16384)
Decimal('274877906944.00067138671875')

これを 10000 倍するのは人間であれば簡単で、 2748779069440006.7138671875 である。ここまでで発生しているのが「誤差の伝播による限界」で計算したものであり、 10000 倍されて真の値と比べると 0.29 の誤差が発生することにある。

さて、このまま四捨五入できればよかったのだが、 この値は 2^ {51}2^ {52} の間にある。

Prelude Data.Ratio> (2^51, 2^52)
(2251799813685248,4503599627370496)

よって、整数のために仮数の bit が 51 必要であり、小数に当てられた bit は 1 bit しかない。そのため、この値を 2748779069440006.52748779069440007.0 に丸めなければならない。近い方を選択すると前者になり、 round の偶数丸めの仕様から 2748779069440006 と違う値に変換されてしまう。ここで生じた誤差は「掛け算後の桁あふれによる限界」で述べたもので、誤差がマイナス方向に 2 度蓄積することで希望する値に丸められていないことがわかった。

うまく整数にできる例

逆に整数部が 274877906943 のときは何が起きているのだろうか。 274877906943.9944 を整数にするときの処理を詳しく見てみよう。

まず、 Double にした段階での誤差を見ると 0.000015 であり、先程より僅かに小さい。

Prelude Data.Ratio> x = 274877906943.9944 :: Rational
Prelude Data.Ratio> y = 274877906943.9944 :: Double
Prelude Data.Ratio> x - toRational y
39 % 2560000
>>> Decimal(39) / Decimal(2560000)
Decimal('0.000015234375')

現在整数 bit は 37 bit であり、誤差は、

Prelude Data.Ratio> 2 ** (-15.0) / 2.0
1.52587890625e-5

未満であるから、現在の整数の bit 数では最大に近い誤差である(わざとそういう数を選んだ)。

さて、この Double の値の正確な数字を見ておこう。

Prelude Data.Ratio> toRational y
1125899906842601 % 4096
>>> Decimal(1125899906842601) / Decimal(4096)
Decimal('274877906943.994384765625')

10000 倍すると、 2748779069439943.84765625 である。整数部 2748779069439943 は先程と同様に 51bit を要する数であり、小数に充てられる bit 数は 1 bit のみである。これを round することになるが、先程と違うのは元の誤差が 0.0000153 未満であることがわかっているので 10000 倍しても 0.153 であり、 0.25 よりも小さいので正確に元の数字の方に丸められるということである。 実際、今回は 2748779069439943.5 か 2748779069439944.0 に丸めなければならないが、 2748779069439944.0 へ正確に丸められることになる。


  1. shiroさんのエントリを紹介したかったので書いてしまったけど、そもそも四捨五入と偶数丸めで仕様が根本的に違うものを比べているので当たり前ではあった。

  2. 本来は動かす桁数が小数になることはないので、値の大きさによって場合分けして整数桁ずらすべき。

Disco Elysium をクリアした

store.steampowered.com

海外でめちゃくちゃ評判のいい Disco Elysium をクリアした。春に日本語訳される予定だが、英語でゲームをプレイする練習のためにそれを待たずしてクリアした。手元の単語帳によると、クリアまでに調べた単語数は 2,400 語。テキストを読むだけのゲームなので、手を止めてゆっくり単語を調べながら進められる。

このゲームは殺人事件の謎を解く探偵モノなのだが、スキル値とサイコロの目に基づくスキルチェックが随所にあり、膨大なテキストを読みながらストーリーの分岐を楽しむゲームである。スキルチェックに失敗してもストーリーが進行不能になるわけではないが、やはり成功したほうが気分は良いし話も進展するので、基本的にはスキルチェックが通るようにゲームを進めることになる。

ちなみに、個人的には探偵モノとしてのこのゲームのストーリーはそんなに好きではない。自分は理系なので、緻密なトリックやアリバイを考えながら進めて、予想が当たったときのアハ体験を一番の楽しみに探偵モノを楽しむのだが、このゲームのストーリーはその類のものではない。科学的なトリックや論理的な思考のプロセスを楽しむものではなく、話が意外な方向に展開するのを楽しむものである。犯人やその後の展開を推理して「ああ、やっぱり!」みたいなことはほぼ一切なく、「え、そういう展開?それで、この話はどこに向うの?」とプレイヤーに衝撃を与えながらゲームは進んでいく。もちろん、ネタバレは避けるが、きちんと殺人事件を解決することはでき、夢オチであったり殺人事件をなかったことにして別のストーリーが始まったりすることもないので、そこは安心して遊んでもらえると思う。後、このゲームのストーリーは、よくある「ゲームをクリアしたらみんな幸せになりました」というようなものでもない。そこはこのゲームの気に入っているところだ。ゲームをクリアしたからと言って主人公がとてつもなく幸福になるかというとそんなことはなく、今までの日々に戻るだけだ。ある意味、余韻というか、消化不良というか、そういうものが残るストーリーになっているが、自分はこの手の話はとても好みである。実は主人公と自分は同い年で、その点も含めてある種の悲哀が余韻として残る終わり方は好きだ。

このゲームの最大の魅力はやはりテキストにあって、英語力の低い自分にでもニヤニヤできるシーンはたくさんあった。特に、相棒のキムとのやり取りは面白く、かっこよく、言うことがないくらい最高である。そのテキストを肉付けするのが、芸術的なグラフィックや、音源、スキルシステムであると言える。グラフィックの雰囲気は本当によく、タバコを吸うだけでなぜか自分まで満足感が得られるほどだ(自分は極度の嫌煙家だが)。そして、サイコロをふるのは単純に楽しい。スキルシステム、思考キャビネットのシステムも、戦闘シーンがあるわけでもないテキストだけのゲームになぜか驚くほどマッチしており、このゲームの最大の発明と言える。

最後に、日本語版を含めこれからプレイする人にコツを。最初にも書いたが、スキルチェックは失敗しても話が変わるだけなので、成功することに拘らないほうが楽しく遊べる(というか、成功と失敗の両方を楽しむゲームだ)。それでもスキルチェックを通す必要はあるわけで、そのためのコツとして、白いチェックは確率が低くても挑戦して、とにかく回数を稼いだほうが効率が良い。と言うのも、白いチェックはレベルアップとストーリーの進展によって再チャレンジ可能になるが、例えば成功率 3% のチャレンジが後から 50% になるとして、 3% は低いからと 50% になるのを待ってからチャレンジすると成功率は 50% なのだが、 3% のときにチャレンジしてさらに 50% のときにもチャレンジすると成功率は 51.5% と僅かだけ高くなるのだ。失敗には体力や気力の低下というペナルティがつくこともあるが、想像しているよりは遥かにペナルティーは小さい。たくさん挑戦して失敗したほうがストレスなく遊べるし、結果として成功率も上がるだろう。そういう理由で、レベルアップもすぐにスキルを振るのではなく、失敗した白チェックで通したいものが明確になったときに使うのが効率がいいだろう。もちろん、思考キャビネットは白チェック関係なくどんどん開けていって問題ないので、そちらに優先してスキルポイントを使うのも良い戦術と言える。後、歩いているときに頭に出る丸の色はスキルの色と一致していて、値が一定以上になることによって出現する。特に認知スキルは高いほうがアイテムの発見が増えたり捜査の進展にも繋がりやすく、便利だろう。スキルを上げた後にレバショールをウロウロすると、新しい発見があるかもしれない。

日本語版は発売元が変わり、発売日も未定なようだ。見ていないシーンも大量にあるので、2周目もやりたいところだが、他の積みゲーがたくさん待っているので、2周目はやらずに攻略サイトやプレイ動画で済ませると思う。次の英語練習は Inscryption をやりたい。

store.steampowered.com

実は zelda (BoW) や pokemon arceus を英語でやっていたりもするし、 divinity original sin や Pathfinder をもう一度プレイ(実はどれもクリアしてない)したい思いもあるが、積みゲーの消化をとりあえず優先すべきだろう。

docker historyがmissingになる

ふと、 docker build をして docker history を実行したら、中間イメージが <missing> と表示されていて、あれ?となった。

$ docker history 790538589d39
IMAGE          CREATED         CREATED BY                                      SIZE      COMMENT
790538589d39   2 minutes ago   CMD ["python" "-c" "print(\"OKay\")"]           0B        buildkit.dockerfile.v0
<missing>      2 minutes ago   RUN pip install -e . # buildkit                 9.41MB    buildkit.dockerfile.v0
<missing>      2 minutes ago   COPY . /python # buildkit                       751kB     buildkit.dockerfile.v0
<missing>      2 minutes ago   WORKDIR /python                                 0B        buildkit.dockerfile.v0
<missing>      2 weeks ago     /bin/sh -c #(nop)  CMD ["python3"]              0B
..snip..

全く意識していなかったのだが、そもそも docker image が中間イメージを親に持つという構成は、 1.10 のバージョンですでに終わっていたようだ。

www.windsock.io

Since Docker v1.10, generally, images and layers are no longer synonymous.

ただ、これは 2016 年の話でちょっと古過ぎるし、よく読むと、

Locally Built Images However, when a layer is committed during an image build on a local Docker host, an 'intermediate' image is created at the same time.

と書いてあって、ローカルでビルドするときちんと中間イメージができると書いてある。

そもそも buildkit.dockerfile.v0 が気になるのだが、これが以下に書いてある。

docs.docker.com

ビルド方法が今までと変わるようで、実際、 DOCKER_BUILDKIT=0 で実行してみると、きちんと(?)中間イメージができた。

$ docker history 47c06ac6f6e0
IMAGE          CREATED          CREATED BY                                      SIZE      COMMENT
47c06ac6f6e0   27 seconds ago   /bin/sh -c #(nop)  CMD ["python" "-c" "print…   0B
d548a2aa34a6   27 seconds ago   pip install -e .                                9.41MB
e6e7465a2860   31 seconds ago   /bin/sh -c #(nop) COPY dir:8a8c73a0932d1c9e7…   751kB
f1e6d23f61f3   31 seconds ago   /bin/sh -c #(nop) WORKDIR /python               0B
a5d7930b60cc   2 weeks ago      /bin/sh -c #(nop)  CMD ["python3"]              0B
<missing>      2 weeks ago      /bin/sh -c set -ex;   wget -O get-pip.py "$P…   8.31MB
..snip..

この機能は 2018 年からある機能なので、なぜ突然有効になったのかは疑問が残るところである(まだ調べてないが風呂の時間なので、わかったら追記する)。

謹賀新年

明けましておめでとうございます。本年もよろしくお願い致します。

去年の同タイトルのエントリを見ると、 2021 年って果たして何をやったのだっけという気分になる。近況だけ記しておくと、最近は英語に興味が向いていて、 スピークバディclimbELSA を4ヶ月間毎日欠かさず継続している。効果があるのかは定かではないが、自分が興味があることを続けるのに効果だけを過度に期待するのは "さもしい" ことだろう。

climb は辞書、兼、単語帳として使っていて、今は以前途中までやって立ち消えしていた Disco Elysium をクリアすべく、ひたすら単語を調べながら進めている。単語帳に追加された単語数は 2,200 語ほど。調べた単語を毎日の climb の QUIZ で復習していて、 1 日 1 語程度のペースで語彙は増えている気がする。受験生と比べるとあまりにも少な過ぎる数だが、着実に増えてはいる。

後、 YouTube よりも Twitch を見ることが増えた。と言っても見ているのはゲーム実況ではなく、日本の町中をただ歩くだけのライブストリーミングだ。この手のストリーミングは reddit live で初めて見たのだけど、 Twitch でも最近(元々なの?)多くの人が日本の町中でストリーミングをしている。 Twitch には他にもライブコーディングをしている人もいて、こちらも一時期見ていた。

時間があるときには、文法書を読んだりしている。今のお気に入りは 一億人の英文法 。それと、 ENGLISH FOR EVERYONE シリーズも数冊家にあるので、こちらも読みたいのだが残念ながら時間がない。

去年のエントリの目標がほとんど達成されていないことを考えると、ここで 2022 年の目標を書くことはひどくおこがましいことのようにも感じるが、それでもあえて目標を書いておくと、今年は discord 通話をもっと使って、英語を話す機会を増やしたい。毎日通話するような習慣をつけられるのがベストだと思っている。( 2022 年中ではなく)将来的には、 洋ゲー を英語で通話しながら苦労なくプレイできるレベルになれればいいな。

条件チェックの順の最適化

複数の条件をすべて満たすときだけ、処理を継続したいということはよくあると思う。例えば以下のようなコード。

fn some_function(x: &Hoge) {
    if !check0(x) {
        return;
    }
    if !check1(x) {
        return;
    }
    if !check2(x) {
        return;
    }
    if !check3(x) {
        return;
    }
    
    // x に対する処理
}

このとき、 check0 から check3 をどのような順番でチェックするのが一番効率がいいだろう? 直感的には、一番通りにくいチェックを最初にやっておいたほうが、残りの処理をスキップできて効率がいいように思える。しかし、それぞれのチェックにある程度時間がかかってしまうときにはどうだろうか?

例えば、処理するデータのうち各チェックが NG となる割合と、チェックに要する時間が以下の表のとおりだったとする。例えばチェック3は、6割のデータがブロックされて以降の処理をスキップできるが、チェックするのに 5 msec もかかってしまう。どの順番に並べるのがいいだろうか?

NGの割合 所要時間(msec)
check0 0.2 1
check1 0.3 2
check2 0.4 4
check3 0.6 5

答えから言うと、所要時間÷NGの割合の昇順で並べると一番効率が良い。この例だと、 check0 check1 check3 check2 の順番にチェックするのが最適となる。

理由を簡単に説明する。 check_i について、 NG の割合を  p_i 、所要時間(cost) を  c_i とする。まず、チェックが  check_0 check_n まで並んでいるときに、ある  i について  \frac{c_i}{p_i} \gt \frac{c_{i + 1}}{p_{i+1}} が成立するとする。このとき、  check_i check_{i + 1} を入れ替えると、コストの期待値が下がることを示すことができる。

実際、 i + 2 以降のチェックにかかるコストの期待値を  D とすると、 check_i 以降の処理でかかるコストの期待値は  c_i + (1 - p_i)(c_{i+1} + (1 - p_{i + 1})D) となる。 check_i check_{i + 1} を並び替えた場合のコストを引き算をして整理すると、  p_{i + 1}p_i(\frac{c_i}{p_i} - \frac{c_{i + 1}}{p_{i + 1}}) という式が得られ、最初の仮定からこの式は正の値を取る。よって、並び替える前のほうがコストが高いことが言え、すなわち目標としていた事実が示された。

後は任意のチェックの列があった場合に、連続する 2 つの「チェックの所要時間÷NGの割合」の値が昇順になっていない部分を入れ替え続けることでどんどんコストを下げることができ、最終的には列全体がこの値の昇順となったときにコストは最小になる、ということである。

今回の check0check3 について、実際にシミュレーションするコードを github に上げておいた。

https://github.com/hiratara/rs-error-check-optimization-simulation/blob/026792790836c04829040fa9a7a346ff74eec10d/src/main.rs

このシミュレーションを実行すると、以下の出力が得られ、実際に並び替えることで性能が向上していることがわかる(元々最適解に近い並び方なので、ほんとにちょっとだけ)。ちなみに、逆の順で並べてしまうのが最悪ケースで、かなりパフォーマンスが悪化することもわかる。

$ ./target/release/rs-error-check-optimization-simulation
68.68248 sec
optimized order: [0, 1, 3, 2]
66.66192 sec (optimized)
worst order: [2, 3, 1, 0]
78.78843 sec (worst)

ちなみに、今回は関数の呼び出し時間の文脈で考えたが、製品の各検査における不具合率とかかる金額(コスト)の文脈でも同じ考え方になるだろう。

TypeScriptの分配条件型

最近オライリーのTypeScript本を読んでいるが、型システムが頭がおかしくて(褒めてる)とても面白い。

www.oreilly.co.jp

TypeScriptでは、こんな感じの型レベル関数が定義できる。以下の Extract2T のうち、 U であるものを展開するというものである。同様の働きをする Extract が組み込みで定義されているので、ここでは 2 と名前を付けた。

type Extract2<T, U> = T extends U ? T : never;

Extract2 を使うと、例えばオブジェクト型のキーの型で、文字列であるものだけを型として取り出せる。

type O = { "name": string, "age": number, 0: number };
type A1 = Extract2<keyof O, string >;
// type A1 = "name" | "age"

Extract2extends を使って定義されており、定義を読む限りは、 1 つ目の型が 2 つ目の型のサブタイプになっていれば 1 つ目の型を返すし、そうでなければ never を返すということになっている。以下の結果はこの考察と一致する。

type A2 = Extract2<string, "a">;
// type A2 = never
type A3 = Extract2<"a", string>;
// type A3 = "a"

しかし、 boolean で同じような操作をすると、 string の場合とは違い直感に反する結果になる。 booleantrue のサブタイプではないので、単純にサブタイプであることだけ確認しているのであれば、 string の場合と同様に A4 の結果は never となるべきである。

type A4 = Extract2<boolean, true>;
// type A4 = true
type A5 = Extract2<true, boolean>;
// type A5 = true

これはタイトルにもある通り、分配条件型という仕様によって実現されている。 Extract2<boolean, true>boolean の定義に立ち返ると Extract2<true | false, true> であり、 Extract2 の定義を展開すると (true | false) extends true ? (true | false) : never となる。しかし、 TypeScript では | を分配規則により展開し、実際は (true extends true ? true : never) | (false extends true ? false : never) として扱う。よって、 true | never と解釈され、それはつまり true である。

冒頭のオブジェクトのキーの型を extract する例が期待通りに動作するのも、この仕様による。仮に string"a" | "b" | ... | "aa" | "ab" | ... のような型であると解釈されて実装されていると、先ほどの A2 の型も "a" となるのだろうが、 TypeScript ではそうなっていない( string 型はリテラル型の有限個の合併では表現できないので、まあ妥当だろう)。実際、 A2string の代わりに合併型を使って試してみると、 never ではなくリテラル"a" が得られる。

type A6 = Extract2<"a" | "b" | "c" | "d", "a">;
// type A6 = "a"