isyumi_netブログ

isyumi_netがプログラミングのこととかを書くブログ

尺取り法の最強ライブラリを作った。

僕は水色コーダーでありながら尺取り法がとても苦手である。
ミスりやすい。
そこでこの度、尺取り法の最強ライブラリを作った。

 

尺取り法の難しさ

実装上の注意として2つの点が挙げられる。

  1. どの尺にも入れない要素がいる
  2. LeftがRightを追い越す時の処理。

 

1.どの尺にも入れない要素がいる

例えば和が100以下の尺を数え上げる問題で、200の要素が混じっていたりすると、その前後の処理が複雑になる

2.LeftがRightを追い越す時の処理

LeftとRightを追い越す時に、Rightを追従させなければいけない。この時の処理を忘れがちである。

時には1と2が同時に起きることもある。非常に辛い

 

解決

尺が存在する区間を列挙

まず、単体で条件を満たす要素を列挙する。
そして、尺が存在する区間を列挙する。
たとえばこの数列から和が8以下の尺を列挙するとする

{ 1, 2, 8, 10, 3, 4, 6}

単体で存在可能な要素は{1, 2, 8, 3, 4, 6}なので、
尺が存在する区間は{1, 2, 8}と{3, 4, 6}である。
この2つの区間をそれぞれ処理すればいい。
この時点で、1のどの尺にも入れない要素がある問題はクリアできた。

尺が存在する区間の始まりをハンドリングする

次に、2の問題はライブラリが区間の開始イベントを送ってくれると解決する。
区間が始まるタイミングは3つだ

  • 配列の最初の要素
  • 自分の左がどの尺にも入れない要素
  • 左が右を追い越した時

プログラマは、区間の開始を知らされた時に尺を初期化すればいい。

 

実装

プログラマは以下の6個のイベントハンドラを処理すればいい。

  • この要素は単体で条件を満たしているか?
  • 左を固定して尺を初期化しろ
  • 右に1個伸ばせるか?
  • 右に1個伸びろ
  • 左を1個捨てろ
  • 区間が確定した

 

ライブラリ

void tow_pointer(int n,
function<bool(int left)> check_begin,
function<void(int left)> begin,
function<bool(int right)> check_right,
function<void(int right)> push_right,
function<void(int left)> pop_left,
function<void(int left, int right)> dead_end
) {

auto go = [&](P range) {
int right = -1;
for (int left = range.first; left <= range.second; left++) {
if (right < left) {
right = left;
begin(left);
}
while (right + 1 <= range.second && check_right(right + 1)) {
right++;
push_right(right);
}
dead_end(left, right);
pop_left(left);
}
};


auto get_ranges = [&] {
vector<bool> enable_items(n);
rep(i, n) enable_items[i] = check_begin(i);

auto start = [&](int i) {
if (i == 0) {
return enable_items[i] == true;
}
if (!enable_items[i - 1] && enable_items[i]) {
return true;
}
return false;
};

auto end = [&](int i) {

if (i == n - 1) {
return enable_items[i] == true;
}

if (enable_items[i] && !enable_items[i + 1]) {
return true;
}

return false;
};

vector<P> ans;
P p;
rep(i, n) {
if (start(i)) {
p = P(i, -1);
}
if (end(i)) {
p.second = i;
ans.push_back(p);
}
}
return ans;
};


vector<P> ranges = get_ranges();
for (P range: ranges) go(range);
}

使い方

例えばこんな感じで使える

https://atcoder.jp/contests/abc032/tasks/abc032_c

 

int main() {
int n;
ll k;
cin >> n >> k;

vector<ll> numbers(n);
rep(i, n) cin >> numbers[i];

if (find(numbers.begin(), numbers.end(), 0ll) != numbers.end()) {
cout << n << endl;
ret();
}
ll sum = 0;

// この要素は単体で条件を満たすか?
auto check_begin = [&](int left) {
return numbers[left] <= k;
};

// leftを左として尺を初期化しろ
auto begin = [&](int left) {
sum = numbers[left];
};

// 右に1個伸びれるか確認しろ
// 次の「1個右の要素は」right
auto check_right = [&](int right) {
return sum * numbers[right] <= k;
};

// 右に1このびろ
// 次の「1個右の要素は」right
auto push_right = [&](int right) {
sum *= numbers[right];
};

// 左を1個捨てろ
// 捨てる左の要素はleft
auto pop_left = [&](int left) {
assert(sum % numbers[left] == 0);
sum /= numbers[left];
};

ll ans = 0;

// 尺が伸びれるところまで伸びた
auto dead_end = [&](int left, int right) {
ll now = right - left + 1;
cmax(ans, now);
};


tow_pointer(
n,
check_begin,
begin,
check_right,
push_right,
pop_left,
dead_end
);
cout << ans << endl;

}

このあたりを見てほしい。

https://atcoder.jp/contests/abc032/submissions/11171624

https://atcoder.jp/contests/abc038/submissions/11171673

https://atcoder.jp/contests/arc022/submissions/11171696

https://atcoder.jp/contests/abc098/submissions/11171718

 

サンプル自動生成力があれば時々青問題が解ける

昨日のAtCoder Grand Contest 043でB問題を解いて2完できた。うれしい。
水色コーダーには望外で僥倖だ。

https://atcoder.jp/contests/agc043/tasks/agc043_b

僕は稀にこの手の青難易度問題を解いてしまうことがある。そのテクニックを紹介しよう。

やること

  • 愚直解を書く
  • テストケースを自動生成するコードを書く
  • For文で小さいケースから順番に全部試す
  • プリントする

昨日のB問題は8桁くらいを一瞬でprintできる。

この手の問題は絶対に簡単な規則性があるので、ずーと眺めていたら何か見つかるかもしれない。

昨日の問題は、「2段目以降は、nが偶数ならトーナメントにして解いても同じ結果になる」ということに気づいた。愚直解なら1段につき1要素しか減らないのでo(n^2)になってTLEだが、トーナメントにして1段を半分にしていいならo(log n)になるのでACできる。ということは、あとはnが奇数の時だけ考えればいい。奇数の時も簡単だ。1段を愚直解すれば長さが偶数になる。

 

// 一段減らす
vector<int> sub(vector<int> &v) {
if (v.size() == 1) return v;
vector<int> v2(v.size() - 1);
rep(i, v.size() - 1) {
v2[i] = abs(v[i] - v[i + 1]);
}
return v2;
}

// 半分にする
vector<int> tournament(vector<int> &v) {
vector<int> next;
for (int i = 0; i < v.size(); i += 2) {
int a = abs(v[i] - v[i + 1]);
next.push_back(a);
}
return next;
}

// 偶数なら半分にする
// 奇数なら一段減らしてから半分にする
int solv(vector<int> v) {
while (v.size() != 1) {
if (v.size() % 2 == 0) {
v = tournament(v);
} else {
v = sub(v);
}
}
return v.front();
}

 

提出前にすること

「多分解けたな」と思ったら、せっかくなのでさっき作ったテストケース自動生成コードを使って確認してほしい。小さいサンプルで、愚直解と同じ結果になるか試すのだ。結構地味なコーナーケースを検出することがある。大体こういう問題はnが極端に小さい時に例外がある。昨日の問題なら2231の時だけこの方法ではうまくいかないことが検出できた。小細工をして通した。逆に言えば、nが小さいケースを全部通せたらだいたいACできる。

その他

愚直解も実装が複雑な問題であれば、TLEになることが分かっていても愚直解をジャッジに投げてほしい。その勇気も必要だ。ペナルティはたかが5分だ。間違った愚直解で時間を失うよりましだ。

 

おススメ

このブログに感化された緑・水色コーダーの方は、ぜひこのやり方でこの問題を解いてみてほしい。
頭で考えるとめちゃくちゃ難しい問題だが、小さいケースからprintしていけば超簡単だ。
https://atcoder.jp/contests/abc059/tasks/arc072_b

 

Web広告系のトラッキングタグは何でこんなに遅いんだ。

お仕事でECサイトを作った。
僕はWebページの高速化が得意だ。
広告系のトラッカーを入れるまではPageSpeed Insightsが97点だった。

 

それから言われたサードパーティの広告系のタグを入れた。
FacebookのトラッキングタグにYahoo広告のトラッキングタグに......その他いろいろ。

 

それらを入れただけでPageSpeed Insightsが80点を切った。
ため息が出る。
もう少し気を使ってくれ。
Google Analyticsくらいは良い奴だと思っていたのに。

 

こういうのは全部WebWorkerに持っていく流れにならないかな。

 

もしくは、どうせサードパーティCookieは消されていくんだし、サーバーサイドからログを送信する方向になってほしい。サーバーからIPとUAとURLを送れば大体事足りるでしょう。

AtCoderの精進管理ツールを作った

AtCoder水色になりました。
丁度ABCを全埋めしたタイミングでした。
ABCを全埋めしたら水色くらいなれるという言説があるようですが、ある程度確からしと思います。

さて、僕はAtCoderで二周目に入ろうと思いました。
AtCoder Problemsは緑色に染まってしまったので、二周目以降の進捗を管理できるツールを作りました。

atcoder-chart.net

 

問題と難易度のデータはAtCoder ProblemsさんのAPIを使わせていただきました。

解けた問題は○をつけ、少しでも詰まった問題は△を付けます。
次回以降は△を付けておいた問題だけを解いていきます。

なぜこんなものを作ろうと思ったのか。
僕はチャート式を使って数学の勉強をする感覚でAtCoderを使うのがいいと思っています。
頑張って難しい問題に挑むより、解答方法丸暗記でもいいから低難易度の問題は必ず全部解けるようにしたほうが成長が速いのではないかと考えています。

 

僕は水色コーダーです。
自分は今まで「茶色問題までなら瞬殺できる。緑色問題もちょっと考えたら解ける」と思っていました。
しかし、このツールで記録を付けながら二周目をした所、驚くことが分かりました。
実は茶色問題でも1/3くらいは悩んだり間違えたりしていました。緑問題の中にも解説を見ないと解けない問題がそこそこありました。
二周目なのに!
一周目の僕は緑色問題が解けたら「緑色余裕!」と思い、解けなかったら「今のはたまたま運が悪かった」と思っていました。実は「運が悪かった」が1/3以上を占めていたのです。運ではなく実力不足です。

あなたも、○○色くらいなら瞬殺出来ると思っているはずです。多分大して解けてないと思います。

僕と同じように、下位問題を全部潰しておきたい人はぜひ使ってください。

CSSの競技プログラミングを作りたい

最近競技プログラミングというものを始めた。

これは大変素晴らしい。
自分の練習のための教材になるし、他人のスキル感を大雑把に掴むことが出来る。
あらゆる技能についてこういう仕組みが備わっていくべきだ。

ところで、最近マークアップエンジニアの募集をせねばならなくなった。HTMLとCSSを書くお仕事の募集だ。

マークアップエンジニアも難しい仕事だ。僕はHTMLのセマンティクスを重視したHTMLを書いてほしいと思っている。そして変更に強いCSSを書いてほしい。様々な画面サイズで意図したとおりに表示してほしい。パフォーマンスについても最低限の理解をしてほしい。Pictureタグとか。deferとか。古いブラウザのことは考えなくていいと思っているが、モダンブラウザ間の差異の吸収の仕方は知っておいてほしい。

専門学校に募集をかけようという話になったことがある。その場にいた専門学校卒の人がこういった。「専門学校には一つのクラスに2、3人だけ凄い人がいて、それ以外は本当に何もできない」。そんな人を引き当ててしまったら困る。まともな人を見分けたい。

マークアップエンジニアのスキルを測るのは難しい。一般的に作品を見せてもらうということにしているらしい。しかし、この方法は問題が多い。まず、どれくらい時間をかけて作ったのかわからないということだ。そして、網羅的な知識を持っているか判断しづらい。
応募者側も、何を作ったら認めてもらえるのかわからないから困っちゃうだろう。つまり、こちらは、基礎技術が有るか無いかを見たいのに、応募者側はネタを見せたくなっちゃうというギャップがある。

だったら、明確なお題がある方が混乱させないだろう。

そこでこういうシステムを考えた。

AtCoderみたいに時間を決めてコンテストを開催する。
問題はワイヤーフレーム形式で出題される。
色や影や角丸の指定がある場合は、画像だとわかりにくいので文章で伝えたほうがいいだろう。
提出されたHTMLとCSSサーバーサイドでレンダリングする。Headless Chromeなどを使えばいいだろう。この時、様々な画面サイズを指定してレンダリングする。
そして、何かしらの判定技術で正誤を付ける。画像処理的に採点するという方法があるし、各DOM要素のclientHogeをチェックしていく方法でもいいだろう。
最後に、正解にかかった時間を元にレーティングを付ける。

こういうアイディアも考えた。
1問提出するごとに、変更依頼が発生するといいのではないか。
AtCoderは1問目と2問目は全く関係ない問題になっていることが多いが、あえて1問目と2問目に繋がりを持たせる。すると、変更に強いマークアップが出来るほど有利になる。

これは採用に困ってる企業からお金を貰えそうだ。

 

2019年の振り返り

去年、人生の五カ年計画を描いた。

 

blog.isyumi.net

 

このとき僕は25歳で30歳までに到達したい目標を書き出したものだ。

26才の一年間でどれだけ達成できたか振り返ってみる。

達成したこと

善処した上で諦めたこと

五箇年計画から外そうと思ったこと

  • レッドコーダーになる

  • 数学検定一級

来年の課題

  • イエローコーダーになる

  • LPIC Level3になる

再来年以降に持ち越す課題

  • TOEIC 800点

  • Webフロントエンドのベストプラクティスホスティングサービスを作る

  • Google Cloud Certified

  • データベーススペシャリスト

  • セキュリティスペシャリスト

  • 年収1000万になる

  • CPUを作る

  • OSを作る

  • 言語を作る

  • RDBの理論面を勉強する

  • 型システムの理論面を勉強する

  • 素晴らしい数式処理システムを作る

  • 暗号論を勉強する

  • 新しいWebの仕様を策定しバーナーズリーの後継者になる

  • 絵を描けるようになる

  • 何か楽器ができるようになる

新しく追加する課題

  • 宣言的に非正規化できるツールを作る

総評

思ったより数学検定準一級にてこずったため人生が遅れた。

もう一級は諦めようと思う。

応用情報技術者ネットワークスペシャリストを連続撃破できたのは嬉しい。

AtCoderを始めた。去年の段階で気前よく「レッドコーダーになる」などと恥ずかしいことを言ってしまった。いざ始めてみると、全力で頑張っても黄色が限界だと思った。

去年の段階でぼんやりしていたWebアプリケーション開発の未来像が見え始めてきたので、いくつかの目標を削除してより具体的な目標を入れた。

僕は今年、Webアプリケーション(スマホアプリ含む)開発の生産力を100倍にする方法を見つけたかもしれない。どんなフレームワークがあれば100倍の速さでWebアプリケーションを作れるか分かった気がする。だから、僕はそれを実現することをライフワークにしようと思った。

最強のサーバーサイド・フレームワーク『イシュミ・デルティスト』

 

Diff as a Service

差分を扱うのが得意なサーバーサイドフレームワークを作りました。

 https://github.com/rikuTanide/isyumi_deltist 

概要

僕はFirestoreにViewを作る!

問題意識

Firestoreはどこまで正規化するべきか問題があります。
バックエンドを書いている時の僕はできるだけ正規化したい派です。
しかし、クライアントを書いている時の僕はそのまま表示できる形式で渡してほしい派です。
また、僕は「非正規形のデータを直接いじるプログラムを書くと絶対間違える」という硬い信念を持っています。
なので、非正規形データは正規形データから純粋関数で展開するべきだと思います。

解決策案

単純な解決策

正規化したデータと非正規化したデータを別々にFirestoreに保存する。正規形データが変更されたら非正規形データをまるごと更新する
豪快にやっちゃいます。
データ量が少ないなら一番簡単な方法です。
しかし、データ量が増えてきたら無理です。read/writeの遅延や課金が大きくなります。

現実的な解決策

正規化したデータと非正規化したデータを別々にFirestoreに持つ。正規形データが変更されたら非正規形データを更新する 。ただし、どの正規形データへの更新がどの非正規データに伝播するか細かくプログラミングする

今の所の最善策だと思います。

このやり方には2つの欠点があります。
一つはテーブルとビューの依存関係を洗い出すのがめんどくさいことです。どのテーブルへの変更がどのビューのどの行に影響するかを確実に洗い出すのは難しいことです。

もう一つは、最適化をしたいならコードを沢山書かないといけないことです。例えば商品ごとの売上なら、売上が発生するごとに売上一覧を集計して出すより、前回の計算結果に今回の売上を加算したほうが速いです。
このような最適化の余地はたくさんありますがめんどくさいです。

夢想的な解決策

全部オンメモリでビューを計算する

まず、全てのテーブルを元に全てのビューをつくる関数を一つ用意します。
メモリに現在のテーブルを載せておき、どこかに変更が発生したらその関数を実行します。
そして前回作ったビューと今回のビューの差分をチェックしてFirestoreを更新しに行けばいいかと思います。
この方法の最大の欠点はメモリ使用量です。
EC2でも、2~4GBよりたくさんのメモリを使えるインスタンスは高いです。

最終解決策 イシュミ・デルティスト

そこで僕は、フレームワークを作りました。

プログラマはこの2つをします。

  • 正規化したテーブルのスキーマDSLで記述
  • テーブルを非正規形に展開する宣言をDSLで記述

フレームワークはこれをします。

  • 起動時
    • JSONなどでエクスポート出来る形式でビューを実体化する
  • テーブルの変更イベント受信時
    • ビューを差分更新する
    • どんな差分が発生したのかを出力する

テーブルとビューのデータはディスクに保存してあるのでメモリをほとんど使いません。
また、どのビューのどの行がどのテーブルのどの行に依存しているかについて細かい依存グラフを作成しているので、最短距離で差分更新できます。

あとは、このフレームワークが返してきたDIFF情報をそのままFirestore APIに書き込めばOKです。
Viewができた!

使い方

デルティストは単純なステートマシンです。
ReduxのReducerに似ています。
Tableへの書き込みイベントを引数にビューの差分が帰ってくる関数です。
返ってくるのは新しいビューではないです。
その中で変更があった行だけが返ってきます。
疑似コードですがこんな感じに動きます。

売上一覧テーブルに鉛筆の売上を挿入したら「月ごとの売上合計ビュー」と「商品ごとの売上ビュー」が1行ずつ変更された
void main() {
  var db = new Database();
  var diff = db.insert("Sales", {productID: 'pencil', date: '2019-09-01' });
  print(diff); 
  
}

出力
[
 {
   viewName: 'SalesParMonth' ,
   data: {year: 2019, month: 8, sum: 1000},
 },
 {
   viewName: 'SalesParProducts',
   data: {productID: 'pencil', productName: '鉛筆', sum: 500 }
 }
] 

Firestoreで使うことを想定していますが、入出力は単純な構造体なので何にでも使えます。
ブラウザからWebSocketで直接つなぐこともできますし、MySQLにMaterialized Viewを作る用途で使うこともできます。

ディスクを使うのでLambdaやGAEなどで使うことはできません。
EC2インスタンスが一つ必要です。

ロードバランスやSPOF回避の仕組みは何も考えていません。

実装方法

デルティストはビューを作る途中の仮想テーブルも全てビューとみなし実体化してディスクに保存しています。
デルティストでは3個以上のテーブルやビューをJOINする方法はありません。JOINは2個に限ります。
3個以上のテーブルやビューをJOINしたければパラマス式トーナメントにします。
そしてそれぞれを実体化します。
例えば4個のテーブルをJOINしてビューを作るなら、合わせて3つビューが実体化されることになります。
下の図の場合、本当にほしいビューがView3ならこうなります。

Table1 -┐
        |-View1┐
Table2 -┘      |-View2-┐
Table3 --------┘       |-View3-
Table4 ----------------┘

テーブルが更新されると、ビューに行変更イベントを通知します。
受け取るのはテーブルに直接依存しているビューだけです。
変更イベントを受け取ったビューは、そのイベントを元に自分を変更しないといけないかどうかを判断します。
もし変更があった場合は自身を書き換えてから行変更イベントを作成しディスパッチします。
それを再帰的に行うと全てのビューが更新されます。
この時の重要なのが、最小コストでビューを更新出来るようにすることです。
例えば、TweetsテーブルとUsersテーブルをJOINしてTimelineビューを作るとします。Tweetsテーブルに一行挿入されたらUsersテーブルからそのTweetのuserIDと一致するUsersテーブルの行だけを取得してJOINしてTimelineビューに挿入します。
逆にUsersテーブルから行が削除されたらTimelineビューの中でuserIDが一致するツイートだけを削除します。

実体化したビューはRocksDBというデータベースで保存します。
RocksDBはKVSです。
TableとViewのPrimary Key == KVSのKeyです。
DBサーバーではなくCのライブラリとして使えるので運用が楽です。
デルティストは1万行の中の1行を書き換えるような処理が多いので、RocksDBのLSM-Treeというアルゴリズムと相性がいい(らしい)です。詳しくは知りません。

大変だった点

DartC++インテロップ

始めてDartC++インテロップを書きました。大変でした。

DSLの文法設計

どういう文法だったらプログラマにわかりやすくて間違えにくいか一生懸命考えました。
データを設定する時に文字リテラルでテーブル名やカラム名を指定するようなことはしたくなかったです。

// 嫌な例
row.set("Tweets" , "UserID", 10);

これは誤字脱字が発生します。
このように書きたいです。

row.set(tweets.userID, 10);

この時型を間違ったらコンパイルエラーにしたいです。

row.set(tweets.userID, "10"); // 第二引数がintじゃないのでエラー

Dartの型システムの強さに救われました。

ビュー更新の実行計画

アルゴぢからが足りないため、大変苦労しました。
やることは各演算のオペランドが増えたときと減った時にそれぞれ前回の結果からどう変わるかを1個ずつプログラミングすることです。
例えばMax関数なら

  • Insert
    • 入って来た数が既存のMaxより大きい -> Maxを更新
    • 入って来た数が既存のMaxより小さい -> 無視
  • Delete
    • 消した数が既存のMaxと等しい -> 二番目をMaxに昇格
    • 消した数が既存のMaxより小さい -> 無視

みたいなコードをいっぱい書きます。

インデックス

RocksDBはRDBのようなインデックスの機能がありません。
その代わりPrefix Seekという機能があります。キーのビット列が前方一致する行を全て列挙してくれます。
つまり主キー以外の属性で行を取得したいなら、その属性をキー、テーブルの主キーをバリューにしたKVSを別に作っておく必要があります。
例えば、Timelineビューの主キーはtweetIDだったとします。
ユーザー名が変更された時にTimelineビューを更新するにはuserIDをキー、tweetIDをバリューにしたKVSが必要です。
どんなインデックスが必要なのか全て洗い出すのが大変でした。

進捗

今のところ完成している機能は

  • INNER JOIN
  • UNION
  • SELECT
  • Optional型
  • Float型
  • 負の数

開発中・調整中なのが

  • GROUP BY
    • MAX
    • MIN
    • COUNT
    • AVERAGE
    • ARRAY
  • OUTER JOINとLEFT JOIN
    • COALESCE
  • RANK
    • DESC
    • ASC
  • WHERE
  • UPDATEの高速化(Insert/Deleteに比べてUpdateは最適化可能性が多すぎるのでだいぶサボってる)
  • 生成列
  • 初期データ

構想中なのが

  • Infinite ScrollのためのSelect機能
  • 休眠ユーザーを識別して計算量をサボる機能

です。
引き続きがんばります。