自宅に給湯器リモコンが登場したので使ってみたら、思い描いていた曲が流れたので大喜びしていた。YouTubeで公式チャンネルが出していた。
給湯器リモコンの音源だけを集めた動画があって一生聞いていたい。自動生成の字幕がおもしろかった。字幕のブレをヒップホップに活用できるかもしれない。
— うたがわきき (@utgwkk) 2021年12月11日
給湯器でフロアを沸かせる動画を探していたのだけどTwitterのブックマークに保存していたので助かった。
給湯器を使ってフロアを沸かせる方法。 pic.twitter.com/3sqTMZzIwp
— lapix (@_lapix_) 2020年5月21日
現地でのライブに行くのは1年以上ぶりだと思う。このブログに記録が残っているものだと去年の1月なのでギリギリ2年ぶりではないぐらい。
チケットとドリンク代に加えて、新型コロナウイルス感染追跡サービスへの登録もしないといけなくて、時世が時世なので仕方ないけど忙しい感じだった。去年の今頃はこういうライブに行くことは夢にも思っていなかったので、ちょっとずつ再開しているのは喜ばしいことだと思う。
トークの雰囲気としてはゆるい感じでこれぐらいがいいと思う。曲は聞いていたけど人間性についてそんなに知らなかったので新鮮だった。
曲目は以下のような感じ。セトリをまとめてくれている人がいてありがたい。後半に向かうにつれて楽しい曲が増えて翌日はすごい筋肉痛だった。「雷火」の高音が高すぎてビビってた。
新しめの曲はあまり追えていなかったのでちゃんと追おう、と思った。
ドラム式洗濯機を無事に設置できた。洗濯物が乾いて出てきてかつてない体験だと思う。これまではびしょびしょの洗濯物が出てきて惨めな気持ちになっていたのでギャップがすごい。
引っ越しにかかる手続きが一通り落ち着いてきた。先週は引っ越しのことが頭から離れない状態のまま凝った実装について考えていて大変だった。空間を活かした収納グッズを揃えにかかっているところで、もうちょっとしたら段ボールを全部やっつけられると思う。
このたび、学生の頃からずっと住んでいたマンションの一室を離れて、新しい部屋に引っ越した。京都市内から京都市内の引っ越しである。
いろいろな物を捨てて、一度も着ないまま場所だけを取っていた服を全部捨てて、とにかくいろいろなものを捨てた結果、段ボール箱の数がギリギリだった。逆に言うと、引っ越し業者の人の見積もり精度が高い。段ボール箱をバラしまくってなんとか生活できるようになってきた。
生活の質をこれ以上よくするには引っ越すしかない、と思ったのが引っ越しのきっかけである。非連続な変化を起こさなければどうしようもない、みたいな感じ。ワンルームマンションでこれ以上やっていくことはできないと判断した。まだ家具を揃えていないので以前と同じように物を置いているけど、部屋に何もない空間があっておもしろい。
有休を取っていろいろ荷物を受け取ったり、住所変更の手続きをしたり、とにかく様々なことをやったら疲れ果ててしまった。銭湯に行ったら回復した。
— うたがわきき (@utgwkk) 2021年12月6日
区役所に行ってたら、ルンバ (パイモンという名前にした) がスタックしてしまった様子が通知されてきて未来っぽい。しかし区役所からはどうすることもできない……。
以下のリンクから引っ越し祝いを送ることができます。
小ネタです。
仕事してたら気づいた。ほたるんの服、完全にGitHubじゃん。 pic.twitter.com/z0m1UuyuAh
— ズッキー (@zukky162) 2021年12月2日
2021/12/3時点での引用リツイートには、どのcommitのどの行かを示したツイートはなかったので、たぶんこれが一番速いと思います。
ほたるんの服のcommit発見した https://t.co/bPH6KcrjtH
— うたがわきき (@utgwkk) 2021年12月3日
firefoxArguments などの変数名からブラウザを起動する何かであるということを推測します。devtools や headless などの引数名からこれはpuppeteerのcommitではないか、とアタリをつけました。ここで外すとタイムロスです。
GitHubのスクリーンショットから、PRの差分かcommitの差分だろうと推測して探します。
puppeteer/puppeteer を手元に git clone してきて以下のコマンドで探します。
-S <探したい文字列> で差分に指定した文字列を含むcommitを探して、-p でcommitの差分も表示します。
% git log -S firefoxArguments -p
ありました。よかったですね。
コミットメッセージから、Firefoxのユーザーデータ用のディレクトリを任意に指定できるようにするcommitであることが分かります。
puppeteerリポジトリのcommitである、というアタリをつけるところが一番難しいですね。全く知らないライブラリだったら探すのに苦労したと思いますが、比較的知ってるツールだったのでなんとかなりました。
これはKMC Advent Calendar 2021 - Adventar 2日目の記事です。
List::Utilの pairs 関数をPythonでも使いたくなって、itertoolsの関数を組み合わせて再現できないかと思ったけど、その時点ではうまくできなかった。仕方ないので手作りする。
ちなみに後述の通り、itertoolsの関数で再現する方法があるし、要件によっては組み込み関数だけで再現できる。
pairs 関数についてリスト @xs を受け取り、([$xs[0], $xs[1]], [$xs[2], $xs[3]], ...) のように、要素を2個ずつに区切った配列リファレンス*1のリストを返す。
% perl -MData::Dumper -MList::Util -e 'print Dumper([List::Util::pairs (qw(foo bar baz qux)) ])'
$VAR1 = [
bless( [
'foo',
'bar'
], 'List::Util::_Pair' ),
bless( [
'baz',
'qux'
], 'List::Util::_Pair' )
];
奇数長のリストの場合は、最後のペアの2番目の要素が undef になる。
% perl -MData::Dumper -MList::Util -e 'print Dumper([List::Util::pairs (qw(foo bar baz)) ])'
$VAR1 = [
bless( [
'foo',
'bar'
], 'List::Util::_Pair' ),
bless( [
'baz',
undef
], 'List::Util::_Pair' )
];
Rubyでは Enumberable モジュールに each_slice というメソッドが生えていて、引数2のとき pairs 関数に近い挙動になる。ただし不足値を nil で補うようなことはしない。
% ruby -e 'p %w(foo bar baz qux).each_slice(2).to_a' [["foo", "bar"], ["baz", "qux"]]
Pythonだとペアを返すときはタプルを使うことが多そうなので、そのようにしてみる。要件としては以下の通り。
Pythonのリスト xs を受け取り、(xs[0], xs[1]), (xs[2], xs[3]) のようなタプルを順にyieldするジェネレータを作る。
奇数長のときの挙動はいったん無視する (つまり、再現されてもされなくてもよい)。リストの末尾に None を足せばよいだけなので、必要に応じて None を補完するのは難しくないはず。
一般化するなら、引数として任意のイテレータを取れるとかっこいいけど、そこまでは考えずとりあえずリストのことだけを考える。
pairs_append_yield)素朴には、2要素ずつ一時的なリストに溜めてからタプルに変換する方法が考えられる。以下のようなコードで実現できる。
def pairs_append_yield(xs): buf = [] for x in xs: buf.append(x) if len(buf) >= 2: yield tuple(buf) buf.clear()
pairs_index_access)以下のように、インデックスをちゃんと計算することで短く記述できる。
def pairs_index_access(xs): for i in range(len(xs) // 2): yield xs[2 * i], xs[2 * i + 1]
pairs_slice_copy)リストの先頭2要素をタプルにしてyieldして、残りのリストをスライスしたもので書き換える方法もありますね、と教えてもらった。
def pairs_slice_copy(xs): for _ in range(len(xs) // 2): yield tuple(xs[:2]) xs = xs[2:]
pairs_even_odd)偶奇に着目すれば実現できないか、と一番最初に思いついたのがこの実装。書いた当時は map と filter を組み合わせていたけどさすがに内包表記の方が読みやすいという意見をもらって書き換えた。その通りだと思う。
def pairs_even_odd(xs): evens = (x for i, x in enumerate(xs) if i % 2 == 0) odds = (x for i, x in enumerate(xs) if i % 2 == 1) for even, odd in zip(evens, odds): yield even, odd
(x for x in ...) のように括弧で囲んだものはジェネレータ式なので、リスト内包表記と違って要素が即座に評価されるわけではない。そういえば以前にリスト内包表記の記事を書いていた。
いろいろな方法で実現できるけど、実行速度が気になる。ということで計測する。
以下のようなスクリプト*2を用意して、 M の値を適当に変えてベンチマークを行う*3。ジェネレータを生成するだけだと何も評価されずに一瞬で終わるので、最後にリストに変換することでベンチマークとしている。
def benchmark(M): N = 10000 target_functions = [ 'pairs_append_yield', 'pairs_index_access', 'pairs_slice_copy', 'pairs_even_odd', ] for funcname in target_functions: stmt = f'xs = list(range({M})); list({funcname}(xs))' elapsed = timeit.timeit(stmt, number=N, globals=globals()) print(f'{funcname}\t{elapsed}') if __name__ == '__main__': M = int(sys.argv[1]) benchmark(M)
M = 100 pairs_append_yield 0.15541480000001684 pairs_index_access 0.06048979999968651 pairs_slice_copy 0.15620510000007926 pairs_even_odd 0.16310169999997015 M = 1000 pairs_append_yield 1.3216025000001537 pairs_index_access 0.6861401999999543 pairs_slice_copy 5.359008399999766 pairs_even_odd 1.6237092000001212 M = 2000 pairs_append_yield 2.619715900000301 pairs_index_access 1.4473646000001281 pairs_slice_copy 21.03976220000004 pairs_even_odd 3.3101166000001285 M = 5000 pairs_append_yield 6.534201899999971 pairs_index_access 3.7242138000001432 pairs_slice_copy 137.1054666 pairs_even_odd 8.382808699999714
グラフにすると以下のような感じ。
M が小さいうちは大差ないけど、大きくなるにつれて差が有意に出てきた。とくに pairs_slice_copy がかなり重たく、pairs_index_access が一番速い。
どの方法も、リストの要素数に比例するforループが1つあるので、少なくともO(N)ぐらいの計算量であることは間違いなさそう。
pairs_slice_copy では、元のリストをスライスしたリストで書き換えている。このときにスライスのコピーが発生している分のコストがかかっていることが予想できる。
pairs_even_odd は中間のジェネレータを生成したり、偶奇で条件分岐したりする分のコストがかかっていそう。
pairs_append_yield はリストに要素を追加したりリストをクリアしたりするコストがかかっていそうだけど、上の2つに比べると微々たるものではありそう？
ということで、余分なオブジェクトを作ったり加工したりする必要がないぶん、pairs_index_access がいちばん速かった、ということになる。
Stackoverflowにあると教えてもらった。更によく見るとitertoolsのドキュメント内に grouper という名前で登場していた……。
今回の要件では足りない値を None でfillする必要はないので、少し修正するとこんな感じになるであろう。
def pairs_grouper(xs): args = [iter(xs)] * 2 return zip(*args)
よく見ると、同じイテレータを浅くコピーしている。これによってイテレータの要素をずらして所望の挙動を得ている。賢い……。
速度が気になるのでベンチマークを取ってみる。ここまで最速だった pairs_index_access と比べてどれくらい変わるのだろうか？
def benchmark(M): N = 10000 target_functions = [ 'pairs_index_access', 'pairs_grouper', ] for funcname in target_functions: stmt = f'xs = list(range({M})); list({funcname}(xs))' elapsed = timeit.timeit(stmt, number=N, globals=globals()) print(f'{funcname}\t{elapsed}')
% for m in 100 1000 2000 5000 10000; do echo M = $m; python3 pairs.py $m; done M = 100 pairs_index_access 0.0634912000004988 pairs_grouper 0.023701099999925646 M = 1000 pairs_index_access 0.7986147999999957 pairs_grouper 0.2131203999997524 M = 2000 pairs_index_access 1.4482410000000527 pairs_grouper 0.46308439999938855 M = 5000 pairs_index_access 3.6113817999994353 pairs_grouper 1.1623411999999007 M = 10000 pairs_index_access 7.749021399999947 pairs_grouper 2.4021535000001677
pairs_grouper の方が、pairs_index_access に比べて3倍ぐらい高速だった。予想では pairs_index_access より少し遅くなると思っていたので意外だった。こんなに速い理由は誰か知ってたら教えてください。
言語によっては組み込みライブラリにこういう実装があるのかもしれない。効率的な実装について考えるいい機会にもなった。イテレータ・ジェネレータを使い倒すと高速かつ最小手数で実現できる場合がある。
あと、難しく考えすぎない、肩の力を抜くのも大事だと改めて認識した。深夜テンションで書いたコードは、寝て起きてから再検討するぐらいがちょうどよさそう。
C拡張を書いたら速度を上げられるかもしれないけど、そこまでやることもなさそう。
KMC (京大マイコンクラブ) では、効率的な実装について考えるのが好きな部員を募集しています。KMCに入部制限はありません。どなたでも入部できます。オンラインでも活動しています。
競技プログラミングの勉強会もやっています。
明日はたまろんさんで Rustコンパイラのソースコードリーディング - tamaron's diary です。
*1:厳密にはblessされたオブジェクトだけど、この記事では触れない
*2:完全なスクリプトは https://github.com/utgwkk/20211127-sketch-each-cons-python/blob/main/pairs.py にある
*3:測定環境: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz, 32GB RAM, Ubuntu 20.04 on WSL
