profiling, C++ (gcc)

Language: Layout:

#include <cstddef>
#include <cstdint>
#include <random>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstdio>

using std::size_t;
using std::int32_t;
using std::int64_t;
using std::vector;
using std::unordered_map;
using std::printf;
using std::accumulate;
using std::sort;

size_t R,W;

struct Int32
{
    Int32():value() {}
    Int32(int32_t src):value(src) {++W;}
    operator int32_t() const {++R; return value;}
    int32_t value;
};

namespace std
{
template<>
struct hash<Int32>
{
    typedef Int32 argument_type;
    typedef std::size_t result_type;
    result_type operator()(argument_type const& s) const noexcept
    {
        return hash<int32_t>().operator()(int32_t(s));
    }
};
};

vector<int32_t> gen(size_t n)
{
    const int32_t M=100000000;
    std::minstd_rand rng(1);
    vector<int32_t> ret(n,0);
    for(size_t i=0;i<n/2;++i) ret[i]=std::uniform_int_distribution<int32_t>(-M,+M)(rng);
    for(size_t i=0;i<n/2;++i) ret[i+(n+1)/2]=-ret[i];
    return ret;
}

bool solve1(const vector<int32_t> &v)
{
    vector<int32_t> w(v);
    size_t n=v.size();
    if(n<2) return true;
    sort(w.begin(),w.end());
    int32_t c=w.front()+w.back();
    for(size_t i=0,j=n-1;i<j;++i,--j)
        if(w[i]+w[j]!=c) return false;
    return true;
}

bool solve2(const vector<int32_t> &v)
{
    unordered_map<Int32,size_t> m;
    size_t n=v.size();
    m.reserve(n);
    int32_t c=int32_t(2ll*accumulate(v.begin(),v.end(),0ll)/n);
    for(auto x:v)
    {
        int32_t y=2*x-c;
        if(y<0) --m[-y]; else ++m[y];
    }
    for(const auto &e:m)
        if(e.first!=0&&e.second!=0) return false;
    return true;
}

int main()
{
    printf("n         :       vector                      hash_map\n");
    for(size_t i=0;i<23;++i)
    {
        size_t n=1ull<<i;
        printf("%-10zu:",n);
        vector<int32_t> v=gen(n);
        double t1,t2;
        t1=clock();
        bool a1=solve1(v);
        t1=clock()-t1;
        t2=clock();
        R=0;W=0;
        bool a2=solve2(v);
        t2=clock()-t2;
        t1 = t1 * 1000.0 / CLOCKS_PER_SEC;
        t2 = t2 * 1000.0 / CLOCKS_PER_SEC;
        printf("%10.3f ms[%d] %10.3f   ",t1,a1,t1/n*1000000.0);
        printf("%10.3f ms[%d] %10.3f   %4.1f %4.1f",t2,a2,t2/n*1000000.0,double(R)/n,double(W)/n);
        printf("\n");
    }
    return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 1.03 sec, absolute running time: 3.05 sec, cpu time: 3.88 sec, memory peak: 113 Mb, absolute service time: 4,08 sec