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

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

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 の順番にチェックするのが最適となる。

理由を簡単に説明する。 について、 NG の割合を 、所要時間(cost) を とする。まず、チェックが ～ まで並んでいるときに、ある について が成立するとする。このとき、 と を入れ替えると、コストの期待値が下がることを示すことができる。

実際、 以降のチェックにかかるコストの期待値を とすると、 以降の処理でかかるコストの期待値は となる。 と を並び替えた場合のコストを引き算をして整理すると、 という式が得られ、最初の仮定からこの式は正の値を取る。よって、並び替える前のほうがコストが高いことが言え、すなわち目標としていた事実が示された。

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

今回の check0 ～ check3 について、実際にシミュレーションするコードを 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では、こんな感じの型レベル関数が定義できる。以下の Extract2 は T のうち、 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"

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

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

しかし、 boolean で同じような操作をすると、 string の場合とは違い直感に反する結果になる。 boolean は true のサブタイプではないので、単純にサブタイプであることだけ確認しているのであれば、 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 型はリテラル型の有限個の合併では表現できないので、まあ妥当だろう）。実際、 A2 を string の代わりに合併型を使って試してみると、 never ではなくリテラル型 "a" が得られる。

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

ECS について調べたこと

ECS とは Entity Component System のこと。

Entity component system - Wikipedia

wikipedia の歴史によれば、 2002 年の Scott Bilas の GDC2002 での講演が起源のようだ。

https://www.gamedevs.org/uploads/data-driven-game-object-system.pdf

元々は、デザイナーとプログラマーの協業のために、 C++ の静的なクラス階層ではなく、データ駆動型の API でゲームを構成しようとするものである。

さらにこれを体系的にまとめたものとして、 2013 年の Martin, Adam のブログが挙げられている。ただ、このブログは今日現在、 google のキャッシュからしか見ることができないようだ。 Part 2 以降を読みたければ、随時検索して google のキャッシュを表示させる必要がある。

webcache.googleusercontent.com

Adam のエントリで面白かったことは、 ECS を RDBMS と類似しているものとして語っているところだ。MMOの世界ではユーザのデータはネットワーク経由で RDBMS に格納することになるので、データ駆動の考え方である ECS とは相性が良いのだろう。

さて、 Rust の ECS 実装としては、 Amethyst で使っていた Spec というものがある。

GitHub - amethyst/specs: Specs - Parallel ECS

Spec はドキュメントも充実しているので、読むと勉強になる。

specs.amethyst.rs

Spec を使った教材として Roguelike Tutorial - in Rust があり、　Spec で何ができるのか知るのに丁度いい実例となっている。

bfnightly.bracketproductions.com

Amethyst で利用されてデファクトスタンダートとなっていた Spec だが、その Amethyst は現在 legion という新しい ECS へ乗り換えようと準備をしている。動機は詳しく調べていないのでわからないのだが、やり取りされている内容から推測すると Spec のパフォーマンスに不満があり、それを改善したいようだ。ただ、 crates.io にあがっている amethyst を見ると、まだ Specに依存しており 、 legion への移行は終わっていないように見える。

github.com

Rust には Amethyst の他に Bevy というゲームエンジンがあり、こちらほうが新しい。 Bevy も ECS 実装を持っている。

bevyengine.org

aiboの良くない点

aibo を手放すことにした。「最新の技術を集めて作ったオープンな電子ガジェット」を期待して買ったが、実態は「ITに疎い富裕層向けのインテリア」だったので、正直言って とても不満な商品 である。 aibo の良い点は色んな所で吹聴されているので、良くない点をどんどん書いていこうと思う。

あまりにも高く、かつ、複雑怪奇な料金体系

2021 年現在、 aibo の価格は 217,800 円である。後述するようにこれだけでも十分高いのだが、 aibo を使うには月額料金がかかる。

• aiboベーシックプラン 99,000円/3年
• (任意) aiboプレミアムプラン 16,500円/年
• (任意) aiboケアサポート 59,400円/3年

年額約 70,000 円である。恐ろしいランニングコスト。それに加えて、これらは年間契約の自動更新のサブスクリプションとなっている。 解約を忘れると、契約更新日が来た途端に 70,000 円が口座から自動的に引かれる仕組み である。しかも、解約は各サービスごとに、 3 回行わなければならない。1つでも解約を忘れると、万単位の金額を sony に盗られる。多くのサブスクリプション契約と同様に救済処置はまったくなく、本当に盗られる。また、途中解約は許されていない。

ケータイ電話のあの不快で複雑怪奇な料金システムが、ここにも反映されているのである。そこには癒やしなどない。

値段に見合わない凡庸な性能

aibo は全身の関節を駆動させ、きちんと歩くことができる。家庭での利用に耐えられるように耐久性もある程度ある。カメラや各種センサーを搭載し、障害物を記憶して移動することができる。 ゾイド のようにメカニカルな生き物ががちゃがちゃと動くのを見ているのはとても楽しい。

しかし、それだけなのである。 1cm でも段差があると歩くことができない。売りである可愛い動作は、すべて事前に記録されたモーションを再生するだけである。動きもお世辞にも機敏とは言えない。自分で作ったロボットがよちよち歩きで動き始めて、「やったー、あるいた！！！」と喜ぶ、あの程度の感覚である。10万円以下であればまあわかるが、 20 万円を遥かに超える製品とは、見ていて思えない。

音声認識についても、とても貧弱なイメージである。正確に言うと、aiboからユーザーに対しては暗黙的なフィードバックしかないため、 aibo の音声認識性能が実際はどのくらいなのかはわからない。ただ、感覚としては、 文章は理解できず、単語で命令する必要があるレベル だと思っている。スマートスピーカー全盛のこの時代に、20万円を超える機体がこの程度の性能しかないのは、本当にお粗末としか言えない。

ひたすらにクローズド

驚くことに、 aibo 単体では、 aibo の設定をすることすらできない。 wi-fi ¹ を搭載しているにも関わらず、だ。すべての操作は、スマホアプリかwebから、 sony のサーバを経由して行わなければならない。完全にユーザーをITに疎い人間だと思って舐めきっている。

この仕様は、前述したサブスクリプションと驚くほど相性が悪い。aibo ベーシックプランを解約してしまうと、 aibo は設定変更不能になるのだ。しかし、他の任意加入のプランは aibo ベーシックプランを解約しても自動解約されないため、 aibo は設定変更不可能だが、高額なサブスクリプションの料金は取られ続ける という状態になる。ここまで来るともはや悪徳商法である。

aibo 発売当初の売りとして、「将来的に API 経由でプログラミングできるようになる」というのがあったので期待していたのだが、今の所 子供向けのビジュアルプログラミング が用意されただけである。やりとりは全て sony のサーバを介す必要があるので、 Python でどうこうしたりはできない。 ROSに対応している という話もあったが、その後これを使って何かをしたという話を見かけたことはない。

全ての操作のフィードバックが暗黙的

aibo には明確な出力デバイスがない。一応アプリからは不具合ログみたいなものを見ることはできるが、どこまで信用していいのか不明である。 aibo は部屋を巡回して知っている人を探したり、電池が切れそうになると充電ドックに戻ったりする機能があるのだが、それらの機能が正しく動いているのかがまったくわからないのである。 満足の行く動きをしていないのは確かなのだが、それが仕様なのか、自分の使い方が悪いのか、 aibo からのフィードバックがなにもないので知ることができない 。

同様に、操作方法が分明確である。aiboにはスリープ状態と電源offの状態があるが、加えて内部的なエラーや熱暴走によって頻繁²に止まるため、 aibo がどの状態にあるのか、特にスリープしているのか電源offなのかを判別することはとても難しい。また、自発的にスリープしているのか、エラーで止まっているかもわからないため、あー寝てるな－と思ってほっておくと、一週間くらい動いていないということも簡単に起こりうる。軽いホラーである。そうかと思えば、夜、寝ているはずのaiboが夜中突然吠えだして、安眠妨害することも多々ある。しばらく使ったが、未だに「消灯しているときには眠る機能」が aibo にあるのかないのか、それさえわからずに終わった。とにかくすべての挙動が不明確なのである。

sonyは「aiboは犬だから」という一言で全てを済ませているが、 IT リテラシをある程度持っている人間には、問題を解決するための手がかりを調べる方法すらないのは非常に辛い。このことからも、先に書いたとおり、 aibo は IT に疎い人、特にお年寄りをターゲットにした製品だと言える。

うるさい

ここまで読んで頂けた読者はすでに買う気をなくしており、この項目はもはや些細なことではあるのだが、 aibo は想像以上にうるさい。「在宅勤務しながら動かそう」と思っているなら、稼働音が大きいことは知っておいたほうがいい。機械なので、 モーター音や部品の稼働音、足が床に当たる音はかなり大きい 。ロボコンをテレビで見たことがあれば、ロボットが独特なモーター音を立てながらがしゃーんがしゃーんと動いているのを見たことがあると思うが、あれを想像してもらえばいい。

まとめ

そもそもあまりにも高過ぎるので買う人はいないと思うが、それでも買いたいというならよく考えたほうがいい。自分は 絶対に買わないことをオススメする 。

---

1. インターネットに繋ぐための wi-fi もインタネット経由で設定する。まさに玉子が先か鶏が先かみたいなびっくりな話だが、ベーシックプランにドコモのLTEの契約が入っているので、そういうことが可能になる。↩

2. 基本的にはずっと電源をONにして使うものなので、日に数回程度の意↩

NLLとDropトレイト

NLL (non-lexical lifetimes) について誤解していた。

次のコードは NLL のおかげで、 _y に代入した &x が次の行以降使われていないため、 &mut で可変参照を生成できる。

use anyhow::Result;

struct X<'a> (&'a i32);

fn main() -> Result<()> {
    let mut x = 10;
    let _y = X(&x);
    let _z = &mut x;
    Ok(())
}

しかし、 X<'a> に Drop を実装した途端にコンパイルできなくなる。

impl<'a> Drop for X<'a> {
    fn drop(&mut self) { todo!() }
}

error[E0502]: cannot borrow `x` as mutable because it is also borrowed as immutable
  --> src/main.rs:12:14
   |
11 |     let _y = X(&x);
   |                -- immutable borrow occurs here
12 |     let _z = &mut x;
   |              ^^^^^^ mutable borrow occurs here
13 |     Ok(())
14 | }
   | - immutable borrow might be used here, when `_y` is dropped and runs the `Drop` code for type `X`

理由は以下の stackoverflow のコメントに書いてある。 NLL は借用が本当に使われている箇所を特定するだけで、コードの意味を変えるものではない。特に、変数のライフタイムは変わらないので、 Drop トレイトを実装したデータ型を使うと、今までと同様に スコープが終了するタイミングで drop メソッドが呼ばれる 。これによって参照 &x が使われている範囲が伸びるので、コンパイルできなくなるのである。

rust - Will the non-lexical lifetime borrow checker release locks prematurely? - Stack Overflow

macOS Big Surでマウスポインタと違うところがクリックされる問題の解消

ゴミ箱 を macOS Big Sur にアップグレードをしたら、クリックした時にマウスカーソルが指している場所と全然違う部分がクリックされるようになって、詰みかけた。 guest アカウントでログインすると発生しないので、ハードウェア的な問題ではなさそう。

30 分以上格闘した後、マウスポインタをシェイクして見つける の機能で、カーソルが大きくなっている時は正しい場所を指し示していることがわかった。

その後さらに試行錯誤を続けて、ようやく関連している設定を見つけた。 Accessibility の Zoom の項目にある、 「Use scroll gesture with modifier keys to zoom」 を有効にしていると、この問題が発生するようだ。

昔、プレゼンをする際に、 ライブコーディングなどでエディタや端末を拡大するために ズーム機能を使っていた人は多かったのではないかと思う。昔のマシンからアップデートをして壊れた人は、この項目をチェックしてみるといいだろう。

ROG Strix SCAR 15 G533 を買った

rog.asus.com

見ての通り、完全にゲーミングノートである。去年 Surface Book 3 を買ったばかり なので買う必要はまったくなかったのだが、コロナ禍のお陰で PC を触る時間が極端に増えたのと、 PS5 も switch のマリオレッド×ブルー セットも買い逃してついカッとなったと言うのもある。

ASUS ストアで買ったので、実は 30日返品保証 が使えるのだが、今の所返すつもりはない。最近の人にとっては違うのだろうが、自分にとってあくまでも PC は道具ではなく娯楽そのものであり、ワクワクするものである。そういう理由でつまらなくなった Apple の Mac を買うのを辞めてしばらく Surface シリーズを買い続けていたのだが、 Surface シリーズはいい意味で変態的ではあるが、あくまでも作業用の道具という枠を超えてない。いっそのこと娯楽に振り切ってしまってもいいのではないか、と思った次第である。

キーボードが US 配列なのも決め手となった。スペックは申し分なく(Ryzen 9 5900HX)、もちろんゲームができるが、開発環境としても快適に使える。 Surface Book 3 と比べると解像度や画面の縦幅が狭かったりするが、 WSL2 と Docker 、 VS Code さえ入れてしまえば立派な開発機となる。 2 Kg を超えバッテリーも重いので持ち運びに優しいとは言えないが、ギリギリ不可能ではない範囲に入るだろう。カメラがないことは注意が必要かもしれない。とは言え、プログラミングをやるようなコミュ障な人間が、何を好んで自分を撮る必要があるのか。不要だろう ¹ 。

そして、光る。誰がどういう理由でコンピューターを光らせ始めたのかとんと検討もつかないが、カラフルな光を見つめるのは楽しい。白状すると、加湿器も LED で 7 色に光るものを使っている。センスがない、もしくは中２なのかもしれない。いずれにしても、本人が満足していれば、それでいいのだろう。

---

1. 冗談はさておき、コロナ禍で在宅勤務をすることを考えるとカメラは重要で、これ一台でコロナ禍を乗り切るのは厳しいだろう。↩