Во время экспериментов с std :: set в C ++ и set () в Python я столкнулся с проблемой производительности, которую я не могу объяснить.Установите пересечение в C ++ по крайней мере в 3 раза медленнее, чем в Python.
Так кто-нибудь может указать мне на оптимизацию, которая может быть сделана для кода C ++, и / или объяснить, как Python делает это намного быстрее?
Я ожидаю, что оба они используют похожий алгоритм со сложностью O (n), пока множество упорядочено.Но, вероятно, Python делает некоторые оптимизации, чтобы достичь меньшего коэффициента.
set_bench.cc
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include <chrono>
#include <functional>
#include <thread>
void elapsed(std::function<void()> f, const std::string& s)
{
auto start = std::chrono::steady_clock::now();
f();
std::chrono::duration<double> elapsed = std::chrono::steady_clock::now() - start;
std::cout << s << " " << elapsed.count() << " seconds" << std::endl;
}
template <typename T>
void fill_set(std::set<T>& s, T start, T end, T step)
{
for (T i = start; i < end; i += step) {
s.emplace(i);
}
}
template <typename T>
void intersect(const std::set<T>& s1, const std::set<T>& s2, std::set<T>& result)
{
std::set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::inserter(result, result.begin()));
}
int main()
{
std::set<int64_t> s1;
std::set<int64_t> s2;
std::set<int64_t> s3;
elapsed(std::bind(fill_set<int64_t>, std::ref(s1), 8, 1000*1000*100, 13), "fill s1 took");
elapsed(std::bind(fill_set<int64_t>, std::ref(s2), 0, 1000*1000*100, 7), "fill s2 took");
std::cout << "s1 length = " << s1.size() << ", s2 length = " << s2.size() << std::endl;
elapsed(std::bind(intersect<int64_t>, std::ref(s1), std::ref(s2), std::ref(s3)), "intersect s1 and s2 took");
std::cout << "s3 length = " << s3.size() << std::endl;
// sleep to let check memory consumption
// while (true) std::this_thread::sleep_for(std::chrono::milliseconds(1000));
}
set_bench.py
#!/usr/bin/env python3
import time
def elapsed(f, s):
start = time.monotonic()
f()
elapsed = time.monotonic() - start
print(f'{s} {elapsed} seconds')
def fill_set(s, start, end, step=1):
for i in range(start, end, step):
s.add(i)
def intersect(s1, s2, result):
result.update(s1 & s2)
s1 = set()
s2 = set()
elapsed(lambda : fill_set(s1, 8, 1000*1000*100, 13), 'fill s1 took')
elapsed(lambda : fill_set(s2, 0, 1000*1000*100, 7), 'fill s2 took')
print(f's1 length = {len(s1)}, s2 length = {len(s2)}')
s3 = set()
elapsed(lambda: intersect(s1, s2, s3), 'intersect s1 and s2 took')
print(f's3 length = {len(s3)}')
# sleep to let check memory consumption
# while True: time.sleep(1)
Вот результаты запуска этой программы вследующая среда:
- clang версия 7.0.1
- gcc 8.2.0
- Python 3.7.2
- i7-7700 CPU @ 3,60 ГГц
$ clang -lstdc++ -O0 set_bench.cc -o set_bench && ./set_bench
fill s1 took 5.38646 seconds
fill s2 took 10.5762 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 1.48387 seconds
s3 length = 1098901
$ clang -lstdc++ -O1 set_bench.cc -o set_bench && ./set_bench
fill s1 took 3.31435 seconds
fill s2 took 6.41415 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 1.01276 seconds
s3 length = 1098901
$ clang -lstdc++ -O2 set_bench.cc -o set_bench && ./set_bench
fill s1 took 1.90269 seconds
fill s2 took 3.85651 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 0.512727 seconds
s3 length = 1098901
$ clang -lstdc++ -O3 set_bench.cc -o set_bench && ./set_bench
fill s1 took 1.92473 seconds
fill s2 took 3.72621 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 0.523683 seconds
s3 length = 1098901
$ gcc -lstdc++ -O3 set_bench.cc -o set_bench && time ./set_bench
fill s1 took 1.72481 seconds
fill s2 took 3.3846 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 0.516702 seconds
s3 length = 1098901
$ python3.7 ./set_bench.py
fill s1 took 0.9404696229612455 seconds
fill s2 took 1.082577683031559 seconds
s1 length = 7692308, s2 length = 14285715
intersect s1 and s2 took 0.17995300807524472 seconds
s3 length = 1098901
Как видите, результаты равны, поэтому я предполагаю, что обе программы выполняют одинаковые вычисления.
Кстати - программа RSS для C ++ стоит 1084896 кБ, а для Python - 1590400 кБ.