just_some_cplusplus.cpp

#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_set>
#include <vector>
 
int32_t some_calculations(int32_t number) {
    std::vector<int32_t> a;
    std::unordered_set<int32_t> s;
 
    s.max_load_factor(2./3);
    a.reserve(number);
 
    int32_t x = 0;
    for (int32_t i=0; i<number; ++i) {
        x += i;
 
        int item = i%2 ? -x : x;
        s.insert(item);
        a.emplace_back(item);
    }
 
    int32_t tot = 0;
    for (auto x=std::begin(a); x != std::end(a); ++x) {
        for (auto y=std::next(x); y != std::end(a); ++y) {
            if (-(*x+*y) != *x && -(*x+*y) != *y && s.find(-(*x+*y)) != std::end(s)) {
                ++tot;
            }
        }
    }
 
    return tot / 3;
}
 
int main(int, char **) {
    int32_t tot = 0;
 
    for (int i=0; i<500; ++i) {
        tot += some_calculations(i);
    }
 
    std::cout << tot << std::endl;
}

just_some_cplusplus_cache_a.cpp

#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_set>
#include <vector>
 
int32_t some_calculations(int32_t number) {
    std::vector<int32_t> a;
    std::unordered_set<int32_t> s;
 
    s.max_load_factor(2./3);
    a.reserve(number);
 
    int32_t x = 0;
    for (int32_t i=0; i<number; ++i) {
        x += i;
 
        int item = i%2 ? -x : x;
        s.insert(item);
        a.emplace_back(item);
    }
 
    int32_t tot = 0;
    auto a_end = std::end(a);
    for (auto x=std::begin(a); x != a_end; ++x) {
        for (auto y=std::next(x); y != a_end; ++y) {
            if (-(*x+*y) != *x && -(*x+*y) != *y && s.find(-(*x+*y)) != std::end(s)) {
                ++tot;
            }
        }
    }
 
    return tot / 3;
}
 
int main(int, char **) {
    int32_t tot = 0;
 
    for (int i=0; i<500; ++i) {
        tot += some_calculations(i);
    }
 
    std::cout << tot << std::endl;
}

just_some_cplusplus_cache_s.cpp

#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_set>
#include <vector>
 
int32_t some_calculations(int32_t number) {
    std::vector<int32_t> a;
    std::unordered_set<int32_t> s;

    s.max_load_factor(2./3);
    a.reserve(number);
 
    int32_t x = 0;
    for (int32_t i=0; i<number; ++i) {
        x += i;
 
        int item = i%2 ? -x : x;
        s.insert(item);
        a.emplace_back(item);
    }
 
    int32_t tot = 0;
    auto s_end = std::end(s);
    for (auto x=std::begin(a); x != std::end(a); ++x) {
        for (auto y=std::next(x); y != std::end(a); ++y) {
            if (-(*x+*y) != *x && -(*x+*y) != *y && s.find(-(*x+*y)) != s_end) {
                ++tot;
            }
        }
    }
 
    return tot / 3;
}
 
int main(int, char **) {
    int32_t tot = 0;
 
    for (int i=0; i<500; ++i) {
        tot += some_calculations(i);
    }
 
    std::cout << tot << std::endl;
}

just_some_cplusplus_constiter.cpp

#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_set>
#include <vector>
 
int32_t some_calculations(int32_t number) {
    std::vector<int32_t> a;
    std::unordered_set<int32_t> s;
 
    s.max_load_factor(2./3);
    a.reserve(number);
 
    int32_t x = 0;
    for (int32_t i=0; i<number; ++i) {
        x += i;
 
        int item = i%2 ? -x : x;
        s.insert(item);
        a.emplace_back(item);
    }
 
    int32_t tot = 0;
    for (auto x=a.cbegin(); x != a.cend(); ++x) {
        for (auto y=std::next(x); y != a.cend(); ++y) {
            if (-(*x+*y) != *x && -(*x+*y) != *y && s.find(-(*x+*y)) != s.cend()) {
                ++tot;
            }
        }
    }
 
    return tot / 3;
}
 
int main(int, char **) {
    int32_t tot = 0;
 
    for (int i=0; i<500; ++i) {
        tot += some_calculations(i);
    }
 
    std::cout << tot << std::endl;
}

just_some_cplusplus_indexes.cpp

#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_set>
#include <vector>
 
int32_t some_calculations(int32_t number) {
    std::vector<int32_t> a;
    std::unordered_set<int32_t> s;

    s.max_load_factor(2./3);
    a.reserve(number);
 
    int32_t x = 0;
    for (int32_t i=0; i<number; ++i) {
        x += i;
 
        int item = i%2 ? -x : x;
        s.insert(item);
        a.emplace_back(item);
    }
 
    int32_t tot = 0;
    for (auto i=0; i != number; ++i) {
        for (auto j=i+1; j != number; ++j) {
            if (-(a[i]+a[j]) != a[i] && -(a[i]+a[j]) != a[j] && s.find(-(a[i]+a[j])) != std::end(s)) {
                ++tot;
            }
        }
    }
 
    return tot / 3;
}

int main(int, char **) {
    int32_t tot = 0;
 
    for (int i=0; i<500; ++i) {
        tot += some_calculations(i);
    }
 
    std::cout << tot << std::endl;
}

just_some_cplusplus_rawptr.cpp

#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_set>
#include <vector>
 
int32_t some_calculations(int32_t number) {
    std::vector<int32_t> a;
    std::unordered_set<int32_t> s;
 
    s.max_load_factor(2./3);
    a.reserve(number);
 
    int32_t x = 0;
    for (int32_t i=0; i<number; ++i) {
        x += i;
 
        int item = i%2 ? -x : x;
        s.insert(item);
        a.emplace_back(item);
    }
 
    int32_t tot = 0;
    for (auto *x=a.data(); x != a.data() + number; ++x) {
        for (auto *y=x+1; y != a.data() + number; ++y) {
            if (-(*x+*y) != *x && -(*x+*y) != *y && s.find(-(*x+*y)) != std::end(s)) {
                ++tot;
            }
        }
    }
 
    return tot / 3;
}
 
int main(int, char **) {
    int32_t tot = 0;
 
    for (int i=0; i<500; ++i) {
        tot += some_calculations(i);
    }
 
    std::cout << tot << std::endl;
}

just_some_cplusplus_rawptr_cache_a.cpp

#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_set>
#include <vector>
 
int32_t some_calculations(int32_t number) {
    std::vector<int32_t> a;
    std::unordered_set<int32_t> s;
 
    s.max_load_factor(2./3);
    a.reserve(number);
 
    int32_t x = 0;
    for (int32_t i=0; i<number; ++i) {
        x += i;
 
        int item = i%2 ? -x : x;
        s.insert(item);
        a.emplace_back(item);
    }
 
    int32_t tot = 0;
    auto a_end = a.data() + number;
    for (auto *x=a.data(); x != a_end; ++x) {
        for (auto *y=x+1; y != a_end; ++y) {
            if (-(*x+*y) != *x && -(*x+*y) != *y && s.find(-(*x+*y)) != std::end(s)) {
                ++tot;
            }
        }
    }
 
    return tot / 3;
}
 
int main(int, char **) {
    int32_t tot = 0;
 
    for (int i=0; i<500; ++i) {
        tot += some_calculations(i);
    }
 
    std::cout << tot << std::endl;
}

just_some_python.py

def some_calculations(number):
    a = []
 
    x = 0
    for i in range(number):
        x += i;
        a.append(-x if i%2 else x);
 
    s = set(a)
 
    tot = 0
    for i, x in enumerate(a):
        for y in a[i+1:]:
            if -(x + y) not in (x, y) and -(x + y) in s:
                tot += 1
 
    return tot // 3
 
print(sum(map(some_calculations, range(500))))

plot_times.py

"""
Graph the time to run the input commands.

Usage:
    plot_times.py <n> <command>...
"""

import docopt
import numpy
import pprint
import resource
import seaborn
import shlex
import subprocess
import sys

from matplotlib import pyplot

options = docopt.docopt(__doc__)

try:
    repeats = int(options["<n>"])
except ValueError:
    print("<n> has to be an integer.")
    raise SystemExit

datas = []


# Time

for raw_command in options["<command>"]:
    command = shlex.split(raw_command)

    data = [resource.getrusage(resource.RUSAGE_CHILDREN).ru_utime]

    for i in range(repeats):
        print("\r{}: {} of {}".format(raw_command, i+1, repeats), end="")
        sys.stdout.flush()

        subprocess.check_output(command)
        data.append(resource.getrusage(resource.RUSAGE_CHILDREN).ru_utime)

    print()
    datas.append(data)


# Plot

figure = pyplot.figure(figsize=(24, 6))
seaborn.set(style="white", font_scale=2)

for command, data in zip(options["<command>"], datas):
    times = numpy.diff(data)

    seaborn.distplot(
        times,
        label=command,
        bins=len(set(times.round(2))),
        norm_hist=True,
        kde_kws={"clip": (min(times), max(times))},
        hist_kws={"histtype": "stepfilled", "alpha": 0.2}
    )

seaborn.despine()
pyplot.title("Time to run")
pyplot.legend()

figure.savefig("time_to_run.png")

The first two timings didn't have just_some_cplusplus_rawptr_cache_a.cpp

python plot_times.py 128 ./just_some_cplusplus*.out "pypy just_some_python.py" 

python plot_times.py 128 ./just_some_cplusplus*.out

Then I combined the two that seemed to work: caching the iterator and using raw pointers.

python plot_times.py 128 "./just_some_cplusplus.out" "./just_some_cplusplus_cache_a.out" "./just_some_cplusplus_rawptr_cache_a.out"