Есть несколько проблем с вашим тестом.
Во-первых, вы не тестируете пересечение множества, а «создаете пару массивов, заполняете их случайными числами и затем выполняете пересечение множества». Вам следует рассчитать только ту часть кода, которая вам действительно интересна. Даже если вы захотите сделать эти вещи, их не следует здесь сравнивать. Измеряйте одну вещь за раз, чтобы уменьшить неопределенность. Если вы хотите, чтобы ваша реализация на C ++ работала лучше, сначала вам нужно узнать, какая ее часть медленнее, чем ожидалось. Это означает, что вы должны отделить установочный код от теста пересечения.
Во-вторых, вы должны запускать тест большое количество раз, чтобы учесть возможные эффекты кэширования и другие неопределенности. (И, вероятно, выведите одно общее время, скажем, 1000 прогонов, а не отдельное время для каждого. Таким образом вы уменьшите неопределенность таймера, который может иметь ограниченное разрешение, и сообщите неточные результаты при использовании в диапазоне 0-20 мс.
Кроме того, насколько я могу прочитать из документов, входные данные для set_intersection должны быть отсортированы, а set2 не будет. И, кажется, нет смысла использовать unordered_map, когда unordered_set будет гораздо лучше соответствовать тому, что вы делаете.
Что касается необходимого кода установки, обратите внимание, что вам, вероятно, не нужно заполнять векторы, чтобы запустить пересечение. И ваша собственная реализация, и set_intersection уже работают с итераторами, так что вы можете просто передать им пару итераторов в структуры данных, в которые уже введены ваши входные данные.
Несколько более конкретных комментариев к вашему коду:
- Используйте
++iterator вместо iterator++
- вместо того, чтобы вызывать vector.end () на каждой итерации цикла, вызывайте его один раз и кэшируйте результат
- эксперимент с использованием отсортированных векторов vs std :: set vs
unordered_set (не unordered_map)
Edit:
Я не пробовал вашу версию C #, поэтому не могу правильно сравнить числа, но вот мой модифицированный тест. Каждый из них запускается 1000 раз на Core 2 Quad 2,5 ГГц с 4 ГБ ОЗУ:
std::set_intersection on std::set: 2606ms
std::set_intersection on tr1::unordered_set: 1014ms
std::set_intersection on sorted vectors: 171ms
std::set_intersection on unsorted vectors: 10140ms
Последний вариант немного несправедлив, потому что он должен копировать и сортировать векторы. В идеале, только сортировка должна быть частью эталона. Я пытался создать версию, в которой использовался массив из 1000 несортированных векторов (поэтому мне не нужно было копировать несортированные данные на каждой итерации), но производительность была примерно одинаковой или чуть хуже, потому что это приводило к постоянным ошибкам в кэше. , поэтому я вернулся к этой версии
И мой код:
#define _SECURE_SCL 0
#include <ctime>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <windows.h>
template <typename T, typename OutIter>
void stl_intersect(const T& set1, const T& set2, OutIter out){
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), out);
}
template <typename T, typename OutIter>
void sort_stl_intersect(T& set1, T& set2, OutIter out){
std::sort(set1.begin(), set1.end());
std::sort(set2.begin(), set2.end());
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), out);
}
template <typename T>
void init_sorted_vec(T first, T last){
for ( T cur = first; cur != last; ++cur)
{
int i = cur - first;
int value = 1000000000 + i;
*cur = value;
}
}
template <typename T>
void init_unsorted_vec(T first, T last){
for ( T cur = first; cur != last; ++cur)
{
int i = rand() % 200000 + 1;
i *= 10;
int value = 1000000000 + i;
*cur = value;
}
}
struct resize_and_shuffle {
resize_and_shuffle(int size) : size(size) {}
void operator()(std::vector<int>& vec){
vec.resize(size);
}
int size;
};
int main()
{
srand ( time(NULL) );
std::vector<int> out(100000);
std::vector<int> sortedvec1(100000);
std::vector<int> sortedvec2(1000);
init_sorted_vec(sortedvec1.begin(), sortedvec1.end());
init_unsorted_vec(sortedvec2.begin(), sortedvec2.end());
std::sort(sortedvec2.begin(), sortedvec2.end());
std::vector<int> unsortedvec1(sortedvec1.begin(), sortedvec1.end());
std::vector<int> unsortedvec2(sortedvec2.begin(), sortedvec2.end());
std::random_shuffle(unsortedvec1.begin(), unsortedvec1.end());
std::random_shuffle(unsortedvec2.begin(), unsortedvec2.end());
std::vector<int> vecs1[1000];
std::vector<int> vecs2[1000];
std::fill(vecs1, vecs1 + 1000, unsortedvec1);
std::fill(vecs2, vecs2 + 1000, unsortedvec2);
std::set<int> set1(sortedvec1.begin(), sortedvec1.end());
std::set<int> set2(sortedvec2.begin(), sortedvec2.end());
std::tr1::unordered_set<int> uset1(sortedvec1.begin(), sortedvec1.end());
std::tr1::unordered_set<int> uset2(sortedvec2.begin(), sortedvec2.end());
DWORD start, stop;
DWORD delta[4];
start = GetTickCount();
for (int i = 0; i < 1000; ++i){
stl_intersect(set1, set2, out.begin());
}
stop = GetTickCount();
delta[0] = stop - start;
start = GetTickCount();
for (int i = 0; i < 1000; ++i){
stl_intersect(uset1, uset2, out.begin());
}
stop = GetTickCount();
delta[1] = stop - start;
start = GetTickCount();
for (int i = 0; i < 1000; ++i){
stl_intersect(sortedvec1, sortedvec2, out.begin());
}
stop = GetTickCount();
delta[2] = stop - start;
start = GetTickCount();
for (int i = 0; i < 1000; ++i){
sort_stl_intersect(vecs1[i], vecs1[i], out.begin());
}
stop = GetTickCount();
delta[3] = stop - start;
std::cout << "std::set_intersection on std::set: " << delta[0] << "ms\n";
std::cout << "std::set_intersection on tr1::unordered_set: " << delta[1] << "ms\n";
std::cout << "std::set_intersection on sorted vectors: " << delta[2] << "ms\n";
std::cout << "std::set_intersection on unsorted vectors: " << delta[3] << "ms\n";
return 0;
}
Нет причины, по которой C ++ всегда должен быть быстрее, чем C #. C # имеет несколько ключевых преимуществ, которые требуют большой осторожности, чтобы конкурировать с C ++.
Первое, о чем я могу подумать, это то, что динамическое распределение смехотворно дешево в .NET-земле. Каждый раз, когда вектор C ++, set или unordered_set (или любой другой контейнер) должен изменять размер или расширяться, это очень дорогая операция malloc. В .NET выделение кучи - чуть больше, чем добавление смещения к указателю.
Так что, если вы хотите, чтобы версия C ++ конкурировала, вам, вероятно, придется решить эту проблему, позволив вашим контейнерам изменить размер без необходимости выполнять фактическое выделение кучи, возможно, с помощью пользовательских распределителей для контейнеров (возможно, может быть boost :: pool может будь хорошей ставкой, или ты можешь попробовать бросить свою собственную)
Другая проблема заключается в том, что set_difference работает только с отсортированным вводом, и для воспроизведения результатов тестов, которые включают сортировку, мы должны делать свежую копию несортированных данных на каждой итерации, что является дорогостоящим (хотя, опять же, Использование пользовательских распределителей очень поможет). Я не знаю, какую форму принимает ваш ввод, но возможно, что вы можете отсортировать ввод напрямую, не копируя его, а затем запустить set_difference непосредственно для этого. (Это было бы легко сделать, если бы вы вводили как минимум массив или контейнер STL.)
Одним из ключевых преимуществ STL является то, что он настолько гибок, что может работать практически с любой последовательностью ввода. В C # вам в значительной степени приходится копировать входные данные в List, Dictionary или что-то еще, но в C ++ вы можете избежать выполнения std::sort и set_intersection для необработанного ввода.
Наконец, конечно, попробуйте запустить код через профилировщик и посмотреть, где именно тратится время. Вы также можете попробовать запустить код через GCC. У меня сложилось впечатление, что производительность STL в MSVC иногда немного странная. Возможно, стоит попробовать под другим компилятором просто посмотреть, есть ли у вас аналогичные тайминги.
Наконец, вы можете найти эти сообщения в блоге, имеющие отношение к производительности C ++ против C #:
http://blogs.msdn.com/ricom/archive/2005/05/10/416151.aspx
Мораль тех, кто в основном состоит в том, что да, вы можете добиться лучшей производительности в C ++, но это удивительный объем работы.