panic: assignment to entry in nil map

原因

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 は参照型の方が良いという人はいるんでしょうか。

Win32アプリケーションにVisual Styleを適用する

Visual Studio 2005以降でWin32アプリケーションを作ったときに、コモンコントロールの Visual Style を適用する簡単な方法をまとめる。(.NETからだと何もしなくても使えるのに…)

コモンコントロールの比較(左:旧,右:新)

Visual Style の仕組み

コモンコントロールが実装されている ComCtrl32.dll の読み込むバージョンに6以降を指定すればその見た目を変えられるらしい。Side by Side (SxS) というインスタンス(exe)によって違うバージョンのdllを読み込む機能に指示を与えるためにマニフェスト(manifest)を埋め込む。 マニフェストはxmlで書かれており、VCのリンカーからある程度自動生成できる。(マニフェストツールから追加情報を与えることもできるが、ファイルを新たに作るのが面倒だったので、今回はリンカーオプションから設定した。)また、Vistaから増えた新しいコモンコントロールも使えるようになる。

設定方法

プロジェクトのプロパティ ≫ 構成プロパティ > リンカー > マニフェスト ファイル ≫ 追加のマニフェスト依存関係

に次の行を貼り付ける。(x86の場合)

type='Win32' name='Microsoft.Windows.Common-Controls' version='6.0.0.0' processorArchitecture='x86' publicKeyToken='6595b64144ccf1df' language='*'

複数のアーキテクチャを設定する場合は x86 を amd64 などに変更するか、VS2010ならマクロ $(ProcessorArchitecture) が使えるのでまとめて設定できる。

プロパティページから設定

ref:

『ふしぎな塔と古代の宝』を頒布しました

表紙コミケ初参加の事後報告です。

8/13(土)、C80二日目東X-01aにてCheeseCakeGamesから新作同人ゲーム『ふしぎな塔と古代の宝』を頒布しました。私はサブプログラマとして製作に参加しています。

ゲーム内容は「ローグライク×3Dアクション」で、主人公が剣と魔法を駆使して行く手を阻む敵を倒しながら立体迷路を攻略し塔を登ってゆき宝を集めハイスコアを目指します。

あまり事前告知をしておらず直前に各SNS等で流した程度でしたが、知名度もないのに予想外の盛況で1時半くらいには完売しました。お求めいただいた皆様、ありがとうございます。持っていける限り用意したつもりの約120本でしたが早々に品切れになってしまい、興味を持って頂いたのに提供できなかった方々は申し訳ありませんでした。

公式サイトはただ今準備中です。ゲームの詳しい紹介やプレイ情報共有、またフィードバックを受け付ける予定です。

ICPC2011国内予選

先週(6/25)ICPC国内予選に参加しました。チームmisoは無事アジア地区予選には出れそうですが合宿は難しい感じです。WA出してないのにtimeがやばいことになってます。

A,Bはかんたん。
Cは全探索やるだけ。問題の読み違いに因るデバッグに時間がかかりDより後に提出。
Dも探索で重複排除する。bit使うといい感じ。計算量を見誤って杜撰なコーディングをしてしまい時間を食われる。
EはDP。たぶん早かった。
Fは面倒なだけ。時間切れ。

B,DとEの補助、あとFで残り時間の消費を担当しました。

結果
公式(問題もある) http://icpc2011.ait.kyushu-u.ac.jp/icpc2011/common/guest_standings_en.php
まとめ http://imoz.jp/icpc/2011-domestic.html

6/29追記
予選通過チーム確定 http://icpc2011.ait.kyushu-u.ac.jp/ja/domestic-contest/result

[obsolete] stringの実装(vc,g++)と扱い方

この記事は陳腐化しました。C++11 から Copy on Write は実装禁止になりました。g++4.5 以降でも消えました。但し、終端文字を必要とする仕様は健在です。

(2013/08/25 追記)

std::stringを参照渡しにすると高速化した。何を言っているのか(ry

なんて記事を見ると改めてstringの扱いはハマるとこ多いよなあと感じる。結論から言うと可能な限りconst&やiterator-pairを使えばいいんですが。

stringは一つの文字列プールを指す文字列クラスで、vectorと次の点で似ています。

  • 連続したアドレス上に保管される
  • メモリは自動で管理される(大抵は一定量から倍々)
  • 要素に’\0’(NULL文字)を使用可能

但し、その実装は処理系によって結構違います。細かいところまでは読んでいませんが、大まかにvcとgccの実装の特徴を紹介します。

g++4.3.4

実装の特徴は、

  • 格納する文字列に必要なプールは常にアロケータから確保
  • プールにCopy on Write(CoW)の実装

stringのコピーの際に文字列プールを共有(参照カウント)して不要な複製をコストを削減しています。以下捕捉です。

  • sizeof(string)がプールへのポインタ一つ分なので引数の受け渡しなどで有利
  • 非constの添字アクセスはほんのちょっと余計な処理が入るかも
  • 空文字列は専用のプールが用意されており領域の確保は起きない
  • 文字列定数は必ずコピーされる
  • 常に終端文字が入っている

実際に変更しなくても、非constで要素にアクセスしたときプール全体のコピーが発生するので、コピーを回避するにはconst必須です。

VC2010

実装の特徴は、

  • 終端文字を含めて16B以下はstringのインスタンス内に入る
  • それ以上はアロケータから確保

16B以下(15文字/wstringなら7文字)の文字列の生成や結合が高速です。短い文字列を大量に扱う場合特に効果を発揮します。以下捕捉です。

  • sizeof(string)は16B+3ポインタ分と大きめ(Debugビルドでは+1ポインタ)
  • 文字列定数は必ずコピーされる
  • 常に終端文字が入っている

主観的な意見

コピーを回避したいならconst&やshared_ptrを使うので、CoWは余計なお節介だと思います。しかもゲームなど応答性が必要な場合、遅延実行の発動タイミングを意識する必要あります。というか長い文字列を扱う場合は別のクラスを使った方が無難です。個人的にはメモリプールの管理と文字列ポリシーを分けてアダプタで繋ぐような実装が欲しいです。

どちらも常に終端文字が入っていますが、本来C形式である必要はなく、それ故data()とc_str()が用意されています。Cと親和性が必要でない限りc_str()は使わなくていいので、特にvcで16文字格納できないのはちょっと勿体無く感じます。またCの関数にdata()を突っ込んでも動くので誤解される原因でもあります。実際は仕様上の制約でデメリットが大きいため終端文字を付けない実装は見たことがありませんが。

ついでに検査用のソースも載せておきます。でも細かい実装は読んだ方が分かり易いです。

#include <iostream>
#include <string>
using namespace std;
int main() {
	string s1, s2 = "a";

	cout << "size of string: "
	     << sizeof(s1) << endl;
	cout << "initial capacity: "
	     << s1.capacity() << endl;

	while ((char*)&s1 <= s1.data() && s1.data() < (char*)(&s1 + 1))
		s1 += s2;
	cout << "capacity inside of string: "
	     << (int)s1.size()-1 << endl;

	s1 = s2;
	cout << "copy on write: "
	     << (s1.data() == s2.data()) << endl;

	return 0;
}

Codeforces Beta Round #38

おはようございます、昨日の話です。

この前のJAPLJ contestが3ヶ月ぶりのコンテストでコーディング速度が非常に遅くなっていたので、またリハビリしないとなあと思いながら、SRMなんかも時間が合わなくて中々出れなかった中21:00という久しぶりに参加しやすい時間帯だったので参加したら4時間という長時間で非常に疲れました。因みに今回でyellow(Captain)になりました(・∀・)!

Aは極単純,Bは面倒なだけ,Cはリーディングハード,Dもややリーディングハード,Eは普通,F,Gは読んでません。アルゴリズムの難易度についてはとやかく言える身分じゃないので言及しません。

Eの解法について何人もに訊かれたので、書き留めておきます。

Problem E “Let’s Go Rolling!”

http://codeforces.com/contest/38/problem/E

1 \le n \le 3000 \, , \, -10^9 \le x_{1..n},c_{1..n}\le 10^9
直線上にn個のビー玉(質点)をx[i]置いて左(負方向)に転がします。ビー玉はピンで留める事もできて、転がっててきたビー玉もそこで止まります。各ビー玉のコストc[i]は転がった距離またはピン留めコストです。コストの総和を最小化して下さい。

DPです。右方向にビー玉を追加していきます。今n-1個のビー玉があって、n番目のビー玉を一番右に追加したとします。その時増加するコストは、次のようになります。

  • ピン留めする→そのビー玉のピン留めコスト分
  • ピン留めしない→(一番右の)最後にピン留めした位置までの距離

つまり、n-1個までの情報の内、解を求める為に必要な情報は、n-1個の中で最後にピン留めした位置とそのコストです。最後にピン留めした位置が同じならそれ以降の最適解は同じなので、ピン留めした位置毎に最適(最小)な値を残せばいいことになります。
よって、DPテーブルは次のようになります。下方向にビー玉の数n。右方向に最後にピン留めしたビー玉の番号。括弧書きは(x,c)。データは総コスト(解)。青い矢印はピン留めしないときの解。緑の丸はその行の最適解(最小値)。赤い矢印はピン留めしたときの解。最終的な解は最後の行の最小値です。

DPテーブル
DPテーブル

最後にC++のコードです。図の二次元の表で、新しい行を計算するときには直前の一行の値しか参照していないので、一次元配列を更新していくように実装しています。計算量は変わりません。

#include <iostream>
#include <vector>
#include <algorithm>
#define REP(i,n) for(int i = 0; i < (n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ALL(cont) (cont).begin(), (cont).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<pii> vii;

int main() {
	int n;
	cin >> n;
	vii x(n);
	REP(i,n) cin >> x[i].first >> x[i].second;
	sort(ALL(x));
	vl c(1, x[0].second);
	FOR(i,1,n) {
		c.push_back(x[i].second + *min_element(ALL(c)));
		REP(j,i) c[j] += x[i].first - x[j].first;
	}
	cout << *min_element(ALL(c)) << endl;

	return 0;
}

TopCoder Arena plugin moj

mojというTopCoder Arenaのプラグインの紹介です。日本語でこれについて書いてある情報が無かったので書きました。因みにこの記事の内容の殆どは次のフォーラムの引用です。
TopCoder Forums moj (TZTester modification, new features)

mojについて

SRMのソースコードのスケルトンを生成するときに賢いテストコードを挿入します。問題に提示されている全テストケースを瞬時に正確に判定でき、時間を節約できます。
mojはTZTesterの修正版です。TZTester他のプラグインについてはぐぐってください。
機能要約:

  • 出力がかわいくなる
  • doubleの誤差1e-9まで許容
  • 簡単にカスタムテストを作れる
  • Javaと切り替え可能
  • 実行時間測定

他に特筆すべきこと:

  • gcc,VCに対応
  • テストコードがclassの外にあり邪魔にならない

出力はこんな感じにかわいくなります。

Test Case #0... PASSED (relative error 5.44969e-014)
Test Case #1... PASSED (relative error 5.68462e-012)
Test Case #2... PASSED (relative error 4.05691e-008)
Test Case #3... PASSED

使い方

フォーラムの “Download moj” のリンクからzipを落とします。CodeProcessorとFileEditも同梱されています。
基本的にmoj_instructions.txtに説明が書かれていますが、周りのプラグインの入れ方は先程のようにぐぐったほうが詳しく画像付きで説明されていたりするので、その方が間違いもなく楽です。TZTesterとの差分は、次のように読み替えるだけです。

  • TZTester.jar → moj.jar
  • tangentz.TZTester → moj.moj

既に他のプラグインを入れている方は、次の箇所を更新してください。

  • Common ClassPath
  • CodeProcessor Configuration > CodeProcessor Script
  • CodeProcessor Configuration > FileEdit Configuration > Code Template

雛形はzipにcpp,javaファイルがあるので、それに習って書き換えます。

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

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倍程度の差でしょうか。まあ十分速い部類だと思いますが、どうでしょう?w
改善の余地もあるそうなので今後にも期待したいです。

Go言語使いたい

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

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

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

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

処理系は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で書けると非常に楽しそうです。特にパースが速いなら快適な補完が利きそう。でもデバッガは難しそうですね。

PowerCommands for Visual Studio 2010

PowerCommands_Preview

PowerCommands for Visual Studio 2010というプラグインの紹介。何気に便利です。ソリューションエクスプローラから右クリックでコンソールやエクスプローラ,パスのコピーが出来るようになります。他にも色々機能がありそうだけどまあそれだけで十分便利。VS2010でしか使えないのが不思議。

使用しているとなぜかエディタで文字列を選択(反転)したときにVS自体のフォーカスが高速にチカチカと明滅(?)する謎の問題が発生。ウィンドウを強調しているわけでなく本当にフォーカスが当たったり外れたりを高速に繰り返します。もちろんエディタにマトモに文字が打てなくなります。

結果的にForumの方に解決法が載っていましたが英語でしか書いてなくてうまく検索にヒットせずちょっと間面倒でした。オプションからExtract Constantのチェックを外すと治ります。

Visual Studio Options