Сортировать массив std :: pair против struct: какой из них быстрее?
Мне было интересно, сортировка ли массив std::pair быстрее, или массив struct?
Вот мои сегменты кода:
Код № 1: сортировка std::pair массив (по первому элементу):
#include <algorithm>
pair <int,int> client[100000];
sort(client,client+100000);
Код № 2: Сортировать struct (от A):
#include <algorithm>
struct cl{
int A,B;
}
bool cmp(cl x,cl y){
return x.A < y.A;
}
cl clients[100000];
sort(clients,clients+100000,cmp);
код № 3: Сортировать struct (от A и внутренний оператор <):
#include <algorithm>
struct cl{
int A,B;
bool operator<(cl x){
return A < x.A;
}
}
cl clients[100000];
sort(clients,clients+100000);
Обновить: Я использовал эти коды для решения проблемы в онлайн-судье. я получил лимит времени 2 секунды для кода № 1 и принимать для кодов № 2 и № 3 (работает за 62 миллисекунды). Почему код # 1 занимает так много времени по сравнению с другими кодами? В чем разница?
Решение
Знаешь что std::pair является? Это структура (или класс, который является тем же самым в C ++ для наших целей). Поэтому, если вы хотите узнать, что быстрее, вам подходит обычный совет: вы должны проверить это и выяснить сами на своей платформе. Но лучше всего, если вы реализуете эквивалентную логику сортировки std::pair, у вас будет эквивалентная производительность, потому что компилятору все равно, будет ли имя вашего типа данных std::pair или что-то другое.
Но учтите, что размещенный вами код не эквивалентен по функциональности operator < предусмотрено std::pair, В частности, вы сравниваете только первый член, а не оба. Очевидно, это может привести к некоторому увеличению скорости (но, вероятно, этого недостаточно, чтобы заметить это в любой реальной программе).
Другие решения
Я бы оценил, что между этими двумя решениями нет большой разницы.
Но, как ВСЕ запросы, связанные с производительностью, вместо того, чтобы полагаться на то, что кто-то в интернете говорит, что они одинаковы, или один лучше другого, сделайте свои собственные измерения. Иногда тонкие различия в реализации будут иметь большое значение для фактических результатов.
Сказав это, реализация std::pair является структурой (или классом) с двумя членами, first а также secondтак что мне трудно представить, что здесь есть какая-то реальная разница — вы просто реализуете свою собственную пару с помощью собственной функции сравнения, которая выполняет те же действия, что и существующая пара … Будь то во внутренней функции в класс или отдельная функция вряд ли будут иметь большое значение.
Изменить: я сделал следующее «смешать код вместе»:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;
const int size=100000000;
pair <int,int> clients1[size];
struct cl1{
int first,second;
};cl1 clients2[size];
struct cl2{
int first,second;
bool operator<(const cl2 x) const {
return first < x.first;
}
};
cl2 clients3[size];template<typename T>
void fill(T& t)
{
srand(471117); // Use same random number each time/
for(size_t i = 0; i < sizeof(t) / sizeof(t[0]); i++)
{
t[i].first = rand();
t[i].second = -t[i].first;
}
}void func1()
{
sort(clients1,clients1+size);
}bool cmp(cl1 x, cl1 y){
return x.first < y.first;
}
void func2()
{
sort(clients2,clients2+size,cmp);
}void func3()
{
sort(clients3,clients3+size);
}
void benchmark(void (*f)(), const char *name)
{
cout << "running " << name << endl;
clock_t time = clock();
f();
time = clock() - time;
cout << "Time taken = " << (double)time / CLOCKS_PER_SEC << endl;
}
#define bm(x) benchmark(x, #x)
int main()
{
fill(clients1);
fill(clients2);
fill(clients3);
bm(func1);
bm(func2);
bm(func3);
}
Результаты приведены ниже:
running func1
Time taken = 10.39
running func2
Time taken = 14.09
running func3
Time taken = 10.06
Я трижды проводил тест, и все они в пределах ~ 0,1 с вышеупомянутых результатов.
Edit2:
И, глядя на сгенерированный код, совершенно ясно, что «средняя» функция занимает немного больше времени, так как сравнение выполняется для pair а также struct cl2, но не может быть встроен для struct cl1 — поэтому каждое сравнение в буквальном смысле делает вызов функции, а не несколько инструкций внутри функций. Это большие накладные расходы.