Տեղի է ունեցել մի քանի օր առաջ . JUG.ru խմբի տղաները հրավիրեցին երազանքի խոսնակներին (Լեսլի Լեմպորտ! Քլիֆ Քլիֆ! Մարտին Քլեպման!) և երկու օր նվիրեցին բաշխված համակարգերին և հաշվողական աշխատանքին: Կոնտուրը համաժողովի երեք գործընկերներից մեկն էր։ Մենք խոսեցինք տաղավարում, խոսեցինք մեր բաշխված պահեստի մասին, խաղացինք բինգո և լուծեցինք գլուխկոտրուկներ:
Սա գրառում է Կոնթուրի ստենդի առաջադրանքների վերլուծությամբ իրենց տեքստի հեղինակից: Ո՞վ էր Հիդրայի վրա, սա ձեր պատճառն է հիշելու հաճելի փորձը, ով ոչ, ձեր ուղեղը ձգելու հնարավորություն մեծ Ո- նշում.
Անգամ կային մասնակիցներ, ովքեր ապամոնտաժեցին ֆլիպչարտը սլայդների՝ իրենց որոշումը գրելու համար: Չեմ կատակում, ստուգման համար հանձնեցին թղթի այս կույտը.
Ընդհանուր առմամբ երեք առաջադրանք կար.
- բեռի հավասարակշռման համար կշիռներով կրկնօրինակներ ընտրելու մասին
- հարցումների արդյունքները հիշողության տվյալների բազայի հետ դասավորելու մասին
- օղակաձեւ տոպոլոգիայով բաշխված համակարգում վիճակի փոխանցման մասին
Առաջադրանք 1. ClusterClient
Անհրաժեշտ էր առաջարկել բաշխված համակարգի N կշռված կրկնօրինակներից K-ի արդյունավետ ընտրության ալգորիթմ.
Ձեր թիմին հանձնարարված է մշակել հաճախորդի գրադարան N հանգույցների զանգվածային բաշխված կլաստերի համար: Գրադարանը կհետևեր հանգույցների հետ կապված տարբեր մետատվյալներին (օրինակ՝ դրանց ուշացումները, 4xx/5xx պատասխանների արագությունը և այլն) և նրանց կհատկացնի W1..WN լողացող կետի կշիռները: Համաժամանակյա կատարման ռազմավարությունն աջակցելու համար գրադարանը պետք է կարողանա պատահականորեն ընտրել N հանգույցներից K-ը՝ ընտրվելու հնարավորությունը պետք է համաչափ լինի հանգույցի քաշին:
Առաջարկեք ալգորիթմ՝ հանգույցներն արդյունավետ ընտրելու համար: Գնահատեք դրա հաշվողական բարդությունը՝ օգտագործելով մեծ O նշում:
Ինչու՞ ամեն ինչ անգլերեն է:
Որովհետև այս ձևով համաժողովի մասնակիցները կռվեցին նրանց հետ և որովհետև անգլերենը Հիդրայի պաշտոնական լեզուն էր: Առաջադրանքները այսպիսի տեսք ունեին.
Վերցրեք թուղթ ու մատիտ, մտածեք, մի շտապեք անմիջապես սփոյլերներ բացել 🙂
Լուծման վերլուծություն (տեսանյութ)
5:53-ից սկսած, ընդամենը 4 րոպե.
Եվ ահա, թե ինչպես են ֆլիպչարտով տղաները ներկայացրել իրենց լուծումը.
Լուծման վերլուծություն (տեքստ)
Հետևյալ լուծումը գտնվում է մակերեսի վրա. գումարել բոլոր կրկնօրինակների կշիռները, ստեղծել պատահական թիվ 0-ից մինչև բոլոր կշիռների գումարը, այնուհետև ընտրել i-կրկնօրինակ, որպեսզի կրկնօրինակների կշիռների գումարը 0-ից մինչև (i-1)-րդն է: փոքր է պատահական թվից, իսկ կրկնօրինակների կշիռների գումարը 0-ից մինչև i-րդ՝ դրանից ավելի: Այսպիսով, հնարավոր կլինի ընտրել մեկ կրկնօրինակ, իսկ հաջորդը ընտրելու համար անհրաժեշտ է կրկնել ամբողջ պրոցեդուրան՝ առանց հաշվի առնելու ընտրված կրկնօրինակը: Նման ալգորիթմով մեկ կրկնօրինակի ընտրության բարդությունը O(N) է, K կրկնօրինակների ընտրության բարդությունը՝ O(N K) ~ O(N2):
Քառակուսի բարդությունը վատ է, բայց այն կարելի է բարելավել: Դա անելու համար մենք կկառուցենք կշիռների գումարների համար. Կստացվի lg N խորության ծառ, որի տերևներում կլինեն կրկնօրինակ կշիռներ, իսկ մնացած հանգույցներում՝ մասնակի գումարներ՝ մինչև ծառի արմատի բոլոր կշիռների գումարը։ Այնուհետև մենք ստեղծում ենք պատահական թիվ 0-ից մինչև բոլոր կշիռների գումարը, գտնում ենք i-րդ կրկնօրինակը, այն հեռացնում ծառից և կրկնում ենք մնացած կրկնօրինակները գտնելու ընթացակարգը: Այս ալգորիթմով ծառ կառուցելու բարդությունը O(N) է, i-րդ կրկնօրինակը գտնելու և ծառից հեռացնելու բարդությունը՝ O(lg N), K կրկնօրինակների ընտրության բարդությունը՝ O(N + K): lg N) ~ O(N lg N) .
Գծային լոգարիթմական բարդությունն ավելի լավն է, քան քառակուսի բարդությունը, հատկապես մեծ Կ.
Այս ալգորիթմն է ClusterClient գրադարաններ նախագծից »«. (Այնտեղ ծառը կառուցված է O(N lg N), բայց դա չի ազդում ալգորիթմի վերջնական բարդության վրա:)
Առաջադրանք 2. Զեբրա
Անհրաժեշտ էր առաջարկել հիշողության մեջ փաստաթղթերի արդյունավետ տեսակավորման ալգորիթմ ըստ կամայական ոչ ինդեքսավորված դաշտի.
Ձեր թիմին հանձնարարված է հիշողության մեջ բեկորային փաստաթղթերի տվյալների բազա մշակել: Ընդհանուր աշխատանքային ծանրաբեռնվածություն կլինի M չափսի հավաքածուից (սովորաբար N < 100 << M) կամայական (չինդեքսավորված) թվային դաշտով դասավորված վերին N փաստաթղթեր ընտրելը: Մի փոքր ավելի քիչ տարածված աշխատանքային ծանրաբեռնվածություն կլինի վերին N-ն ընտրելը վերին S փաստաթղթերը (S ~ N) բաց թողնելուց հետո:
Առաջարկեք ալգորիթմ՝ նման հարցումները արդյունավետ կերպով կատարելու համար: Գնահատեք դրա հաշվողական բարդությունը՝ օգտագործելով մեծ O նշում միջին դեպքում և վատագույն սցենարներում:
Լուծման վերլուծություն (տեսանյութ)
34:50-ից սկսած, ընդամենը 6 րոպե.
Լուծման վերլուծություն (տեքստ)
Մակերեւութային լուծում. տեսակավորել բոլոր փաստաթղթերը (օրինակ՝ հետ ), ապա վերցրեք N+S փաստաթղթերը։ Այս դեպքում տեսակավորման բարդությունը միջինում O(M lg M), վատագույն դեպքում՝ O(M2):
Ակնհայտ է, որ բոլոր M փաստաթղթերի տեսակավորումը, իսկ հետո դրանց միայն մի փոքր մասը վերցնելն անարդյունավետ է։ Բոլոր փաստաթղթերը չտեսակավորելու համար հարմար է ալգորիթմը , որը կընտրի ցանկալի փաստաթղթերի N + S (դրանք կարելի է տեսակավորել ցանկացած ալգորիթմով): Այս դեպքում բարդությունը միջինում կնվազի մինչև O(M), մինչդեռ ամենավատ դեպքը կմնա նույնը:
Այնուամենայնիվ, դուք կարող եք դա անել նույնիսկ ավելի արդյունավետ. օգտագործեք ալգորիթմը . Այս դեպքում առաջին N+S փաստաթղթերը ավելացվում են min- կամ max-heap-ին (կախված տեսակավորման ուղղությունից), այնուհետև յուրաքանչյուր հաջորդ փաստաթուղթ համեմատվում է ծառի արմատի հետ, որը պարունակում է ընթացիկ նվազագույն կամ առավելագույն փաստաթուղթը, և անհրաժեշտության դեպքում ավելացվում է ծառին։ Այս դեպքում բարդությունը վատագույն դեպքում, երբ պետք է անընդհատ վերակառուցել ծառը, O(M lg M) է, բարդությունը միջինում O(M), ինչպես արագ ընտրության դեպքում:
Այնուամենայնիվ, կույտային հոսքը պարզվում է, որ ավելի արդյունավետ է այն պատճառով, որ գործնականում փաստաթղթերի մեծ մասը կարող է հեռացվել առանց կույտը վերակառուցելու՝ դրա արմատային տարրի հետ մեկ համեմատությունից հետո: Նման տեսակավորումն իրականացվում է Zebra-ի հիշողության մեջ գտնվող փաստաթղթերի տվյալների բազայում, որը մշակվել և օգտագործվում է Kontur-ում:
Առաջադրանք 3. Պետական սվոպներ
Անհրաժեշտ էր առաջարկել վիճակների փոփոխման ամենաարդյունավետ ալգորիթմը.
Ձեր թիմին հանձնարարված է մշակել շքեղ վիճակի փոխանակման մեխանիզմ N հանգույցների բաշխված կլաստերի համար: i-րդ հանգույցի վիճակը պետք է փոխանցվի (i+1)-րդ հանգույցին, N-րդ հանգույցի վիճակը՝ առաջին հանգույցին։ Միակ աջակցվող գործողությունը վիճակի փոխանակումն է, երբ երկու հանգույցները փոխանակում են իրենց վիճակները ատոմային եղանակով: Հայտնի է, որ պետական սվոպը տևում է M միլիվայրկյան։ Յուրաքանչյուր հանգույց կարող է ցանկացած պահի մասնակցել մեկ վիճակի փոխանակմանը:
Որքա՞ն ժամանակ է պահանջվում կլաստերի բոլոր հանգույցների վիճակները փոխանցելու համար:
Լուծման վերլուծություն (տեքստ)
Մակերեւութային լուծում՝ փոխանակեք առաջին և երկրորդ տարրի վիճակները, այնուհետև առաջինը և երրորդը, ապա առաջինը և չորրորդը և այլն: Յուրաքանչյուր փոխանակումից հետո մեկ տարրի վիճակը կլինի ցանկալի դիրքում: Դուք պետք է կատարեք O(N) փոխարկումներ և ծախսեք O(N M) ժամանակ:
Գծային ժամանակը երկար է, այնպես որ դուք կարող եք փոխանակել տարրերի վիճակները զույգերով՝ առաջինը երկրորդի հետ, երրորդը՝ չորրորդի հետ և այլն։ Յուրաքանչյուր պետական փոխանակումից հետո յուրաքանչյուր երկրորդ տարրը ճիշտ դիրքում կլինի։ Դուք պետք է կատարեք O(lg N) փոխարկումներ և ծախսեք O(M lg N) ժամանակ:
Այնուամենայնիվ, հնարավոր է հերթափոխն էլ ավելի արդյունավետ դարձնել՝ ոչ թե գծային, այլ մշտական ժամանակում։ Դա անելու համար առաջին քայլին անհրաժեշտ է փոխանակել առաջին տարրի վիճակը վերջինի հետ, երկրորդը՝ նախավերջինի հետ և այլն։ Վերջին տարրի վիճակը կլինի ճիշտ դիրքում: Իսկ հիմա պետք է երկրորդ տարրի վիճակը փոխանակենք վերջինի հետ, երրորդը՝ նախավերջինի հետ և այլն։ Փոխանակումների այս փուլից հետո բոլոր տարրերի պետությունները ճիշտ դիրքերում կլինեն։ Ընդհանուր առմամբ կլինեն O(2M) ~ O(1) փոխարկումներ:
Նման լուծումը բոլորովին չի զարմացնի մաթեմատիկոսին, ով դեռ հիշում է, որ պտույտը երկու առանցքային համաչափությունների բաղադրություն է։ Ի դեպ, այն տրիվիալ կերպով ընդհանրացվում է տեղաշարժի համար ոչ թե մեկ, այլ K < N դիրքերով։ (Գրեք մեկնաբանություններում, թե կոնկրետ ինչպես):
Ձեզ դուր եկավ հանելուկներ: Գիտե՞ք այլ լուծումներ։ Կիսվեք մեկնաբանություններում։
Եվ վերջում ահա մի քանի օգտակար հղումներ.
- մասին ավելին իմանալ ուրվագծի մեջ
- տես ներքին գրառումները բաշխված համակարգերի մասին
- դիտեք տեսադասախոսությունների շարքը»
- բաժանորդագրվել մեր
Source: www.habr.com