Hatena::ブログ(Diary)

oupoの日記

2017-01-08

計算結果をキャッシュする&コピーコストのかからないMT

14:28

背景

乱数調整のツールを作っていると次のようなコードを書きたくなります。

しかし、このコードはshow_ivs()を呼び出すたびにMTがコピーされるので遅いです。

struct MT {
	uint32_t table[624];
	int index;
};

void init_genrand(MT *mt, uint32_t seed);
uint32_t genrand_int32(MT *mt);

void show_ivs(MT mt) {
	for (int i = 0; i < 6; i ++) {
		printf("%02d ", (int)((uint64_t)(genrand_int32(&mt) * 32) >> 32));
	}
	printf("\n");
}

void list(uint32_t seed) {
	MT mt;
	init_genrand(&mt, seed);
	for (int i = 0; i < 100; i ++) {
		show_ivs(mt);
		genrand_int32(&mt);
	}
}

本題

そこでコピーのコストがかからず、また一度計算した値はキャッシュするMTを作ってみました。

しかし、連結リストを使っているので遅い気がします。

配列乱数値を貯めておき、それを使うという方法の方がずっといいかもしれません。

#include <memory>
#include <cstdint>
#include <cstdio>

#define N 624
#define M 397

namespace MT {

// デバッグ用
int objects_count = 0;
int calc_count = 0;

const uint32_t MATRIX_A = 0x9908b0dfUL;
const uint32_t UPPER_MASK = 0x80000000UL;
const uint32_t LOWER_MASK = 0x7fffffffUL;

class State;

class Node {
	friend State;
private:
	uint32_t m_val;
	std::shared_ptr<Node> m_next;
	std::shared_ptr<Node> m_prev_624;
	std::shared_ptr<Node> m_prev_623;
	std::shared_ptr<Node> m_prev_227;
public:
	Node(uint32_t val) : m_val(val) {
		objects_count++;
	}
	Node(std::shared_ptr<Node> prev_624, std::shared_ptr<Node> prev_623, std::shared_ptr<Node> prev_227)
		: m_prev_624(prev_624), m_prev_623(prev_623), m_prev_227(prev_227) {
		calc_value();
		objects_count++;
	}

	Node(Node &other) : m_val(other.m_val), m_next(other.m_next),
		m_prev_624(other.m_prev_624), m_prev_623(other.m_prev_623), m_prev_227(other.m_prev_227) {
		
		objects_count++;
	}

	~Node() {
		objects_count--;
	}

	std::shared_ptr<Node> next() {
		if (m_next != nullptr) {
			return m_next;
		} else {
			m_next = std::make_shared<Node>(Node(m_prev_624->next(), m_prev_623->next(), m_prev_227->next()));
			m_prev_624 = m_prev_623 = m_prev_227 = nullptr;
			return m_next;
		}
	}

private:
	void calc_value()
	{
		uint32_t y = (m_prev_624->m_val & UPPER_MASK) | (m_prev_623->m_val & LOWER_MASK);
		m_val = m_prev_227->m_val ^ (y >> 1) ^ ((y & 1) != 0 ? MATRIX_A : 0);
		calc_count++;
	}
};

class State {
	std::shared_ptr<Node> m_node;
public:
	State(uint32_t seed) {
		uint32_t vals[N];
		std::shared_ptr<Node> nodes[N];
		vals[0] = seed;
		for (int i = 1; i < N; i++)
		{
			vals[i] = 1812433253 * (vals[i - 1] ^ (vals[i - 1] >> 30)) + i;
		}
		for (int i = 0; i < N; i++)
		{
			nodes[i] = std::make_shared<Node>(Node(vals[i]));
		}
		for (int i = 1; i < N; i++)
		{
			nodes[i - 1]->m_next = nodes[i];
		}
		m_node = std::make_shared<Node>(Node(nodes[0], nodes[1], nodes[M]));
		nodes[N-1]->m_next = m_node;
	}


	uint32_t rand()
	{
		uint32_t value = m_node->m_val;
		m_node = m_node->next();
		return temper(value);
	}
private:
	uint32_t temper(uint32_t y)
	{
		y ^= (y >> 11);
		y ^= (y << 7) & 0x9d2c5680;
		y ^= (y << 15) & 0xefc60000;
		y ^= (y >> 18);
		return y;
	}

};
}

void show_ivs(MT::State mt) {
	for (int i = 0; i < 6; i++) {
		printf("%02d ", (int)(((uint64_t)mt.rand() * 32) >> 32));
	}
	printf("\n");
}

int main() {
	MT::State mt(0);
	for (int i = 0; i < 10000; i++) {
		show_ivs(mt);
		mt.rand();
	}
	printf("objects_count=%d\n", MT::objects_count);
	printf("calc_count=%d\n", MT::calc_count);
	return 0;
}

calc_count(次の乱数値を計算する回数)は10006回となって最小限におさえられています。

またobjects_count(現在メモリに存在するノードの数)は625となって不要なノードは消されていることが分かります。


問題点

MT::State mt(0);

の行の次に

MT::State mt2 = mt;

を追加するとmain()関数終了時にSEGVしてしまいます。

これはNodeのデストラクタが再帰的に呼ばれ、再帰の回数が大きくなりすぎてスタックオーバーフローするためです。

トラックバック - http://d.hatena.ne.jp/oupo/20170108/1483853303
Connection: close