From 3c745606e9494917763313e821e3722d010e2e97 Mon Sep 17 00:00:00 2001 From: KunoiSayami Date: Fri, 22 Jul 2022 16:40:36 +0800 Subject: refactor: Rename files Signed-off-by: KunoiSayami --- CMakeLists.txt | 10 ++-- ex_0702.py | 23 ------- ex_normal_distribution.py | 35 ----------- exp_0702.cpp | 102 ------------------------------- exp_3.cpp | 142 -------------------------------------------- expt_0702.cpp | 102 +++++++++++++++++++++++++++++++ expt_0702.py | 23 +++++++ expt_0722.cpp | 3 + expt_3.cpp | 142 ++++++++++++++++++++++++++++++++++++++++++++ expt_normal_distribution.py | 35 +++++++++++ 10 files changed, 311 insertions(+), 306 deletions(-) delete mode 100755 ex_0702.py delete mode 100755 ex_normal_distribution.py delete mode 100644 exp_0702.cpp delete mode 100644 exp_3.cpp create mode 100644 expt_0702.cpp create mode 100755 expt_0702.py create mode 100644 expt_0722.cpp create mode 100644 expt_3.cpp create mode 100755 expt_normal_distribution.py diff --git a/CMakeLists.txt b/CMakeLists.txt index e340d9d..bec9954 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -65,11 +65,11 @@ build_different_target(true 1048576 8) add_executable(normal_distribution normal_distribution.cpp) set_target_properties(normal_distribution PROPERTIES LINKER_LANGUAGE CXX) -add_executable(normal_distribution_ex3 exp_3.cpp) -set_target_properties(normal_distribution PROPERTIES LINKER_LANGUAGE CXX) +add_executable(normal_distribution_expt3 expt_3.cpp) +set_target_properties(normal_distribution_expt3 PROPERTIES LINKER_LANGUAGE CXX) -add_executable(normal_distribution_ex0702 exp_0702.cpp) -set_target_properties(normal_distribution PROPERTIES LINKER_LANGUAGE CXX) +add_executable(normal_distribution_expt0702 expt_0702.cpp) +set_target_properties(normal_distribution_expt0702 PROPERTIES LINKER_LANGUAGE CXX) add_executable(work work.cu) target_link_libraries(work m stdc++) @@ -78,4 +78,6 @@ set_target_properties(work PROPERTIES CUDA_SEPARABLE_COMPILATION ON) set_target_properties(work PROPERTIES CUDA_ARCHITECTURES "75") +add_executable(expt_0722 expt_0722.cpp) +set_target_properties(expt_0722 PROPERTIES LINKER_LANGUAGE CXX) diff --git a/ex_0702.py b/ex_0702.py deleted file mode 100755 index 5ac42b0..0000000 --- a/ex_0702.py +++ /dev/null @@ -1,23 +0,0 @@ -#!/usr/bin/env python3 -import argparse -import os -import subprocess - -import matplotlib.pyplot as plt - - -def function_pdf(proc: str): - p = subprocess.Popen([proc], stdin=subprocess.PIPE, stdout=subprocess.PIPE) - output, _ = p.communicate(b"1024 1024\n32768 1024\n32768 32768\n") - p.stdin.close() - for index in range(0, len(lines := output.splitlines()), 2): - plt.hist(list(map(int, lines[index].split())), bins=100) - plt.title(f"stddev: {lines[index + 1].decode()}") - plt.show() - - -if __name__ == '__main__': - parser = argparse.ArgumentParser() - parser.add_argument('proc') - matches = parser.parse_args() - function_pdf(matches.proc) diff --git a/ex_normal_distribution.py b/ex_normal_distribution.py deleted file mode 100755 index 272b9b6..0000000 --- a/ex_normal_distribution.py +++ /dev/null @@ -1,35 +0,0 @@ -#!/usr/bin/env python3 -import numpy as np -import matplotlib.pyplot as plt -from matplotlib.ticker import PercentFormatter - - -def function_pdf(element: list[int]): - plt.hist(element, bins=500, histtype='step') - plt.show() - - -def function_cdf(element: list[int]): - plt.hist(element, bins=500, cumulative=True, histtype='step') - plt.show() - - -def function_1000_cdf(element: list[int]): - plt.hist(element, bins=250, histtype='step', label='x', cumulative=True, - weights=np.ones(len(element)) / len(element)) - plt.hist(element[:1000], bins=100, histtype='step', label='y', cumulative=True, weights=np.ones(1000) / 1000) - plt.gca().yaxis.set_major_formatter(PercentFormatter(1)) - plt.show() - - -def normal_distribution() -> list[int]: - with open('normal_distribution.txt') as fin: - context = fin.read() - return list(map(int, context.splitlines())) - - -if __name__ == '__main__': - elements = normal_distribution() - function_pdf(elements) - function_cdf(elements) - function_1000_cdf(elements) diff --git a/exp_0702.cpp b/exp_0702.cpp deleted file mode 100644 index f7023f7..0000000 --- a/exp_0702.cpp +++ /dev/null @@ -1,102 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include - -constexpr size_t length = 1048576; -std::vector population_vector, sample_vector, - original_vector; -std::vector> result_storage; - -long double sample_cdf(long double x) { - auto it = lower_bound(sample_vector.begin(), sample_vector.end(), x); - if (it == sample_vector.end()) { - return 1; - } - if (it == sample_vector.begin()) { - return 0; - } - auto it_prev = it - 1; - return ((long double)(it_prev - sample_vector.begin()) + - (long double)(x - *it_prev) / (*it - *it_prev)) / - (long double)(sample_vector.size() - 1); -} - -inline long double safe_ceil(long double value) { - auto c = std::ceil(value); - return c == 0 ? 1 : c; -} - -long double calc_stddev(const long sample_length) { - std::vector elements; - std::vector tmp_vector; - for (auto &element : result_storage) { - elements.push_back(element.size()); - } - tmp_vector.resize(elements.size()); - // auto sum = std::accumulate(elements.begin(), - // elements.end(),decltype(elements)::value_type(0)); size_t sum = length; - // printf("\nsum: %ld\n", sum); - auto mu = length / (long double)elements.size(); - // long double mu = sample_length; - // printf("mu: %Lf\n", mu); - - std::transform(elements.begin(), elements.end(), tmp_vector.begin(), - [&mu](size_t element) { return std::pow(element - mu, 2); }); - - return std::sqrt(std::accumulate(tmp_vector.begin(), tmp_vector.end(), - decltype(tmp_vector)::value_type(0)) / - elements.size()); -} - -void mian(const long sample_length, const long split_size) { - sample_vector = std::vector( - original_vector.begin(), original_vector.begin() + sample_length); - result_storage.resize(sample_length, std::vector()); - - sample_vector.push_back(population_vector[0]); - sample_vector.push_back(*(population_vector.cend() - 1)); - std::sort(sample_vector.begin(), sample_vector.end()); - const auto slice_size = 1.0 / (long double)split_size; - - for (auto &element : original_vector) { - result_storage[(int)safe_ceil(sample_cdf(element) / slice_size) - 1] - .push_back(element); - /*auto tmp = sample_cdf(element) / slice_size; - if (tmp < 1) { - printf("%lld %Lf ", element, tmp); - }*/ - } - for (const auto &element : result_storage) { - printf("%ld ", element.size()); - - } - printf("\n%Lf\n", calc_stddev(sample_length)); - result_storage.clear(); -} - -int main(int argc, char const *argv[]) { - assert((length & 1) == 0); - assert(length > 1024); - - FILE *file = fopen("normal_distribution.txt", "r"); - assert(file); - for (long long i; fscanf(file, "%lld ", &i) != EOF; - population_vector.push_back(i)) - ; - fclose(file); - - assert(population_vector.size() == length); - - original_vector = population_vector; - - std::sort(population_vector.begin(), population_vector.end()); - auto sample_length = 0, split_size = 0; - while (std::cin >> sample_length >> split_size) { - mian(sample_length, split_size); - } -} \ No newline at end of file diff --git a/exp_3.cpp b/exp_3.cpp deleted file mode 100644 index f8ed1e7..0000000 --- a/exp_3.cpp +++ /dev/null @@ -1,142 +0,0 @@ -#include -#include -#include -#include -#include -#include - -constexpr size_t length = 1048576; -constexpr size_t sample_length = 1000; - -#define CALC_HEIGHT -//#define CALC_CDF_DIFF -//#define INSERT_LIMIT_VALUE - -#ifdef CALC_HEIGHT -constexpr int block_size = 2; -unsigned trailing_zeroes(size_t index) { - unsigned bits = 0; - unsigned x = index; - - if (x) { - while (x % block_size == 0) { - ++bits; - x /= block_size; - } - } - return bits; -} - -unsigned int getHeight(long loc) { - // if (loc % block_size == 0) { - auto level = trailing_zeroes(loc) + 1; - return level; - //} - - // return 1; -} -#else -unsigned int getHeight(long loc) { return loc; } -#endif - -std::vector population_vector, sample_vector; - -void initialize(const std::vector &input_population, - const std::vector &input_sample) { - population_vector = input_population; - std::sort(population_vector.begin(), population_vector.end()); - sample_vector = input_sample; - std::sort(sample_vector.begin(), sample_vector.end()); -#ifdef INSERT_LIMIT_VALUE - sample_vector.insert(sample_vector.cbegin(), *population_vector.begin()); - sample_vector.push_back(*(population_vector.end() - 1)); -#endif -} - -long double sample_cdf(long double x) { - auto it = lower_bound(sample_vector.begin(), sample_vector.end(), x); - if (it == sample_vector.end()) { - return 1; - } - if (it == sample_vector.begin()) { - return 0; - } - auto it_prev = it - 1; - return ((long double)(it_prev - sample_vector.begin()) + - (long double)(x - *it_prev) / (*it - *it_prev)) / - (long double)(sample_vector.size() - 1); -} - -int infer_offset(long double x) { - return (int)std::round(sample_cdf(x) * double(population_vector.size())); -} -#ifdef CALC_CDF_DIFF -int infer_offset_from_cdf(long double cdf) { - return int(cdf * double(population_vector.size())); -} - -// const double M_SQRT1_2 = sqrt(0.5); -constexpr long long s_avg = 2147483648; -constexpr long long s_stddev = 2147483648; - -long double goal_cdf(long double x) { return std::erfc(-x * M_SQRT1_2) * 0.5; } -long double stat_cdf(long double x) { return goal_cdf((x - s_avg) / s_stddev); } - -long double finite_population_cdf(long double x) { - auto it = upper_bound(population_vector.begin(), population_vector.end(), x); - return (long double)(it - population_vector.begin()) / - population_vector.size(); -} -#endif - -int main() { - - std::vector original_vector; - - std::set set2; - - FILE *file = fopen("normal_distribution.txt", "r"); - assert(file); - for (long long i; fscanf(file, "%lld ", &i) != EOF; - original_vector.push_back(i)) - ; - fclose(file); - - assert(original_vector.size() >= length); - - auto it = original_vector.begin(); - for (int i = 1; i <= sample_length; i++) { - auto element = *it; - auto ret = set2.insert(element); - if (ret.second) { - sample_vector.push_back(element); - // printf("%lld\n", element); - } - it++; - } - - assert(sample_vector.size() == sample_length); - - initialize(original_vector, sample_vector); - - for (auto iter = population_vector.begin(); iter != population_vector.end(); - iter++) { -#ifdef CALC_CDF_DIFF - auto cdf = sample_cdf(*iter); - printf("%d,%d,%.6Lf ", getHeight(infer_offset_from_cdf(cdf)), - getHeight(iter - population_vector.begin()), - std::abs(cdf - stat_cdf(*iter))); -#else - auto index = infer_offset(*iter); - printf("%d,%d,%d,%ld\n", getHeight(index), index, - getHeight(iter - population_vector.begin() + 1), - iter - population_vector.begin() + 1); -#endif - // fflush(stdout); - } - // puts(""); - // printf("%lld, %lld\n", sample_vector[1], *(sample_vector.end() - 2)); - // printf("%lld, %lld\n", population_vector[0], *(population_vector.end() - - // 1)); - return 0; -} \ No newline at end of file diff --git a/expt_0702.cpp b/expt_0702.cpp new file mode 100644 index 0000000..f7023f7 --- /dev/null +++ b/expt_0702.cpp @@ -0,0 +1,102 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +constexpr size_t length = 1048576; +std::vector population_vector, sample_vector, + original_vector; +std::vector> result_storage; + +long double sample_cdf(long double x) { + auto it = lower_bound(sample_vector.begin(), sample_vector.end(), x); + if (it == sample_vector.end()) { + return 1; + } + if (it == sample_vector.begin()) { + return 0; + } + auto it_prev = it - 1; + return ((long double)(it_prev - sample_vector.begin()) + + (long double)(x - *it_prev) / (*it - *it_prev)) / + (long double)(sample_vector.size() - 1); +} + +inline long double safe_ceil(long double value) { + auto c = std::ceil(value); + return c == 0 ? 1 : c; +} + +long double calc_stddev(const long sample_length) { + std::vector elements; + std::vector tmp_vector; + for (auto &element : result_storage) { + elements.push_back(element.size()); + } + tmp_vector.resize(elements.size()); + // auto sum = std::accumulate(elements.begin(), + // elements.end(),decltype(elements)::value_type(0)); size_t sum = length; + // printf("\nsum: %ld\n", sum); + auto mu = length / (long double)elements.size(); + // long double mu = sample_length; + // printf("mu: %Lf\n", mu); + + std::transform(elements.begin(), elements.end(), tmp_vector.begin(), + [&mu](size_t element) { return std::pow(element - mu, 2); }); + + return std::sqrt(std::accumulate(tmp_vector.begin(), tmp_vector.end(), + decltype(tmp_vector)::value_type(0)) / + elements.size()); +} + +void mian(const long sample_length, const long split_size) { + sample_vector = std::vector( + original_vector.begin(), original_vector.begin() + sample_length); + result_storage.resize(sample_length, std::vector()); + + sample_vector.push_back(population_vector[0]); + sample_vector.push_back(*(population_vector.cend() - 1)); + std::sort(sample_vector.begin(), sample_vector.end()); + const auto slice_size = 1.0 / (long double)split_size; + + for (auto &element : original_vector) { + result_storage[(int)safe_ceil(sample_cdf(element) / slice_size) - 1] + .push_back(element); + /*auto tmp = sample_cdf(element) / slice_size; + if (tmp < 1) { + printf("%lld %Lf ", element, tmp); + }*/ + } + for (const auto &element : result_storage) { + printf("%ld ", element.size()); + + } + printf("\n%Lf\n", calc_stddev(sample_length)); + result_storage.clear(); +} + +int main(int argc, char const *argv[]) { + assert((length & 1) == 0); + assert(length > 1024); + + FILE *file = fopen("normal_distribution.txt", "r"); + assert(file); + for (long long i; fscanf(file, "%lld ", &i) != EOF; + population_vector.push_back(i)) + ; + fclose(file); + + assert(population_vector.size() == length); + + original_vector = population_vector; + + std::sort(population_vector.begin(), population_vector.end()); + auto sample_length = 0, split_size = 0; + while (std::cin >> sample_length >> split_size) { + mian(sample_length, split_size); + } +} \ No newline at end of file diff --git a/expt_0702.py b/expt_0702.py new file mode 100755 index 0000000..5ac42b0 --- /dev/null +++ b/expt_0702.py @@ -0,0 +1,23 @@ +#!/usr/bin/env python3 +import argparse +import os +import subprocess + +import matplotlib.pyplot as plt + + +def function_pdf(proc: str): + p = subprocess.Popen([proc], stdin=subprocess.PIPE, stdout=subprocess.PIPE) + output, _ = p.communicate(b"1024 1024\n32768 1024\n32768 32768\n") + p.stdin.close() + for index in range(0, len(lines := output.splitlines()), 2): + plt.hist(list(map(int, lines[index].split())), bins=100) + plt.title(f"stddev: {lines[index + 1].decode()}") + plt.show() + + +if __name__ == '__main__': + parser = argparse.ArgumentParser() + parser.add_argument('proc') + matches = parser.parse_args() + function_pdf(matches.proc) diff --git a/expt_0722.cpp b/expt_0722.cpp new file mode 100644 index 0000000..041977a --- /dev/null +++ b/expt_0722.cpp @@ -0,0 +1,3 @@ +// +// Created by user on 22/07/22. +// diff --git a/expt_3.cpp b/expt_3.cpp new file mode 100644 index 0000000..f8ed1e7 --- /dev/null +++ b/expt_3.cpp @@ -0,0 +1,142 @@ +#include +#include +#include +#include +#include +#include + +constexpr size_t length = 1048576; +constexpr size_t sample_length = 1000; + +#define CALC_HEIGHT +//#define CALC_CDF_DIFF +//#define INSERT_LIMIT_VALUE + +#ifdef CALC_HEIGHT +constexpr int block_size = 2; +unsigned trailing_zeroes(size_t index) { + unsigned bits = 0; + unsigned x = index; + + if (x) { + while (x % block_size == 0) { + ++bits; + x /= block_size; + } + } + return bits; +} + +unsigned int getHeight(long loc) { + // if (loc % block_size == 0) { + auto level = trailing_zeroes(loc) + 1; + return level; + //} + + // return 1; +} +#else +unsigned int getHeight(long loc) { return loc; } +#endif + +std::vector population_vector, sample_vector; + +void initialize(const std::vector &input_population, + const std::vector &input_sample) { + population_vector = input_population; + std::sort(population_vector.begin(), population_vector.end()); + sample_vector = input_sample; + std::sort(sample_vector.begin(), sample_vector.end()); +#ifdef INSERT_LIMIT_VALUE + sample_vector.insert(sample_vector.cbegin(), *population_vector.begin()); + sample_vector.push_back(*(population_vector.end() - 1)); +#endif +} + +long double sample_cdf(long double x) { + auto it = lower_bound(sample_vector.begin(), sample_vector.end(), x); + if (it == sample_vector.end()) { + return 1; + } + if (it == sample_vector.begin()) { + return 0; + } + auto it_prev = it - 1; + return ((long double)(it_prev - sample_vector.begin()) + + (long double)(x - *it_prev) / (*it - *it_prev)) / + (long double)(sample_vector.size() - 1); +} + +int infer_offset(long double x) { + return (int)std::round(sample_cdf(x) * double(population_vector.size())); +} +#ifdef CALC_CDF_DIFF +int infer_offset_from_cdf(long double cdf) { + return int(cdf * double(population_vector.size())); +} + +// const double M_SQRT1_2 = sqrt(0.5); +constexpr long long s_avg = 2147483648; +constexpr long long s_stddev = 2147483648; + +long double goal_cdf(long double x) { return std::erfc(-x * M_SQRT1_2) * 0.5; } +long double stat_cdf(long double x) { return goal_cdf((x - s_avg) / s_stddev); } + +long double finite_population_cdf(long double x) { + auto it = upper_bound(population_vector.begin(), population_vector.end(), x); + return (long double)(it - population_vector.begin()) / + population_vector.size(); +} +#endif + +int main() { + + std::vector original_vector; + + std::set set2; + + FILE *file = fopen("normal_distribution.txt", "r"); + assert(file); + for (long long i; fscanf(file, "%lld ", &i) != EOF; + original_vector.push_back(i)) + ; + fclose(file); + + assert(original_vector.size() >= length); + + auto it = original_vector.begin(); + for (int i = 1; i <= sample_length; i++) { + auto element = *it; + auto ret = set2.insert(element); + if (ret.second) { + sample_vector.push_back(element); + // printf("%lld\n", element); + } + it++; + } + + assert(sample_vector.size() == sample_length); + + initialize(original_vector, sample_vector); + + for (auto iter = population_vector.begin(); iter != population_vector.end(); + iter++) { +#ifdef CALC_CDF_DIFF + auto cdf = sample_cdf(*iter); + printf("%d,%d,%.6Lf ", getHeight(infer_offset_from_cdf(cdf)), + getHeight(iter - population_vector.begin()), + std::abs(cdf - stat_cdf(*iter))); +#else + auto index = infer_offset(*iter); + printf("%d,%d,%d,%ld\n", getHeight(index), index, + getHeight(iter - population_vector.begin() + 1), + iter - population_vector.begin() + 1); +#endif + // fflush(stdout); + } + // puts(""); + // printf("%lld, %lld\n", sample_vector[1], *(sample_vector.end() - 2)); + // printf("%lld, %lld\n", population_vector[0], *(population_vector.end() - + // 1)); + return 0; +} \ No newline at end of file diff --git a/expt_normal_distribution.py b/expt_normal_distribution.py new file mode 100755 index 0000000..272b9b6 --- /dev/null +++ b/expt_normal_distribution.py @@ -0,0 +1,35 @@ +#!/usr/bin/env python3 +import numpy as np +import matplotlib.pyplot as plt +from matplotlib.ticker import PercentFormatter + + +def function_pdf(element: list[int]): + plt.hist(element, bins=500, histtype='step') + plt.show() + + +def function_cdf(element: list[int]): + plt.hist(element, bins=500, cumulative=True, histtype='step') + plt.show() + + +def function_1000_cdf(element: list[int]): + plt.hist(element, bins=250, histtype='step', label='x', cumulative=True, + weights=np.ones(len(element)) / len(element)) + plt.hist(element[:1000], bins=100, histtype='step', label='y', cumulative=True, weights=np.ones(1000) / 1000) + plt.gca().yaxis.set_major_formatter(PercentFormatter(1)) + plt.show() + + +def normal_distribution() -> list[int]: + with open('normal_distribution.txt') as fin: + context = fin.read() + return list(map(int, context.splitlines())) + + +if __name__ == '__main__': + elements = normal_distribution() + function_pdf(elements) + function_cdf(elements) + function_1000_cdf(elements) -- cgit v1.3.1