URLSearchParams は使って良い
概要
- URLSearchParams の仕様は HTML form submission の仕様と揃えられている。
- これを RFC 3986 違反と言うのはやめてほしい。
本文
この記事では("URLSearchParams RFC" で検索して出てきがちな)以下のような主張から URLSearchParams を弁護していきます。
URLSearchParams を使ったら
*
を%2A
に変換せずそのままにしていた。RFC 3986 で*
は予約された文字なので厳密には仕様に準拠していない。
実は WHATWG の出している URL Standard に
Align RFC 3986 and RFC 3987 with contemporary implementations and obsolete the RFCs in the process.
と書かれているので、もし仕様変更があったとしても WHATWG が正統とみなすというので終わる話だったのですが、中身を読んでしまったので確認した話が続きます。
URLSearchParams の仕様 https://url.spec.whatwg.org/#urlsearchparams の Note は URL.search
と URL.searchParams
の差の説明を目的としているようにも読めるが、ともかく application/x-www-form-urlencoded
を利用することが書かれている。名前のとおり HTML form submission で使われる形式で、エンコード対象は
https://url.spec.whatwg.org/#application-x-www-form-urlencoded-percent-encode-set
The application/x-www-form-urlencoded percent-encode set contains all code points, except the ASCII alphanumeric, U+002A (*), U+002D (-), U+002E (.), and U+005F (_).
なので RFC 3986 で unreserved の記号 -._~
と差がある。
そもそも RFC 3986 の reserved character とは何なのか。
https://datatracker.ietf.org/doc/html/rfc3986#section-2.2
reserved = gen-delims / sub-delims gen-delims = ":" / "/" / "?" / "#" / "[" / "]" / "@" sub-delims = "!" / "$" / "&" / "'" / "(" / ")" / "*" / "+" / "," / ";" / "="
URL をコンポーネントに分解するのに用いる区切り文字 (gen-delims) より多くを予約しているらしい。
The purpose of reserved characters is to provide a set of delimiting characters that are distinguishable from other data within a URI.
で始まる段落を読むと、目的は区切り文字として使用可能にすること、実装は percent encode するしないを区別することだと分かる。より具体的に言えば、
- sub-delims が
&
,=
を含むので以下を区別することができる:
> new URLSearchParams([['x', 'a'], ['y', 'b&y=c']]).toString()
'x=a&y=b%26y%3Dc'
> new URLSearchParams([['x', 'a&y=b'], ['y', 'c']]).toString()
'x=a%26y%3Db&y=c'
- sub-delims が
+
を含むことが form data のスペースを+
にエンコードする実装を許している一方、そのために form data の+
を%2B
にエンコードすることと直接の関係はない。
すなわち reserved characters は勝手に encode, decode されないという仕様であって、一律に使うなと言われているわけではない。実際、RFC 3986 が query について定める範囲では
pchar = unreserved / pct-encoded / sub-delims / ":" / "@" query = *( pchar / "/" / "?" )
なので #[]
以外の reserved characters は使用が想定されている。
微妙なところとしては "specifically allowed by the URI scheme to represent data in that component" でなければ送信は厳格に受信は寛容にと(いつものパターンで)書かれている。こうなると RFC 3986 に閉じた話でなくなり、現実は WHATWG に反映されているはずなのでそちらを見ると、
URL.search
は single quote'
も http(s) を含む一部 scheme でエンコードしているのでこれだけは何か事情がありそう。application/x-www-form-urlencoded
のデコードでは&=+
以外は percent decode するだけなので、他に特別な意味を持つ記号がない前提で寛容な受信をしているようだ。application/x-www-form-urlencoded
のエンコードで*
がそのままなので、意味を持たない記号として定義されているとみなせるかもしれない。
ちなみに URL に現れない printable ASCII は"<>\^`{|}
の 9 文字。これに加え
#
fragment 開始専用%
percent encoding 専用[]
IPv6 (or later) を囲む専用
が除外されていることが古い仕様書では説明されている。https://datatracker.ietf.org/doc/html/rfc2396#section-2.4.3
最近の仕様書には使える文字のほうのリストしかないようだ。https://url.spec.whatwg.org/#url-code-points
また、 encodeURIComponent についてはどの scheme のどの component に使うか分からないから reserved character すべてをエンコードする仕様だったほうが適切という主張に理がある。(sub-delims の差なので「URL の」パース結果が変わるようなひどいことにはならないが。)
URL の query 部分に限って言えば form data から *
がそのまま入る仕様を消すとしてもさらに十分な時間が経つまでは *
に別の意味を持たせる状況は考えにくいので URLSearchParams が将来の標準に沿っているかの点でも懸念は少ないだろう。
戦力を3つに分けて2勝したら勝ちのゲームのナッシュ均衡
概要
- 「分割して番勝負」はゲームの基本的なメカニクスの1つだと思うが、知っていたのは三すくみを含んでいることくらいで、考察したことがなかった。
- こういう具体例を計算してみると、ナッシュ均衡の特徴付けのどれが便利かが分かってくる。
- 正六角形(内側を含む)の上の確率分布で辺に垂直な成分への射影がどれも(長さ√3の)線分上の一様分布となるものを挙げよ。
経緯
課金ゲームを無課金で遊んでいたら、レベルカンストで3編成作るのが難しいという困難が発生して、3つに分ける部分がそれなりに重要になってしまう。
ボードゲームでこのタイプの判断が出てくることもよくある。リソースを今使うか後で使うかということ。どちらかというと前の勝敗を見てから後の分割を決めてよいルールになりがちなので違うゲームだが今回は考察しない。
ゲームのメカニクスは構成要素にすぎないが、それぞれの要素について考察しておくと有用そうな気がしたので、最も簡単な「3つに分けて2本とったら勝ち」だけのゲームを解いてみよう。
定式化
(純粋)戦略 $(x, y, z) \in \Delta = \lbrace x + y + z = 1, x ≥ 0, y ≥ 0, z ≥ 0\rbrace$ 上の零和ゲーム。利得は $\mathrm{sign}(x - x') + \mathrm{sign}(y - y') + \mathrm{sign}(z - z')$ で与えられる。
- ゲームの例として紹介されるときは「石100個を分けて、〜〜」などとされるが連続にした。
- 勝敗数から線形に利得になることを用いた。
- 「2勝以上したら勝ち」と表現されがちだが、全勝できないので。
- 4つ以上に分けるときや合計値が不公平なときは今回のようにはできない。
- 一方、「サイコロの目を書いて振る」ようなゲームなら分割数(何面ダイスか)によらずこのように扱える。(0, 3, 3) > (2, 2, 2) > (4, 1, 1) > (0, 3, 3) の三すくみがあることは有名(漫画のネタで使われているのも見た)。
混合戦略のナッシュ均衡が存在するかについては、コンパクト集合上の連続関数なら良かったはずで、今回は符号関数 sign が不連続だが sigmoid にかえた場合は存在することは言える。その極限っぽいが存在だけを先に厳密に示す方法はよく分からない。なお、以下で実際に構成できるので良い。
必要条件をつめる
ナッシュ均衡の存在定理を勉強したときには補題がいろいろあったり、どれが重要な特徴付けなのか記憶に残らなかったのだが、実際に手計算していると決まったテクがあるように感じられてくる。(コンピュータで解く場合のアルゴリズムについては私はあまり詳しくないがCounterfactual Regret Minimizationがよく使われているかもしれない。)
ナッシュ均衡を手計算するテクを一言でまとめると、混合戦略であって純粋戦略に exploit されないものを探すと良い。
- 例1:じゃんけん。対称零和ゲームなので目標の利得は0。ナッシュ均衡になりうる混合戦略(それぞれの手を出す確率)を(p, q, r) (p+q+r=1)とおくと、相手の手に対して q−r≥0, r−p≥0, p−q≥0 を得るので p=q=r=1/3 である。
例2:利得行列 $\begin{pmatrix}1 & -1 \newline -2 & 2\end{pmatrix}$ の零和ゲーム。行を選ぶプレイヤーの混合戦略を (p, q) とおくと、 min(p−2q, −p+2q) を最大化したいので (p, q) = (2/3, 1/3) のとき最大値 0 を得る。同様に列を選ぶプレイヤーの混合戦略 (1/2, 1/2) が求まりこれらについてナッシュ均衡となる。
- ところで、ある漫画で例2のゲームについてナッシュ均衡と異なる戦略がセオリーとされていたが、人の直感の当てにならなさを表していたのか、キャラの頭の悪さを表していたのか、作者が知らなかっただけなのかどれだろう。
補足:手番が1度きりのゲームのみここでは扱っているが、複数回の手番があるゲームでも、相手の純粋戦略のみ考えればよい。すなわち、どの状態でも相手は非確率的に選択するとしてよい。
では3つに分けて2勝するゲームを考えていこう。対称零和ゲームなので 0 にできれば良い。混合戦略を表す $\Delta$ 上の確率分布 μ(x, y, z) と相手の純粋戦略 $(a, b, c)\in\Delta$ について満たすべき条件は
ただし確率分布 μ(x, y, z) の射影(同時分布に対する周辺分布)を μ(x), μ(y), μ(z) とおいた。さらにcdf(累積分布関数)を f(x), g(y), h(z) とおけば、 $f(a) + g(b) + h(c) \le 3/2$ と同値(厳密にはcdfが端点を1/2だけ算入するように定義をいじる必要があるが)。
また、 x+y+z = 1 だったので、cdfたちは $\int f(x)\mathrm{d}x + \int g(y)\mathrm{d}y + \int h(z)\mathrm{d}z=2$ を満たす。なぜなら、
構成
ここからは予想して証明する感じになっていく。
$f(x) + g(y) + h(z) \le 3/2 \;(x+y+z=1)$ を満たしつつ f, g, h を大きくしようとすると、 f(x) = g(x) = h(x) = min(3x/2, 1) くらいしかないと予想できるので、こうなる分布 μ を構成したい。
言い換えると、正六角形 $\lbrace x+y+z=1, 0\le x\le 2/3, 0\le y\le 2/3, 0\le z\le 2/3\rbrace$ 上の分布で、それぞれの成分が [0, 2/3] 上の一様分布であるものがほしい。
ここで何らかのひらめきにより、 (2/3, 1/3, 0), (0, 2/3, 1/3), (1/3, 0, 2/3) を結ぶ正三角形の周上の一様分布($\mu_1$ とおく)が条件を満たすことが分かる。このゲームをするように迫られた場合の実用上はこの戦略でとりあえず損しないので覚えておくと良さそう。
別のひらめきにより、正六角形の辺からの距離が辺と中心の距離 (= √6/6) の (1-t) 倍である点の確率密度を t に比例するようにした分布($\mu_2$ とおく)も条件を満たすことが分かる。実際、 $$ t^{2} + 2\int_{t}^{1} s\mathrm{d}s = 1 = \textrm{const.} $$
唯一性
このようにナッシュ均衡は唯一ではないが、「内側含む正六角形上の分布で3つの射影がすべて一様」という特徴付けが正しいことは以下のように示せる。
2個めに紹介する有用なテクとして、強そうな戦略が見つかったら相手に代入すると良い。(今回は対称なのでそのまま代入しているが、一般には考察するプレイヤーがここで入れ替わる。)
言い換えた条件の側でいえば、見つけた戦略(確率分布)$\nu=\mu_1$ や $\nu=\mu_2$ で $f(x) + g(y) + h(z) \le 3/2$ を積分することを意味し、 $$ \begin{aligned} \frac{3}{2} &\ge \int_\Delta (f(x)+g(y)+h(z))\mathrm{d}\nu(x,y,z) \newline &= \int f(x)\mathrm{d}\nu(x) + \int g(y)\mathrm{d}\nu(y) + \int h(z)\mathrm{d}\nu(z) \newline &= \frac{3}{2} (\int_0^{\frac{2}{3}}f(x)\mathrm{d}x + \int_0^{\frac{2}{3}}g(y)\mathrm{d}y + \int_0^{\frac{2}{3}}h(z)\mathrm{d}z) \end{aligned} $$ が分かる。 f ≤ 1, g ≤ 1, h ≤ 1, $\int f(x)\mathrm{d}x + \int g(y)\mathrm{d}y + \int h(z)\mathrm{d}z=2$ を思い出すと ν 上確率1で等号成立して $f(x) + g(y) + h(z) = 3/2$ となっている。$\nu = \mu_2$ のほうを用いると内部を含む正六角形上ほとんどいたるところで成立するので、あとは単調性と加法性から線形性を示す関数方程式でよくある議論をすれば f(x) = 3x/2 (0 ≤ x ≤ 2/3) などが出る(はず)。
あとがき
相手を純粋戦略として良いことと、相手にうまい混合戦略を代入すると良いことを紹介した。これらは相反して見えるが、ナッシュ均衡の同値な定義は形式上近い一方うまい使い方に違いが出るということだと思う。
記事を書いていて、線形計画法あたりの分野で知られている話題なのではと思った。(仕事じゃないから先行研究調べないのが許されている。自分で考えるのは楽しい。)
ナッシュ均衡の例を挙げ、そこそこの必要条件を出しただけなので、均衡 (μ, ν) 全体のなす空間をうまく書けるかは未解決。別のfuture workとしては分割前の戦力が不公平な場合や分割数が4以上の場合などがある。知っている方、計算した方がいたら教えてください。
ナッシュ均衡をしっかり手計算したのは、ポーカーのベット部分だけをうまく簡略化して解けないかな、とか考えていたとき以来。結局何回もレイズできる場合を解けずに放置してしまっていて悔しい。
heads-up preflop only game の厳密解の議論を探したのに出てこず、(ポーカーの教科書的なものを読まずに)まずは raise 1回までの場合とかを自分で解こうとしていたけれど、解かれてしまった……。https://t.co/enVvO6DPYc
— tos(とす) (@toslunar) August 8, 2022
実際のゲームに適用するには、混合戦略のナッシュ均衡が何を意味するか理解しているほうが良く、よくある誤解への解説がこれもmaspyさんのポーカー記事にまとまっている。
AtCoder で Option も Result も ? で .unwrap() する
競技プログラミングでの Rust のつらさのひとつに .unwrap()
と9文字も書くのがだるいというのがあります。エラー伝搬は ?
1文字なのでエラー無視も楽に書きたいところですが、この記事にあるように stable Rust が入っている競プロサイトでは無理そうに見えます。ところが、実はできます。1
fn main() { main1().ok().unwrap() } fn main1() -> Result<(), Never> { // ここにメインの実装 dbg!("foo 42 bar".split_ascii_whitespace().nth(1)?.parse::<i32>()?); Ok(()) } enum Never {} impl<E: std::fmt::Debug> From<E> for Never { fn from(e: E) -> Self { panic!("unwrap ?: {:?}", e) } }
解説
現在の AtCoder 上の Rust はコンパイラのバージョンが 1.42.0 なので ?
の仕様は (v2 になる前の) try_trait
です。ここで Option
に ?
して Result
を early-return するための型 std::option::NoneError
は #[feature(try_trait)]
がないと名指しできないのですが、 Debug
トレイトを持つすべての型からの変換なら stable の範囲で書けるため、 From<NoneError>
が実装できてしまいます。標準的に使われるエラーは std::error::Error
トレイトなので Debug + Display
以上と分かっているし fn binary_search(&self, x: &T) -> Result<usize, usize>
2 のように「エラー」ではない Result
もだいたい Debug
です。
ちなみに try_trait_v2
では専用の FromResidual
トレイトを実装する必要がある3のでこういう抜け穴はありません。
main 関数に書きたい場合
fn main() -> Result<(), Never> { // ここにメインの実装 Ok(()) } #[derive(Debug)] enum Never {} impl<E: std::fmt::Debug + Clone> From<E> for Never { fn from(e: E) -> Self { panic!("unwrap ?: {:?}", e) } }
Never: Debug
にするとそのまま main
にできるのですが、 T: From<T>
との重複実装が許されないため、変換できるエラー型を絞る必要があり、たとえば Debug + Clone
を課すと良さそうです。 std::marker::PhantomPinned
を用いて Never: Debug + !Unpin
にして E: Debug + Unpin
にできれば使い勝手良くなりそうですが、なぜかできませんでした (T: From<T>
との重複判定が消えないため)。
-
.unwrap()
を直接書く場合と比べるとエラー時に表示されるソースコード位置が変わってしまう問題はあります。RUST_BACKTRACE=1
で1つ下を見ましょう。↩ -
partition_point
が 1.52.0 からなので AtCoder では仕方なく使ったりします。↩ -
try_trait_v2
については以前の日記にも書きました。 https://toslunar.hatenablog.com/entry/2021/08/03/230856↩
Rust の Iterator で cumsum をどう書くべきか、あるいは map の闇
Rust の Iterator で cumsum をどう書くべきか、あるいは map の闇
最近、競プロ典型90問を解いて競プロのリハビリ兼 Rust 練習しています。
Iterator::scan の謎
cumulative sum といえば Haskell でいう scanl 0 (+)
だと思っているので it.scan(0, |a, b| a + b)
と書けば良いだろうと scan
を見に行くと、予想に反する型がついている。型は少し省略して書くと
fn scan<St, B>( self, initial_state: St, f: impl FnMut(&mut St, Self::Item) -> Option<B>, ) -> impl Iterator<Item = B>
なのだが、 St
と B
が異なっていることからも分かるように 0 番目に initial_state
を返す実装ではないのが残念だし、逆に長さを縮める機能を Option
を返すことで実装しているのも意図が分からない。
つまり、後者の目的で scan
を使うくらいなら map_while
(since 1.57) で十分だし、 _while
要素もないので map
(FnMut(Self::Item) -> B
を渡す) で良く、 cumsum は
std::iter::once(0) .chain(it.map({ let mut s = 0; move |a| { s += a; s } }))
となる。
Iterator と FnMut
副作用のある関数を書いて良いのが盲点で、実際そういう言語だから map
という名前で
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
あるいは mapM
相当だと思っておくのが自然だった。 Rust だと state monad 使う面倒さがなくて楽。めでたしめでたし。
とはいえ、 Fn/FnMut/FnOnce の区別みたいなところでも mut ref は unique ref という話みたいな対応もあって、 API 設計の意図が mut 側か unique 側かは分からない。副作用があっても実装が変わらないから FnMut とも言えるし、必要条件の側を考えて「同時に callback が呼ばれないから Fn を課す必要はなく、 Option::map
などと違って 2 回以上呼ばれるかもしれないから FnOnce では足りない」という理由で FnMut になっているとも言える (これらは言い方が違うだけ)。
DoubleEndedIterator
Rust の Iterator のうち一部は後ろからも値を取り出せる (next_back
)。たとえば、よく書くのは for i in (0..n).rev()
だが、全部読んで Vec::reverse
のような実装ではなく end -= 1
を返すような効率の良い実装が呼ばれる (std::ops::Range<A>
については Iterator ならば DoubleEndedIterator)。
さて、 Iterator::map
のドキュメントをよく見るともとの iterator が DoubleEndedIterator なら map 結果も DoubleEndedIterator を実装するらしい。見るからに副作用がやばい。そう思ってドキュメントを確認するともっと目立つところに具体例付きで注意書きがある。上の cumsum 実装も同じ理由で .rev()
などすると壊れる。
.map(f).rev()
は .rev().map(f)
に直すように lint 出ても良いくらいだと思うが、 DoubleEndedIterator は 1 回 rev
して終わりと限らず両端から自由な順序で取り出す想定の API だから pure function で map して DoubleEndedIterator を保ちたい用途がないとも言い切れない。
advanced_by
ところで、 for i in (0..n).step_by(k)
は上限と modulo を指定できて便利なだけでなく O(n/k) 時間で動く。これは Iterator (required method は next
のみ) は nth
を自動実装しているが std::ops::Range
が O(1) 時間の nth
を与えることで実現されている。
自分で .map(f).rev()
と書くことはないはずだが、 .map(f).step_by(k)
は書きかねないので、 rev
がやばいのなら step_by
もやばいのではと思って調べたところ、これはセーフ。
Iterator::map
が副作用無視の nth
の高速化をしないことが保証されているか気になって iterator map nth で GitHub issue を検索したら advanced_by
(unstable) の tracking issue の中で議論されていた。 map の副作用の注意書きすでにあるし nth
でも副作用飛ばそうぜみたいな意見もあって一応予断を許さない雰囲気はちょっとある。競プロに限らなければ順序不定でもよい副作用とか消えても良い副作用とかいろいろあるので対立もやむなし。
立場をあえて明確にすれば自分は現状に賛成。 DoubleEndedIterator::rev
は subtrait として分かれているから自己責任で、 Iterator::step_by
が自動実装と挙動が違ったらやばすぎるみたいな裁定で正しいと思う。 Iterator::last
は DoubleEndedIterator::next_back
ではないし Iterator::count
は ExactSizeIterator::len
ではない。
AtCoder で cumsum したいとき
自分で書きたくないなら itertools_num::ItertoolsNum::cumsum
か ndarray::ArrayBase::accumulate_axis_inplace
を使えばよさそう。いずれも最初に 0 をつけたい場合はいじる必要あり。
cumsum を書く場合は map
後すぐ collect_vec()
しておけば罠を踏むリスクはない。そもそも、ライブラリ整備せずその場で書くとなれば短いのが強く、
let mut s = vec![0]; // let n = a.len(); // 別のところで入力しているはず // s.reserve(n); // Rustでそんなにパフォーマンス気にせずともACとれるはず for i in 0..n { s.push(s[i] + a[i]); }
とするか、 i
, n
の typo を避けて
let mut s = vec![0]; for a in &a { s.push(s.last().unwrap() + a); }
にしそう。
try_trait_v2でOptionとResult両方に?を使う
この前 NoneError
(try_trait
(v1) の実装) が消えていたのを見て、どうやら try_trait_v2
に移行したらしいということで勉強した。
参考:RFC https://rust-lang.github.io/rfcs/3058-try-trait-v2.html
Result<T, E>
の Ok(t)
については t: T
があれば良いが、 Err(e)
については型情報を持ったまま return に処理を移すために e: E
ではなく Err(e): Result<Infallible, E>
を "residual" として残すことになるというのが v2 のポイント(v1のときに不勉強だったのに差分を説明……)。もちろん、この2通り(early-return しないかするか)は enum で表現され、なぜか Result::{Ok, Err}
ではなく ControlFlow::{Continue, Break}
が使われる。
Option, Result 両方を ?
できる関数を書くには Option<Infallible>
, Result<Infallible, E>
について FromResidual
を実装した型をつくる。コード例では OptionResult<T, E>
としたが、 struct Foo(Option<Result<T, E>>)
のようにもできるはず(いずれにせよ orphan rule により新しい型が必要だし、そもそも Option<_>
や Result<_, _>
はすでに impl Try
されてしまっていて重複不可)。
#![feature(try_trait_v2, try_blocks)] // try_blocks は使用例のみで使う。 use std::{ convert::Infallible, ops::{ControlFlow, FromResidual, Try}, }; #[derive(Debug)] enum OptionResult<T, E> { Ok(T), Err(E), None, } impl<T, E> FromResidual<Option<Infallible>> for OptionResult<T, E> { fn from_residual(_: Option<Infallible>) -> Self { OptionResult::None } } impl<T, E, E0> FromResidual<Result<Infallible, E0>> for OptionResult<T, E> where E: From<E0>, { fn from_residual(e: Result<Infallible, E0>) -> Self { OptionResult::Err(e.unwrap_err().into()) } }
また、残念ながら、 -> OptionResult<T, E>
な関数に ?
を使っていくにはこの型自身の値も ?
できる必要があることになっている。すなわち Try
trait を以下のように実装する(使わないなら todo!
で十分)。
impl<T, E> Try for OptionResult<T, E> { type Output = T; type Residual = OptionResult<Infallible, E>; fn from_output(t: T) -> Self { OptionResult::Ok(t) // ここも todo!() にしても良いが、 try block で便利 } fn branch(self) -> ControlFlow<Self::Residual, T> { todo!() } } impl<T, E> FromResidual<<Self as Try>::Residual> for OptionResult<T, E> { fn from_residual(_: <Self as Try>::Residual) -> Self { todo!() } }
なんでも Result<Option<T>, Box<dyn std::error::Error>>
にするのが使い勝手良さそうということで、使用例は以下のとおり。
fn main() { let mut xs = "42,3,foo,7".split(','); for _ in 0..6 { println!("{:?}", f(&mut xs)); } } fn f<'a>( it: &mut impl Iterator<Item = &'a str>, ) -> Result<Option<i32>, Box<dyn std::error::Error>> { let res: OptionResult<_, _> = try { it.next()?.parse::<i32>()? + 1 }; res.into_result() } impl<T, E> OptionResult<T, E> { fn into_result(self) -> Result<Option<T>, E> { match self { Self::Ok(t) => Ok(Some(t)), Self::Err(e) => Err(e), Self::None => Ok(None), } } }
Ok(Some(43)) Ok(Some(4)) Err(ParseIntError { kind: InvalidDigit }) Ok(Some(8)) Ok(None) Ok(None)
ICFPC 2021 振り返り
今回はおもに解の手動更新用のGUIを作っていた。入力をグラフとしてGraphvizで可視化するするのとかも初期はやっていた。
グラフ表示の位置などのヒント情報を用いてGUIの頂点に色を塗るとか、そこからGUIで動かす頂点選択するとかは時間内に思いつきたかったなあ。
今年は WebAssembly (wasm) がなかなか良い働きをしていて、Rust実装を使い回しやすくなったのは大きい。使いやすかったかというと微妙なところもなくはなく……。Rustから生成、TypeScriptで使うという2点に分けて以下に書いた。
いろいろ技術ごとに振り返ってみる。
Rust
wasmを準備したのは正解。 evcxr_jupyter
を動かして Jupyter Notebook で動いて楽しいとか言っていたが、使わなかった。imosにRust用のファイル置いておくよう言われて開始前に cargo init
および去年使ったマクロをサンプルとして置いたのは良かったと思う。
コンテスト中に書いた行数でいうと今年はそんなにRustを書いていないような気がする。
追加データで負の座標が出てきたのはx座標に2を加えて対処されたが、 serde_json::from_reader
などと書くのが簡単すぎるせいで座標ずれバグをつぶしにくかった。型を分けるのは無理なので、ずらしたかの情報をstructに足して正気を保つようにした。
#[serde(skip_serializing_if = "Option::is_none")] #[serde(default)] pub internal: Option<InputInternal>,
他にも入力時に多角形の向きが直されていて、実は線分が多角形に含まれるかの判定にもその仮定が使われているみたいな罠もあり、ついでに気付くことができた。
iwiが普段エラー処理anyhow使っていると言っていたが、Unagiでも使っていくべきなのでは。
かつて、stderr軍拡競争はloggingで平和解決したはずだが、Rustになってloggingはどうなったんだっけ。
serde
神。毎回使うので使い方も慣れてきた。
今回のJSONはbonusのシリアライズ仕様がイケてなくて、
type Bonus = { bonus: string, problem: number, edge?: [number, number], }
みたいな仕様だったが、serdeのattrつけていけばなんとかなるはず。実際は BREAK_A_LEG
無視されたのでやってないが。
#[serde(rename_all = "camelCase")] struct { .. } #[serde(rename_all = "SCREAMING_SNAKE_CASE")] enum { .. }
なども使っていきたかったが、 WALLHACK
を WallHack
と誰かに書かれてしまった後なのでできず。
ordered-float
From<u8>
がなくて困ったらしい。Haskellの Num
は (+), (*), abs, signum, fromInteger, (negate | (-))
が良いかというと abs, signum は違う気がしてしまうので結局分からないが。
wasm-bindgen
Vecを #[wasm_bindgen]
できないのはつらくて、serdeによる変換に頼ってしまったが、ドキュメントにはパフォーマンス悪いかもとかわざわざ書かれていて、無駄に不安になっていた。Rustから型をexportしなかったのでTypeScript側でも型を書き直している。
i64を変換するのも不安要素で、f64になるのかbigint的なのになるのかも知らないし。
Result<T, JsValue>
を返す明示的なエラー処理をしなくてもrustでのpanicがjs側のエラーになるっぽいのは良かったが、巻き込んで落ちるのが直せなくてつらかった。原因はいまだ不明。
JavaScript / TypeScript
wasm関係続き
async import よく分からない。その場で調べたので準備不足。
webpackのWasmPackPlugin使ったほうが良かったか。結局make file書くのは不毛だが、wasm-pack buildするタイミングは自分で決めたいし、今回はwasm mime type問題で後処理も発生していた。
1ファイル(index.html + index.js くらい?)で済めば file:// で開いても動くからwebpackにしたのに、.wasmが別ファイルというのが罠。http-serverが.wasmを正しく扱わない(またmime type問題)のも問題。wasmがファイルの先頭から(読み込み完了する前に)ネイティブコードに?1-pathで変換する設計を昔聞いたときはよくできているなって思ったが、mime typeあってないとそのAPIが使えません(読み込み終わってからByteArray渡してね)って仕様になったのは納得できてない。
tosk.jpの置かれているValueServerが.wasmを正しいmime type返さない。設定をユーザーが変えられるのかみたいなことを知らない。この辺の一般知識がない。imosのいつものicfpcサイトではちゃんと動いたので多分Googleは偉い。github.ioとかにしても良いが、こういう非公開用途で困る。
PIXI.js
PIXI.jsの採用は迷惑掛けてしまった。WebGL直接は書きたくないのでjs側から書くには楽だが、Rustのライブラリ探しておくのが理想か。svgのpathくらい描画する機能あっても良いと思うんだけど……(無いことを知っていたのでなおさらなぜ選んだって感じだ)。
GUI、model matrixではなくview matrixをいじるべき場面なのに手動で線形変換の逆変換求めていたりして無駄だった。
というか、WebGLとsvgどちらで行くかの選択の問題もある。svgをインタラクティブなGUIに使えない気がしたが、sulumeがちゃんとしたのを作っていて感心した。
UI一般
色を適当に決めてしまったが、matplotlibからcolormaps拾ってくるくらいの準備はしておきたかった。具体的には、edge長の違反量に応じた色付けという要望が出ていたのに実装せずに終わってしまった。
index.html直書きで大丈夫だという予定だったが、React入れても良かったよなあ。npmはcargoほど安心して依存追加できない。でかいパッケージが相性問題起こしがちで、たとえばwebpackの設定を変えないといけなかったような。あまり良く分かっていなくて、npmをyarnにするみたいなのは平時に試しておいてもよかった(これが関係あるのかさえ分かっていない)。
他
package-lock.json
で編集合戦が発生していたのは準備不足。自分とimosの環境では "lockfileVersion": 2
だがsulumeの環境では "lockfileVersion": 1
で他の場所にもdiffが出ていた。
自分もnodeのバージョンをコンテスト中に12から16に上げたので人のことを言えないが、こういうやばさはなかったと信じたい。
チーム開発
表記ゆれ (input/problem, output/solution/pose, score/dislike) がやばい。ソルバー班の考えやすい普段の言葉遣いでやっているが、poseも読み込むし、dislikeは最終的なチームスコアに変換される。「型の名前くらいは公式に従っておいて、変数名は自由」みたいなのが良いのかなあ。vscodeで型や変数のrenameするのは簡単だが、1回pushするとconflictをおそれて直せなくなって const solutionJson = this.pose;
とか runCheckSolution1(input: Problem, output: Solution): void
とか書き続けてしまった。
ソルバー側が負の座標や多角形の向きを気にすることなく開発できるのはあまりに大事なので、ソルバーからも手動からもvisualizeしたいという要求をどう処理するかということになりがち。今年はy座標が下向きなので平和だった。
cargo fmt してほしい。自分のファイルだけ rustfmt するのはちょっと面倒。同じファイルを同時編集する場合は、1ファイルよりさらに細かい単位のみを自動整形したくなるが、それが(たぶん)できなくて困る。
hard tabでインデントしたいならそれに合わせても自分は文句ないので、 rustfmt.toml
作るのが良いのでは。今気付いたが、空の rustfmt.toml
を置きさえすれば個人の global config の適用回避できるっぽい……。実際に src/lib.rs
で tab vs spaces の編集合戦を原因の一部とするmerge失敗があったので、実際に損している。 auto-mergeになったと聞いていたが検証したら自分のgitの設定では衝突したので、そちらに対策を入れるのが先という可能性もある。
iwiがgit submoduleを使わず直接足したのは正解だと思っていて、1回ライセンスを確認するほうが、後で誰かが操作失敗する可能性や、VSCodeのgitタブでsubmoduleの存在が表示されてうざいという認知負荷より安い。GitHubがメインの言語Javaって表示するのが気になって後で直したが。
「だから僕は音楽を辞めた」を聴いて思ったことを書いていく
1回しか聴いていないしMV見なかったけど140字におさまらない感想が出てきそうだったので。これは正当でない解釈や無関係の話題を出すための予防線だし,1回でそれなりに聴き取れているという主張でもある。ヒットチャートを聴かなくなって久しいので最近の曲がだいたいそうだったらごめんだし例外だった場合もごめん。
聴いたきっかけ:
「だから僕は音楽を辞めた」で真面目に感動できるくらい真面目に音楽をやっていたかった
— ふりふりモノトーン (@furifuri_mono) May 11, 2020
聴いた場所:https://youtu.be/KTZ-y85Erus
タイトルから予想できるように恋愛以外について歌っている歌だったはず。アニソンにもよくそういう良さがあって好きだがいつもそうではない。J-POPには少ないのではという印象があって,ポケモンマスターに絶対なってやるというような強い気持ちを歌ってほしい,とは普段から思う。
歌詞の内容は,「世の中で信じられている価値観(例えば「愛」とか)が分からないし,自分にはそれと違って伝えたい価値観があったはずなのだが,何らかの理由により音楽をやめた」みたいな感じだった。適当に聴いていたからなのか「何らか」が何かが分かっていないが,前提と結果が重要でそこは重要ではないか一言では表せないかみたいな気がする。
当然の反論として「愛が分からないは失恋や悲恋みたいなものではないか」があり得るが,世の中の普通の失恋ソングがそんなに共感できない人は一定数いて,愛が「失われた」については想像しかできず「そもそも無かった」ならよく分かる,みたいになりがち。両親から愛されて育っていても他人からの愛はよく分からなかったので,世の中のせいなんだと思う。そういう社会になってしまった。足切りされてしまう人にとっては恋愛は深く考える余地のないものだ。
おそらくいつの時代もだが,上の世代の価値観の拒否がここで共感を呼んでいるテーマで,自分のほしい幸せがすでにある言葉で表現できていなかったり言葉の定義が嫌いだったり,より屈折した感覚としてはかつてあった幸せの形が自分の周囲にはなかったりそれでもそれを目指せと上の世代に言われたり,みたいなところを分かっている気がする。まあこの世代について言えば,適当な単語を言っていれば団結できる時代は終わっている。最近の「敬意・感謝・絆」もよく分からなかったし。この歌がウケている世代が同世代ではないかもしれないし,作者が本当に音楽をやめたのかがどうでも良いのと同じくらいには作者の世代はどうでも良いんだけど。(実際知らない。)
歌の歌詞が聞こえない派から歌詞で大体の評価を決めてしまう派までいるのは知っているが,私はどちらかといえば聞こえない派。楽器先行の育ち方をすると認識がそうなりがち。この歌でも歌詞はどうでも良いよみたいに言っていたし,ピアノは技術があるような雰囲気を出している。
一方で,繰り返しの多さは技術はあるのにやる気がないという表現になっていたような。クラブミュージックで繰り返しは当然なので聴き慣れてはいるが,ピアノ・ギター・ベースといったバンドサウンドで前小節完全コピー(単にリズムが同じという以上に音程も同じ)を多用されると「もっとやる気を出せ」って感じる。もっとも本当にやる気ないわけではなくて,即興曲が本当に即興で作られているわけではないのと同様に意図的に情報量を落としていると思われる。間奏にアドリブあるし。
サビが5音階だった。あからさまにそうなのは1周回ってきているのかもしれない。とはいえ,歌番組でこの曲のサビだけ流されたとしたらどうでも良いよってなっていたと思うので,サビは(J-POPの)マナーとしてあるんだなあって持論が強化されてしまう。歌詞としては「結論」がサビにあったりするけど結論が一番大事かっていうとそうじゃないよねみたいな。