Go の module cache と vendor の違い
Go の module cache と vendor の違いがよく分からなかったので調べた。結論としては、違いというか go.mod に記述されているバージョンによってデフォルトで module cache と vendor のどちらを go run
や go build
時に使うかが異なる。
環境
- Go 1.15.3
$GO111MODULE
= ON
module cache
- 外部のモジュールに依存したコードをビルドする場合、依存モジュールを1度ダウンロードする。ダウンロードしたモジュールは、
$GOPATH/pkg/mod/
にキャッシュされるので次回のビルド時には再度ダウンロードする必要はなくなる。 go clean --modcache
で消せるgo run -mod=mod
フラグで明示的に module cache を使用するように指定できる
vendor
go mod vendor
すると外部の依存モジュールをvendor
ディレクトリにダウンロードするgo run -mod=vendor
で明示的に vendor ディレクトリを使用するように指定できる- コードのビルド時のデフォルト動作として、 vendor が使われるかどうかは、go.mod ファイルのバージョン記述に依存する。
// go.mod module github.com/pokuwagata/ichigo-cli go 1.15 <- これ require github.com/urfave/cli/v2 v2.1.1
- Go 1.14 以降は vendor が優先して使用される。1.14 未満の場合は module cache が優先される。
なぜ module cache と vendor の両方が存在するのか
- module mode は Go 1.11 から使えるようになったが、それ以前は module cache を使っていて、現在は移行・後方互換性のために残留しているっぽい。詳しくは分からない。
参考
パスカルの三角形を利用して組み合わせの数を求める
ABC 132 D 問題 の公式解説で、パスカルの三角形を利用して組み合わせの数を求めていたが、一見して何をしているか理解できなかった。
実装はこんな感じで、nCk を計算できる。
int n, k; cin >> n >> k; int c[105][105] = {}; c[0][0] = 1; for(int i=0; i<=100; i++) { for(int j=0; j<=i; j++) { c[i+1][j] += c[i][j]; c[i+1][j+1] += c[i][j]; } } cout << c[n][k] << endl;
パスカルの三角形とは何か、パスカルの三角形がなぜ組み合わせの数と対応するのかはこちらを参照して頂くとして、自分が分からなかったのはこの実装でパスカルの三角形が求められる理由。
これは図で書いてみると分かりやすくて、c[i][j]
を下段の c[i+1][j]
, c[i+1][j+1]
に配っているイメージ。
○ | \ ○ ○ | \ | \ ○ ○ ○
これなら両端は必ず1になるし、両端以外はパスカルの三角形の定義通りの加算が行われた値になる。
ちなみに、組み合わせの数は公式を使って愚直に計算しても(数が大きくなければ)良いと思う。
int n, k; cin >> n >> k; int ans = 1; for(int i=0; i<k; i++) { ans *= n-i; } ans /= k; cout << ans << endl;
ただし、組み合わせの数を求める度に O(k) の計算が必要になるのと、掛け算がオーバーフローする可能性もあるので、パスカルの三角形で事前に計算しておいた方が良い場合も多そう。
総和の剰余(mod) を計算したい
C - Sum of product of pairs で躓いたのでメモ。
総和の剰余(mod)
整数 a1, a2, a3 ... の 総和の剰余(mod) を計算したい。
(a1 + a2 + a3 ... ) % m
このとき、上の計算は以下と同値である。
(a1 % m + a2 % m + a3 % m ... ) % m
これを剰余演算の分配法則と同一性から示す。
剰余演算の分配法則から以下が成り立つ。
(a1 + a2) % m = (a1 % m + a2 % m) % m
すると、以下のように変形できる。
(a1 + a2 + a3 ... ) % m = (a1 % m + (a2 + a3 ... ) % m ) % m = (a1 % m + (a2 % m + (a3 + a4...) % m) % m) % m ... = (a1 % m + a2 %m + ...) % m % m ...
また、剰余演算の同一性から以下が成り立つ。
a % m = (a % m) % m
したがって、
(a1 % m + a2 %m + ...) % m % m ... = (a1 % m + a2 %m + ...) % m
と変形できる。
なので、総和の剰余を求める場合は、剰余の総和を取って最後に剰余を取ってもいいし
int sum = 0; for(int i = 0; i < n; i++) { sum += a[i] % m; } sum %= m;
変形前の式から見ると、加算する度に剰余を取ってもいい(オーバーフローを防げるので安全)
int sum = 0; for(int i = 0; i < n; i++) { sum += a[i] % m; sum %= m; }
(+-*)の演算をする度に剰余を取ると思っておいて良さそう。除算は逆元が絡むのでまた別の話。
参考
TypeScript の演算子を整理する
TypeScript (というか最近のJavaScript)って、よく分からない演算子多くないですか? なんか色々な箇所で!
とか ?
とか見るので意味が分からないと結構ストレスになります。
自分があんまりキャッチアップしてないのが悪いんですが、馴染みがない/薄い演算子について使い方と登場の背景を整理した自分用のメモ。
- Nullish Coalescing (??)
- Optional Chaining(?)
- Optional parameter (?)
- rest parameters (...)
- Non-null assertion operator (!)
- Short-Circuiting Assignment Operators (&&=, ||=, ??=)
Nullish Coalescing (??)
こういうやつ
let x = foo ?? bar();
要はこれのシンタックスシュガー
let x = foo !== null && foo !== undefined ? foo : bar();
なぜ必要か
JavaScript を書いてフロントエンドの開発をすると上のような書き方を頻繁にするから。特にレガシーなフロントエンドのコードベースに少し手を入れる時なんかは、どの変数がいつ null や undefined になるか予想がつかない場合も多く、とにかく安全側に倒したかったりする。(例外が発生すると処理が止まるので)
ちなみに、単に x = foo || bar()
と書くと、foo
が 0 だったり空文字だったりすると false
になって bar()
が評価されるので困る。JavaScript 初心者が絶対に1度はハマる罠。??
だと NaN
は回避されないみたいですが。
Optional Chaining(?)
こういつやつ
let x = foo?.bar;
要はこれのシンタックスシュガー
let x = foo === null || foo === undefined ? undefined : foo.bar;
なぜ必要か
let x = foo && foo.bar
とか書きたくないから。これもレガシー系フロントエンドの改修でありがちで、オブジェクトのプロパティと値がまったく予想できないので、こう書くしか無いパターンが多かった。とても助かる。がそもそも使わなくても良いのが望ましいとは思う。
Optional parameter (?)
こういうやつ
function foo(bar?: string) { ... }
?
を付けると string | undefined
型に推論される。これは厳密に演算子という区分なのかは分からないけど、まあそんな感じのものだと思ってる。
なぜ必要か
JavaScript の関数の引数は全て省略可能だが、引数が与えられない可能性があるのか、ないのかは区別できた方が嬉しい。そしてそうしないと型定義できない。
rest parameters (...)
こういうやつ
function foo (bar: string, ...baz: string[]) { ... }
引数を無限に受け取ることを宣言できる。spread operators とはまた別だと思う。
なぜ必要か
無限に引数を受け取ること自体は従来からできて、 関数内から arguments
で参照可能だった。ただし引数の宣言からはそれが読み取れなかったので分かりやすくなった。そしてそうしないと型定義できない。
Non-null assertion operator (!)
こういうやつ
function foo(f?: Foo) { let bar = f!.bar; }
要はこれのシンタックスシュガー
let bar = (f as Foo).bar;
なぜ必要か
外部のライブラリの型定義上 foo | undefined
みたいに定義されているが、自分の実装上は絶対に undefined
にならないから何とかしたいみたいなときに使うことが多い気がする。(自分が定義した型でこれが頻出するならそもそも型定義を見直した方がいいんじゃないか)
Short-Circuiting Assignment Operators (&&=, ||=, ??=)
こういうやつ
a &&= b; a ||= b; a ??= b;
要はこれのシンタックスシュガー
a = a && b; a = a || b; a = a ?? b;
ちなみに、JavaScript に馴染みがなかったり、しばらく別の言語を書いていたりすると、「え? a && b
とか a || b
って bool 型しか返さないのでは?」となるかもしれない。
JavaScript の場合はそんなことはなく、短絡評価をして
a && b
:a が false なら a を返すa || b
:a が true なら a を返す
という仕様になっている。この true か false かというのは、bool 型を期待しているわけではなく、JavaScript 流の解釈で、0, "", NaN, undefined, null ... 等は false でそれ以外が true みたいな感じに評価されるだけ。
非 bool 型の a, b で if(a && b)
のように書くと、(if 文の条件式なので)返値が bool 型に変換されるのでそれっぽく振る舞っているだけという感じ。
なぜ必要か
正直、自分はあんまりこういうコードが必要になったことはない。まず、変数に対する再代入をすることがあまりない。JavaScript が一部継承している関数型プログラミングのパラダイム的にも推奨してないと思う。
一方、競プロの問題を解く時は手続き的にサッと書きたいので、sum+=a
とか sum /= a
とかは頻繁に使う。でも a &&= b
はあっても使うことないと思う。
あと、a ||= b
するなら大抵は a ??= b
の方が適切じゃないかと思う。上でも書いたけど、0 とか 空文字を false として扱って欲しいケースの方が少ない気がするので...
(a + b - 1) / b で a / b の切り上げを計算する
整数 a, b に対して、 a / b
の切り上げを計算したい場合 (a + b - 1) / b
するという小技が競技プログラミングではよく使われる。
なぜこれで切り上げが計算できるのか、良い感じの説明が検索しても出てこなかったので自分なりの理解を書いておく。
以下 /
は一時的に分数の記号として、 b = 3 , a を 3から1ずつ増加させていく場合を考える。
3/3 = 1 4/3 = 1+1/3 5/3 = 1+2/3 6/3 = 2 7/3 = 2 + 1/3 ...以下略
となるので、1 - 1 / b
(b=3 の場合は 2/3) を加算して小数点以下を切り捨てれば切り上げと同じになる。
切り上げすべき場合は必ず商が繰り上がる。
切り上げすべきでない場合(上記の 3/3 , 6/3 のケース)は商が繰り上がらない。
よって、floor(a/b + (1-1/b))
をすればよく、今度は /
を切り捨て除算の記号として式変形すると
(a+b-1)/b
で同値と言える。したがってa / b
の切り上げを計算したい場合 (a + b - 1) / b
で計算できる。
ceil
が使える言語ならそれでもいいんじゃないか?と思われるが、a, b の値によっては浮動小数点計算の誤差が発生する可能性があるので、この方法が安全らしい。なるほど。
まあ (a+b-1)/b
の方がシンプルだし賢いやり方感がある。
TypeScript の共用体型は or ではないのかについて考えた
TypeScript の共用体型(Union Types)は or ではない を読み、確かによく分からん挙動だなーと思って色々調べたり考えたりしたことを書いておく。
最初に書いておくと、結論はよく分かってない。
まず、共用体型はタグ無し共用体型とタグ付き共用体型(Discriminated Unions)の2つに分けることができる。ので分けて考える。タグ付き共用体型が何を指すのかは後述する。
タグ無し共用体型
最初に、タグ無し共用体型について考える。
形状A, B に対して、A | B
と A & B
で定義される型の性質
そもそもの性質の整理。何かベン図を使った説明をすることが多いみたいだけど、形状*1を表す型の場合はベン図ではうまく説明できない気がしている。
A | B
は 少なくとも、A, B のいずれかの型を満たすようなプロパティを持つ(Aを満たすなら部分的にBのプロパティを持つことは許容される)A & B
は A, B のプロパティを全て持つ形状(A, B を満たしながら他のプロパティを持つことは許容されない)
ここで、A | B
は Partial(A & B)
、つまり A, B のプロパティを全て持つが、省略も可能な形状と同値なのか?と思ったが、それは違う。A | B
は、
- A,B のプロパティを部分的に持ち、A, B のいずれも満たさない場合は不可
- プロパティを持たない形状
{}
は代入不可
type A = { a: string; }; type B = { b: number; }; type C = A | B; const ab : C = {} // error
A | B = A ∪ B
という理解は正しいのか
ベン図で理解しようとすると、A | B
= A ∪ B 、つまり、AかBかAとB両方を満たす集合なんじゃないかと考えたくなる。
集合A を形状Aに割り当て可能な型とみるか、形状Aが持つプロパティの集合と見るかで違ってきそう。
前者で考えると、A を満たしながら B のプロパティを一部持つ形状は、A に割当不可能だし、A, B, A&B のどれにも割当不可能なので、A ∪ B に含まれないということになってしまう。「共用体型が or でない」ように思える。
後者で考えると、型を満たすかは関係なくて、単にプロパティの集合なので A ∪ B になる。すると共用体型が or であるように思える。
結局 A | B
とは何なのか
少なくとも、A, B のいずれかの型を満たすプロパティを持つ形状としか言えないような。A, B のいずれかの型を実際に満たすわけでなくて、(余計なプロパティがなければ)少なくとも A, B のいずれかを満たすようなプロパティを持つ形状というだけなことが大事なのかも。
同じことを、単一の形状として、オブジェクトリテラル表記で形状の型として定義することはできない気がしている。
ちなみに type-fest というライブラリに、RequireAtLeastOne
という型定義があり、見た感じ形状をA | B
することで得られる性質を利用しているみたいだった。この型ユーティリティは1つの形状から特定のプロパティの集合を選択していずれかを必須にできるので、もっと汎用性が高い感じ。
例えば、RequireAtLeastOne<A, "a" | "b">
すると a, b のどちらかを必須にできる。
型定義の理解の仕方はこの記事 が役に立った。
タグ付き共用体型
次にタグ付き共用体型について考える。そもそもタグ付き共用体型とは何かというと、こういうやつ。
type A = { type: 'a' a: string }; type B = { type: 'b' b: number }; type C = A | B;
タグは、同じプロパティで定義され、値は共用体型の中で一意である必要がある。
この場合は、単純で、A | B
は必ず A, B のいずれかになる。両方を満たしたり、片方を満たしながら片方のプロパティを持つことはできない。ベン図でいうと、A ∪ B から A ∩ Bを除いた集合で、形状以外の型の共用体型はこうなるはず。
なので、上の例でいうとこういうのはエラーになる。A を満たしているが、他の型のプロパティを部分的に持つことは許されない。
type C = A | B; const c :C = {type: 'a', a: "hoge", b: 1} // error
タグ付きの場合は A | B
に対する TypeScript の型推論も単純になる。(例えば a.type == 'a'
で分岐させれば以降は 型が A に定まる)
ちなみに、タグを重複させるとタグ無し共用体型みたいに部分的にプロパティを持つことが可能になる。というか多分タグ無し共用体型と同じ型定義になる気がする。
type A = { type: 'a' a: string }; type B = { type: 'a' b1: number b2: number }; type C = A | B; const c :C = {type: 'a', a: "hoge", b1: 1} // ok
*1:形状は、書籍プログラミングTypeScript で使われている用語で、オブジェクトリテラル表記で宣言される型のこと。TypeScript のオブジェクト型の他、クラスインスタンスも含まれる。多分最終的に JavaScript のオブジェクト型に変換されるものは全て含まれる
そもそも reflection とは何なのか
Go 言語を勉強していて reflection って何なんだろ、となったので調べた内容を書いておく。
そもそも reflection とは何なのか
wikipediaによると
情報工学においてリフレクション (reflection) とは、プログラムの実行過程でプログラム自身の構造を読み取ったり書き換えたりする技術のことを指す。
よく分からない。以下では reflection の概念について書いていく。(Go 言語の reflection パッケージ固有の話ではない)
自己書き換えコード
プログラムの実行過程でプログラム自身の構造を読み書きするというのはどういうことか。1つの例として自己書き換えコードがある。
プログラムはプロセッサが処理可能な機械語に変換されて動作する。例えば C言語の場合だと以下のような変換になる。
C言語 -> アセンブリ言語 -> 機械語
より変換の下流に位置している、アセンブリ言語や機械語のコードの内容をプログラムから書き換えることができれば、プログラム(ソースコード)に記述された処理とは見かけ上異なる処理*1を実行させることができる。そのようなプログラムを自己書き換えコードと呼ぶ(らしい)
例えば、C言語やアセンブリ言語で書かれたプログラムで命令が格納されているメモリを直接操作すると、その前にプログラム内で書かれた命令は意味をなさなくなる。具体例としては、自己書き換えコード(self-modifying code) 等を参照。
自己書き換えをしたいモチベーションとしては色々あるみたいで自分は低レイヤーな部分に明るくないのであまり理解できていない。とりあえず wikipedia には色々載っていた。
Brian Cantwell Smith は、このアセンブリ言語の自己書き換えコードの発想(メタプログラミング)を高級言語にも導入しようとした。これが reflection という概念の元になっているらしい。(Procedural reflection in programming languages がその論文っぽい。読んではない。)
reflection はメタプログラミング
上述のような背景があるので、メタプログラミングをしたいから reflection がある、と考えても良さそう。
メタプログラミング
ところでメタプログラミングとは何か。定義は色々ありそうだが、メタなプログラミング、プログラムをプログラムする(ある言語がある言語を読み書きする)というイメージで良いっぽい。
例えば eval
に渡す文字列を組み立てるプログラムは、まさにプログラムをプログラムが書いているのでメタプログラミングの1つになると思う。
また、SQL の組み立てもそうだし、TypeScript も JavaScript のメタプログラミングになると思う。
先程の自己書き換えコードがメタプログラミングに含まれるかは微妙かもしれない(C言語がアセンブリ言語(機械語)を読み書きしていると言えるのかもしれない)
reflection を実装し、プログラム自身の構造を読み書きしたい背景として、このメタプログラミング(特に、操作する言語と読み書き対象の言語が一致している場合)に役立つからというものがあると思う。 自分は reflection の概念を Go 言語で初めて知ったが、他の多くの言語にも実装されている。例えば Java や JavaScript にもある。
なぜメタプログラミングしたいのか
じゃあなぜメタプログラミングしたいのか。特に、操作する言語と読み書き対象の言語が一致しているメタプログラミングは何が目的なのか。
TypeScript 等、別の言語を生成するならまだしも、なぜ同じ言語を取り扱うメタプログラミングが必要とされるのか。
実行時にしか分からない情報を取得したい・その情報を使った処理を行いたい
例えば、Go の場合は以下がある。
- interface 型の変数の値の型*2
- 構造体タグ (タグ名や値は任意の値を設定でき、構文がおかしい場合は実行時エラーになる)
- json 等の外部データ (を Go の型システムの世界に変換したい)
また、ジェネリックに近いことも reflect パッケージを使えば実現できる(コード例はWho needs generics? Use ... instead!の 5. Use reflection を参照)
ジェネリックのためにreflect パッケージを使うとそれなりに面倒な感じにはなるっぽいが、元々の言語仕様にないことを実現できてしまうのはメタプログラミングの力だと思う。
Go 言語の reflection について
色々と reflection の概念について書いてきた。実際の Go の reflect パッケージの取り扱い方については以下の資料が役に立ちそうなのでリンク。