2020-09-13

ISUCON10 参加記

はじめに

2020/9/12に行われたISUCON10に参加しました。そのときにやったことや感想などを備忘録として残します。

チーム構成

最大3人で参加が可能ですが、今年は1人(チーム名: takoshi)で出ました。理由は

誘ったはいいものの何も成果が生まれないと申し訳ない気持ちで死んでしまう(去年がそうだった)
複数人チームと比べたアドとして、1人だと作業のコンフリクトが発生しないので思ったことをすぐ試せる
シンプルに友達が少ない

という感じです。言語はGoかRustで迷いましたが、修正をシュッと反映できそうだったのと、Goのほうが書きなれているのでGoでいきました

やったこと

何をどの順番でやったかはそんなに記憶していないので思い出せる範囲で箇条書き

計測コードを挿入して動かす。初期スコア480くらい
/api/estate/searchと/api/chair/searchが重そうだったのでコードを読むが、自明な改善点が見つからなくて困る。適当にインデックスを張った。
ベンチがバグってたりしてアプリケーションコードの変更が試せなかったので、この時間を使って複数台構成にしておいた。
マニュアルを良く読むとBotからアクセスがいっぱい来るらしいのでnginxで弾くように修正。割とスコアが伸びた。
ベンチマーカーの出力をみると「なぞって検索」のレスポンスおそすぎることがわかった。元のコードでは多角形の内部に物件があるかの判定をMySQLに投げていたが、MySQLはCPU張り付いている状態 & N+1だったのでアプリケーション側でやることに。ここで競プロをした。
相変わらず/api/estate/searchと/api/chair/searchが重いが、ブレイクスルーできるだけの改善は思いつかなくて本当に困っていた。
困ったので色々観察することに徹し、以下のことが判明
- サーバリソースはCPUが1コア、メモリ2G
- mysql専用サーバーのCPUは常に100%近く張り付いていてヤバそう
- アプリのサーバーはCPU/メモリともにかなり余裕がある
- データ更新系のPOSTはそんなにこない
Redisに乗っけるオンメモリ戦略でいくことを決意 (この方針にたどり着くまでにかなり時間がかかった)
リクエストパラメータが一緒ならredisから返す + POSTでデータ更新されたらredisの中身をクリアする処理をいれるとそれっぽいスコア改善があり嬉しい気持ちになる
が、相変わらず/api/estate/searchと/api/chair/searchが重い。リクエストパラメータ単位ではなくもっと細かな粒度でオンメモリにすればスコアが良くなることが想像できたが、そこまでやっている時間がなく最後の方はmysqlやnginxのパラメータ調整 + このブログを書いて終了
最終スコア: 1461 (max: 1503)、凍結前順位: 500チーム中35位前後最終順位: ？位

感想

過去問を解いていたときは予選通過ラインに入れることが多かったのでウッキウキで参加しましたが、結果予選敗退で結構悔しい。反省点はオンメモリ戦略の決断が遅かったことと、限られた時間で粒度を小さくメモリに乗っけれるだけの実装力がなかったことで、このあたりを来年までに改善して予選通過できるようになりたい。

2020-04-30

Topcoder Marathon Match 117 参加記

はじめに

2020/04/23 ~ 2020/04/30に行われたMM117の参加記です．時間を割いて参加できたのでやったことなどを残したいと思います．

問題概要

www.topcoder.com

2次元ルービックキューブのような問題です．問題文に貼られていたGIF画像が非常に直感的でわかりやすかった．

f:id:t-pro-6q:20200430212003g:plain

任意サイズの正方形マスを回転させることができ，各マスが本来あるべき場所に近いほどペナルティが少なくなります．回転させるのにもサイズに応じたペナルティが課されるので，できるだけ少ない回転ペナルティで完成形に近いものを作ることができれば高得点となります．

やったこと

回転させる操作の順番を入れ替えると大きく状態が変わるので，ヒューリスティックに解くならビームサーチ(以下BS)が良さそうというのが第1印象でしたが，グリッドサイズが最大40 $\times$ 40なので，この盤面情報を常に持ちながらBSをするとあまりビーム幅などが出せません．

f:id:t-pro-6q:20200430213713p:plain

雑な図ですが，赤色部分の回転探索を行うときに青色部分の情報はあまり重要そうではなさそうなので，必要最低限の情報を持ちながらBSを行えば擬似的に40 $\times$ 40のBSを再現できそうと考えました．具体的には，ざっくりと7 $\times$ 7のブロックに盤面を分け，各ブロック内でBSを行うという感じです

f:id:t-pro-6q:20200430214004p:plain

各ブロックは少しずつ重ねることで，本来あるべきブロックへの「輸送」もできるようにしました．

BSの行い方ですが，各ブロック内での最適配置になるまでBSを行う -> 次のブロックで最適配置になるまでBSを行う -> etc... という方法ではあまりスコアが伸びませんでした．おそらくですが，最初から最適配置にしてしまうと，後から輸送されてきたブロックを配置するとき，最適な配置を一度崩す->輸送されてきたものを配置するという無駄な動作が発生してしまうからだと思います．最終的に自分の出したコードでは，各ブロック内でのBSを並列に少しずつ進めていくという感じにしました．

BSの評価関数ですが，「本来のペナルティ + Σマスの目的地までの距離のk乗」を採用しました．kはPに応じて変わる係数です(?)．前述の理由より，最適配置のブロックに後からマスを埋め込むのは余分なコストがかかってしまうため，各マスが本来あるべきブロックへ早く輸送できるようにするため，このような形になっています．

以上をいい感じに実装するとこんな感じで動きます．(seed値は3)

MM117
最終的にはこんな感じになった(意味不明)
1: 12
2: 17416
3: 813
4: 32
5: 4493
6: 449
7: 8876
8: 6450
9: 61
10: 3331 pic.twitter.com/U4VCFiWobQ
— たこし (@takoshiiiiiiiii) 2020年4月30日

結果

provisinal 順位: 20位, 相対スコア: 71.80061

各シード値ごとのスコア

12
17416
813
32
4493
449
8876
6450
61
3331

Psyhoさんがぶっちぎって強すぎる...

BSのやり方がよくないのか， f:id:t-pro-6q:20200430223051p:plain

上図のように，ひとつずれてしまう構図が散見されました．これを解消できたらもっとスコア伸ばせそうですが，解消方法がよくわからず...

2019-12-12

Immutableなデータ構造について(Stack, Queue)

この記事はデータ構造とアルゴリズム Advent Calendar 2019 - Qiitaの12日目の記事です．

はじめに

唐突にデータ構造を勉強したくなり，怖そうだからという理由で今まで逃げてきた永続データ構造について勉強したものを一部まとめてみました．本記事の構成はこんな感じです．

Mutable, Immutableってそもそも何
一般的(Mutable)なStackとQueueについて
Immutable Stackについて
Immutable Queueについて(前編)
Immutable Queueについて(中編)
Immutable Queueについて(後編)

Immutable Stackについてはパッと見つけることができましたが，効率の良いImmutable Queueについては自分のググラビリティが低すぎて見つけることができませんでした． Immutable Queueを考察しているときに，「もっと簡単な構造に落ち着くはずでしょ。。。」という気持ちになったので，そういうものがあれば教えていただけると嬉しいです．

Immutableってそもそも何

Mutable Objectは「可変オブジェクト」という意味で，より直感的な説明をすると変更できるオブジェクトのことを指します． Mutableなオブジェクトに何かしらの操作を加えると，オブジェクト自身が変化をします．

f:id:t-pro-6q:20191208104352p:plain

反対に，Immutable Objectはそのまま日本語にすると「不変なオブジェクト」という意味で，変更できないオブジェクトのことを指します． Immutableなオブジェクトに何かしらの操作を加えると，オブジェクト自身は変化をせず，操作を加えた後の新たなオブジェクトを返してくれます． JavaだとStringなどがImmutable Objectとして知られています．

f:id:t-pro-6q:20191208104405p:plain

データ構造をImmutableで持つことの大きなメリットは，

メソッドに渡しても壊されないことが保証されている
ある時点の操作後の情報を遡って取得できる

ということが挙げられるかと思います(個人的には実プログラミングでは前者が，競技プログラミングでは後者が大きいと考えています)．

Immutableなデータ構造を作る際にまず最初に思いつくのが以下のようなものではないでしょうか

注目しているインスタンスのディープコピーを作成する
ディープコピーしたオブジェクトに操作を反映し、返り値として返す

この実装だと，データ構造が管理しているデータの数をNとすると毎回の操作でO(N)かかってしまい効率が悪いです．

本記事では効率が良いImmutable Stack，Immutable Queueの実装について紹介しますが，その前にMutableなStackとQueueについて簡単に紹介します

一般的(Mutable)なStackとQueueについて

そもそもStackとQueueって何ですか？という方はこちらの記事がとてもわかりやすかったので参考にしてください． qiita.com

上記記事でも紹介されていますが，StackとQueueはListが実装されているならば簡単に実装することができます(どちらもpush,pop共にO(1))．

後のImmutable Queue実装に関わってくることですが，Queueに関してはStackを2つ持つことでも実装ができます．

具体的なアルゴリズムはこちら

2つのスタックをそれぞれback，forwardとする(初期値はそれぞれ空のスタックとする)
push(a)の操作がされたら，backのスタックにaをpushする
pop()の操作がされた場合，forwardの状況に応じて以下のように場合分けする
- forwardが空の場合: backが空になるまでpop()し，pop()した順番にforwardにpush()する．その後，forwardをpop()したものを返す
- forwardに要素がある場合: forwardをpop()したものを返す

3番目の「forwardが空の場合」で何をやっているかというと，「先入れ後出し」の性質(Stack)を「先入れ先出し」の性質(Queue)へと変化させています．

f:id:t-pro-6q:20191207164816p:plain

スタックを2つ持つ実装の時間計算量ですが，反転させる操作が最悪O(N)かかるので，全体でO(N)かかるように見えますが，各要素は高々1回しか反転操作をされないので，償却時間計算量はO(1)になります． Listを使って実装した場合はpush，popどちらの操作もO(1)になるので，stackを用いたqueue実装のほうが効率は悪くなってしまいますが， Immutable Queueを手軽に実装しようとすると，ここで紹介したような感じの実装になります．

Immutable Stackについて

Immutable Stackの基本的な考え方は，Immutable Stackにpushするオブジェクトはグローバルに共有し， Immutable Stackの各インスタンスは，オブジェクトがどのように連結(接続)しているかを管理します．

具体的な実装方法は先人様のレポジトリを参照くださいmm github.com

動作例はこちら

public class Main {
  public static main() {
    ImmutableStack q0 = new ImmutableStack();
    ImmutableStack q1 = q0.push(1); // q1は緑
    ImmutableStack q2 = q1.push(2); // q2はオレンジ
    ImmutableStack q3 = q1.push(3); // q3は黄
    ImmutableStack q4 = q3.push(4); // q4は紫
    ImmutableStack q5 = q2.pop(); // q5は黒 
  }
}

f:id:t-pro-6q:20191207143300p:plain

各インスタンスは色付きの枠でオブジェクトの接続情報を管理しているイメージです．例えばq3(黄)に管理するオブジェクト(4)をpushしてq4(紫)を作成する場合は，q3への参照と管理するオブジェクト 4への参照の2つを持ち，オブジェクト自体は全インスタンスで共有して参照することで，ディープコピーをせずにImmutable Stackを実装できます． (ただし，head()などでオブジェクトへアクセスし，管理しているオブジェクトがMutableな場合はオブジェクトのディープコピーをする必要があります)

こちらのImmutable Stackの時間計算量はpush, pop共にO(1)になっています．StackをImmutableにしても計算量が変わらないのは個人的に面白いなと思います．

Immutable Queueについて (前編)

Immutable QueueもImmutable Stackと基本的な考え方は同じで，pushするオブジェクトはImmutable Queueの全インスタンスで共有し，オブジェクトの接続情報を各インスタンスが管理するという形で実装をします．

一般的(Mutable)なStackとQueueについてで紹介しましたが，Mutable QueueはMutable Stackを2本持つことでも実装をすることができました．なので，Immutable QueueについてもImmutable Stackを2本もつことで実装できます．アルゴリズムについては一般的(Mutable)なStackとQueueについてで紹介した方法と全く同じなので省略します． (Immutable Stackの章でリンクを貼らせていただいたレポジトリの中にImmutable Queueの実装もあります)

1回の操作(popやstack)に対し，Mutable Queueの償却時間計算量はO(1)だったので，Immutable Queueの償却時間計算量もO(1)になりそうですが，悪意に満ちた入力が来た場合はImmutable Queueの時間計算量はO(N)になってしまいます．

悪意に満ちた入力例の一例を以下に示します． f:id:t-pro-6q:20191207151917p:plain

各インスタンス $q_i$ は緑の枠で囲まれた部分と，オブジェクト $N/2 + i$ を参照としているとします．あるインスタンス $q_i$ でpop操作が行われると，一般的(Mutable)なStackとQueueについてで紹介したように反転処理が走ります．が，オブジェクトの接続情報(順番)は各インスタンス毎に管理されているため， $q_i$ 以外のインスタンスがpop操作をする場合は再び反転処理が走ってしまいます．上図の場合，各インスタンス $q_i$ が全てpop操作を行うと，各pop操作で $N/2$ 回反転処理が起こります．

したがって，ここで紹介したImmutable Queueの時間計算量はpushがO(1), popがO(N)となります．

Immutable Queueについて (中編)

前編で紹介した方法ではpop操作がO(N)となっており，データ構造警察に見つかれば逮捕されてしまいます． O(N)となってしまう原因は，各インスタンスがそれぞれ独立してオブジェクトの接続情報(順番)を保存していることにありました．ならばいっそのこと，オブジェクトの接続情報をグローバルに管理してしまえばこの問題は回避できそうです．より具体的には，接続情報を木構造でグローバルに管理し，各インスタンスはQueueのhead(H)とtail(T)を管理します．

push操作とpop操作は次のような実装します．

push操作: push操作を行うImmutable Queueのインスタンスをins, pushするオブジェクトをobjとしたとき，objをins.tailの子要素として接続し，(ins.head, objの参照)を返す
pop操作: pop操作を行うImmutable Queueのインスタンスをinsとしたとき，(ins.headの子要素で，かつins.tailに繋がるオブジェクトへの参照, ins.tail)を返す

具体的な動作例は次のようになります． f:id:t-pro-6q:20191207155321p:plain (Queueなのでpopをするとheadが移動することに注意してください)

ここで，pop操作の「ins.headの子要素で，かつins.tailに繋がるオブジェクト」を特定する部分がボトルネックとなってきます．接続情報が木構造となっているので，子要素から先祖の要素へは簡単に辿ることができますが，親要素から特定の子孫の要素へ辿るパスを特定することは簡単にはできません．これは，接続の向きが子要素から親要素に向いているので難しいということではなく，子要素は親要素を高々1つしか持たないが，親要素は子要素を複数持つことがあるからです．

したがって，popをするたびにins.tailから親要素を辿っていき，ins.headの次の子要素を特定する必要がありますが，ここで最悪O(N)かかってしまいます．残念!

このままだと計算量の改善ができていませんが，木構造となっているので子要素から親要素へ2冪のインデックスを貼る(ダブリング)と高速に親要素へ辿ることができます．

ダブリングについてはこちらの記事をご参照ください． satanic0258.hatenablog.com

ざっくりと2冪のインデックスを説明すると，各要素について1つ上の親，2つ上の親，4つ上の親，...，2ⁿ上の親，...への参照を持っていると，子要素から特定の親要素への遷移がO( $logN$ )でできるというものです．また，新しい要素が挿入された時，その要素へ2冪のインデックスを貼るのもO( $logN$ )でできます．

ここまでを実装すると，push・popの時間計算量がO( $logN$ )になりました．pushした時に2冪のインデックスを貼る必要が生じるので，前編で紹介したImmutable Queueと比べるとpush操作の時間計算量が悪化していますが， $O(logN)$ は実質定数(過激派)なので時間計算量が改善しました．

Immutable Queueについて (後編)

ここまでは主に時間計算量，つまり一回あたりの操作でどれくらい計算時間がかかるかに注目してました．この章ではImmutable Queueが消費するメモリについて注目してみたいと思います．

Immutable Queueについて考察する前に，まずはImmutable Stackが消費するメモリ量を確認したいと思います． f:id:t-pro-6q:20191207143300p:plain

上の図はImmutable Stackについてで用いたImmutable Stackの動作例です．ここで，オレンジの枠で囲まれているインスタンス(1,2から構成されているスタック)が破棄されたとします．すると，2を参照しているインスタンスが存在しなくなるので，JavaのGCや参照カウンタ方式の言語では2を表すオブジェクトのメモリを解放してくれます． Immutable Stackでは，どのインスタンスからも参照されなくなり，今後使用されることがなくなったオブジェクトはいい感じにメモリが解放されます．

Immutable Queue(前編)で紹介させていただいたImmutable Queueは，Immutable Stack2つで動いているので，Immutable Stackと同様，今後使用されることがなくなったオブジェクトはメモリが解放されます．

Immutable Queue(中編)で考察したImmutable Queueにおいては，今後使用されることがないオブジェクトであったとしてもメモリが解放されないことがあります．

f:id:t-pro-6q:20191207173714p:plain

左側のような状況の時に，解放されるべきオブジェクトを灰色で表したものが右の木になります．

このうち，5と7については誰からも参照されなくなったので勝手に解放されます．一方で，1と3については今後必要ないオブジェクトですが，インスタンスからは到達可能なオブジェクトなのでメモリが解放されません．

解放できるオブジェクトとは，どのインスタンスの(head,tail)のパス上にも存在しないオブジェクトになります(上図だと2-6-8が緑のパス，4がオレンジのパスになるので，それ以外の1,3,5,7が解放できるオブジェクトとなる)．

オブジェクトの解放判定に全てのオブジェクトを走査しても良いとするならば，葉から順番にimos法の考え方を適用していけば解放できるオブジェクトを特定できます．

imoz.jp

オブジェクトを解放するときに，先ほど利用した2冪のインデックスも外していく必要があります．オブジェクトの数をN個とすると，インデックスの数はO( $NlogN$ )となるので，1つのオブジェクトのインデックスを外す償却時間計算量はO( $logN$ )になります．接続情報を外す償却時間計算量も同じような考え方でO(1)，imos法の時間計算量はO(N)なので，全体でO( $NlogN$ )となります．逮捕!!!

1回のpush, pop操作毎に解放するオブジェクトを特定するのではなく，複数回操作を行なった後に使わないオブジェクトを特定するというやり方を行えば，時間計算量を削減できそうです．より具体的には，現在管理しているデータの個数をN個としたとき，push, popの操作がN回行われたタイミングで管理しているオブジェクトが解放できそうかを判定・解放していきます．push, pop操作がN回行われるとオブジェクト解放判定が1回走り，1回あたりのオブジェクト解放判定はO( $NlogN$ )かかるので，1回の操作におけるオブジェクト解放判定・解放操作の償却時間計算量はO( $logN$ )となります(ほんまか？)．

ここまでの話をまとめると，Immutable Queueは頑張って実装をするとpushがO( $logN$ ), popがO( $logN$ )になるので，データ構造警察署から無事に釈放されました!!! 間違ってたら再逮捕で!!!

まとめ

競技プログラミングでImmutable Stackを使う問題は見たことがありますが，Immutable Queueを使う問題は見たことがありません．また，実プログラミングでもImmutable Queueを使うことはおそらくないので，ここで紹介したImmutable Queueの参考実装はありません(は？)．最後になりましたが，ここまで駄文を見ていただきありがとうございます．最後のオブジェクト解放うんぬんの話はだいぶ怪しいのでコメント等で間違いを指摘していただけるとありがたいですmm

2019-10-19

【Spring boot】RestControllerのレスポンスボディにThymeleafで動的に値を埋め込んだhtmlを含める

背景

(タイトルがわかり辛すぎるので背景から...)

Spring bootは@RestControllerをつけたクラスのメソッドの返り値がそのままレスポンスボディになります

@RestController
public class HelloRestController {
  @RequestMapping("index")
  public HelloModel index() {
    return new HelloModel(200, "Hello, world!");
  }
}

@Data
@AllArgConstructor
public class HelloModel {
  private Integer status;
  private String message;
}

この場合，indexにGETリクエストを送れば下記のようなレスポンスが得られます

{
  status: 200,
  message: "Hello, world!"
}

ところで，一般的なwebアプリはhtmlの描画をサーバーサイドでやる同期的な描画と，javascriptで非同期通信をし，取ってきたデータをクライアント側で描画する方法に分けることができるかと思います．ここで，javascript側での描画処理を極力抑えて，ほぼすべての描画をサーバーサイドでやりたいという欲が生まれることがあります．理由は色々ありますが，サーバーサイドで描画を行う方法に統一することでテンプレートがサーバーサイドに集約されて保守がしやすいといったことが挙げられます．

Spring bootのサーバーサイドレンダリングは@Controllerを使います．

@Controller
public class HelloController {
  @RequestMapping("index")
  public String index(Model model) {
    model.addAttribute("message","Hello, world!");
    return "index";
  }
}

index.html

<!doctype html>
<html xmlns:th="http://www.thymeleaf.org">
<head>
    <meta charset="UTF-8" />
    <title>Hello World</title>
</head>
<body>
<p th:text="${message}"></p>
</body>
</html>

ここで，たとえば

{
  status: 200,
  message: "ここにthymeleafで動的に描画したものを埋め込みたい"
}

というレスポンスを返したい場合，どのように実装すればいいのかというのをこの記事では紹介します． (調べた限り，Spring Bootの標準的な機能としてこのような使い方が見当たりませんでした．もし標準的な機能で出来る場合はコメントにてご指摘いただけると幸いですmm)

結論

こちらのレポジトリに参考実装を置いてあります． github.com

仕組み

Spring BootにおけるControllerの動き

詳しくはこちら terasolunaorg.github.io

レンダリング処理のポイントは以下の2点です

ViewResolverが描画で使うテンプレートを決定し，Viewインスタンスを返す
ViewがModelを受け取って値を動的に埋め込む

RestControllerでも同じ動きを模倣してあげれば動的に埋め込まれたものを生成することができるので，あとはこれを必要に応じてレスポンスの一部に加えてあげれば良いです．

2018-12-18

あると便利なマラソン用ジャッジ環境について

まえがき

(当ブログに掲載された内容によって生じた損害等の一切の責任を負いかねますので、ご了承ください。)

これは Competitive Programming Advent Calendar 2018 18日目の記事です

topcoder marathon matchやchokudai contest等のマラソン系コンテストに取り組む上で、

テスト環境を作るのが面倒
大量のテストケースでプログラムを動かして結果を見たいけど、ローカルのパソコンが可哀想だからあんまりやりたくない
プログラムのスコアをコメント付きでうまいこと管理したい
パラメータ調整を手動でやるのが辛い

等々の課題があります。プログラムのスコアはジャッジに投げることで管理すればええやんという気持ちもありますが、例えばtopcoderの場合は一度提出してから2時間は間を空けないといけなかったりするので、もっと手軽に投げれる環境があればそれに越したことはないよね！あと開発経験積みたいね！

ということで作った時の苦労・嵌った罠とかいろいろ書いておくので、自分用ジャッジ環境を作成したい人の参考になればとっても嬉しい😀

2018-05-27

SECCON Beginners CTF 2018 write up

CTFは前から興味があったけど、界隈に生息している人たちに対して怖そうなイメージを持ってたのでコンテストに出たことなかったけど、初心者向けということでゆるふわチームを作って参加した。やってみた感想としてはこれが初心者向けなのか...という気持ちになりました。以下かろうじて解けた問題

2017-10-28

ハル研究所プログラミングコンテスト2017 参加記

はじめに

3年前から参加し始めたハル研究所プログラミングコンテストに今年も参加しました。マラソン形式のコンテストに久々に参加できたのと、1年以上ブログを更新しないのは如何なものかと思ったので参加記を残します。最終結果はまだですが、暫定順位は16位でした。(最終順位はきっともう少し上がってくれると信じてる)

たこし++の備忘録

競技プログラミングの備忘録

ISUCON10 参加記

はじめに

チーム構成

やったこと

感想

Topcoder Marathon Match 117 参加記

はじめに

問題概要

やったこと

結果

Immutableなデータ構造について(Stack, Queue)

はじめに

Immutableってそもそも何

一般的(Mutable)なStackとQueueについて

Immutable Stackについて

Immutable Queueについて (前編)

Immutable Queueについて (中編)

Immutable Queueについて (後編)

まとめ

【Spring boot】RestControllerのレスポンスボディにThymeleafで動的に値を埋め込んだhtmlを含める

背景

結論

仕組み

Spring BootにおけるControllerの動き

あると便利なマラソン用ジャッジ環境について

まえがき

SECCON Beginners CTF 2018 write up

ハル研究所プログラミングコンテスト2017 参加記

はじめに