median_test.cpp

#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;
}