モチベ

WikiBlame は古典的なPHP性のWebアプリだが、これはリクエスト時の待ち時間が長くてマイクロインタラクションがイマイチ。しかもリロードなどの遷移時にも都度都度リクエストが走るので遅い。

↑ 証明書の設定をミスってて、セキュリティーの警告が出るのも面倒だ。

これをJSベースのSPAに改修したい。

なるべくWikipediaサーバーの負荷も軽くしたい。

wint

REST API

昔の Action API の代わりに REST API を使いたい。

Action API

wint

二分探索

アルゴリズムの諸要素をREST APIのアクションに対応付けてみる

リビジョン総数

Get page history counts

件数しか取れないので、カーソルでの移動ができない。不適。

count

上限あり。

limit

cf.

中央値計算

REST API は、挙動がカーソルベースなので、件数では取れないようだ？

vs. 古い Action API なら取れる

rvlimit: 1..500|max

→ 最大500件のバッチで取れる。

→ まずはこれで探索範囲を確定する。

追加・削除判定

diff.type
- 1 = 追加
- 2 = 削除
- 3 = 段落内変更。 diff.highlightRanges 参照
- 4
- 5
diff.highlightRanges
- type
  - 0 = 追加
  - 1 = 削除

wint

履歴取得

REST API を使う場合

Get page history

Response schema
revisions
Array of 0-20 revision objects

20件ずつしか取れないので、何度もリクエストする必要がある。まずはこれで revision の配列を作る必要がある。

revision object は要約しか持ってない。

Get HTML

ページのソースはリビジョンで取れないようだ

wint

代替アルゴリズム

Action API で revision を 500 件ずつ取るのは、相応に負荷が掛かりそうだが、大丈夫だろうか？:

rvlimit: 1..500|"max"

rvprop=content を指定しなければ大丈夫？

線形探索

ここはあくまでも REST API に留まって、線形探索にするか？

ただし、20件単位のバッチ処理（リビジョン比較）はする:

wint

テーブル構造

Wikipedia の DB に与える負荷を予想したい

revision と content とは、 slot の連想entity 経由で関連がある。

wint

技術スタック

UI = frontend
- Web UI: Elm?
- JS FW?
  - React
    - SWR
backend
- なし。ブラウザで完結させる。

wint

既存実装

これをガンバって読む。
たぶん読まなくても実装できる。

利用している機能

pagehistory, action=history

特別ページ …、Special:PageHistory、… が、各操作のショートカットとして作成されました。…。PageHistory、… は、それぞれ &action= history、… に対応します。

code:

コンテンツ取得

HTML をパースしてる？

revision ごとに source を取得してる様だ。

疑問

なぜ Action API を使わないんだ…。

ref

Action API には action=raw は存在しない。

こっちが action=raw

wint

2分探索

懸念: 検索語の出現に関する単調性が保証されない。

→ それでも境界のひとつを検出できる。

// @returns {number} the lower bound or a boundary
// @returns {undefined} no boundary found
function binary_search<T>(
	xs: ReadonlyArray<T>,
	key: T,
	cond: <T>(xs: ReadonlyArray<T>, key: T) => (mid: number) => boolean,
	l = -1,
	r = xs.length
): number {
	const c = cond(xs, key);
	while (l + 1 < r) { // = l < r and diff(l, r) > 1
		const mid = l + r >> 1; // = avg(l, r)
		if (c(mid)) {
			r = mid;
		} else {
			l = mid;
		}
	}
	return r; // the lower bound or a boundary
}

const cond =
	<T,>(xs: ReadonlyArray<T>, key: T) =>
	(i: number): boolean =>
		xs[i] >= key;

memo.

r が求める条件を満す最小の index になる。
位置: l = -1, 0..(N-1), r = N
l: 満たさない index の上限
r: 満たす index の下限
index の列は明らかに鎖である。
不変条件: l < r
事前条件 (!c(l)) && c(r) が不成立でも、 r → 0 になるだけでアルゴリズムが破綻することはない。もし単調ならば、わざわざ探索する必要性がなくなるだけ。

参考

wint

方針

入力された項目名を受け付ける。
Revisions Action API で 500件の revision を取得する。
2分探索を開始する。
1. Compare Revisions REST API で diff[].type|in([1, 3, 5]) の差分に検索対象文字列が含まれてるかを判定する。
結果（発見・できず）を返す。
1. 下限・上限を更新する。
optional: revision をもう500件過去の batch にスライドさせる。3に戻る。

補記

特に通信部分は並行処理ができる？

wint

WikiBlame を近代化したい

モチベ

REST API

Action API

二分探索

リビジョン総数

Get page history counts

中央値計算

追加・削除判定

履歴取得

Get page history

Get HTML

代替アルゴリズム

線形探索

テーブル構造

技術スタック

既存実装

利用している機能

コンテンツ取得

疑問

ref

2分探索

参考

方針

補記

WIP