Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?

Вот здесь рабочий параллельный quicksort? Есть мнение, что оно не рабочее...

Здравствуйте, sysenter, Вы писали:

S>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?

Здесь

Автор: Димчанский
Дата: 10.11.10

я выкладывал один из вариантов параллельной быстрой сортировки.

Здравствуйте, Димчанский, Вы писали:

Д>Здравствуйте, sysenter, Вы писали:

S>>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?

Д>Здесь

Автор: Димчанский
Дата: 10.11.10

я выкладывал один из вариантов параллельной быстрой сортировки.

а тут

Автор: Sergey Chadov
Дата: 01.10.09

я выкладывал другой

Здравствуйте, sysenter, Вы писали:

S>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?
S>Вот здесь рабочий параллельный quicksort? Есть мнение, что оно не рабочее...

Это комбинация qsort и merge sort. На больших объемах (сотни миллионов) срабатывает хорошо, направление мысли верное. На малых — не стоит игра свечь. Мне удавалось заливать весь GenBank в BerkleyDB за 4 часа (да, с предварительной сортировкой по 10 разным критериям), а на Оракле для этого требовалась неделя. Позже я похожий метод применял для вычислительной химии, где уже миллиарды компаундов. Единственный недостаток qsort — non-stable, то есть одинаковые элементы может поменять местами. В остальном — восхитительный метод сортировки, если его грамотно применять. Ну и плюс финальный merge sort с десятками файлов по пол-гига.

Здравствуйте, sysenter, Вы писали:

S>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?

Если потом сливать в один массив это mergesort.

Идея qsort очень простая разбить задачу на несколько эквивалентных и для них сделать тоже самое. В класическом варианте массив разбивают на две части (partitioning). Что мешает разбивать на несколько частей и параллелить именно этот процесс.

Здравствуйте, sysenter, Вы писали:

S>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?

S>Вот здесь рабочий параллельный quicksort? Есть мнение, что оно не рабочее...

В принципе, должна быть рабочей. В крайнем случае свое написать дело одного часа. Вот только на GPU плохо ложиться, там какой-нить битоник лучше

http://youtube.com/watch?v=qeN6PCK5rRM

S>>Вот здесь рабочий параллельный quicksort? Есть мнение, что оно не рабочее...

M>В принципе, должна быть рабочей. В крайнем случае свое написать дело одного часа. Вот только на GPU плохо ложиться, там какой-нить битоник лучше

на GPU radix sort рулит

Здравствуйте, Lepsik, Вы писали:

L>на GPU radix sort рулит

Рулит безусловно. Единственная проблема — сделать этот radix. Можно попробовать radix, но надо сделать, чтобы он работал. Когда критерии отличаются на миллиарды миллиардов, извините, не катит. Необходима децимация, потом досортировка на GPU. Все дело в объемах. Но можно и наоборот, думайте.