Skip to content

Instantly share code, notes, and snippets.

@bseibold
Last active February 10, 2024 15:14
Show Gist options
  • Save bseibold/bf878e2689eba4cd5f47cf959a4ef7ed to your computer and use it in GitHub Desktop.
Save bseibold/bf878e2689eba4cd5f47cf959a4ef7ed to your computer and use it in GitHub Desktop.
#include <algorithm>
#include <array>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <random>
#include <vector>
using namespace std;
using namespace std::chrono;
template<size_t N>
size_t median_sort(array<uint8_t, N>& data) {
sort(data.begin(), data.end());
return data[N / 2];
}
template<size_t N>
size_t median_histo(const array<uint8_t, N>& data) {
array<int, 256> histo {};
int sum = 0;
for (uint8_t v : data)
histo[v]++;
for (size_t idx = 0; idx < 256; idx++) {
sum += histo[idx];
if (sum > (N / 2))
return idx;
}
return 0;
}
template<size_t N>
void fill(array<uint8_t, N>& data)
{
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distrib(0, 255);
for (size_t i = 0; i < data.size(); i++)
data[i] = distrib(gen);
}
int main(int argc, char *argv[])
{
constexpr size_t n = 100000;
vector<array<uint8_t, 1000>> data { n };
volatile int sum = 0;
unsigned long t_histo, t_sort;
for (size_t i = 0; i < n; i++)
fill(data[i]);
{
sum = 0;
auto t1 = high_resolution_clock::now();
for (size_t i = 0; i < n; i++) {
sum += median_histo(data[i]);
}
auto t2 = high_resolution_clock::now();
t_histo = duration_cast<milliseconds>(t2 - t1).count();
}
{
sum = 0;
auto t3 = high_resolution_clock::now();
for (size_t i = 0; i < n; i++) {
sum += median_sort(data[i]);
}
auto t4 = high_resolution_clock::now();
t_sort = duration_cast<milliseconds>(t4 - t3).count();
}
printf("histo: %lu ms\n", t_histo);
printf("sort: %lu ms\n", t_sort);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment