pointer.csv

PrimeHash.cpp

#include <array>
#include <cassert>
#include <fstream>
#include <iostream>
#include <numeric>
#include <random>
#include <ppl.h>

struct integer_info {
	int value;
	std::vector<int> prime_factors;

	bool is_prime() const { return prime_factors.size() == 1; }
};

// 素因数分解
std::vector<int> factorize(int value) {
	assert(value > 1);

	std::vector<int> result;

	while (value > 1) {
		if (value % 2 == 0) {
			value /= 2;
			result.push_back(2);
		}
		else {
			int i = 3;
			while (value % i != 0) i += 2;
			value /= i;
			result.push_back(i);
		}
	}

	return result;
}

// 一様分布でテスト
float test_uniform_distribution(int divisor) {
	std::vector<int> buckets(divisor);

	// 一様分布で乱数（0 ～ 1,000,000）を生成
	std::random_device seed_gen;
	std::mt19937 rng(seed_gen());
	std::uniform_int_distribution<> dis(0, 1000000);

	const auto TEST_COUNT = 100; // テスト回数
	int result = 0;

	for (int i = 0; i < TEST_COUNT; i++) {
		std::fill(buckets.begin(), buckets.end(), 0);

		// divisor 個のランダムな値に対して、各バケットの到達回数を記録していく
		for (int j = 0; j < divisor; j++) {
			int key = dis(rng);
			int hash = key % divisor;
			buckets[hash]++;
		}

		// すべてのバケットが 1 であることが理想なので
		// 1 からの差を足し合わせて評価する
		for (int count : buckets) {
			result += std::abs(count - 1);
		}
	}

	return result / (float)divisor / (float)TEST_COUNT;
}

// malloc した結果のポインタでテスト
float test_pointer(int divisor) {
	const auto TEST_COUNT = 100; // テスト回数
	const auto ALLOC_SIZE = 24; // malloc の引数

	std::vector<int> buckets(divisor);
	std::vector<void*> ptrs;
	ptrs.reserve(divisor * TEST_COUNT);

	int result = 0;

	for (int i = 0; i < TEST_COUNT; i++) {
		std::fill(buckets.begin(), buckets.end(), 0);

		// divisor 個のランダムな値に対して、各バケットの到達回数を記録していく
		for (int j = 0; j < divisor; j++) {
			void* key = malloc(ALLOC_SIZE);
			ptrs.push_back(key);
			int hash = (int)((uintptr_t)key % divisor);
			buckets[hash]++;
		}

		// すべてのバケットが 1 であることが理想なので
		// 1 からの差を足し合わせて評価する
		for (int count : buckets) {
			result += std::abs(count - 1);
		}
	}

	for (void* p : ptrs) free(p);

	return result / (float)divisor / (float)TEST_COUNT;
}

int main() {
	// 2000～2999 までの数を用意
	const auto NUM_FROM = 2000;
	const auto NUM_COUNT = 1000;
	std::array<integer_info, NUM_COUNT> nums;
	for (int i = 0; i < NUM_COUNT; i++) {
		int v = NUM_FROM + i;
		nums[i] = { v, factorize(v) };
	}

	auto run_test = [&](std::function<float(int)> test_func, const char* output_file) {
		float* results = new float[NUM_COUNT];

		concurrency::parallel_for(0, NUM_COUNT, [&](int i) {
			results[i] = test_func(nums[i].value);
		});

		std::ofstream os(output_file);
		os << "Number,Number of Prime Factors,Score" << std::endl;

		for (int i = 0; i < NUM_COUNT; i++) {
			os << nums[i].value << ","
				<< nums[i].prime_factors.size() << ","
				<< results[i] << std::endl;
		}

		delete[] results;
	};

	concurrency::parallel_invoke(
		[&]() { run_test(test_uniform_distribution, "uniform_distribution.csv"); },
		[&]() { run_test(test_pointer, "pointer.csv"); }
	);

	return 0;
}

uniform_distribution.csv