#include <cstdint>
#include <cmath>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <deque>
using namespace std;
template <typename T>
class RandomDeque : public deque<T>
{
public:
RandomDeque() : deque<T>() {}
RandomDeque(const vector<T> &list) : deque<T>()
{
for (const auto &item : list)
{
this->push_random(item);
}
}
void push_random(const T &value)
{
static auto gen = default_random_engine{random_device{}()};
uniform_int_distribution<size_t> dist(0, 1);
size_t index = dist(gen);
if (index == 0)
{
this->push_front(value);
}
else
{
this->push_back(value);
}
}
void pop_n_elements(vector<T> &out, const uint32_t n)
{
if (n > this->size())
{
throw runtime_error("Not enough elements to pop");
}
for (uint32_t i = 0; i < n; i++)
{
out.push_back(this->front());
this->pop_front();
}
}
};
inline constexpr auto select_n_elements_a_1 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
static auto gen = default_random_engine{random_device{}()};
vector<uint32_t> indexes(in.size());
iota(begin(indexes), end(indexes), 0);
shuffle(indexes.begin(), indexes.end(), gen);
sort(indexes.begin(), indexes.begin() + n);
for (auto it = indexes.begin(); it != indexes.begin() + n; it++)
{
out.push_back(in[*it]);
}
};
inline constexpr auto select_n_elements_a_2 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
if (in.size() == 0 || n == 0 || n > in.size())
{
return;
}
static auto gen = default_random_engine{random_device{}()};
uint32_t indexes[in.size()];
for (uint32_t i = 0; i < in.size(); i++)
{
indexes[i] = i;
}
const uint32_t limit = in.size() - 1;
for (uint32_t i = 0; i < in.size(); i++)
{
uint32_t j = uniform_int_distribution<uint32_t>{0, limit}(gen);
swap(indexes[i], indexes[j]);
}
sort(indexes, indexes + n);
for (uint32_t i = 0; i < n; i++)
{
out.push_back(in[indexes[i]]);
}
};
inline constexpr auto select_n_elements_a_3 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
if (in.size() == 0 || n == 0 || n > in.size())
{
return;
}
RandomDeque<E> rdeque(in);
rdeque.pop_n_elements(out, n);
};
inline constexpr auto select_n_elements_b = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
static auto gen = default_random_engine{random_device{}()};
sample(in.begin(), in.end(), back_inserter(out), n, gen);
};
// test until the first match, unused
template <typename T>
void test1(T select_n_elements, const uint32_t n, const uint32_t type)
{
vector<uint32_t> in(n);
iota(begin(in), end(in), 0);
for (size_t i = 0; i < in.size();)
{
vector<uint32_t> out = {};
select_n_elements(in, out, type == 0 ? 1 : n - 1);
if (type == 0 && out[0] == i || type == 1 && find(out.begin(), out.end(), i) == out.end())
{
i++;
}
}
}
template <typename T>
chrono::duration<double> time1(T select_n_elements, const uint32_t n1, const uint32_t n2)
{
vector<int> in(n1);
iota(begin(in), end(in), 0);
vector<int> out = {};
auto start = chrono::system_clock::now();
select_n_elements(in, out, n2);
auto end = chrono::system_clock::now();
return end - start;
}
int main()
{
{
// Example usage
vector<string> in = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"};
vector<string> out = {};
select_n_elements_a_3(in, out, 4);
for (const auto &item : out)
{
cout << item << " ";
}
cout << endl;
}
const uint32_t n1 = 100000; // 100 thousand
uint32_t n2 = 0;
uint32_t delta = n1 / 2;
double dist = 100;
cout << setprecision(4);
for (size_t i = 1; i <= 55; i++)
{
auto t1 = time1(select_n_elements_a_3, n1, n2);
auto t2 = time1(select_n_elements_b, n1, n2);
auto d = (t1 - t2) / t1 * 100.0;
cout << "i=" << i << "\tn2=" << n2 << "\told_dist=" << dist << "\tnew_dist=" << d << "\tdelta=" << delta << endl;
if (d < dist)
{
n2 += delta;
}
else if (d > dist)
{
n2 -= delta;
}
delta -= delta / 5;
dist = d;
}
cout << "Final n2: " << n2 << endl;
const uint32_t n11 = n1 * 10; // 1 million
const uint32_t n21 = n2 * 10;
auto t1 = time1(select_n_elements_a_3, n11, n21);
auto t2 = time1(select_n_elements_b, n11, n21);
auto diff_percent = (t1 - t2) / t1 * 100.0;
cout << "Final test with n1=" << n11 << " n2=" << n21 << " t1=" << t1.count() << " t2=" << t2.count() << " diff_percent=" << diff_percent << "%" << endl;
return 0;
}
