IPB
ЛогинПароль:

2 страниц V < 1 2  
 Ответить  Открыть новую тему 
> Алгоритмы пузырьковой сортировки
TarasBer
сообщение 28.06.2011 15:58
Сообщение #21


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


То есть у тебя получился ЛИНЕЙНЫЙ рост времени? Забавно. Думаю, дело в погрешности измерений.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Account
сообщение 28.06.2011 20:31
Сообщение #22


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

Репутация: -  0  +


Цитата(TarasBer @ 28.06.2011 16:58) *

То есть у тебя получился ЛИНЕЙНЫЙ рост времени? Забавно. Думаю, дело в погрешности измерений.


Это только по алгоритму расческой по астольным все путем
Код
        Последов.  Чет-нечет     Шейкер    Расчёской
5000     0.235000    0.235000    0.313000    0.000000
10000    0.782000    0.704000    1.047000    0.000000
20000    2.906000    2.640000    3.953000    0.016000
30000    6.484000    5.828000    8.719000    0.015000
40000    11.515000    10.234000    15.453000    0.016000
50000    17.844000    16.485000    23.906000    0.016000
100000    75.140000    68.063000    97.125000    0.062000


код всех применяемых сортировок и рабочей проги в одном из ранних постов, сам алгоритм расчески брался с американской вики, по ссылки предоставленой IUnknown, там называется Comb sort. Алгоритм работает нормально, проверял на малых количествах чисел. Так что да же не знаю что тут сказать. Дело думается не в погрешности.

Сообщение отредактировано: Account - 28.06.2011 20:38
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
IUnknown
сообщение 28.06.2011 21:13
Сообщение #23


a.k.a. volvo877
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской

Репутация: -  627  +


Цитата
погонял сортировку алгоритмом расческой, так на моем ноуте Dual-Core 2.1 GHz . 2 гига ОЗУ, 100000 элементов сортирует показывает за 0.062 с. 30000000 примерно за 21 секунду.
Это реально? Просто что то сомнения гложат в этом направлении.
Это реально. В одном из описаний алгоритма встречал вот такое:

Цитата
"Пузырек" сортирует 10К элементов за 1.36 сек, тогда как "Расческа" - те же 10К элементов сортирует всего за 0.0042 сек., всего на 10% дольше, чем стандартный С-шный qiucksort(). Удивительно, что такое небольшое изменение алгоритма "пузырька" приводит к результатам, сравнимым с QuickSort. Более того, "Расческа" не требует никаких специальных действий для того, чтобы исключить потерю времени при обработке уже упорядоченных последовательностей.
Так что не сомневайся, это действительно очень быстрый метод...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Account
сообщение 28.06.2011 21:30
Сообщение #24


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

Репутация: -  0  +


Цитата(IUnknown @ 28.06.2011 22:13) *


Так что не сомневайся, это действительно очень быстрый метод...


Спасибо, а то что то меня это напрягало...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Account
сообщение 29.06.2011 17:41
Сообщение #25


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

Репутация: -  0  +


IUnknown, случаем не знаешь иностранных ресурсов(в наших путного не нашел ничего), где можно посмотреть графическое ( в виде графиков) отражение трудоемкости методов сортировки и их алгоритмов?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
IUnknown
сообщение 29.06.2011 17:55
Сообщение #26


a.k.a. volvo877
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской

Репутация: -  627  +


У меня где-то был даже PDF, в котором сведены графики для некоторых алгоритмов сортировок (именно в параллельном варианте), вечером поищу...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Account
сообщение 29.06.2011 19:57
Сообщение #27


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

Репутация: -  0  +


IUnknown, заранее благодарю.
Еще вопрос такой. Ранее ты (если лучше на Вы, то скажи) давал ссылку на вот этот код. не пойму вот что где тут цикл ,ведь по сути дела не один раз ведь нужно пройтись по четным и нечетным процессам или процессорам. Вижу только один раз сортировку(локальную), которая выполняется я так понимаю на всех узлах
qsort(elmnts, nlocal, sizeof(int), IncOrder); 


Далее я так понимаю код для распределения данных между процессами
for (i=0; i<npes-1; i++) { 
58 if (i%2 == 1) /* Odd phase */
59 MPI_Sendrecv(elmnts, nlocal, MPI_INT, oddrank, 1, relmnts,
60 nlocal, MPI_INT, oddrank, 1, MPI_COMM_WORLD, &status);
61 else /* Even phase */
62 MPI_Sendrecv(elmnts, nlocal, MPI_INT, evenrank, 1, relmnts,
63 nlocal, MPI_INT, evenrank, 1, MPI_COMM_WORLD, &status);

потом объединение и разбиение снова, но ведь это все не один раз должно произойти?
А то надо блок схему чертить, а я что то не догоню.

Сообщение отредактировано: Account - 29.06.2011 19:59
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
IUnknown
сообщение 29.06.2011 21:06
Сообщение #28


a.k.a. volvo877
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской

Репутация: -  627  +


Цитата
Далее я так понимаю код для распределения данных между процессами
Неправильно понимаешь. Это не код основного приложения. Это код, выполняющийся на каждом ядре. То есть, на каждом ядре сначала выполняется сортировка локальных данных, а потом начинается цикл, в течении которого это ядро связывается с соседними и обменивается с ними информацией, после чего полученную от соседа информацию совмещает (это CompareSplit) со своей локальной (это тоже сортировка, я ж показывал тебе выше, что таким образом совокупность elmnts + relmnts поддерживается в упорядоченном состоянии). В итоге каждое ядро содержит свою порцию данных, которые при объединении дают отсортированный массив.

Цитата
ведь это все не один раз должно произойти?
Угу. Полная сортировка - один раз, перед началом процесса. А потом - доупорядочивание с учетом данных, полученных по обмену с соседним процессом - в цикле. Причем, учитывая, что соседний процесс также получает данные из текущего (MPI_Sendrecv пересылает информацию в обе стороны: текущий elmnts -> соседний relmnts, и соседний elmnts -> текущий relmnts) - картинка складывается...

Для полноты картины не хватает пересылки порции реального массива в каждый процесс, и потом - объединения всех данных обратно в один массив-результат. Но я, к сожалению, MPI не очень хорошо владею, что называется, "читаю", но не пишу, поэтому добавить это не смогу...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Account
сообщение 29.06.2011 22:15
Сообщение #29


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

Репутация: -  0  +


А количесвто пересылок, выражается трудоемкостью алгоритма чет-нечет(n в квадрате) ?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
IUnknown
сообщение 29.06.2011 22:45
Сообщение #30


a.k.a. volvo877
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской

Репутация: -  627  +


Каждый процесс посылает свою часть данных всем остальным процессам, и получает в ответ их данные. Это было не совсем верно: каждый с каждым не взаимодействует, скажем, если работают 6 процессов - то смысла связывать 2 и 5-ый нет: второй связывается только с теми, с кем он граничит, т.е., с 1-ым и с 3-им. Также, как пятый - только с 4-ым и с 6-ым. Но вот эти действия повторяются по количеству запущенных процессов, чтобы изменения в старших процессах (тех, которые контролируют максимальные индексы исходного массива) через промежуточные процессы достигли младших (контролирующих минимальные индексы), и наоборот. То есть, количество пересылок зависит от количества параллельно выполняемых процессов.

Вот тут лежит PDF (165 Кб, англ.), о котором я говорил. Пока больше ничего вменяемого не нашлось.

Сообщение отредактировано: IUnknown - 30.06.2011 2:02
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Account
сообщение 29.06.2011 23:14
Сообщение #31


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

Репутация: -  0  +


IUnknown, огромное тебе спасибо за все. Очень помог.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Account
сообщение 29.06.2011 23:36
Сообщение #32


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

Репутация: -  0  +


Кстати, а вот с какого процесса начинается объединение блоков и их разделение.
например если если заполнить массив к убыванию 24 23 22 21 и так далее, а отсортировать естественно по возрастанию. Допустим имеем 24 числа, и 4 процессора. каждому по 6 чисел, 1 и 4 процессоры могут только взаимодействовать с 2 и 3 соответственно, тогда как 2 и 3 как с друг другом так и с ними, получается что будет 6 операций объединений и разделений или нет?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
IUnknown
сообщение 30.06.2011 2:11
Сообщение #33


a.k.a. volvo877
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской

Репутация: -  627  +


Во-первых, я чуть-чуть поправил свой предыдущий пост, см. выше.

Теперь касаемо твоего вопроса: да, будет 6 сообщений между процессами. И 12 пересортировок (после каждого обмена сообщениями каждый процесс пересортировывает данные у себя). Вот, я прогнал тут свой код на этих данных (добавил служебные сообщения, кто кому что передал и кто от кого что получил):

Array :
24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
ID = 0 Even_Rank = 1 Accepted_From = 1
ID = 2 Even_Rank = 3 Accepted_From = 3
Sorter : ID = 0 Accepted_From = 1
Sorter : ID = 2 Accepted_From = 3
Sorter : ID = 1 Accepted_From = 0
Sorter : ID = 0 Accepted_From = -1
Sorter : ID = 3 Accepted_From = 2
ID = 1 Odd_Rank = 2 Accepted_From = 2
Sorter : ID = 2 Accepted_From = 1
Sorter : ID = 1 Accepted_From = 2
Sorter : ID = 3 Accepted_From = -1
ID = 0 Even_Rank = 1 Accepted_From = 1
Sorter : ID = 0 Accepted_From = 1
ID = 2 Even_Rank = 3 Accepted_From = 3
Sorter : ID = 0 Accepted_From = -1
Sorter : ID = 1 Accepted_From = 0
Sorter : ID = 2 Accepted_From = 3
Sorter : ID = 3 Accepted_From = 2
ID = 2 Odd_Rank = 1 Accepted_From = 1
Sorter : ID = 2 Accepted_From = 1
Sorter : ID = 1 Accepted_From = 2
Sorter : ID = 3 Accepted_From = -1
Result :
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24


При получении от (-1) пересортировки не производится, потому что фактически не было изменения данных, (-1) у меня - аналог MPI_PROC_NULL, так что его можно не считать. Остальных Sorter-ов ровно 12 штук. С какого процесса всё начинается - это без разницы: все процессы начинают работать одновременно, и пары процессов пересылают сообщения друг другу тоже одновременно (если ты запускаешь программу на машине с достаточным количеством ядер/процессоров).

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Account
сообщение 30.06.2011 2:28
Сообщение #34


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

Репутация: -  0  +


Еще раз спасибо, разжевал и в рот положил можно сказать, теперь все ясно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V < 1 2
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 28.03.2024 22:12
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"