сообщество.У меня есть этот кусок кода, который находит ближайшую пару точек в евклидовом трехмерном пространстве.Этот вопрос не касается ни алгоритма, ни его реализации, ни чего-либо еще.Проблема в том, что он работает на значительно * на 1002 * медленнее при компиляции с GCC, а не с Clang.Самое странное, что он имеет сопоставимое время выполнения на случайных выборках и примерно в 100 раз медленнее на некоторых конкретных.Я подозреваю, что в GCC может быть ошибка, так как я не могу думать ни о какой другой опции.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <fstream>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
static std::mt19937 mmtw(std::chrono::steady_clock::now().time_since_epoch().count());
int64_t rng(int64_t x, int64_t y) {
static std::uniform_int_distribution<int64_t> d;
return d(mmtw) % (y - x + 1) + x;
}
constexpr static int MAXN = 1e5 + 10;
void solve(std::istream &in, std::ostream &out);
void generate(std::ostream &out) {
constexpr int N = 1e5;
out << N << '\n';
int MIN = -1e6;
int MAX = 1e6;
for (int i = 0; i < N; ++i) {
out << 0 << ' ';
out << i << ' ';
out << (i + 1) * int(1e4) << '\n';
}
}
int main() {
freopen("input.txt", "r", stdin);
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cerr.tie(nullptr);
std::ofstream fout("input.txt");
generate(fout);
fout.close();
solve(std::cin, std::cout);
return 0;
}
struct point_t {
int32_t x, y, z;
int id;
point_t() = default;
point_t(int32_t x, int32_t y, int32_t z) : x(x), y(y), z(z) {}
point_t operator +(const point_t &rhs) const {
return point_t(x + rhs.x, y + rhs.y, z + rhs.z);
}
point_t operator -(const point_t &rhs) const {
return point_t(x - rhs.x, y - rhs.y, z - rhs.z);
}
int64_t abs2() const {
return 1LL * x * x + 1LL * y * y + 1LL * z * z;
}
};
std::istream &operator >>(std::istream &in, point_t &pt) {
return in >> pt.x >> pt.y >> pt.z;
}
inline bool cmp_x(const point_t &lhs, const point_t &rhs) {
return lhs.x < rhs.x;
}
inline bool cmp_y(const point_t &lhs, const point_t &rhs) {
return lhs.y < rhs.y;
}
inline bool cmp_z(const point_t &lhs, const point_t &rhs) {
return lhs.z < rhs.z;
}
struct pair_t {
int64_t distance_sq;
point_t a {}, b {};
pair_t() : distance_sq(std::numeric_limits<int64_t>::max()) {};
pair_t(const point_t &a, const point_t &b) : distance_sq((a - b).abs2()), a(a), b(b) {}
bool operator<(const pair_t &rhs) const {
return distance_sq < rhs.distance_sq;
}
};
template <typename T> inline T sqr(T arg) { return arg * arg; }
point_t pts[MAXN];
static pair_t ans = pair_t();
void recur_2D(point_t pts[], int size, int64_t threshold_sq) {
if (size <= 3) {
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j < size; ++j) {
ans = std::min(ans, pair_t(pts[i], pts[j]));
}
}
std::sort(pts, pts + size, cmp_y);
return;
}
int mid = size / 2;
int midx = pts[mid].x;
recur_2D(pts, mid, threshold_sq);
recur_2D(pts + mid, size - mid, threshold_sq);
static point_t buffer[MAXN];
std::merge(pts, pts + mid, pts + mid, pts + size, buffer, cmp_y);
std::copy(buffer, buffer + size, pts);
int buff_sz = 0;
for (int i = 0; i < size; ++i) {
if (sqr(pts[i].x - midx) >= threshold_sq) {
continue;
}
int64_t x_sqr = sqr(pts[i].x - midx);
for (int j = buff_sz - 1; j >= 0; --j) {
if (sqr(pts[i].y - buffer[j].y) + x_sqr >= threshold_sq) {
break;
}
ans = std::min(ans, pair_t(pts[i], buffer[j]));
}
buffer[buff_sz++] = pts[i];
}
}
void recur_3D(point_t pts[], int size) {
if (size <= 3) {
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j < size; ++j) {
ans = std::min(ans, pair_t(pts[i], pts[j]));
}
}
std::sort(pts, pts + size, cmp_x);
return;
}
int mid = size / 2;
int midz = pts[mid].z;
recur_3D(pts, mid);
recur_3D(pts + mid, size - mid);
static point_t buffer[MAXN];
std::merge(pts, pts + mid, pts + mid, pts + size, buffer, cmp_x);
std::copy(buffer, buffer + size, pts);
int buff_sz = 0;
for (int i = 0; i < size; ++i) {
if (sqr(pts[i].z - midz) >= ans.distance_sq) {
continue;
}
buffer[buff_sz++] = pts[i];
}
recur_2D(buffer, buff_sz, ans.distance_sq);
}
void solve(std::istream &in, std::ostream &out) {
clock_t start = clock();
int num_of_points;
in >> num_of_points;
for (int i = 0; i < num_of_points; ++i) {
in >> pts[i];
pts[i].id = i + 1;
}
std::sort(pts, pts + num_of_points, cmp_z);
recur_3D(pts, num_of_points);
out << ans.distance_sq << '\n';
out << 1.0 * (clock() - start) / CLOCKS_PER_SEC << " s.\n";
}
Ссылка на этот код: https://code.re/2yfPzjkD
Он генерирует пример, который делает код оченьмедленно, а затем измеряет время выполнения алгоритма.
Я компилирую с
g++ -DLOCAL -std=c++1z -O3 -Wno-everything main.cpp
и с
clang++ -DLOCAL -std=c++1z -O3 -Wno-everything main.cpp
изапустите ./main, имея input.txt в том же каталоге.
Скопированный в Clang двоичный файл работает в 0.053798 s., а GCC - в 12.4276 s..Эти числа взяты из вывода программы, вы можете видеть, что функция solve.
Я также проверил разницу на https://wandbox.org/ в разных версиях компилятора.https://wandbox.org/permlink/YFEEWSKyos2dQf32 - лязг https://wandbox.org/permlink/XctarNHvd3I1B0x8 - gcc
Обратите внимание, я сжал вход и, таким образом, пришлось немного изменить показания в solve.
На моемЛокальный компьютер У меня есть эти компиляторы.
clang++ --version
clang version 7.0.0 (tags/RELEASE_700/final)
g++ --version
g++ (GCC) 8.2.1 20180831
Такое чувство, что я запускаю код GCC без оптимизации компилятора.В чем может быть причина?
UPD.
Также есть версия, которая вызывает std::sort только один раз в самом начале.https://wandbox.org/permlink/i9Kd3GdewxSRwXsM
Я также пытался скомпилировать Clang с -stdlib=libstdc++, перетасовывая данные, и думаю, что различные реализации std::sort не являются причиной.