前回と前々回で Go 言語の基本的なデータ型と制御構造について一通り説明しました。今回は「関数 (function)」について説明します。
プログラミングは模型を組み立てる作業と似ています。簡単な処理は Go 言語の機能やライブラリを使って実現することができます。ところが、模型が大きくなると、一度に全体を組み立てるのは難しくなります。このような場合、全体をいくつかに分割して、まずその部分ごとに作ります。最後に、それを結合して全体を完成させます。
これはプログラミングにも当てはまります。実現しようとする処理が複雑になると、一度に全部作ることは難しくなります。そこで、全体を小さな処理に分割して、一つ一つの処理を作成し、それらを組み合わせて全体のプログラムを完成させます [*1]。
分割した処理を作成する場合、それを一つの部品として扱えると便利です。つまり、小さな部品を作り、それを使って大きな部品を作り、最後にそれを組み合わせて全体を完成させます。このとき、もっとも基本となる部品が関数になります。
Go 言語の関数定義はとても簡単です。例題として、数を 2 乗する関数を作ってみましょう。次のリストを見てください。
リスト : 数を 2 乗する関数 (sample31.go)
package main
import "fmt"
func square(x int) int {
return x * x
}
func main() {
fmt.Println(square(10))
}
関数定義の構文を下図に示します。
func 名前(仮引数名 型, ...) 返り値の型 {
処理A
処理B
...
}
図 : Go 言語の関数定義
関数の定義は次の図のように数式と比較するとわかりやすいでしょう。
ｆ （ｘ） ＝ ｘ * ｘ
名前 引数 処理内容
func square (x int) int { return x * x }
図 : 関数定義と数式の比較
関数定義は func から始めます。次の square が関数名、( ) の中の x が入力データを受け取る引数とその型、次が関数が出力する値の型、ブロック { } の中の return x * x が実行される処理です。関数定義で使用する引数のことを「仮引数」、実際に与えられる引数を「実引数」といいます。square の定義で使用した x が仮引数で、square(10) の 10 が実引数になります。
そして、関数が出力する値を「返り値」といいます。返り値の型は仮引数リスト ( ) の後ろで指定します。Go 言語の場合、関数の値は return 文を使って返します。return x * x とすることで、x * x の計算結果を返します。
それでは実際に実行してみましょう。
$ go run sample31.go 100
なお、引数がない場合でも仮引数リスト ( ) は必要です。また、値を返さない関数も定義することができます。この場合、main 関数のように返り値の型を指定しません。
それでは、ここで変数 x に値が代入されている場合を考えてみましょう。次の例を見てください。
リスト : 局所変数と大域変数 (sample32.go)
package main
import "fmt"
var x = 10
func square(x int) int {
return x * x
}
func main() {
fmt.Println(x)
fmt.Println(square(5))
fmt.Println(x)
}
$ go run sample32.go 10 25 10
関数の外で変数 x を定義しています。main 関数の中で変数 x は定義されていません。最初の Println では外側の変数 x を参照するので 10 が表示されます。それでは、square(5) の実行結果はどうなると思いますか。
x には 10 がセットされているので 10 の 2 乗を計算して返り値は 100 になるのでしょうか。これは 5 の 2 乗を計算して結果は 25 になります。そして、square を実行したあとでも変数 x の値は変わりません。
square の仮引数 x は、その関数が実行されている間だけ有効です。このような変数を「ローカル変数 (local variable)」もしくは「局所変数」といいます。これに対し、プログラムのどこからでもアクセスできる変数を「グローバル変数 (golbal variable)」もしくは「大域変数」といいます。Go 言語は変数の値を求めるとき、それが局所変数であればその値を参照します。局所変数でなければ、大域変数の値を参照します。
プログラムを作る場合、関数を部品のように使います。ある関数を呼び出す場合、いままで使っていた変数の値が勝手に書き換えられると、呼び出す方が困ってしまいます。部品であるならば、ほかの処理に影響を及ぼさないように、自分自身の中で処理を完結させることが望ましいのです。これを実現するための必須機能が局所変数なのです。
Go 言語の場合、関数の仮引数は局所変数になりますが、それ以外にも関数の中で局所変数が必要になる場合があります。Go 言語は関数内で宣言された変数を局所変数として扱います。
簡単な例を示しましょう。
リスト : 局所変数の有効範囲 (sample33.go)
package main
import "fmt"
func main() {
x := 1
{
y := 2
{
z := 3
fmt.Println(x)
fmt.Println(y)
fmt.Println(z)
}
fmt.Println(x)
fmt.Println(y)
// fmt.Println(z) z は範囲外 (コンパイルエラー)
}
fmt.Println(x)
//fmt.Println(y) y は範囲外 (コンパイルエラー)
//fmt.Println(z) z は範囲外 (コンパイルエラー)
}
$ go run sample33.go 1 2 3 1 2 1
局所変数が値を保持する期間のことを、変数の「有効範囲 (scope : スコープ)」といいます。局所変数の有効範囲は変数が定義されているブロックの中だけです。for 文の場合も同じで、初期化処理で宣言された局所変数は、そのあとのブロックが有効範囲になります。
変数 x は main の一番外側のブロックで定義されているので、main の処理が終了するまで有効です。変数 y は 2 番目のブロックで、変数 z は 3 番目のブロックで定義されているので、各々のブロックの終わりまでが変数の有効範囲になります。ブロックの実行が終了すると、そのブロックで定義された局所変数は廃棄されます。
したがって、3 番目のブロックの中では変数 x, y, z が有効です。ブロックの処理が終了すると変数 z が廃棄されるので、2 番目のブロックの中では変数 x, y が有効です。そして、そのブロックの処理が終了すると、変数 y が廃棄されるので有効な変数は x だけになります。
もう一つ簡単な例を示しましょう。
リスト : x の n 乗を求める (sample34.go)
package main
import "fmt"
func pow(x int, n int) int {
v := 1
for i := 0; i < n; i++ {
v *= x
}
return v
}
func main() {
fmt.Println(pow(2, 8))
fmt.Println(pow(2, 16))
}
関数 pow は x の n 乗を求めます。関数の定義で引数の型が同じ場合は、最後の型を残してあとは省略することができます。
pow(x int, n int) ==> pow(x, n int)
変数 v は関数内で宣言しているので、局所変数として扱われます。また、for 文で使う変数 i も局所変数になります。pow の処理内容は簡単です。最初に変数 v を 1 に初期化します。次に for 文で v *= x を n 回繰り返します。これで v の値は x の n 乗になります。最後に v の値を返します。実際に実行すると次のようになります。
$ go run sample34.go 256 65536
Go 言語の関数は複数の値を返すことができます。これを「多値」といいます。Lisp / Scheme ではお馴染みの機能です。Go 言語で複数の値を返すのは簡単です。
func 関数名(引数1 型1, ...) (型1, 型2, ..., 型n) {
...
return 値1, 値2, ..., 値n
}
上図のように、return で複数の値をカンマで区切って指定します。もちろん、返り値の型も複数指定してください。関数の呼び出し側は、多重代入を使って簡単に多値を受け取ることができます。
簡単な例を示しましょう。
リスト : 多値 (sample35.go)
package main
import "fmt"
func divMod(x, y int) (int, int) {
return x / y, x % y
}
func main() {
p, q := divMod(10, 3)
fmt.Println(p)
fmt.Println(q)
}
関数 divMod は x と y の商と剰余を多値で返します。呼び出し側は変数 p, q で 2 つの値を受け取ります。
それでは実行してみましょう。
$ go run sample35.go 3 1
Go 言語は返り値を変数名で指定することができます。
func 関数名(引数1 型1, ...) (変数a 型a, 変数b 型b, ...) {
...
return
}
この場合、return に変数名を指定する必要はなく、あらかじめ宣言した変数 a, b, ... の値が返されます。たとえば、関数 divMod を書き直すと、次のようになります。
リスト : 多値 (2)
func divMod(x, y int) (p, q int) {
p, q = x / y, x % y
return
}
仮引数の個数よりも多くの値を受け取りたい場合は、最後の引数の後ろに ... を付けて、その後ろに型を指定します。これを「可変長引数」といい、仮引数に入りきらない値は、スライスに格納されて可変長引数に渡されます。これで可変個の引数を受け取る関数を定義することができます。
簡単な例を示しましょう。
リスト : 可変長引数 (sample36.go)
package main
import "fmt"
func foo1(a int, args ...int) {
fmt.Println(a, args)
}
func foo0(args ...int) {
fmt.Println(args)
}
func main() {
foo0()
foo0(1)
foo0(1, 2)
foo0(1, 2, 3)
foo1(1)
foo1(1, 2)
foo1(1, 2, 3)
foo1(1, 2, 3, 4)
}
$ go run sample36.go [] [1] [1 2] [1 2 3] 1 [] 1 [2] 1 [2 3] 1 [2 3 4]
可変長引数は通常の仮引数よりも後ろに定義します。関数 foo0 は、0 個以上の引数を受け取る関数、つまり、引数があってもなくてもどちらでも動作します。この場合、仮引数は args だけになります。実引数がない場合、引数 args には空のスライス (nil) が渡されます。もし、複数の引数があれば、それらをスライスにまとめて仮引数 args に渡します。
関数 foo1 は通常の引数が一つしかありません。foo1(1) と呼び出すと、引数 a に 1 がセットされます。実引数はもうないので、仮引数 args には空のスライスが渡されます。次に foo1(1, 2) と呼び出すと、実引数 2 がスライスに格納されて仮引数 args に渡されます。同様に、foo(1, 2, 3) は 2 と 3 がスライスに格納されて仮引数 args に渡されます。
可変長引数を持つ関数にデータを渡すとき、データがスライスに格納されていると、スライスから要素を取り出して渡さないといけません。これでは面倒なので、Go 言語にはスライスを展開して要素を可変長引数に渡す機能が用意されています。次の例を見てください。
リスト : スライスを展開して可変長引数に渡す (sample3c.go)
package main
import "fmt"
func foo(x int, y... int) {
fmt.Println(x, y)
}
func main() {
a := []int{1, 2, 3}
b := []int{4, 5, 6}
foo(0, a...)
fmt.Println(append(a, b...))
}
$ go run sample3c.go 0 [1 2 3] [1 2 3 4 5 6]
関数 foo は仮引数 x と可変長引数 y を持っています。ここで、foo の可変長引数にスライス a の要素を渡すことを考えます。このとき、a の後ろに ... を付けて呼び出すと、スライス a を展開して要素を可変長引数に渡します。つまり、foo(0, a[0], a[1], a[2]) と同じ動作になります。
組み込み関数 append の第 2 引数は可変長引数なので、append(a, b...) とするとスライスを連結することができます。
それでは簡単な例題として、データの探索処理を作ってみましょう。データの探索とは、データの集まりの中から特定のデータを見つける処理のことです。データの探索はプログラムの中で最も基本的な操作の一つです。たとえば配列からデータを探す場合、いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを「線形探索 (linear searching)」といます。次のリストを見てください。
リスト : データの探索 (sample37.go)
package main
import "fmt"
// n があるか
func find(n int, ary []int) bool {
for _, v := range ary {
if n == v { return true }
}
return false
}
// n の位置を求める
func position(n int, ary []int) int {
for i, v := range ary {
if n == v { return i }
}
return -1
}
// n の個数を求める
func count(n int, ary []int) int {
c := 0
for _, v := range ary {
if n == v { c++ }
}
return c
}
func main() {
a := []int{1, 2, 3, 1, 2, 3, 4, 5};
fmt.Println(find(4, a))
fmt.Println(find(6, a))
fmt.Println(position(5, a))
fmt.Println(position(7, a))
fmt.Println(count(3, a))
fmt.Println(count(8, a))
}
C>go run sample37.go true false 7 -1 2 0
Go 言語の場合、関数の引数に配列を指定すると、関数の仮引数として配列の領域が確保され、そこに実引数の配列がコピーされます。小さな配列であれば問題は少ないのですが、大きな配列になるといちいちコピーするのは大変です。そこで、Go 言語は配列ではなくスライスを渡すのが一般的です。
関数 find はスライス ary の中から引数 n と等しいデータを探します。for 文で配列の要素を一つずつ順番に取り出して n と比較します。等しい場合は true を返します。for ループが終了する場合は n と等しい要素が見つからなかったので false を返します。関数 position は、データを見つけた場合はその位置 i を返し、見つからない場合は -1 を返します。
position は最初に見つけた要素の位置を返しますが、同じ要素が配列に複数あるかもしれません。関数 count は等しい要素の個数を数えて返します。局所変数 c を 0 に初期化し、n と等しい要素 x を見つけたら c の値を +1 します。最後に c の値を返します。
このように、線形探索は簡単にプログラムできますが、大きな欠点があります。データ数が多くなると処理に時間がかかるのです。近年、パソコンの性能は著しく向上しているので、線形探索でどうにかなる場合もありますが、データ数が多くて時間かかかるのであれば、次の例題で取り上げる「二分探索」やマップ (map) を使ってみるとよいでしょう。
次は「二分探索 (バイナリサーチ：binary searching)」を例題として取り上げます。線形探索の実行時間は要素数 N に比例するので、N が大きくなると時間がかかるようになります。これに対し、二分探索は log2 N に比例する時間でデータを探すことができます。
ただし、探索するデータはあらかじめ昇順に並べておく必要があります。この操作を「ソート (sort)」といいます。二分探索は最初にデータをソートしておかないといけないので、線形探索に比べて準備に時間がかかります。
二分探索の動作を下図に示します。
[11 22 33 44 55 66 77 88 99] key は 66
↑ 66 > 55 後半を探す
11 22 33 44 55 [66 77 88 99] 88 > 66 前半を探す
↑
11 22 33 44 55 [66 77] 88 99 77 > 66 前半を探す
↑
11 22 33 44 55 [66] 77 88 99 66 = 66 発見
↑
図 : 二分探索
二分探索は探索する区間を半分に分割しながら調べていきます。キーが 66 の場合を考えてみましょう。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索すればいいのです。
あとは、これと同じことを後半部分に対して行います。最後には区間の要素が一つしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 1,000,000 個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。
それでは、配列からデータを二分探索するプログラムを作ってみましょう。次のリストを見てください。
リスト : 二分探索 (sample38.go)
package main
import "fmt"
func binarySearch(n int, ary []int) bool {
low := 0
high := len(ary) - 1
for low <= high {
mid := low + (high - low) / 2
if ary[mid] == n {
return true
} else if ary[mid] < n {
low = mid + 1
} else {
high = mid - 1
}
}
return false
}
func main() {
a := []int{10, 20, 30, 40, 50, 60, 70, 80}
fmt.Println(binarySearch(10, a))
fmt.Println(binarySearch(40, a))
fmt.Println(binarySearch(80, a))
fmt.Println(binarySearch(0, a))
fmt.Println(binarySearch(45, a))
fmt.Println(binarySearch(90, a))
}
$ go run sample38.go true true true false false false
最初に、探索する区間を示す変数 low と high を初期化します。配列の長さは len(ary) で取得し、最後の要素の位置を high にセットします。次の for ループで、探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて変数 mid にセットします。if 文で mid の位置にある要素と n を比較し、等しい場合は探索成功です。return で true を返します。
n が大きい場合は区間の後半を調べます。変数 low に mid + 1 をセットします。逆に、n が小さい場合は前半を調べるため、変数 high に mid - 1 をセットします。これを区間が二分割できるあいだ繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し false を返します。
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、途中でデータを追加するには、データを挿入する位置を求め、それ以降のデータを後ろへ移動する処理が必要になります。つまり、データの登録には時間がかかるのです。
したがって、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。
ソート (sort) は、ある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。Go 言語には配列 (スライス) をソートするパッケージ sort がありますが、私達でもプログラムすることができます。
今回は簡単な例題ということで、単純挿入ソート (insert sort) を取り上げます。単純挿入ソートの考え方はとても簡単です。ソート済みの配列に新しいデータを挿入していくことでソートを行います。次の図を見てください。
[9] 5 3 7 6 4 8 5 を取り出す
[9] * 3 7 6 4 8 5 を[9]の中に挿入する
[5 9] 3 7 6 4 8 9 をひとつずらして先頭に 5 を挿入
[5 9] * 7 6 4 8 3 を取り出して[5 9]の中に挿入する
[3 5 9] 7 6 4 8 先頭に 3 を挿入
[3 5 9] * 6 4 8 7 を取り出して[3 5 9] に挿入
[3 5 7 9] 6 4 8 9 を動かして 7 を挿入
残りの要素も同様に行う
図 : 挿入ソート
最初は先頭のデータひとつがソート済みと考えて、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。
プログラムは次のようになります。
リスト : 単純挿入ソート (sample39.go)
package main
import "fmt"
func insertSort(ary []int) {
for i := 1; i < len(ary); i++ {
tmp := ary[i]
j := i - 1
for ; j >= 0 && tmp < ary[j]; j-- {
ary[j + 1] = ary[j]
}
ary[j + 1] = tmp
}
}
func main() {
a := []int{5,6,4,7,3,8,2,9,1,0}
b := []int{9,8,7,6,5,4,3,2,1,0}
c := []int{0,1,2,3,4,5,6,7,8,9}
insertSort(a)
insertSort(b)
insertSort(c)
fmt.Println(a)
fmt.Println(b)
fmt.Println(c)
}
最初のループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ（添字では 1）を取り出して挿入していきます。2 番目のループで挿入する位置を探しています。探索は後ろから前に向かって行っていて、このときデータの移動も同時に行っています。
それでは実行してみましょう。
$ go run sample39.go [0 1 2 3 4 5 6 7 8 9] [0 1 2 3 4 5 6 7 8 9] [0 1 2 3 4 5 6 7 8 9]
単純挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。単純挿入ソートは簡単ですが遅いアルゴリズムなのです。高速なソートは次回の例題で取り上げます。
それでは関数を使って、前回作成した素数を求めるプログラムを書き直して見ましょう。次のリストを見てください。
リスト : 素数を求める (prime1.go)
package main
import "fmt"
func isPrime(n, primeSize int, primeTable []int) bool {
for i := 1; i < primeSize; i++ {
p := primeTable[i]
if p * p > n { break }
if n % p == 0 {
return false
}
}
return true
}
func main() {
primeTable := make([]int, 100)
primeTable[0] = 2
primeSize := 1
for n := 3; n < len(primeTable); n += 2 {
if isPrime(n, primeSize, primeTable) {
primeTable[primeSize] = n
primeSize++
}
}
fmt.Println(primeTable[:primeSize])
}
$ go run prime1.go [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]
数値 n が素数か判定する処理を関数 isPrime で行うように変更します。isPrime は数値 n と素数の個数 primeSize と配列 primeTable を受け取り、n が素数で割り切れれば false を返し、そうでなければ true を返します。
isPrime を使うと、素数を求める処理は簡単にプログラムすることができます。isPrime が true を返したら n を配列 primeTable に追加するだけです。素数の判定処理を関数 isPrime で行うことにより、関数 main はとてもわかりやすいプログラムになりました。
一般に、関数呼び出しには二つの方法があります。一つが「値呼び (call by value)」で、もう一つが「参照呼び (call by reference)」です。近代的なプログラミング言語では「値呼び」が主流です。
値呼びの概念はとても簡単です。
値呼びのポイントは 2 です。データを引数に代入するとき、データのコピーが行われるのです。たとえば、変数 a の値が 10 の場合、関数 foo(a) を呼び出すと、実引数 a の値 10 が foo の仮引数にコピーされます。変数に格納されている値そのものを関数に渡すので、「値渡し」とか「値呼び」と呼ばれます。
また、値呼びは任意の式の値を実引数として渡すことができます。たとえば foo(a + b) の場合、引数に渡された式 a + bを計算し、その結果が foo の仮引数に渡されます。
値呼びは単純でわかりやすいのですが、呼び出し先 (caller) から呼び出し元 (callee) の局所変数にアクセスできると便利な場合もあります。仮引数に対する更新が直ちに実引数にも及ぶような呼び出し方が「参照呼び」です。
Go 言語は「値呼び」です。関数を呼び出すとき、実引数の値は仮引数にコピーされます。ただし、スライスやマップは「参照呼び」のように振舞います。これは、スライスやマップが本体となる配列への参照 (ポインタ) を持っていて、それが仮引数にコピーされるからです。したがって、スライスやマップのような更新可能なデータ構造の場合、関数の引数にスライスを渡してそれを破壊的に修正すると、呼び出し元の変数の値も書き換えられたようにみえます。
簡単な例を示しましょう。
リスト : 渡されたスライスを破壊的に修正 (sample3a.go)
package main
import "fmt"
func foo(ary []int) {
ary[0] *= 10
}
func main() {
a := []int{1, 2, 3, 4}
fmt.Println(a)
foo(a)
fmt.Println(a)
}
$ go run sample3a.go [1 2 3 4] [10 2 3 4]
変数 a にスライス []int{1, 2, 3, 4} をセットします。関数 foo は配列 ary の先頭要素を 10 倍します。このとき、スライス ary の内容を破壊的に修正していることに注意してください。foo(a) を呼び出したあと a を表示すると、先頭要素が 10 に書き換えられていることがわかります。
この場合、変数 a の値が書き換えられたのではなく、a が参照している配列の内容を直接書き換えているだけなのです。元の値をそのままにしておきたい場合は、元のスライスをコピーして新しいスライスを生成してください。スライスのコピーは組み込み関数 copy を使うと簡単です。
copy(dst, src []T) int
copy はスライス src の要素を dst にコピーします。返り値はコピーした要素数です。src と dst で長さが異なる場合は短いほうに合わせます。
簡単な例を示します。
リスト : copy の使用例 (sample3b.go)
package main
import "fmt"
func main() {
a := []int{1,2,3,4,5,6,7,8}
b := make([]int, 10)
c := make([]int, 4)
fmt.Println(a)
fmt.Println(b)
fmt.Println(c)
copy(b, a)
copy(c, a)
fmt.Println(b)
fmt.Println(c)
}
$ go run sample3b.go [1 2 3 4 5 6 7 8] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0] [1 2 3 4 5 6 7 8 0 0] [1 2 3 4]
このように、copy を使ってスライスの要素を簡単にコピーすることができます。
今回はここまでです。次回は「再帰定義」について説明します。