2022-03-04

関数テンプレートの明示的実体化と実体の宣言

C/C++

明示的実体化を説明する前に実体化の意味をはっきりさせておく必要がある。似た言葉に特殊化があるが、特殊化と実体化は異なる。まずはその違いを説明する。

以下を例に考える。

template<typename T>
T calc(T a, T b) { return a + b; }

実体化の方がわかりやすい。実体化は、calc<int>(1, 2)のような呼び出しがあるソースコードをコンパイルしたときに、

int calc(int a, int b) { return a + b; }

に相当する関数定義を生成することである。このとき生成される関数を実体と呼ぶ。

これに対し特殊化は、

// (a)
template<typename T>
T calc(T a, T b) { return a + b; }

// (b)
template<>
double calc<double>(double a, double b) { return a - b; }

のように、ある関数テンプレート（ここではcalc）に対して、「基本は(a)の通りに実体化してほしいけれど、もし特定の型（ここではdouble）が与えられた場合は(b)のように実体化してね」とソースコード中で指示することをいう。

これを踏まえた上で、明示的実体化とは、calc<int>(1, 2)のような呼び出しの有無に関係なく、ユーザーの指示によってT=intの実体を生成することをいう。明示的実体化を行うには、ソースコード中に次のように記述する。

template<typename T>
T calc(T a, T b) { return a + b; }

template int calc<int>(int a, int b); // T=intの実体が作られる

明示的実体化と対比して、calc<int>(1, 2)のような呼び出しによって起こる実体化を暗黙的実体化という。

明示的実体化は、実体の宣言と組み合わせることで効果的に使用できる。実体の宣言を行うには以下のように記述する。

template<typename T>
T calc(T a, T b) { return a + b; }

extern template int calc<int>(int a, int b); // 宣言

calc<int>(1, 2); // このファイルのコンパイルでは実体化されない

宣言された実体は、たとえ元になる関数テンプレートの定義が見えていたとしても、暗黙的には実体化されない。なぜなら、実体を宣言することは、その実体がどこかで明示的に実体化されることをプログラマが保証することだからである。

よく使うことがわかっている実体を宣言しておけば、その実体をたくさんのファイルから呼び出していても、実体化はあるファイルで1度明示的に行うだけで済む。これによりコンパイル時間を削減できる。

2021-08-06

合成関数の微分

数学

関数 $f, g$ が微分可能であるとする。このとき、関数 $f(g(x))$ の点 $x=a$ における微分係数は $f'(g(a))g'(a)$ である。このことは合成関数の微分の公式として知られ、高校数学の教科書にも載っているが、そのよくある証明には厳密でない部分がある。この記事ではよくある証明を少しだけ修正することで厳密な証明を与える。

証明？

関数 $f(g(x))$ の点 $x=a$ における微分係数を求めよう。$u=g(a), y=f(u)=f(g(a))$ とおく。$a$ が $\Delta x$ だけ増加したときの $u$ の増加分を $\Delta u$、$u$ が $\Delta u$ だけ増加したときの $y$ の増加分を $\Delta y$ とする。すなわち、 \begin{align} \Delta u &= g(a+\Delta x) - g(a)\\ \Delta y &= f(u+\Delta u) - f(u)= f(g(a+\Delta x)) - f(g(a)) \end{align} と定義する。微分係数の定義により、求める極限は \begin{align} \lim_{\Delta x \rightarrow 0} \frac{f(g(a+\Delta x)) - f(g(a))}{\Delta x} \end{align} である。ここで、$\lim$ の中の式は \begin{align} \frac{f(g(a+\Delta x)) - f(g(a))}{\Delta x} = \frac{\Delta y}{\Delta x} = \frac{\Delta y}{\Delta u} \cdot \frac{\Delta u}{\Delta x} \cdots \cdots (*) \end{align} と変形できる。$g$ は連続なので $\Delta x \rightarrow 0$ のとき $\Delta u \rightarrow 0$ である。さらに $f, g$ は微分可能なので、極限値 \begin{align} \lim_{\Delta u \rightarrow 0} \frac{\Delta y}{\Delta u}, & & \lim_{\Delta x \rightarrow 0} \frac{\Delta u}{\Delta x} \end{align} が存在する。それぞれ $f'(u), g'(a)$ とおけば、求める極限値は \begin{align} \lim_{\Delta x \rightarrow 0} \frac{f(g(a+\Delta x)) - f(g(a))}{\Delta x} =\lim_{\Delta x \rightarrow 0} \frac{\Delta y}{\Delta u} \cdot \frac{\Delta u}{\Delta x} =f'(u)g'(a)=f'(g(a))g'(a) \end{align} である。

問題点

上の証明には厳密でない点がある。問題は $(*)$ の変形にある。この変形は両辺が $\Delta x=0$ の十分近くで $\Delta x$ の関数として等しいことを根拠にした変形である。しかしながら、これは成り立たないケースがある。$\Delta u$（$\Delta x$ によってその値が定まる）が $0$ となるような $\Delta x$ を考えよう。このとき、$(*)$ の変形前の式の値は $0$ であるのに対し、変形後の式の値は分母に $\Delta u$ があるため未定義である。したがって $\Delta x=0$ のどれだけ近くを考えても $\Delta u=0$ となる点が存在するような関数 $g$ が与えられた場合には、$\Delta x=0$ のどれだけ近くを考えても $(*)$の両辺は $\Delta x$ の関数として異なることになり、$(*)$ の変形は非合法である。といってもほとんどの場合で問題は起きない気がするが、実際に問題が起きる例としては、関数 $g$ が定数関数である場合が挙げられる。っていうか関数 $g$ が定数関数だったら $f(g(x))$ も定数なわけで、普通は合成関数の微分しようとか思わないじゃん。

修正

イメージとしては $\Delta x$ を $0$ に近づけていくとき、 $(*)$ の最左辺と最右辺は、見えているときはいつも等しいが、最右辺だけが時折チラついているような状況である。このチラつきをなくしてやればよい。チラつきの原因は $\Delta y / \Delta u$ の部分である。この部分を次の関数で置き換える。 \begin{align} h(\Delta u) = \begin{cases} \Delta y / \Delta u & \Delta u \neq 0\\ f'(u) & \Delta u = 0 \end{cases} \end{align} そうすれば任意の $\Delta x$ について \begin{align} \frac{f(g(a+\Delta x)) - f(g(a))}{\Delta x} = h(\Delta u) \cdot \frac{\Delta u}{\Delta x} \end{align} である。つまり両者は $\Delta x$ の関数として等しい。さらに $\Delta x \rightarrow 0$ とすると、$\Delta u / \Delta x \rightarrow g'(a)$ かつたとえ $\Delta u$ の値が $0$ を取りながら $0$ に収束したとしても $h(\Delta u) \rightarrow f'(u)$ である。したがって求める極限値は $f'(u)g'(a)=f'(g(a))g'(a)$ である。

2021-06-05

C言語で可変長引数を取る関数を定義する

C/C++

可変長引数とは、printf関数が取るような、あらかじめ個数が決まっていない形式の引数のことである。

例えば、自分用のprintfを新たに定義したいとすると、引数の部分は次のように書く。

void myprintf(char *fmt, ...) {

}

こう書くと、fmtに続く引数が可変になる。 ...の前には引数が複数あってもよいが、...の後に引数があってはならない。つまり、...は引数の最後でなければならない。

渡された可変長引数を使うには、stdarg.hで定義されている型やマクロを使う。以下にそれらの使い方の例を示す。

#include <stdio.h>
#include <stdarg.h>

void myprintf(char *fmt, ...) {
    va_list ap;
    va_start(ap, fmt);
    
    char *p = fmt;
    
    while (*p) {
        if (*p == 'd') {
            printf("%d ", va_arg(ap, int));
            p++;
            continue;
        }

        if (*p == 'c') {
            printf("%c ", va_arg(ap, char));
            p++;
            continue;
        }
        
        fprintf(stderr, "不正な文字\n");
        exit(1);
    }
    
    printf("\n");
}

va_list型は引数のリストをイテレートするためのポインタを表す。 "va"はおそらく可変超引数を表す英語variadic argumentsの略。

va_start(ap, fmt)によって、apがfmtに続く引数のリストの先頭を指している状態になる。一般にva_startの第二引数には...の直前の引数の識別子を指定する。

引数のリストを順番に調べるには、va_argマクロを使う。va_arg(ap, int)はapが指している位置の引数をint型として返し、apが指す位置を一つ先に進める。

myprintf関数は簡易的なprintfを実現する。具体的には、dとcからなる文字列と可変長引数を受け取り、可変長引数を参照しながら、dを整数に、cを文字に置き換える。例えばmyprintf("dcdcd", 1, 'a', 2, 'b', 3)を呼び出すと1 a 2 b 3と表示される。

2021-05-23

Gistのコードを貼ってみるテスト

マークダウンのコードブロックより見やすいかも

2021-05-16

VSCodeのC/C++拡張(ms-vscode.cpptools)のデバッグ機能がM1 Macに対応していない件

VSCode C/C++ Apple M1

2ヶ月ぐらい前に届いたMacBook Air (M1, 2020)をやっと使い始めている。VSCodeがもうApple M1チップにネイティブ対応しているらしいので、設定をすることにした。今のところプロコンぐらいしか使い道が思い浮かばないので、すごく本格的なことができる必要はない。C/C++のコードが書けて、コンパイルできて、デバッグできればよい。

とりあえずVSCodeのドキュメントに書いてある通りに進めた。コンパイラとデバッガはAppleのCommand Line Toolsをインストールすると入っているClangとLLDBを使う。

Configure VS Code for Clang/LLVM on macOS

ビルド（コンパイル）するところまではよかったが、デバッグのところでこんなエラーが出てうまくいかなかった。

Warning: Debuggee TargetArchitecture not detected, assuming x86_64.
ERROR: Unable to start debugging. Unexpected LLDB output from command "-exec-run". process exited with status -1 (attach failed ((os/kern) invalid argument))
The program '/Users/sitorasu/projects/helloworld/helloworld' has exited with code 42 (0x0000002a).

調べてみると、現在のところMicrosoftのC/C++拡張(ms-vscode.cpptools)のデバッグ機能はApple M1チップでネイティブに動作するデバッガには対応していないらしい。

Support Apple Silicon ARM64 architecture natively for debugger · Issue #7035 · microsoft/vscode-cpptools · GitHub

このスレッドを見ると、対処法としてはrosettaを使って全部x86_64で完結させる（？）か、すでにApple M1チップに対応している別の拡張機能を使うのがいいらしい。前者はよくわからなかったので後者を選択することにした。別の拡張機能というのはCodeLLDB(vscode-lldb)というやつ。VSCodeの拡張機能検索でlldbとか調べれば出る。

GitHub - vadimcn/vscode-lldb: A native debugger extension for VSCode based on LLDB

どうやらこっちは対応済みらしい。

Please support Apple silicon (M1, arm64-darwin) · Issue #397 · vadimcn/vscode-lldb · GitHub

launch.jsonにはこんな感じで書く。

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "vscode-lldb",
            "type": "lldb",
            "request": "launch",
            "program": "${workspaceFolder}/${fileBasenameNoExtension}",
            "args": [],
            "cwd": "${workspaceFolder}",
            "preLaunchTask": "clang++ build active file"
        }
    ]
}

"type": "lldb"と指定することで（Microsoftのではなく）CodeLLDBがデバッグに使われるようになるっぽい。ちなみに、tasks.jsonには上のVSCodeのドキュメントに書いてある通りに書いてある。

これでちゃんとデバッグできるようになりました。めでたしめでたし。

2021-05-08

競プロ典型90問 001 - Yokan Party

プロコン AtCoder

スコアを与えられた数以上にできるかどうかの判定法について。（注意：説明がくどい）

問題と解説

問題はこちら→https://atcoder.jp/contests/typical90/tasks/typical90_a

出題者による解説はこちら（添付画像左）↓

【2 日目】
昨日の解説と今日の典型問題です。問題 001 については E869120 の想定ソースコードも GitHub に追加しました。今日は昨日と比較すると少し易しい問題だと思います。（昨日と同様、入力形式・入出力例は GitHub を参照のこと） #競プロ典型90問 pic.twitter.com/ewcAKEKEP1
— E869120@公開アカウント (@e869120) 2021年3月30日

解法のポイント

与えられた整数 $M$ に対して、「スコアを $M$ 以上にできるか？」は簡単に判定できる

二分探索は知っていたが、この事実に気付けなかったために解けなかった。逆にこれに気付きさえすれば、「 $M$ を動かして調べればいい」→「全範囲を調べると間に合わない」→「二分探索を使おう」という発想に至るのは難しくないと思う。しかしながら、解答を読んでも上記の問いに対する判定法の正しさをすぐには理解できなかった。そこで、以下ではその判定法について詳しく考察する。（二分探索については解説しない。）

判定のしかた

解答のステップ2にある通りだが、改めて説明する。

切れ目を左から見ていく。
最後に切ったところ（一度も切っていないときは左端）からの距離が初めて $M$ 以上になったらその切れ目で切る。これを繰り返す。
ただし、次の条件をいずれかを満たす場合はそれ以上切らずに繰り返しをやめる。
- 切れ目の右端まで見終わった。
- もし今見ている切れ目を切ると、右側の残った部分の長さが $M$ 未満になる。
トータルで切った回数が $K$ 以上ならスコアを $M$ 以上にできる。 $K$ 未満ならできない。

この判定法を「判定法A」と呼ぶことにする。

例

下の図に示すようなようかんがあるとする。縦線は切れ目を表し、切れ目と切れ目の間の数字はそれらの間の距離を表す。

f:id:sitorasu_today:20210508202617p:plain

このようかんを $4$ 回切って $5$ つのピースに分けることを考える。このとき、スコアを $3$ 以上にできるか？は次のようにして判定できる。

f:id:sitorasu_today:20210508182207p:plain

では、スコアを $6$ 以上にはできるだろうか？

f:id:sitorasu_today:20210508183339p:plain

一番右の切れ目は切らないことに注意してほしい。

判定法の正しさ

なるほど、判定のしかた自体は分かった。でもどうしてこの方法で正しく判定できるのだろう？先ほどの例で考えてみよう。ようかんを $4$ 回切って $5$ つのピースに分けるとき、スコアを $3$ 以上にはできるのだった。

この理由を説明するのは簡単だ。 $5$ 回切ったうちの $1$ 回を切らないようにすれば、スコアを $3$ 以上にする切り方のひとつが構成できる。同様に、 $5$ 回切ったうちの何回かを切らないようにすることで、 $5$ 回以下の任意の回数切ってスコアを $3$ 以上にする方法が構成できる。一般に、与えられた整数 $M$ に対して、判定法Aで $X$ 回切ることができたならば、 $X$ 回以下の任意の回数切ってスコアを $M$ 以上にできる。

問題は、 $X$ 回より多く切ってスコアを $M$ 以上にする方法が本当に存在しないのかということである。言い換えれば、 $X$ はスコア $M$ 以上になるように切れる最大の回数なのかということだ。もしそうであれば判定法Aは正しい。しかし、判定法Aはパッと見ではすべての切り方を考慮しつくしているようには思えない。例えば先ほどの結果によれば、 $4$ 回切ってスコアを $6$ 以上にする方法は存在しないのであった。

果たして本当にそうだろうか？違う切り方を試してみよう。例えば、最初に切る位置を少し左にずらしてみる。

f:id:sitorasu_today:20210508183914p:plain

これは全然ダメだ。今切り出したピースの長さが $6$ 未満なので、この時点でスコアが $6$ 未満になってしまうことが確定する。それでは、今度は最初に切る位置を少し右にずらしてみよう。

f:id:sitorasu_today:20210508183937p:plain

このように切っても、スコア $6$ 以上を保って切れる最大回数は増えそうにない。なぜならば、判定法Aで最初に切った段階よりも残り少ないようかんを、より多く切らなければならないからである。たとえるなら、テスト用紙の小さな記名欄に、自分の名前の一文字目を大きく書いてしまったような状況だ。でも実際の状況はもう少し複雑だ。今回の問題設定では切れ目の位置が決まっているし、それらが均等に配置されているとも限らないからだ。もう少しちゃんと考えることにする。

任意のようかんと切れ目と整数 $M$ が与えられたとする。判定法Aにしたがって最初の一回を切った後、残りをスコアが $M$ 以上になるように切る方法のうち、切れる最大の回数を $S$ とする。また、最初の一回を判定法Aより右側で切り、残りをスコアが $M$ 以上になるように切る方法のうち、切れる最大の回数を $S'$ とする。

f:id:sitorasu_today:20210508193045p:plain

このとき、 $S \geq S'$ である。なぜなら、もし仮に $S \lt S'$ であるとすると、判定法Aにしたがって最初の一回を切った後、残りをスコアが $M$ 以上になるように $S'(\gt S)$ 回切ることができるからである（下図参照）。これは $S$ が最大であることに矛盾する。

f:id:sitorasu_today:20210508193113p:plain

したがって、一回目を判定法A以外の方法で切ってもトータルで切れる最大回数は増えないことがわかる。つまり、最初の一回は判定法Aにしたがうのが最善である。これにより、ようかん全体をスコアが $M$ 以上になるようにできるだけたくさん切る問題は、最初の一回を判定法Aにしたがって切り、残りをできるだけたくさん切るという、より小さな問題に帰着できる。さらに、この理屈は残りのようかんに対して繰り返し適用できる。つまり、残りのようかんを改めてようかん全体だとみなすことで、残りをできるだけたくさん切るという問題は、残りを判定法Aにしたがって一回切り、それでもなお残った部分をできるだけたくさん切るというさらに小さな問題に帰着できる（下図参照）。これを繰り返すことで元の問題は自明な問題に帰着され、最大回数を求めることができる。これは判定法Aそのものである。

f:id:sitorasu_today:20210508195103p:plain