repl.it
@moytrage/

RuStackOverflow_733927

C++11

No description

fork
loading
Files
  • main.cpp
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <random>
#include <cstdint>
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>
#include <chrono>
#include <string>
using namespace std;

typedef uint32_t u32;
typedef uint32_t s32;
typedef uint64_t u64;

enum {
    c_nums_min = 1 << 10,
    c_nums_max = 1 << 20,
    c_nums_cnt = 1 << 16,
    c_table_size = 1 << 10,
    c_num_tests = 1 << 16,
};

class TimeMeasure {
public:
    TimeMeasure(string const & name) {
        name_ = name;
        start_time_ = std::chrono::high_resolution_clock::now();
        end_time_ = start_time_;
    }

    u64 TimeElapsedNS() {
        end_time_ = std::chrono::high_resolution_clock::now();
        u64 diff = chrono::duration_cast<chrono::nanoseconds>(end_time_ - start_time_).count();
        return diff;
    }

    ~TimeMeasure() {
        cout << "Time elapsed for [" << name_ << "] = " << dec << TimeElapsedNS() / 1000000 << " ms." << endl;
    }
private:
    string name_;
    chrono::time_point<chrono::high_resolution_clock> start_time_, end_time_;
};

int main() {
    // Initialize random number generator.
    std::default_random_engine generator;
    std::uniform_int_distribution<u32> distribution(c_nums_min, c_nums_max);
    auto rng = std::bind(distribution, generator);
    
    // Generate random numbers.
    vector<u32> nums(c_nums_cnt);
    for (u32 i = 0; i < nums.size(); ++i) {
        nums[i] = rng();
    }
    nums.push_back(c_nums_min);
    nums.push_back(c_nums_max + 1);

    // Sort numbers.
    sort(nums.begin(), nums.end());
    
    // Create lookup table.
    vector<u32> table(c_table_size + 1);
    u32 const c_bucket_size = (c_nums_max - c_nums_min + c_table_size) / c_table_size;
    for (u32 i = 0, i_nums = 0; i < table.size() - 1; ++i) {
        u32 const bucket_end = c_nums_min + (i + 1) * c_bucket_size;
        table[i] = i_nums;
        while (i_nums < nums.size() - 1 && nums[i_nums] < bucket_end) ++i_nums;
    }
    table.back() = nums.size() - 1;
    
    // Generate random nums for queries.
    vector<u32> query_nums(c_num_tests);
    for (u32 i = 0; i < query_nums.size(); ++i) {
        query_nums[i] = rng();
    }
    
    // Do lookups.
    {
        TimeMeasure time_measure("AllTests");
        
        for (u32 i = 0; i < query_nums.size(); ++i) {
            u32 n = query_nums[i];
            if (n < c_nums_min || n > c_nums_max) {
                cout << "Wrong n: " << n << endl;
                return -1;
            }
            u32 table_index = (n - c_nums_min) / c_bucket_size;
            u32 found_index = max(u32(1), table[table_index]) - 1;
            for (u32 j = table[table_index]; j < table[table_index + 1]; ++j) {
                if (n < nums[j + 1]) {
                    if (nums[j] <= n) {
                        found_index = j;
                    }
                    break;
                }
            }
            if (!(nums[found_index] <= n && n < nums[found_index + 1])) {
                cout << "Incorrect algorithm!" << endl
                     << n << " [" << nums[found_index] << ", " << nums[found_index + 1] << ")" << endl;
                return -1;
            }
        }
    }
    
    return 0;
}
Fetching token
?