Միաձուլման տեսակավորում

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Կաղապար:Ներքին ալգորիթմ: Միաձուլման տեսակավորումը O(n log n) համեմատման վրա հիմնված տեսակավորման ալգորիթմ է: Կատարման մեծ մասն արտադրում է ստաբիլ տեսակավորում, որը նշանակում է, որ կատարումը պաշտպանում է մուտքի հրամանը տեսակավորված ելքի հավասար էլեմենտներից: Դա անջատ և նվաճված ալգորիտմ է: Միաձուլումը հայտնաբերվել է 1945 թ-ին Ջոն վոն Նյումանի կողմից:[1] Goldstine [2]

Բովանդակություն

Ալգորիթմ [խմբագրել]

Միաձուլման տեսակավորման օրինակ: Առաջին հերթին բաժանել էջը փոքրագույն մասնիկների, ապա համեմատել յուրաքանչյուր մասնիկ հարակից էջի հետ` տեսակավորելու և միավորելու երկու հարակից էջերը: Արդյունքում բոլոր մասնիկները տեսակավորվում և միավորվում են իրար: Միաձուլումը տեղի է ունենում հետևյալ կերպ՝ 1. Եթե էջի լայնությունը 0 – ից 1 է, այն արդեն տեսակավորված է 2. Բաժանել չտեսակավորված էջը 2 ենթաէջերի՝ կես էջի չափով 3. Տեսակավորել յուրաքանչյուր ենթաէջը ռեկուրսիվ եղանակով առաջարկելով միաձուլում 4. Վերամիավորել 2 ենթաէջերը 1 տեսակավորված էջերի մեջ:

recursively Merge

Միաձուլումը կազմի մեջ է մտցնում 2 հիմնական գաղափարները՝ արդարացնելու իր աշխատաժամանակը: 1. Փոքր էջն ավելի քիչ քայլեր կպահանջի միաձուլման համար, քան մեծ էջը: 2. Քիչ քայլերը նախատեսված են կառուցելու տեսակավորված էջ 2 տեսակավորված և 2 չտեսակավորված էջերից: Օրինակ միայն պետք է հատել յուրաքանչյուր էջը մի անգամ, եթե դրանք արդեն տեսակավորված են: Կիրառենք միաձուլումը տեսակավորելու integer – ների էջ, որը պարունակվում է զանգվածում: Կիրառենք միաձուլումը տեսակավորելու integer – ների էջ։

Ենթադրենք ունենք A զանգված n ինդեքսով, որը դասավորված է A0 – ից An-1: Մենք առաջարկում ենք միաձուլումը A (A0 ... Ac-1 ) և A (Ac... An-1), որտեղ c – ն n/ 2 – ի integer մասն է: Երբ 2 կեսերը վերադարձվում են, դրանք պետք է տեսակավորվեն: Դրանք այժմ կարող են միաձուլվել միմյանց հետ՝ կազմելով տեսակավորված զանգված: An-1_0 to A_{n-1}.

Հասարակ pseudocode ձևում ալգորիտմը կարող է ունենալ հետևյալ տեսքը՝

function merge_sort(m)

    if length(m) ≤ 1
        return m
    var list left, right, result
    var integer middle = length(m) / 2
    for each x in m up to middle
         add x to left
    for each x in m after middle
         add x to right
    left = merge_sort(left)
    right = merge_sort(right)
    result = merge(left, right)
    return result

merge Ֆունկցիան  պահանջում  է  և  աջ  և  ձախ  էջերի  միաձուլում:Այն  ունի  հետևյալ  վարիացիաները՝

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) ≤ first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

Վերլուծություն [խմբագրել]

Կրկնվող միաձուլման ալգորիտմը սովորաբար տեսակավորում է 7 ինթեջեր արժողությամբ զանգված: Միաձուլումն իրականացնելու համար պետք է հետևել հետևյալ քայլերին:

Տեսակավորման n միաձուլվող օբյեկտներն ունեն O(n log n ) – ի ներկայացման միջին և վատագույն դեպքեր:Եթե n լայնության էջի միաձուլման ժամանակը T( n) է, T(n) = 2T(n/2) + n, որը հետևում է ալգորիթմի որոշիչին(առաջարկել սովորական էջի կեսի չափով 2էջի ալգորիթմ և ավելացնել n քայլեր, որոնք վերձված են միաձուլելու արդյունքային 2 էջերը ): Փակ ձևը հետևում է վարպետ թեորեմից: Տեսակավորման n միաձուլվող օբյեկտներն ունեն O(n log n ) – ի ներկայացման միջին և վատագույն դեպքեր: Եթե n լայնության էջի միաձուլման ժամանակը T( n) է վատագույն դեպքի ներկայացում: Վատագույն դեպքում ձեռնարկությունների թվի միաձուլումը հավասար կամ փոքր է ( n ⌈lg n⌉⌉ - 2⌈ lg n⌉+ 1), որը (n lg n- n + 1) - ի և (n lg n + n + O(lg n)) – ի միջև է: Մեծ n- ի և հազվադեպ կարառվող մուտքի էջի համար միաձուլման ենթադրվող միջին համեմատության թիվը ավելի քիչ է մոտեցնում a n, քան վատագույն դեպքում:

Վատագույն դեպքում միաձուլումը կատարում է 39% պակաս համեմատություն, քան արագ տեսակավորումը կատարում է միջինի դեպքում: Սակայն կան հատուկ դեպքեր, երբ նրանք սահմանափակ են, որտեղ միաձուլման վատագույն դեպքը միաժամանակ է ընթանում տեսակավորման լավագույն դեպքի հետ: Շարժման պայմաններում միաձուլման վատագույն դեպքի բաղադրությունը՝ O(n lg n) – ը նույնն է, ինչ որ արագ տեսակավորման դեպքում, և լավագույն դեպքը խլում է կեսը, ինչպես շատ կրկնություններ վատագույն դեպքում: Միաձուլման ռեկուրսիվ կատարումը ստիպում է 2n- 1 մեթոդը վատագույն դեպքում համեմատել արագ տեսակավորման n – ի հետ, չնայած միաձուլումն ունի մոտավորապես 2 անգամ ավել ռեկուրսիվ ավելցուկ, քան արագ տեսակավորումը: Այնուամենայնիվ, միաձուլման կրկնվող ոչ ռեկուրսիվ կատարումները, խուսափելով ավելցուկ կոչվող մեթոդից , դժվար չէ կոդավորել: Միաձուլման ամենատարածված կատարումը չի տեսակավորվում տեղում, դրա համար մուտքի հիշողության ծավալը պետք է առանձնացված լինի տեսակավորված ելքի տեսակավորման համար:

Միաձուլումը, ինչպես նշված է, նույնպես ունի հաճախակի վերահսկողություն, պրակտիկորեն կարևոր է լավագույն դեպքի հատկությունը: Եթե մուտքն արդեն տեսակավորված է, դրա բարդությունն ընկնում է մինչև O(n): Մասնավորապես, n- 1 համեմատությունները և 0 շարժումները ներկայացված են, որը նույնն է, ինչ հասարակ անցումը մուտքով, ստուգելով, արդյոք այն վերատեսակավորված է: Տեղում տեսակավորումը հնարավոր է ( օգտագործելով էջերը զանդվածների փոխարեն), բայց շատ դժվար և պրակտիկայում առաջարկում է փոքր ներկայացման ձեռքբերված նույնիսկ եթե ալգորիթմը տևում է O(n log n) ժամ: Տվյալ դեպքերում ալգորիթմները կուտակված տեսակավորման նման հաճախ առաջարկում են համեմատական արագություն, և պակաս կոմպլեքս են: Պայմանականորեն, չնայած ստանդարտ միաձուլման, տեղում կատարվող միաձուլումը ստաբիլ տեսակի չէ: Հղված էջերի դեպքում ալգորիթմը չի օգտագործում ավել տարածք, քան արդեն էջերի ներկայացման ժամանակ օգտագործված տարածքը, բայց O(log(k)) օգտագործվում է ռեկուրսիվ հետքի ժամանակ:

Միաձուլումն ավելի արդյունավետ է, քան արագ տեսակավորումը որոշ էջերի համար, եթե տեսակավորվող ամսաթիվը կարող է լինել միայն արդյունավետորեն թույլատրված հերթականությամբ և հայտնի Lisp – ի նման լեզուներում, որտեղ հերթականությամբ թույլատրված թվային ստրուկտուրաները շատ նման են: Ի տարբերություն արագ տեսակավորման որոշ( արդյունավետ ) կատարումների, միաձուլումը ստաբիլ տեսակավորում է այնքան ժամանակ, քանի դեռ միաձուլման օպերացիան ճիշտ է կատարված: Միաձուլումը նույնպես ունի որոշ պայմաններ: Դրանցից մեկը նրա 2n դիրքի օգտագործումն է, պայմանական n դիրքերն անհրաժեշտ են, քանի որ հնարավոր չէ տեղում տրամաբանորեն կապել 2 տեսակավորված խմբեր: Բայց չնայած այս տարածքի օգտագործման ալգորիտմը դեռևս շատ աշխատանք է անում: m – ի պարունակությունը առաջին անգամ պատճենվել է միաձուլման յուրաքանչյուր փուլի արդյունքային էջի ձախ կամ աջ մասում: Այդ պատճենման ալտերնատիվն ինֆորմացիայի նոր դաշտը բանալու հետ ասոցիացնելն է (m – ի էլեմենտները կոչվում են բանալիներ): Այս դաշտը կօգտագործվի բանալիները և յուրաքանչյուր կապված ինֆորմացիա իրար հետ կապելու տեսակավորված էջում (բանալին և նրա վերաբերյալ ինֆորմացիան կոչվում է գրառում): Այնուհետև տեսակավորված էջերի միաձուլումը կատարվում է կապի արժեքները փոփոխելով: Ոչ մի գրառում կարիք չկա տեղաշարժել: Դաշտը, որը պարունակում է միայն կապ, հիմնականում փոքր կլինի լիարժեք գրառումից, հետևաբար քիչ տարածք կօգտագործվի: Տարածքի n/2- ից մեկ այլ ալտերնատիվ է դիտարկել աջը և ձախը որպես միասնական ստրուկտուրա, պատճենել m- ի միայն ձախ մասը ժամանակավոր տարածքում և ուղեկցել միաձուլման սահմանված կարգը, տեղադրել միաձուլված արտադրանքը m- ի մեջ: Ավելի լավ է առանձնացնել ժամանակավոր տարածքը միաձուլված սահմանված կարգից դուրս այնպես, որ անհրաժեշտ լինի միայն մեկ առանձնացում: Չափից ավելի պատճենումը, որը պահպանվել է նախորդ պարագրաֆում, նույնպես գործում է, քանի դեռ տողերի վերջին զույգը՝ մինչ ետադարձ արդյունքի պնդումը, չի դարձել գերծավալուն:

Օգտագործումը չափերիզների կրիչների հետ [խմբագրել]

Արտաքին միաձուլումը պրակտիկ է ժապավենի շարժակներն օգտագործել որպես մուտքային և ելքային սարքեր: Այն ունի փոքր հիշողության ծավալ և դա կախված չէ գրառումների թվից:

Այդ նույն պատճառով այն օգտակար է սկավառակի վրա ինֆորմացիայի տեսակավորման համար, որը շատ մեծ է հիմնական հիշողությունում պահելու համար: Եթե ունենք 4 ժապավենի շարժիչներ, դրանք աշխատում են հետևյալ կերպ՝ 1. Կիսել հատվածը և դնել 2 ժապավենների մեջ: 2. Միավորել 2 ժապավենների գրառումների յուրահատուկ մասերը, գրել 2 առանձին գրառում արտադրվող 2 ժապավենների համար: 3. Միավորել 2 արտադրված ժապավենների գրառումները և գրել դրանք օրիգինալ 2 մուտքային ժապավեններին: 4. Կրկնել, մինչև ստանաք մեկ քայլ, որը կպարունակի ամբողջ ժամանակահատվածը, կտարբերակի, որ log n-ն անցել է, որտեղ n-ը գրառումների թիվն է:

Ժապավենների վրա արդեն տեսակավորված ժամանակահատվածի համար տարածված է բնական միաձուլում տարբերակը: Վատագույն դեպքում այն արտացոլում է այն, ինչ ներսում է, այն միավորում է առանձնահատուկ գրառումները 2 գրառումների ցուցակի մեջ, այնուհետև 2- ը՝ 4- ի մեջ, և այլն: Լավագույն դեպքում այն միավորում է լայնածավալ, արդեն տեսակավորված ցուցակներն ավելի ծավալուն ցուցակների մեջ, հուսալիորեն ավարտելով ավելի քիչ ժամանակում, քան log n- ն է անցնում: Պարզագույն pseudocode ձևում բնական միաձուլման տեսակավորման ալգորիթմն ունի հետևյալ տեսքը`

 # Original data is on the input tape; the other tapes are blank
 function merge_sort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
     while any records remain on the input_tape
         while any records remain on the input_tape
             merge( input_tape, output_tape, scratch_tape_C)
             merge( input_tape, output_tape, scratch_tape_D)
         while any records remain on C or D
             merge( scratch_tape_C, scratch_tape_D, output_tape)
             merge( scratch_tape_C, scratch_tape_D, input_tape)

 # take the next sorted run from the input tapes, and merge into the single given output_tape.
 # tapes are scanned linearly.
 # tape[next] gives the record currently under the read head of that tape.
 # tape[current] gives the record previously under the read head of that tape.
 # (Generally both tape[current] and tape[previous] are buffered in RAM ...)
 function merge(left[], right[], output_tape[])
     do
        if left[current] ≤ right[current]
            append left[current] to output_tape
            read next record from left tape
        else
            append right[current] to output_tape
            read next record from right tape
    while left[current] < left[next] and right[current] < right[next]
    if left[current] < left[next]
        append current_left_record to output_tape
    if right[current] < right[next]
        append current_right_record to output_tape
    return

Օպտիմալացվող միաձուլման տեսակավորում [խմբագրել]

Ժամանակակից համակարգիչներում առնչության լոկալացումը կարող է հսկայական կարևորություն ունենալ թեթև արդյունաբերության մեջ, քանի որ օգտագործվում են հիերարխիկ հիշողություններ: Միաձուլման ալգորիթմի Cache տարբերակը, որի գործողությունները հատուկ ընտրված են էջերի շարժման մինիմիզացման համար մեքենայի Cache հիշողության ներսում և դրսում, առաջարկված են: Օրինակ tiled միաձուլման ալգորիթմը դադարեցրեց ենթազանգվածների մասնակցությունը, երբ S չափի ենթազանգվածները նվաճված են, որտեղ S- ը ժամանակահատվածի թիվն է, որը զբաղեցնում է CPU- ի cache- ը: Այս ենթազանգվածներից յուրաքանչյուրն ընտրված է տեղում տեսակավորմամբ, խափանել հիշողության փոխանակումները և նորմալ միաձուլումն ավարտվում է ստանդարտ ռեկուրսիվ ձևով: Այս ալգորիթմն ունեցել է ավելի լավ ազդեցություն մեքենաների վրա: Քրոնռոդն առաջարկել է միաձուլման ալտերնատիվ միջոց, որն օգտագործում է միայն իր համար նախատեսված տարածքը:

Զուգահեռ գործընթաց [խմբագրել]

[3] Միաձուլումը լավ համընկնում է բաժանիր և տիրիր մեթոդի հետ: Զուգահեռ կատարումը ցույց է տրված pseudocode- ում: Այս ալգորիթմ օգտագործվում է զուգահեռ միաձուլման ալգորիթմը զանգվածի ռեկուրսիվ բաժանումը ոչ միայն զուգորդման, այլև միաձուլման գործընթացում: insertion sort,[4]

Համեմատումն այլ տեսակավորման ալգորիթմների հետ [խմբագրել]

Չնայած կուտակված տեսակավորումն ունի միևնույն ժամանակի ծախսը, ինչ միաձուլումը, այն ծախսում է միայն Θ(1) օժանդակ տարածք միաձուլման Θ(n)- ի փոխարեն, և հաճախ ավելի արագ է պրակտիկ կիրառման ժամանակ: Տիպիկ ժամանակակից կառույցներում արդյունավետ արագ տեսակավորման գործընթացը հիմնականում չեն ներկայացնում միաձուլումը RAM – ի վրա հիմնված զանգվածների տեսակավորման համար: Մյուս կողմից միաձուլումը ստաբիլ տեսակ է և ավելի արդյունավետ է: Միաձուլումը հաճախ լավագույն տարբերակն է կապված էջը տեսակավորելու համար:heapsort. quicksort[փա՞ստ]linked list։

Utility- ն օնլայն տեսակավորման մեջ [խմբագրել]

Միաձուլման գործընթացն օգտակար է online տեսակավորման համար, որտեղ էջը տեսակավորելու համար սկզբում ստանում է կտոր ժամանակին, ամբողջի փոխարեն: Այս ապլիկացիայում մենք տեսակավորում ենք յուրաքանչյուր նոր տեսակավորման ալգորիթմների օգտագործումից ստացված կտոր, և միացնում այն տեսակավորված էջին՝ օգտագործելով միացման գործընթացը: algorithm|online.

Նշումներ [խմբագրել]

  1. ↑ Կաղապար:Harvtxt
  2. ↑ Jyrki Katajainen and Jesper Larsson TrՊff (1997). A meticulous analysis of mergesort programs. 
  3. ↑ Cormen, Thomas; Leiserson, Charles; Stein, Ronald, Introduction to Algorithms=Third Edition, MIT Press and McGraw-Hill, 2009 .
  4. ↑ [http։//drdobbs.com/high-performance-computing/229400239 V. J. Duvanenko, "Parallel Merge Sort", Dr. Dobb's Journal, March 2011]

Կարծիքներ [խմբագրել]

Արտաքին կապեր [խմբագրել]

Վիքիդարանի պատկերանիշը
Անգլերեն Վիքիդարանում կան նյութեր այս թեմայով՝
Sorting/Merge_sort
Ստացված է «http://hy.wikipedia.org/w/index.php?title=Միաձուլման_տեսակավորում&oldid=1173376» էջից