Алгоритмы пузырьковой сортировки |
Алгоритмы пузырьковой сортировки |
Account |
23.06.2011 17:39
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
Итак, все знают что есть такой вид сортировки, как пузырьковая. Меня интересует какие еще есть алгоритмы в этом виде сортировки кроме: последовательного и чет-нечетной перестановки? И если есть информация о них поделиться ей, если не жалко.
|
IUnknown |
23.06.2011 20:04
Сообщение
#2
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Odd-Even Sort (так называемая "параллельная пузырьковая") интересует? Или ты ее и называешь чет-нечетной перестановкой? Сортировка расческой (вроде как тоже усовершенствование пузырька)?
|
Account |
23.06.2011 21:18
Сообщение
#3
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
Первая, действительно чет-нечет, а вот вторую не видел, спасибо. Нашел еще шейкер-сортировку
Просто нужно для курсового проекта рассмотреть варианты алгоритмов пузырьковой ,выбрать наилучший по трудоемкости для дальнейшего распараллеливания вычисления данным алгоритмом))) |
Account |
23.06.2011 21:55
Сообщение
#4
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
Сортировка расческой (вроде как тоже усовершенствование пузырька) - что-то у меня она прооигрывает обычной сортировке. Вот как сделал
void combsort( double *pData, int DataSize ) Сообщение отредактировано: Account - 23.06.2011 21:55 |
IUnknown |
23.06.2011 22:18
Сообщение
#5
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Ты б лучше обе реализации привел, чтоб сравнить можно было... Лучше всего - целиком программу, которая показывает, где больше, а где - меньше времени. А то так знаешь, все может зависеть от многих факторов...
P.S. Вот тут лежит реализация "расчески на С", на кой велосипед придумывать опять? Сообщение отредактировано: IUnknown - 23.06.2011 22:19 |
Account |
23.06.2011 22:48
Сообщение
#6
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
IUnknown, велосипед не придумывал выдернул код представленный с первой твоей ссылки))), но он оказался медленнее представленного тобой по последней ссылке.Походу по первой не совсем верный алгоритм.
Вот прога целиком #include <cstdlib> еще надо будет добавить чет-нечет Дальше дело за малым, прогон на проверку каждого алгоритма. Сообщение отредактировано: Account - 23.06.2011 22:51 |
IUnknown |
23.06.2011 23:09
Сообщение
#7
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата Походу по первой не совсем верный алгоритм. Это надо сказать спасибо переводчикам Википедии. Вот именно поэтому я и предпочитаю работать с англоязычными источниками.Цитата Дальше дело за малым, прогон на проверку каждого алгоритма. Не понял. То есть, ты считаешь, что если какая-то из написанных тобой функций будет быстрее без распараллеливания, то и при параллельном выполнении тоже она же будет быстрее? Наивный такой Ты сначала сделай параллельные версии всех этих методов, а потом сравнивай. На 2-х ядрах, на 4-х и на 8 (если есть - еще и на большем количестве). Результаты тебя заставят удивиться, я думаю...Сообщение отредактировано: IUnknown - 23.06.2011 23:09 |
Account |
23.06.2011 23:27
Сообщение
#8
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
Это надо сказать спасибо переводчикам Википедии. Вот именно поэтому я и предпочитаю работать с англоязычными источниками. Не понял. То есть, ты считаешь, что если какая-то из написанных тобой функций будет быстрее без распараллеливания, то и при параллельном выполнении тоже она же будет быстрее? Наивный такой Ты сначала сделай параллельные версии всех этих методов, а потом сравнивай. На 2-х ядрах, на 4-х и на 8 (если есть - еще и на большем количестве). Результаты тебя заставят удивиться, я думаю... Я не считаю что она будет быстрее))) Просто с видом сортировки как бы определилось, а вот алгоритм нужно выбрать по наименьшей трудоемкости, но опять же каждый алгоритм по разному ведет себя при разных объемах сортируемых данных, т.е. нужно построить график зависимости от кол-ва элементов ко времени, и уже отсюда плясать. Так как например грубо говоря дана задача отсортировать 100000 элементов. допустим прогоним эти алгоритмы, посмотрим результат. Для примеру допустим среднее от всех результатов алгоритмов 20 минут. Ставим задачу отсортировать за 4 минуты. т.е. создать кластер из подобных машин, на которй ставиться эксперимент, расчитать кол-во узлов кластера. Это все естетсвенно теоретически насчет вычислений параллельных, так как высчитать негде и нужно MPI изучать для реализации. курсовой проект такой дали. |
Account |
23.06.2011 23:51
Сообщение
#9
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
Добавил чет-нечет и проводил эксперимент на сортировку 25000 элементов. Комбинированная всех уделала, разница во времени просто обалдеть можно.
|
Account |
26.06.2011 15:36
Сообщение
#10
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
Никак до конца не пойму применения чет-нечет алгоритма для параллельной обработки.
1 - сортировка на всех узлах 2-обмен соседних узлов (Везде приводиться один и тот же пример причем после 2 пункта в соседних процессах хранятся уже упорядоченный данные, а не просто обмененные.) вот второй пункт не до конца понимаю, нигде в подробностях не описано. Как я понял, это объединения данных соседних узлов, сортировка этого объединенного массива и разбиение опять на две части. Правильно ли я понимаю и где можно почитать в подробностях данного параллельного алгоритма? Сообщение отредактировано: Account - 26.06.2011 15:41 |
IUnknown |
26.06.2011 18:05
Сообщение
#11
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Вот по этому разобраться сможешь?
|
Account |
26.06.2011 22:13
Сообщение
#12
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
Основа понятна вот этот участок не очень особенно по распределению элементов
/* This is the CompareSplit function */ Сообщение отредактировано: Account - 26.06.2011 22:14 |
IUnknown |
27.06.2011 13:38
Сообщение
#13
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
if (keepsmall) { /* Keep the nlocal smaller elements */ |
Account |
27.06.2011 20:50
Сообщение
#14
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
if (keepsmall) { /* Keep the nlocal smaller elements */ Правильно ли я понимаю, что wspace[i--]//<---совокупность и elmnts и relmnts и по сути из него выбирается опять же методом сравнения(как по твоему, если бы отсортировать его и потом просто делить, привело бы к уменьшению времени выполнения данного кода ?) Сообщение отредактировано: Account - 27.06.2011 20:51 |
IUnknown |
28.06.2011 11:13
Сообщение
#15
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата как по твоему, если бы отсортировать его и потом просто делить, привело бы к уменьшению времени выполнения данного кода ? С использованием MPI проверить нет возможности, а вот используя встроенную многозадачность Ады - проверил. Ночью запустил несколько тестов (все одно дежурил, делать особо нечего было, скучно ), для 4, 8, 16 и 32-х процессов с разным количеством элементов (для простоты - кол-во элементов кратное кол-ву процессов, как и в программе по ссылке). Разницы в скорости выполнения не обнаружил. Т.е, что с CompareSplit, что с готовой сортировкой - одинаково. Это, учти, при том, что у меня есть возможность не копировать поэлементно два массива в один, а воспользоваться Array Slices, и обратно - то же самое, просто взять и вернуть часть массива, тебе же в Сях придется копировать в цикле. Можешь еще и потерять в скорости... |
TarasBer |
28.06.2011 11:38
Сообщение
#16
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
В Сях можно явно передавать то, что Ада передаёт неявно - т.е. указатель на начало и границы подмассива.
Многозадачность на скольки ядрах смотрел? -------------------- |
IUnknown |
28.06.2011 11:54
Сообщение
#17
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата Многозадачность на скольки ядрах смотрел? 16-ть процессоров, 8 ядер на каждом... 128, получается...Цитата В Сях можно явно передавать то, что Ада передаёт неявно - т.е. указатель на начало и границы подмассива. Смотри:Array_Size : constant Integer := Total_Elements / Processes_Count;Сможешь написать аналог на С без потерь на копирование? |
TarasBer |
28.06.2011 13:33
Сообщение
#18
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Я так понял, тут фишка в том, что velmnts и vrelmnts могут храниться в совсем разных областях памяти и всё равно компилятор умеет убирать копирование?
Ну грубо говоря, можно написать класс "располовиненный массив" с перегруженным оператором []. Правда, это уже не совсем чистый Си, но на Си принцип тот же. А вообще, чё там Си, да хоть на ассемблере. Дизассембелирую твой код и посмотрю. Другое дело, что одна и та же конструкция языка высокого уровня может в зависимости от контекста скомпилироваться в принципиально разные вещи. То есть если переписать этот пример на Си именно для располовиненного массива, то алгоритм пузырька изуродуется до неузнаваемости, и если мне понадобится подредактировать уже изуродованный алгоритм, то я тупо задолбаюсь. А если это "уродование" делает компилятор, сохраняя исходник в чистоте, то всё в порядке. Я вот что не пойму. Ты хочешь сказать, что твой компилятор умеет анализировать всё, что будет делаться над массивом и сделать вывод о том, что его вообще есть смысл хранить по частям (отдельные половинки в разных областях памяти)? Что-то я не заметил у ГНАТа высокий уровень интеллекта (я даже не смог заставить заменить вызов функции подсчёта суммы элементов константного массива на значение). Или я не заметил какой-то простой нюанс? Или у тебя не ГНАТ, а коммерческий мегакомпилятор? -------------------- |
IUnknown |
28.06.2011 14:28
Сообщение
#19
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата Я вот что не пойму. Ты хочешь сказать, что твой компилятор умеет анализировать всё, что будет делаться над массивом и сделать вывод о том, что его вообще есть смысл хранить по частям (отдельные половинки в разных областях памяти)? <...> Или у тебя не ГНАТ, а коммерческий мегакомпилятор? Я ничего не хочу сказать, я констатирую факт: если я вызываю вместо CompareSplit готовую функцию сортировки - это фактически не влияет на скорость выполнения задачи. Как буду дежурить опять - попробую погонять для очень больших значений Total_Elements, может, там что прояснится. Да, разумеется, используется GNAT Pro (другого здесь просто нет) и, разумеется, не под Windows. |
Account |
28.06.2011 15:05
Сообщение
#20
|
Бывалый Группа: Пользователи Сообщений: 212 Пол: Мужской Репутация: 0 |
Вот что меня еще смущает , погонял сортировку алгоритмом расческой, так на моем ноуте Dual-Core 2.1 GHz . 2 гига ОЗУ, 100000 элементов сортирует показывает за 0.062 с. 30000000 примерно за 21 секунду.
Это реально? Просто что то сомнения гложат в этом направлении. а так еще надумал что тогда при таких результатах можно для распараллеливания использовать чет-нечет алгоритм, а для сортировки на узлах расческой. |
Текстовая версия | 16.11.2024 10:25 |