読者です 読者をやめる 読者になる 読者になる

文字列型をキーとしたunordered_map

プログラミングをしている際、文字列型をキーとした連想配列を扱いたい時がある。

そのような時に用いられるのは多くの場合unordered_mapだ。

using Map = unordered_map<string, int>;

Map m = {
	{ "a", 1 },
	{ "b", 2 },
	{ "c", 3 },
};
m["a"]; // 1
m["b"]; // 2

ところで、unordered_map の []演算子 の引数は (const key_type&) あるいは (key_type&&) である。

そして、今 key_type は std::string だ。

そのため、

m["a"];

m.operator[](string{"a"});

と同義だ。

なんでもないアクセスのために std::string のインスタンスが生成されている。そして、std::string のコンストラクタでは "a" という文字列を格納するためのバッファが確保される。バッファの確保は大抵の場合比較的遅い。

なにか良い方法はないか。


さて、boost::string_ref と言うものが存在する。詳細な説明は省略するが、要は文字列を格納したバッファへの ポインタ と 文字数 のみを保持するだけのクラスである。

string_ref は内部でポインタを保持するだけで、一切のバッファ確保を行わない。

つまり、こいつをキーに出来れば上のような問題は起きないのだ。

そして勿論、 string_ref 等のような独自定義の型であっても、==演算子オーバーロード(あるいはコンパレータ)とハッシュ値を求めるハッシャさえ存在すれば、unordered_mapのキーとして使える。

#include <boost/utility/string_ref.hpp>
#include <boost/functional/hash.hpp> // boost::hash_range

using namespace boost;

struct Hasher {
	size_t operator()(string_ref str) const {
		return hash_range(str.cbegin(), str.cend());
	}
};

using Map = unordered_map<string_ref, int, Hasher>;

Map m = {
	{ "a", 1 },
	{ "b", 2 },
	{ "c", 3 },
};
// バッファの確保は起こらない
m["a"]; // 1
m["b"]; // 2

一見これで良さそうだ。

だが、これにもまだ問題がある。

先程も述べたように、string_ref はあくまでバッファへのポインタを保持するクラスである。つまり、文字列の本体はどこかに存在していなくてはならないのだ。

そのため、

int main() {
	Map m;

	{
		string str = "###";
		m[str] = 42;
	}// もはやstrは存在しない

	m["###"]; // ?
}

このようなコードは未定義動作となる。

何故ならば、m["###"]; が実行されるときにはもうバッファの本体たる str は破壊されているからだ。


今必要なのは、キーを登録する際には std::string のようにバッファを確保し、ただアクセスするときには boost::string_ref のようにバッファを確保せず、比較とハッシュ値の算出のみを行う型である。

では、愚直に実装してみる。

#include <boost/optional.hpp>

using namespace boost;

class Key {
	optional<string> str;
	string_ref       ref;

public:
	Key(string_ref s, bool flag = false) {
		if(flag) {
			str = s.to_string();
			ref = *str;
		}
		else {
			ref = s;
		}
	}

	Key(const Key& key)
		: str(key.str), ref(str ? *str : key.ref) {}

	Key(Key&& key)
		: str(std::move(key.str)), ref(str ? *str : key.ref) {}

	bool operator==(const Key& key) const {
		return ref == key.ref;
	}

	string_ref str() const {
		return ref;
	}
};

struct Hasher {
	size_t operator()(const Key& key) const {
		return hash_range(key.str().cbegin(), key.str().cend());
	}
};

boost::optional を用いてバッファの有効/無効を表現した。

また、コンストラクタの第二引数のフラグのon/offによってバッファを確保するかどうかを分岐させている。

実際にキーとして使用するときには以下のようになる。

using Map = unordered_map<Key, int, Hasher>;

Map m = {
	{ Key{"a", true}, 1 },
	{ Key{"b", true}, 2 },
	{ Key{"c", true}, 3 },
};

m[{"a"}]; // 1

string_ref str = "b";
m[str]; // 2   暗黙の型変換

……………………。

テキトーに時間計測を行ってみた結果、確かに、string をキーとした時よりも、速かった。とは言えそこまで大した差ではない。

ぶっちゃけこんなことするくらいならばもっと別の箇所を見直したほうがいいような気がした。

v8を崇めよ

映画を見に行った。

今年頭の「楽園追放」ぶりの映画館だ。

お目当ては「ジュラシック・ワールド」、Twitterで某氏がご満悦のようであったので気になっていたのだ。

予約は済ませた。そして、映画館にたどり着いた。

 

――上映時間を間違えた。20:40からの上映にもかかわらず18:50着。我ながらどう勘違いしたのか分からない。そこでふとチケット売り場の上映情報を見た。「2D字幕・マッドマックス 19:05」。

そもそも今日はマッドマックスを見るために映画館に行くはずだったのだが、マッドマックスのレイトショーでの上演は22:00以降であったため、マッドマックスは次の機会に、取り敢えず本日のところは興味のあったジュラシック・ワールドを見ておこうと思ったのだ。

19:05は通常料金ではあるがまあ差分は大した出費ではない。チケットを購入した。

 

マッドマックスは全席ペアシートであった。

一人で悠々と、広い座席を専有してくつろぎつつ上映を待った。

 

 

本編開始2分から上映時間の7000秒間、口を閉じることすら忘れひたすらにv8エンジンに脳汁を絞られ続けた。

v8エンジンを崇めよ。

四則演算がしたかった

さて、文字列として与えられた数式を計算して、その結果を得たい。

まず思い浮かんだのは逆ポーランド記法である。

逆ポーランド記法ならば簡単に数式を解釈出来る。

数値が現れればスタックにプッシュ、演算子が現れれば数値をスタックからポップして計算結果をプッシュするだけだ。

以下のコードはD言語によって記述されている。また、コードを単純にするために入力された式の誤りは考えない。

import std.stdio;
import std.string;
import std.ascii:isDigit;
import std.conv:to;

T popBack(T)(ref T[] arr) {
	T back = arr[$-1];
	arr = arr[0..$-1];
	return back;
}

double npl(string[] tokens) {
	double[] stack;

	foreach(token; tokens) {
		if(token[0].isDigit) {
			//	数値はプッシュ
			stack ~= token.to!double;
		}
		else  {
			//	演算子ならポップ
			double b = stack.popBack();
			double a = stack.popBack();

			switch(token) {
			case "+": stack ~= a+b; break;
			case "-": stack ~= a-b; break;
			case "*": stack ~= a*b; break;
			case "/": stack ~= a/b; break;
			default : assert(0);
			}
		}
	}

	//	スタックの一番上が計算結果
	return stack[$-1];
}


double eval(string src) {
	return src.split(" ").npl();
}

void main() {
	readln().chomp.eval().writeln();
}
>dmd -run a.d
3 1 5 + 2 3 + * - 9 /
-3

逆ポーランド記法の数式

3 1 5 + 2 3 + * - 9 /

中置記法で表すと

(3-(1+5)*(2+3))/9 == -3

であるため、出力は正しい。

数式を文字列で受け取り、計算結果を返す関数eval()は、トークン列を受け取り計算結果を返す関数npl()にほとんどの処理を丸投げしている。

では、中置記法の数式を解析したい。調べてみるとおあつらえ向きのものが存在した。「操車場アルゴリズム」である。

これは、ようは中置記法から逆ポーランド記法の数式を生成するためのアルゴリズムと言える。

ひとまず括弧のことは考えずに数値と +-*/ の4つの演算子のみで構成された中置記法の数式を解析しようと思う。

import std.conv:to, parse;

double eval(string src) {
	string[] nplTokens;
	string[] opStack;

	while(src.length) {
		if(src[0].isDigit) {
			//	数値ならば読み進める
			nplTokens ~= src.parse!double().to!string;
		}
		else {
			//	演算子
			if(src[0] == '+' || src[0] == '-') {
				//	空になるまで取り出す
				while(opStack.length)
					nplTokens ~= opStack.popBack();
			}

			//	スタックにプッシュ
			opStack ~= src[0..1];
			src = src[1..$];
		}
	}

	//	残った演算子を全部取り出す
	foreach_reverse(op; opStack)
		nplTokens ~= op;

	//	変換結果を出力
	nplTokens.writeln();

	return nplTokens.npl();
}
>dmd -run b.d
3-1+5*2+3/9
["3", "1", "-", "5", "2", "*", "+", "3", "9", "/", "+"]
12.3333

mainとnplには手を加えていないため省略した。

いろいろと無駄は多いが、気にしないことにする。

次に、括弧の処理を加える。

コードの変更は少しだ。

double eval(string src) {
	string[] nplTokens;
	string[] opStack;

	while(src.length) {
		if(src[0].isDigit) {
			//	数値ならば読み進める
			nplTokens ~= src.parse!double().to!string;
		}
		else {
			//	演算子
			if(src[0] == '+' || src[0] == '-') {
				//	空になるか、左括弧まで取り出す
				while(opStack.length && opStack[$-1] != "(")
					nplTokens ~= opStack.popBack();
			}
			else if(src[0] == ')') {
				//	右括弧の時は左括弧まで取り出す
				while(opStack[$-1] != "(")
					nplTokens ~= opStack.popBack();

				//	左括弧は捨てる
				opStack.popBack();
			}

			//	右括弧でないならばスタックにプッシュ
			if(src[0] != ')')
				opStack ~= src[0..1];
		
			src = src[1..$];
		}
	}

	//	残った演算子を全部取り出す
	foreach_reverse(op; opStack)
		nplTokens ~= op;

	//	変換結果を出力
	nplTokens.writeln();

	return nplTokens.npl();
}
>dmd -run c.d
(3-(1+5)*(2+3))/9
["3", "1", "5", "+", "2", "3", "+", "*", "-", "9", "/"]
-3

効率もいいとは言えないし、現状柔軟性もなにもない。更にはエラーチェックもろくにしていないため妙なものを渡せば即落ちる危ういものではあるが、一応文字列として与えられた数式から計算結果を得られた。

今回はD言語でプログラムを記述したが、配列を柔軟に扱えるのはありがたい。

それから、個人的にD言語のUFCS(Uniform Function Call Syntax)は好きだ。

やり過ぎは良くないとはわかっているのだがついつい関数をぽんぽんと後ろに繋げていってしまう。