Go言語

panic: assignment to entry in nil map

sulume

原因

Go のプリミティブ型の一つ map は値型だと勘違いしていて、こんな runtime error と出会いました。

var m map[int]int // a map variable
m[0] = 1 // panic: assignment to entry in nil map

map は参照型でした。nil 値 (nil map) があります。実体は make か literal で作ります。

var a = make(map[int]int) // make an (initialized) map value
a[0] = 1
var b = map[int]int{} // a map literal value
b[0] = 1

注意点

Java 等の参照型主体の言語を使う人にはむしろ自然に見えるかもしれないが、次のような挙動は流石にきもいので気をつけて使ったほうが良さそう。

var m = *new(map[int]int)
println(m[0]) // 0
m[0] = 1 // panic: assignment to entry in nil map

new は non-nil な値を返しますが initialized value は作られず、nil map は empty map のように振る舞い、0で呼び出すと既定動作として初期値が返ります。そのあと代入して初めて落ちます。nil map は内部表現の実体が無く要素を追加することだけができず、挙動は似ていても nil map と empty map は区別されます。

var a = map[int]int(nil)
var b = map[int]int{}
println(a[0], a == nil) // 0 true
println(b[0], b == nil) // 0 false
// println(a == b) // invalid operation: a == b (map can only be compared to nil)
a[0] = 1
b[0] = 1 // panic: assignment to entry in nil map

なお、参照型なので普通に変数や引数にコピーを取ると実体は共有されます。

var a = map[int]int{}
a[0] = 1
var b = map[int]int(a)
b[0] = 2
println(a[0]) // 2

動作は仕様 Map types にさっくりと書いてあります。他には slice や channel も参照型で、それらも変数や new の初期値は nil で、当然 empty とも区別されます。

言い訳

なぜ勘違いしたかというと、多くの参照型を扱う言語と違って、Go にはポインタ型と強い型付けがあり C のように値とポインタを区別して扱うので、参照として扱いたい部分にはポインタを使うことで実現でき、特別な理由がない限り言語としては参照型は必要ないからです。ユーザ定義型 struct, interface だけでなく array も値型です (string, function は immutable)。

特別な理由とは例えば、slice は pointer と同じく本質的に他の値を参照する機能を持っているので参照型（逆に C 等のポインタと配列型がもつ配列を参照する機能は Go の pointer にはない）。channel は、通信は普通実体を共有し、実体の違うコピーが取れるのは直感に反するので、毎回ポインタを使うコストも掛かる uncopyable な型を作るよりは参照型の方が妥当。とかたぶんそんな感じです。

一方 map は、C++ ののように連想配列自体は値型で実現できます。Go にポインタ型がある以上それなりの理由がないと参照型ににはならないと思っていたので値型だと思い込んでいました。array が値型でも map は参照型の方が良いという人はいるんでしょうか。

Go言語の並列性と実行速度

sulume

Go言語の並列性については次を参照。並列性

測定にはそれなりに時間がかかる処理で並列化出来る問題が必要です。ということで「任意の大きさのライツアウトの答えを求める」プログラムにしました。
入力は整数二つ横幅と縦幅、出力は0,1で押すボタン。範囲は矩形で初期状態は全点灯。 アルゴリズムは最上段を全通り試して二段目以降は上段から確定していって、全消灯できたときそれを解とします。全通りの解を全て求めてもいいけど、話の都合上見つかった1つの特解のみ出力します。
GoとC++/OpenMPで実装しました。両方取り敢えず並列化しています。

package main

import "fmt"
import "runtime"

const NCPU = 4 // 実行するスレッド数

func main() {
	runtime.GOMAXPROCS(NCPU) // 今後いずれ不要になる
	var w, h uint
	fmt.Scan(&w, &h)

	var m uint64 = 1 << w - 1
	cans := make(chan []uint64)
	go func() {
		for i := uint64(0); i <= m; i++ {
			go func(p uint64) { // 最上段の値毎の処理をgoroutineに
				d := make([]uint64, h)
				d[0] = p
				f := p << 1 ^ p ^ p >> 1
				for i := uint(1); i < h; i++ {
					d[i] = ^f & m
					f = d[i-1] ^ d[i] << 1 ^ d[i] ^ d[i] >> 1
				}
				if f & m == m {
					cans <- d // cansはクロージャ
				}
			}(i)
		}
	}()

	format := fmt.Sprintf("%%0%vb\n", w)
	for _, e := range <- cans {
		fmt.Printf(format, e)
	}
}

#include <iostream>
#include <vector>
#include <bitset>
#include <omp.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{
	size_t w, h;
	cin >> w >> h;

	vector<ull> ans;
	ull m = (1ull << w) - 1;
	#pragma omp parallel for schedule(dynamic, 1)
	for(ll p = 0; p <= m; ++p) // omp forの要求でsigned
	{
		if(!ans.empty()) continue; // omp parallel中はbreak不可
		vector<ull> d(h, 0);
		d[0] = p;
		ull f = p << 1 ^ p ^ p >> 1;
		for(size_t i = 1; i < h; ++i)
		{
			d[i] = ~f & m;
			f = d[i-1] ^ d[i] << 1 ^ d[i] ^ d[i] >> 1;
		}
		if((f & m) == m)
			#pragma omp critical
			ans = d;
	}

	for(size_t i = 0; i < h; ++i)
		cout << bitset<64>(ans[i]).to_string().substr(64ull - w) << endl;

	return 0;
}

goroutine間では共有変数は極力使用せず、チャネルを使って通信します。L14でcansは解を得るためのチャネルです。L33で解を求めて処理をブロックします。またL28でiをクロージャにしないのは参照型だからです→詳しく。 L15をgoする理由は、mが大きい時cansを要求するまでに時間が掛かるのを防ぐためです。もしgoしないと、L17のgoroutineがmだけ大量に生成されます。またgoしておくことでcansの要求に応じてL17の方が優先的に実行され、goroutineが減ったときに勝手に増やしてくれるようになります。実行中のメモリ使用量を見ると一目瞭然です。
mainが返るとgoroutineが残っていてもプログラムは終了します。このプログラムではcansは一回しか要求していませんが、もう一度要求すると次の解が出てきます。

2つのプログラムを実行時間を測定しました。共に4並列で、入力は20×20です。厳密な比較にはなりませんが、参考にはなると思います。因みにgcのスケジューリングは不完全だそうなので、今後改善されるかもしれません。C++のomp forでschedule(dynamic, 1)としているのは、Goのスケジュールと近似するためですが、実際はstaticの方が速いです。
Atom D510; C++:1.30[s] Go:6.88[s]
Core i7 860; C++:0.22[s] Go:2.16[s]
ざっと5～10倍程度の差でしょうか。まあ十分速い部類だと思いますが、どうでしょう？ｗ
改善の余地もあるそうなので今後にも期待したいです。

Go言語使いたい

sulume

周知のGo言語、Google社員によって作られた変だけど実用的な言語。と思ってます。公式サイトに十分に情報が乗っているので参考書には困りません。英語が難しいなら日本語訳している情報サイトもあります。プログラミング言語Goの情報サイト
これからちょくちょく勉強して行くつもりです。Go言語はアルゴリズムの記述や速度が必要なWebシステムなんかに持って来いな気がします。因みにgcではC++とリンク不可で、Cのみ可だそうです（gccgoは両方可）。尚、GoからC++に、C++からGoに引っ張るのは”まだ”できないそうです。ｗｋｔｋ

主観的に特徴を書くとこんな感じです。

  • ステートメントが少ない
  • 構文の制約が厳しい（表現の統一）
  • ビルトイン型/関数が必要十分
  • 動的言語のような柔軟な記述
  • 独特で便利な機構
  • コンパイルが超高速
  • 実行も速い
  • 並列処理が簡単
  • 豊富な標準パッケージ

正確に知りたい方は他を参照してください。

処理系はgo-windowsもあるけど何かうまい使い方が分からないから今はlinux上のgcで試してみました。

Codeforces #23 A. Youre Given a String…
文字列の中から2回以上出現する部分文字列の最大長を求める。

package main
import "fmt"
func main() {
	var s string
	fmt.Scanln(&s)
	g := 0
	for i := 0; i < len(s); i++ {
		for j := i+1; j < len(s); j++ {
			k := 0
			for j+k < len(s) && s[i+k] == s[j+k] { k++ }
			if g < k { g = k }
		}
	}
	fmt.Println(g)
}

特に変な機構も使ってないので構文しか分かりませんが。。次に比較用にC++で、

#include <iostream>
#include <string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int g = 0;
	for(int i = 0; i < s.size(); ++i)
		for(int j = i+1; j < s.size(); ++j)
		{
			int k = 0;
			while(j+k < s.size() && s[i+k] == s[j+k]) k++;
			g = max(g, k);
		}
	cout << g << endl;
	return 0;
}

IDEで書けると非常に楽しそうです。特にパースが速いなら快適な補完が利きそう。でもデバッガは難しそうですね。