最大フローを求めるアルゴリズム

Ford-Fulkerson法をベースに、最大フローにおける経路探索の深さ優先と幅優先の速度の違いをAOJで比較した。基本的なアルゴリズムを試したいときにAOJは便利。

幅優先を使ったときは、特にEdmonds-Karpのアルゴリズムと呼ばれ、計算量はO(VE2)である。

AOJの実行時間を比較結果は以下。思ったより差がでた。

  • 深さ優先：0.99s
  • 幅優先：0.03s

時間のかかっている問題（#27）をピックアップすると、フロー増加操作の繰り返し回数が以下の通り、実際結構違っていた。

  • 深さ優先：1664
  • 幅優先：21

コードは以下。ちなみに深さ優先はほとんど蟻本のC++を移植しただけで、幅優先は適当に組んだもの。幅優先のほうが経路のトレースバックとかは一部ナイーブな処理が残っている。

from collections import deque
import sys
sys.setrecursionlimit(10**7)

INF = 10 ** 15

V, E = [int(v) for v in input().split()]

CAP = 1
REV = 2

G = [[] for _ in range(V)]

for i in range(E):
    u, v, c = [int(v) for v in input().split()]
    rv = len(G[v])
    ru = len(G[u])
    G[u].append([v, c, rv])
    G[v].append([u, 0, ru])

def dfs(v, t):
    closed = [False] * V
    return _dfs(v, t, INF, closed)

def _dfs(v, t, f, closed):
    if v == t:
        return f
    closed[v] = True
    for e in G[v]:
        v1 = e[0]
        if closed[v1] or e[CAP] <= 0:
            continue
        d = _dfs(v1, t, min(f, e[CAP]), closed)

        if d <= 0:
            continue

        e[CAP] -= d
        G[v1][e[REV]][CAP] += d
        return d
    return 0

def bfs(v0, t):
    if v0 == t:
        return INF

    closed = [0] * V
    closed[v0] = INF

    q = deque([v0])
    path = [-1] * V
    path[v0] = -2

    while len(q) > 0:
        v = q.popleft()
        c = closed[v]
        for e in G[v]:
            v1 = e[0]
            if e[CAP] <= 0:
                continue
            c1 = min(c, e[CAP])
            if closed[v1] != 0:
                continue
            path[v1] = v
            closed[v1] = c1
            if v1 == t:
                traceback(t, path, c1)
                return c1
            q.append(v1)
    return 0

def traceback(p, path, c):
    p0 = p
    while path[p0] >= 0:
        p = path[p0]
        for e in G[p]:
            if e[0] != p0:
                continue
            e[CAP] -= c
            G[p0][e[REV]][CAP] += c
            break
        p0 = p

def max_flow(s, t):
    flow = 0
    count = 0
    while True:
        f = bfs(s, t)
        #f = dfs(s, t)
        if f == 0:
            return flow
        flow += f
        count += 1


print(max_flow(0, V - 1))

アセンブラのグローバル変数の定義

Low-level ASM

アセンブラ、調べてもすぐ忘れるのでまとめる。

intelシンタックスで、 -pieか-no-pieかでだいぶ違うみたいだが、以下は最近主流の-pieを前提とする。

セッション

アセンブリプログラムは、複数のセッションで構成される。 グローバル変数の配置を理解するには、まずセッションの違いを理解しておく必要があるのでまとめておく。

違うセッションに配置したからといって、必ずSEGVるわけではなく、動いてしまうこともある。

  • .text
    • 命令、要は関数定義とか
    • 定数なら配置できる？
      • .textセッションでwriteしようとするとSEGVる。
  • .bss
  • .data

グローバル変数の定義

初期化しないグローバル変数の定義

    .comm v,4,4

.commはリンカがまとめて.bssセクションに配置してくれるらしいので、初期値は0になっている。 .commの第2引数はサイズ, 第 3 引数はアライメントの指定サイズらしい。配列などのサイズは型×配列長で求まる。 （アライメントはどう決まるのか、決めるのかはよくわからない。）

0で初期化したグローバル変数の定義（gccの場合）

    .bss
v:
    .zero 4

初期化するグローバル変数の定義

v:
    .long 4

ちなみに.longは4バイトの型を示す。

Typescriptの型の扱いのメモ

Typescript/Javascript

Typescriptの型関連の演算子、?とか!とかググらビリティがあまりよくないので、ちょっとメモしておく。

Type Assertion

asは型アノテーション。キャストと違うのはコンパイラ向けの情報のみで、それ自体は実行環境に影響を与えないことが違いのよう。

型アノテーションでは、無理やり型を変える危険な処理であることを理解しておく必要がある。 ダイヤモンド演算子を使ったcastもあるらしいが、JSX/TSXが出てきたので、asが推奨されている。

typeof

typeofは組み込み型(numberとかstringとか)のTypeguard。

instanceof

instanceof はクラスの判定に利用する。

Optional Parameters / ?

引数やクラスフィールドにおいて、Optionalであることを示す。

function task(a: number, b?: number) {
}

bは引数に指定してもしなくてもよいことを示す。型としては number | undefinedとして解釈される。

ローカル変数などの宣言においては利用できない。

let a?: number; // NG
let a: number | undefined; // OK

Optional chaining

Optionalな変数はifなどでチェックするほかに、変数や変数を取得する関数のあとに?を付けてメソッドチェインすれば、undefinedやnullの場合でも短絡してundefinedを返すようになる。

    function task(a?: number | null) {
      const b = a?.toString().substr(0, 1); // undefined
      const c = task2(a)?.toString(); // undefined
    }

    function task2(a?: number | null): number | null {
      return null;
    }

Non-null assertion operator

nullやundefinedでないことを保証できるなら、?ではなく!を付ければよい。これでnullチェックやundefチェックが入らなくなる。 つまり、nullやundefinedが入力されていると、実行時エラーが発生するということである。 安全ではなくなるので、利用する場合には注意が必要である。

    function task(a?: number | null) {
      const a = a!.toString(); // aがnullの場合は実行エラーが起きる
    }

ほかにも出てきたら追記する。

React Hooksでカウンターを実装してみる。

Typescript/Javascript React

とりあえず実装すると以下のような形か。

import React from 'react';

const Counter = () => {
    const [count, setCount] = React.useState(0);

    const handleClick = React.useCallback((e: React.MouseEvent<HTMLInputElement, MouseEvent>) => {
      setCount(c => c + 1);
    }, []);

    return (
      <div>
        <p>Count: {count}</p>
        <input type="button" value="Up" handleClick={handleClick}>
      </div>
    );
};

export { Counter }

カウント処理をuseCallbackで無駄に生成しないようにしている。

このカウント処理を、ほかのコンポーネント、特に子のコンポーネントで実施したいことがある。 子コンポーネントをRichButtonとすると、こんな感じか。

import React from 'react';
import { RichButton } from './RichButton';

const Counter = () => {
    const [count, setCount] = React.useState(0);

    const handleClick = React.useCallback((e: React.MouseEvent<HTMLInputElement, MouseEvent>) => {
      setCount(c => c + 1);
    }, []);

    return (
      <div>
        <p>Count: {count}</p>
        <RichButton handleClick={handleClick}></RichButton>
      </div>
    );
};

export { Counter }

ただ、Reactは親コンポーネントが更新されると、子コンポーネントも更新されるらしい。

今回だと、Counter（親コンポーネント）で管理しているcountを更新するとCounterコンポーネント以下のコンポーネントすべてに更新がかかる。しかし、RichButtonなどは状態が変わっていない（そもそも状態を持っていない）ので別に更新する必要はない。

その場合は、React.memoで関数コンポーネントをラップする必要があるらしい。

import React from 'react';

interface Prop {
  handleClick: (event: React.MouseEvent<HTMLInputElement, MouseEvent>) => void;
}

const RichButton = React.memo((props: Prop) => {
    const { handleClick } = props;

    return <input type="button" value="Button" onClick={handleClick}></input>;
});

export { RichButton }

ただ、memoするのにもコストはかかるので、どちらが効果的かはちゃんと計測していく必要があるらしい。 React、なんとなくでも動いちゃうが、パフォーマンスを気にする場合は結構めんどくさい。

React Hooksでタイマーを実装してみる。

React Typescript/Javascript

状態が頻繁に更新されるコンポーネントということで、タイマーを実装してみる。とりあえず、実装すると以下のようになる。

import React from 'react';

const Timer = () => {

    const [time, setTime] = React.useState(0);

    React.useEffect(() => {
      const id = setInterval(() => {
        setTime(time + 1);
      }, 1000);
      return () => clearInterval(id);
    }, [time]);

    return (
      <p>Time: {time}</p>
    );
};

export { Timer }

React.useStateで必要な状態timeを宣言し、React.useEffectで副作用のあるtimeの更新処理を宣言している。

ただ、これだと、timeを更新するたびに、useEffectの関数も更新する必要があり、あまり効率が良くない。（ちなみに関数を更新しないと、クロージャによってtimeの値が変わらないのでtimeが更新されない。）特にfpsを稼ぎたい場合などはつらい。

どうすればいいんだと思ったら、公式に書いてあった。

import React from 'react';

const Timer = () => {

    const [time, setTime] = React.useState(0);

    React.useEffect(() => {
      const id = setInterval(() => {
        setTime(t => t + 1);
      }, 1000);
      return () => clearInterval(id);
    }, []);

    return (
      <p>Time: {time}</p>
    );
};

export { Timer }

setTimeには更新のための関数を設定できるらしい。

nginxのタイムアウトの設置の確認

Web

nginxのロードバランサに割り当てたバックエンドのサーバがダウンしていることは、タイムアウトで判定される。タイムアウトする時間は以下のパラメータで調整できる。

長く設定すると、タイムアウトの検出が遅れるが、短く設定すると誤検知が増える。

仮にタイムアウトが誤検知されると、最初のバックエンドにも、次のバックエンドにもPOSTが送信され、複数のサーバで同じリクエストを多重に処理してしまうことがある。そのため、バックエンドは、誤検知を避けるより、同じPOSTを複数受けても状態が変わらないように設計しておく必要がある。

タイムアウトの処理は、fail_timeoutで指定した時間内にmax_failsの回数だけタイムアウトすると、fail_timeoutで指定した時間のあいだ、そのサーバにはアクセスしないようになる。

適当に設定ファイルを書くと以下のような形になる。

    upstream backend {
        server express1:3000 max_fails=1 fail_timeout=60s;
        server express2:3000 max_fails=1 fail_timeout=60s;
        server express3:3000 max_fails=1 fail_timeout=60s;
    }

    server {
        listen 80 default_server;

        location / {
            proxy_connect_timeout 60s;
            proxy_send_timeout 60s;
            proxy_read_timeout 60s;

            proxy_pass http://backend;
        }
    }

これでnginxを使ってバックエンドサーバの冗長化構成を組むことができる。 ただし、nginx自体の冗長化については別途検討が必要である。

docker-composeの揮発性

Container

docker-composeで開発環境を作っているのだが、 環境作りなおしたいとき、ただdownしてupしなおせばよいと思っていた。

が、なにもマウントしないRDBは空になっていることを期待していたが、 データが残っているときと、残っていないときがあって、？？？となっていた。

docker-compose のヘルプをみても

$ docker-compose

(略)

Commands:
  build              Build or rebuild services
  config             Validate and view the Compose file
  create             Create services
  down               Stop and remove containers, networks, images, and volumes
(略)

削除すると書いてあるのだが、、、もうちょっと調べる。

$ docker-compose down -h
Stops containers and removes containers, networks, volumes, and images
created by `up`.

By default, the only things removed are:

- Containers for services defined in the Compose file
- Networks defined in the `networks` section of the Compose file
- The default network, if one is used

Networks and volumes defined as `external` are never removed.

Usage: down [options]

Options:
    --rmi type              Remove images. Type must be one of:
                              'all': Remove all images used by any service.
                              'local': Remove only images that don't have a
                              custom tag set by the `image` field.
    -v, --volumes           Remove named volumes declared in the `volumes`
                            section of the Compose file and anonymous volumes
                            attached to containers.
    --remove-orphans        Remove containers for services not defined in the
                            Compose file
    -t, --timeout TIMEOUT   Specify a shutdown timeout in seconds.
                            (default: 10)

以下のようにしないとvolumeは削除されないらしい。へー。

docker-compose down --v

というかコンテナのライフサイクルとvolumeのライフサイクルは別なのね。いろいろ理解が足らんことを理解した。