Лекция. Параллель алгоритмдер

Берілген тараудағы 1-бөлімінде біз әртүрлі сұрыптау алгоритмдерін қарастырамыз:

1. 
   Аттап өту сұрыптамасы (ранг әдісі)
   
2. 
   Салыстыру және ауыстыру сұрыптау алгоритмі.
   

● Көпірші әдісмен сұрыптау және «тақ-жұп» сұрыптау.

● Бірігу сұрыптауы

● Жылдам сұрыптау

екінші бөлімде – параллельдеудің сандық әдістері: матрицаларды көбейту; сызықтық теңдеулер жүйесін шешудің тура және итерациялық әдістері.

5.1. Ранг әдісімен сұрыптау

сұрыптаудың бұл түрінің екінші атауы – аттап өту сұрыптауы. (Wilkinson6 B. and Allen6 M., 1999). Бұл сұрыптаудың негізгі идеясы: берілген сандардың ішінен таңдалғаннан аз сандарды санаймыз. Бұл санау тізімдегі таңдалған санның позиция нөмерін қамтамасыз етеді, яғни тізімдегі оның «рангін» табамыз.

a[0],a[1],…, a[n-1] массивіндегі сақталған n саны берілген деп есептейік. Ал нәтижелері сұрыпталған b[0], b[1], … , b[n-1] массивінде сақталған. Тізбекті коды келесі түрде сипатталуы мүмкін.
For (i=0; i

{

x=0

If (a[i]>a[j]) x++;

B[x]=a[i]; // копирует номер в провильное место

}

Сұрақ: Қандай жағдайда берілген код сәтсіз болады? Талданған жағдайды ескере отырып программа жаз.

Осы кодты n процессор үшін қайта жазуға тырысамыз.

n процессор бар деп есептейік. Әрбір процессор бір санға бекітілген. Бұл жағдайда әрбір процессор сандардың біреуінің соңғы индексін О(n) қадамға яғни time complexity=O(n) табу.

Мұнда біз forall операторын қолданамыз, мұндағы i-процессор нөмері.

Forall (i=0; i

{x=0;

for (j=0; ja[j]) x++;

b[x]=a[i];

}
көптеген программаларда, дербес жағдайда, сұрыптау орындайтын программада ағымдағы сандарды уақытша қажетті қосымша айнымалыға орын бөлінеді, келешекте басқа санмен позициясын алмастыруды жүзеге асыратын әдістеме қарастырылады.

Төмендегі осы уақытша айнымалыларды қолданбайтын әдісті қарастырамыз.

жүктеу/скачать 0,76 Mb.

Достарыңызбен бөлісу: