Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?
Вот здесь рабочий параллельный quicksort? Есть мнение, что оно не рабочее...
Здравствуйте, sysenter, Вы писали:
S>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?
Здравствуйте, Димчанский, Вы писали:
Д>Здравствуйте, sysenter, Вы писали:
S>>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?
Д>Здесь
Здравствуйте, sysenter, Вы писали:
S>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort? S>Вот здесь рабочий параллельный quicksort? Есть мнение, что оно не рабочее...
Это комбинация qsort и merge sort. На больших объемах (сотни миллионов) срабатывает хорошо, направление мысли верное. На малых — не стоит игра свечь. Мне удавалось заливать весь GenBank в BerkleyDB за 4 часа (да, с предварительной сортировкой по 10 разным критериям), а на Оракле для этого требовалась неделя. Позже я похожий метод применял для вычислительной химии, где уже миллиарды компаундов. Единственный недостаток qsort — non-stable, то есть одинаковые элементы может поменять местами. В остальном — восхитительный метод сортировки, если его грамотно применять. Ну и плюс финальный merge sort с десятками файлов по пол-гига.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: Паралельный quicksort
От:
Аноним
Дата:
23.08.13 21:44
Оценка:
Здравствуйте, sysenter, Вы писали:
S>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?
Если потом сливать в один массив это mergesort.
Идея qsort очень простая разбить задачу на несколько эквивалентных и для них сделать тоже самое. В класическом варианте массив разбивают на две части (partitioning). Что мешает разбивать на несколько частей и параллелить именно этот процесс.
Здравствуйте, sysenter, Вы писали:
S>Если порубить массив значений на куски равные количеству логических процессоров и отсортировать эти куски с помощью quicksort в таком же количестве потоков и после слить в один массив, это всё ещё будет quicksort?
S>Вот здесь рабочий параллельный quicksort? Есть мнение, что оно не рабочее...
В принципе, должна быть рабочей. В крайнем случае свое написать дело одного часа. Вот только на GPU плохо ложиться, там какой-нить битоник лучше
S>>Вот здесь рабочий параллельный quicksort? Есть мнение, что оно не рабочее...
M>В принципе, должна быть рабочей. В крайнем случае свое написать дело одного часа. Вот только на GPU плохо ложиться, там какой-нить битоник лучше
Здравствуйте, Lepsik, Вы писали:
L>на GPU radix sort рулит
Рулит безусловно. Единственная проблема — сделать этот radix. Можно попробовать radix, но надо сделать, чтобы он работал. Когда критерии отличаются на миллиарды миллиардов, извините, не катит. Необходима децимация, потом досортировка на GPU. Все дело в объемах. Но можно и наоборот, думайте.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
