Это не алгоритмический вопрос, а вопрос реализации.Есть ли процедура сортировки быстрее, чем qsort?
У меня есть структура данных, которая выглядит как:
struct MyStruct {
float val;
float val2;
int idx;
}
Я иду через массив около 40 миллионов элементов, а также назначить поля в «VAL» быть элементом, а поле «IDX» в быть индексом.
Я тогда вызова:
MyStruct* theElements = new MyStruct[totalNum];
qsort(theElements, totalNum, sizeof(MyStruct), ValOrdering);
, а затем, когда я заполняю val2, в обратном порядке с
qsort(theElements, totalNum, sizeof(MyStruct), IndexOrdering);
где
static int ValOrdering(const void* const v1, const void* const v2)
{
if (((struct MyStruct*) v1)->val < ((struct MyStruct*) v2)->val)
return -1;
if (((struct MyStruct*) v1)->val> ((struct MyStruct*) v2)->val)
return 1;
return 0;
}
и
static int IndexOrdering(const void* const v1, const void* const v2)
{
return ((struct MyStruct*) v1)->idx- ((struct MyStruct*) v2)->idx;
}
Эта настройка занимает 4 секунды для выполнения обоих типов. 4 секунды, похоже, долгое время для своего рода 40 миллионов элементов, чтобы взять на себя процессор 3Ghz i5; есть ли более быстрый подход? Я использую vs2010 с компилятором Intel (у него есть сортировки, но не над такими структурами, которые я вижу).
Update: Использование зОго :: рода бреет около 0,4 секунд от среды выполнения, называется как:
std::sort(theElements, theElements + totalPixels, ValOrdering);
std::sort(theElements, theElements + totalPixels, IndexOrdering);
и
bool GradientOrdering(const MyStruct& i, const MyStruct& j){
return i.val< j.val;
}
bool IndexOrdering(const MyStruct& i, const MyStruct& j){
return i.idx< j.idx;
}
добавив 'инлайн' ключевое слово предикаты делает похоже, не имеет значения. Поскольку у меня есть, и спецификация позволяет, четырехъядерную машину, я буду проверять какой-то многопоточный вид.
Update 2: После @SirGeorge и @stark, я взял взгляд на одного сорта сделано с помощью указателя перенаправляет:
bool GradientOrdering(MyStruct* i, MyStruct* j){
return i->val< j->val;
}
bool IndexOrdering(MyStruct* i, MyStruct* j){
return i->idx< j->idx;
}
Даже если есть только один вызов сортировки (подпрограмме GradientOrdering), полученный алгоритм занимает 5 секунд, на 1 секунду дольше, чем подход qsort. Похоже, std :: sort выигрывает.
Update 3: Похоже, Intel, tbb::parallel_sort является победителем, принимая время выполнения одного сорта до 0,5с на моей системе (так, 1.0с для обоих, что означает, что это довольно хорошо масштабировании из оригинальной версии 4.0 s для обоих). Я попытался пойти с параллельной фантазией, предложенной Microsoft here, но поскольку я уже использую tbb, а синтаксис для parallel_sort идентичен синтаксису для std::sort, я мог бы использовать мои более ранние std::sort компараторы, чтобы все было закончено.
Я также воспользовался предложением @ gbulmer (действительно, с помощью перехвата над головой), что у меня уже есть исходные индексы, поэтому вместо второго сортировки мне просто нужно назначить второй массив с помощью индексы от первого назад в отсортированном порядке. Я могу избавиться от использования этой памяти, потому что я только развертываю на 64-битных машинах с объемом памяти не менее 4 ГБ (хорошо, чтобы эти спецификации работали раньше времени); без этого знания потребуется вторая сортировка.
Предложение @ gbulmer дает наибольшее ускорение, но исходный вопрос задает вопрос о наиболее быстрой сортировке. std::sort является самым быстрым однопоточным, parallel_sort является самым быстрым многопоточным, но никто не ответил на этот вопрос, поэтому я даю @gbulmer чек.
'std :: sort' = больше информации о типе и более встраиваемых возможностей. –
Вы можете попробовать многопоточную сортировку слияния. – manasij7479
Вы знаете что-нибудь о распределении данных? Или это совершенно случайно? –