diff options
| -rw-r--r-- | CMakeLists.txt | 3 | ||||
| -rw-r--r-- | expt_0726.cpp | 107 |
2 files changed, 110 insertions, 0 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index bec9954..858cea0 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -81,3 +81,6 @@ set_target_properties(work PROPERTIES CUDA_ARCHITECTURES "75") add_executable(expt_0722 expt_0722.cpp) set_target_properties(expt_0722 PROPERTIES LINKER_LANGUAGE CXX) +add_executable(expt_0726 expt_0726.cpp) +set_target_properties(expt_0726 PROPERTIES LINKER_LANGUAGE CXX) + diff --git a/expt_0726.cpp b/expt_0726.cpp new file mode 100644 index 0000000..5b37df3 --- /dev/null +++ b/expt_0726.cpp @@ -0,0 +1,107 @@ +#include <algorithm> +#include <cassert> +#include <chrono> +#include <cmath> +#include <cstdio> +#include <iostream> +#include <vector> + +constexpr size_t length = 1048576; +std::vector<unsigned long long> population_vector, sample_vector, + original_vector; +// std::vector<std::vector<unsigned long long>> result_storage; +std::vector<bool> 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; +} + +unsigned long long max_value = 0, min_value = 0xfffffffff; + +inline void store_into_vector(unsigned long long value) { + if (max_value < value) { + max_value = value; + } + if (min_value > value) { + min_value = value; + } + population_vector.push_back(value); +} + +constexpr long sample_length = 1024; +constexpr long test_size = 2048; + +void mian(long scale_size) { + const long split_size = test_size * scale_size; + result_storage.clear(); + result_storage.resize(split_size, false); + + const auto slice_size = 1.0 / (long double)(split_size); + + for (long i = 0; i < test_size; i++) { + auto index = (int)safe_ceil(sample_cdf(original_vector[i + sample_length]) / + slice_size) - + 1; + // printf("%Lf\n", index); + if (result_storage[index]) { + while (result_storage[++index]) { + assert(index < split_size); + } + } + result_storage[index] = true; + } +} + +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; store_into_vector(i)) + ; + fclose(file); + + assert(population_vector.size() == length); + + original_vector = population_vector; + + sample_vector = std::vector<unsigned long long>( + original_vector.begin(), original_vector.begin() + sample_length); + sample_vector.push_back(min_value); + sample_vector.push_back(max_value); + + std::sort(sample_vector.begin(), sample_vector.end()); + + for (int i = 2; i <= 16; i++) { + + auto start = std::chrono::high_resolution_clock::now(); + mian(i); + auto end = std::chrono::high_resolution_clock::now(); + + auto element_size_max = 0; + for (auto element : result_storage) { + if (element_size_max < element) { + element_size_max = element; + } + } + assert(element_size_max == 1); + printf("scale: %d, time spend: %ldms\n", i, + duration_cast<std::chrono::microseconds>((end - start)).count()); + } +}
\ No newline at end of file |