#include <ctime>
#include <algorithm>
#include <random>
#include <iostream>
#include <set>
double boundedSumJoe(std::vector<int> x, int lower, int upper) {
int myMax = *std::max_element(x.begin(), x.end());
int offSet = std::abs(*std::min_element(x.begin(), x.end())) + 1;
unsigned long int myRange;
if (myMax > 0)
myRange = myMax + offSet; // E.g. if myMax = 10 & myMin = -2, then myRange = 12
else
myRange = offSet;
offSet--;
std::vector<int> frequency(myRange, 0);
std::vector<int> values(myRange, 0);
std::vector<int>::iterator it, itEnd = x.end();
int myIndex;
double mySum = 0;
for (it = x.begin(); it < itEnd; it++) {
myIndex = *it + offSet;
frequency[myIndex]++;
values[myIndex] = *it;
}
int count = 0;
bool firstHit = true;
for (std::size_t j = 0; j < myRange; j++) {
if (frequency[j]) {
if (count >= lower) {
if (count <= upper) {
firstHit = false;
mySum += values[j] * frequency[j];
} else {
if ((count - upper) > 1) {
int k = j - 1;
while (!frequency[k]) {k--;}
mySum -= (values[k] * (count - upper - 1));
}
break;
}
}
count += frequency[j];
if ((count - lower) >= 1 && firstHit) {
firstHit = false;
mySum += (values[j] * (count - lower));
}
}
}
return mySum;
}
double boundedSumBen(std::vector<int> x, int lower, int upper) {
double mySum = 0;
// First partition vector at larger bound
std::nth_element(x.begin(), x.begin() + upper, x.end());
// Now create partition of above at lower bound
std::nth_element(x.begin(), x.begin() + lower, x.begin() + upper);
std::vector<int>::iterator it, itEnd = x.begin() + upper;
for (it = x.begin() + lower; it <= itEnd; it++)
mySum += *it;
return mySum;
}
double boundedSumOP(std::vector<int> x, int lower, int upper) {
double mySum = 0;
std::sort(x.begin(), x.end());
std::vector<int>::iterator it, itEnd = x.begin() + upper;
for (it = x.begin() + lower; it <= itEnd; it++)
mySum += *it;
return mySum;
}
int main() {
std::vector<int> v(200001);
std::random_device rd;
std::mt19937 gen(rd());
std::iota(v.begin(), v.end(), -100000);
std::shuffle(v.begin(), v.end(), gen);
// random-sample without replacement
std::vector<int> randVec(v.begin(), v.begin() + 100000);
int val1, val2, val3;
std::clock_t start_time, end_time;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val1 = boundedSumBen(randVec, 49900, 50100);
end_time = clock();
std::cout << "time taken on sample w/o rep std::nth_element : " <<
end_time - start_time << std::endl;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val2 = boundedSumJoe(randVec, 49900, 50100);
end_time = clock();
std::cout << "time taken on sample w/o rep indexing method by Joe : " <<
end_time - start_time << std::endl;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val3 = boundedSumOP(randVec, 49900, 50100);
end_time = clock();
std::cout << "time taken on sample w/o rep naive approach with std::sort : " <<
end_time - start_time << std::endl;
std::cout << "All functions on sample w/o rep return the same value of : " <<
val1 << ", " << val2 << ", and " << val3 << std::endl;
/// Now we test a random sample with replacement
std::uniform_int_distribution<int> distribution(-100000, 100000);
for (std::size_t i = 0; i < 100000; i++)
randVec[i] = distribution(gen);
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val1 = boundedSumBen(randVec, 9900, 10100);
end_time = clock();
std::cout << "time taken on sample with rep std::nth_element : " <<
end_time - start_time << std::endl;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val2 = boundedSumJoe(randVec, 9900, 10100);
end_time = clock();
std::cout << "time taken on sample with rep indexing method by Joe : " <<
end_time - start_time << std::endl;
start_time = clock();
for (std::size_t i = 0; i < 100; i++)
val3 = boundedSumOP(randVec, 9900, 10100);
end_time = clock();
std::cout << "time taken on sample with rep naive approach with std::sort : " <<
end_time - start_time << std::endl;
std::cout << "All functions on sample with rep return the same value of : " <<
val1 << ", " << val2 << ", and " << val3 << std::endl;
std::cout << "Number of unique elements in vector with replacement "
<< std::set<int>(randVec.begin(), randVec.end()).size()
<< std::endl;
return 0;
}