થોડા દિવસ પહેલા થયું હાઇડ્રા કોન્ફરન્સ. JUG.ru ગ્રૂપના લોકોએ ડ્રીમ સ્પીકર્સને આમંત્રિત કર્યા (લેસ્લી લેમપોર્ટ! ક્લિફ ક્લિક! માર્ટિન ક્લેપમેન!) અને વિતરિત સિસ્ટમ્સ અને કમ્પ્યુટિંગ માટે બે દિવસ ફાળવ્યા. કોન્ટુર કોન્ફરન્સના ત્રણ ભાગીદારોમાંથી એક હતા. અમે બૂથ પર વાત કરી, અમારા વિતરિત સ્ટોરેજ વિશે વાત કરી, બિન્ગો વગાડ્યો અને કોયડાઓ ઉકેલ્યા.

આ કોન્ટુર સ્ટેન્ડ પર તેમના લખાણના લેખકના કાર્યોના વિશ્લેષણ સાથેની પોસ્ટ છે. હાઇડ્રા પર કોણ હતું - આ સુખદ અનુભવને યાદ રાખવાનું તમારું કારણ છે, કોણ ન હતું - તમારા મગજને ખેંચવાની તક મોટા ઓ- નોટેશન.

એવા સહભાગીઓ પણ હતા જેમણે ફ્લિપચાર્ટને સ્લાઇડ્સમાં તોડીને તેમનો નિર્ણય લખ્યો હતો. હું મજાક કરતો નથી - તેઓએ ચકાસણી માટે કાગળનો આ સ્ટેક આપ્યો:

કુલ ત્રણ કાર્યો હતા:

• લોડ બેલેન્સિંગ માટે વજન દ્વારા પ્રતિકૃતિઓ પસંદ કરવા વિશે
• ઇન-મેમરી ડેટાબેઝ સામે ક્વેરી પરિણામોને સૉર્ટ કરવા વિશે
• રિંગ ટોપોલોજી સાથે વિતરિત સિસ્ટમમાં રાજ્ય ટ્રાન્સફર પર

કાર્ય 1. ClusterClient

વિતરિત સિસ્ટમની N ભારિત પ્રતિકૃતિઓમાંથી K ની કાર્યક્ષમ પસંદગી માટે અલ્ગોરિધમનો પ્રસ્તાવ મૂકવો જરૂરી હતો:

તમારી ટીમને N નોડ્સના મોટા પ્રમાણમાં વિતરિત ક્લસ્ટર માટે ક્લાયન્ટ લાઇબ્રેરી વિકસાવવાનું કામ સોંપવામાં આવ્યું છે. લાઇબ્રેરી નોડ્સ સાથે સંકળાયેલા વિવિધ મેટાડેટાનો ટ્રૅક રાખશે (દા.ત., તેમની લેટન્સી, 4xx/5xx રિસ્પોન્સ રેટ, વગેરે) અને તેમને ફ્લોટિંગ પોઈન્ટ વેઈટ W1..WN સોંપશે. સમવર્તી અમલીકરણ વ્યૂહરચનાને ટેકો આપવા માટે, લાઇબ્રેરીએ N નોડ્સના K ને રેન્ડમલી પસંદ કરવા સક્ષમ હોવા જોઈએ - પસંદ કરવાની તક નોડના વજનના પ્રમાણસર હોવી જોઈએ.

નોડ્સને અસરકારક રીતે પસંદ કરવા માટે અલ્ગોરિધમનો પ્રસ્તાવ કરો. મોટા O નોટેશનનો ઉપયોગ કરીને તેની કોમ્પ્યુટેશનલ જટિલતાનો અંદાજ કાઢો.

બધું અંગ્રેજીમાં કેમ છે?

કારણ કે આ સ્વરૂપમાં કોન્ફરન્સના સહભાગીઓ તેમની સાથે લડ્યા હતા અને કારણ કે અંગ્રેજી હાઇડ્રાની સત્તાવાર ભાષા હતી. કાર્યો આના જેવા દેખાતા હતા:

કાગળ અને પેન્સિલ લો, વિચારો, તરત જ સ્પોઈલર ખોલવા ઉતાવળ ન કરો 🙂

ઉકેલનું વિશ્લેષણ (વિડિઓ)

5:53 થી શરૂ, માત્ર 4 મિનિટ:

અને ફ્લિપચાર્ટવાળા લોકોએ તેમનો ઉકેલ કેવી રીતે રજૂ કર્યો તે અહીં છે:

ઉકેલનું વિશ્લેષણ (ટેક્સ્ટ)

નીચેનું સોલ્યુશન સપાટી પર આવેલું છે: તમામ પ્રતિકૃતિઓના વજનનો સરવાળો કરો, 0 થી તમામ વજનના સરવાળા સુધીની રેન્ડમ સંખ્યા બનાવો, પછી એક i-પ્રતિકૃતિ પસંદ કરો કે જેથી પ્રતિકૃતિના વજનનો સરવાળો 0 થી (i-1)th સુધી હોય. રેન્ડમ સંખ્યા કરતાં ઓછી છે, અને પ્રતિકૃતિના વજનનો સરવાળો 0 થી i-th - તે કરતાં વધુ છે. તેથી એક પ્રતિકૃતિ પસંદ કરવાનું શક્ય બનશે, અને બીજી પસંદ કરવા માટે, તમારે પસંદ કરેલ પ્રતિકૃતિને ધ્યાનમાં લીધા વિના સમગ્ર પ્રક્રિયાને પુનરાવર્તિત કરવાની જરૂર છે. આવા અલ્ગોરિધમ સાથે, એક પ્રતિકૃતિ પસંદ કરવાની જટિલતા O(N) છે, K પ્રતિકૃતિઓ પસંદ કરવાની જટિલતા O(N K) ~ O(N2) છે.

ચતુર્ભુજ જટિલતા ખરાબ છે, પરંતુ તેને સુધારી શકાય છે. આ કરવા માટે, અમે બિલ્ડ કરીશું સેગમેન્ટ વૃક્ષ વજનના સરવાળા માટે. lg N ની ઊંડાઈનું એક વૃક્ષ મેળવવામાં આવશે, જેના પાંદડાઓમાં પ્રતિકૃતિ વજન હશે, અને બાકીના ગાંઠોમાં - આંશિક સરવાળો, વૃક્ષના મૂળમાં તમામ વજનના સરવાળા સુધી. આગળ, અમે 0 થી તમામ વજનના સરવાળા સુધી રેન્ડમ નંબર જનરેટ કરીએ છીએ, i-th પ્રતિકૃતિ શોધીએ છીએ, તેને વૃક્ષમાંથી દૂર કરીએ છીએ અને બાકીની પ્રતિકૃતિઓ શોધવા માટે પ્રક્રિયાને પુનરાવર્તિત કરીએ છીએ. આ અલ્ગોરિધમ સાથે, વૃક્ષ બનાવવાની જટિલતા O(N) છે, i-th પ્રતિકૃતિ શોધવાની અને તેને વૃક્ષમાંથી દૂર કરવાની જટિલતા O(lg N) છે, K પ્રતિકૃતિઓ પસંદ કરવાની જટિલતા O(N + K) છે. lg N) ~ O(N lg N) .

રેખીય-લોગ જટિલતા ચતુર્ભુજ જટિલતા કરતાં વધુ સારી છે, ખાસ કરીને મોટા K માટે.

તે આ અલ્ગોરિધમ છે કોડમાં અમલી પ્રોજેક્ટમાંથી ક્લસ્ટરક્લાયન્ટ લાઇબ્રેરીઓ "પૂર્વ" (ત્યાં, વૃક્ષ O(N lg N) માં બનેલ છે, પરંતુ આ અલ્ગોરિધમની અંતિમ જટિલતાને અસર કરતું નથી.)

કાર્ય 2. ઝેબ્રા

મનસ્વી નોન-ઇન્ડેક્સ્ડ ફીલ્ડ દ્વારા મેમરીમાં દસ્તાવેજોના કાર્યક્ષમ વર્ગીકરણ માટે અલ્ગોરિધમનો પ્રસ્તાવ મૂકવો જરૂરી હતો:

તમારી ટીમને એક શાર્ડ ઇન-મેમરી દસ્તાવેજ ડેટાબેઝ વિકસાવવાનું કામ સોંપવામાં આવ્યું છે. એક સામાન્ય વર્કલોડ M (સામાન્ય રીતે N < 100 << M) કદના સંગ્રહમાંથી મનસ્વી (નૉન-ઇન્ડેક્સ્ડ) આંકડાકીય ક્ષેત્ર દ્વારા સૉર્ટ કરેલા ટોચના N દસ્તાવેજોને પસંદ કરવાનું હશે. ટોચના S દસ્તાવેજો (S ~ N) છોડ્યા પછી ટોચના N પસંદ કરવાનું થોડું ઓછું સામાન્ય વર્કલોડ હશે.

આવા પ્રશ્નોને અસરકારક રીતે ચલાવવા માટે અલ્ગોરિધમનો પ્રસ્તાવ કરો. સરેરાશ કેસ અને સૌથી ખરાબ સંજોગોમાં મોટા O નોટેશનનો ઉપયોગ કરીને તેની કોમ્પ્યુટેશનલ જટિલતાનો અંદાજ કાઢો.

ઉકેલનું વિશ્લેષણ (વિડિઓ)

34:50 થી શરૂ, માત્ર 6 મિનિટ:

ઉકેલનું વિશ્લેષણ (ટેક્સ્ટ)

સપાટી ઉકેલ: બધા દસ્તાવેજોને સૉર્ટ કરો (ઉદાહરણ તરીકે સાથે ક્વિક્સર્ટ), પછી N+S દસ્તાવેજો લો. આ કિસ્સામાં, વર્ગીકરણની જટિલતા સરેરાશ O(M lg M), સૌથી ખરાબ O(M2) પર છે.

તે સ્પષ્ટ છે કે બધા M દસ્તાવેજોને સૉર્ટ કરવા અને પછી તેમાંથી માત્ર એક નાનો ભાગ લેવો બિનકાર્યક્ષમ છે. બધા દસ્તાવેજોને સૉર્ટ ન કરવા માટે, એક અલ્ગોરિધમ યોગ્ય છે ઝડપી પસંદગી, જે ઇચ્છિત દસ્તાવેજોમાંથી N + S પસંદ કરશે (તેઓ કોઈપણ અલ્ગોરિધમ દ્વારા સૉર્ટ કરી શકાય છે). આ કિસ્સામાં, જટિલતા સરેરાશ O(M) સુધી ઘટશે, જ્યારે સૌથી ખરાબ સ્થિતિ એ જ રહેશે.

જો કે, તમે તેને વધુ અસરકારક રીતે કરી શકો છો - અલ્ગોરિધમનો ઉપયોગ કરો બાઈનરી હીપ સ્ટ્રીમિંગ. આ કિસ્સામાં, પ્રથમ N+S દસ્તાવેજો મિનિમમ- અથવા મેક્સ-હીપ (સૉર્ટ દિશાના આધારે) માં ઉમેરવામાં આવે છે, અને પછી દરેક આગલા દસ્તાવેજની સરખામણી વૃક્ષના મૂળ સાથે કરવામાં આવે છે, જેમાં વર્તમાન લઘુત્તમ અથવા મહત્તમ દસ્તાવેજ હોય ​​છે, અને જો જરૂરી હોય તો ઝાડમાં ઉમેરવામાં આવે છે. . આ કિસ્સામાં, સૌથી ખરાબ કિસ્સામાં જટિલતા, જ્યારે તમારે વૃક્ષને સતત પુનઃનિર્માણ કરવું પડે છે, તે O(M lg M) છે, સરેરાશ જટિલતા O(M) છે, જેમ કે ઝડપી પસંદગી સાથે.

જો કે, હીપ સ્ટ્રીમિંગ એ હકીકતને કારણે વધુ કાર્યક્ષમ હોવાનું બહાર આવ્યું છે કે વ્યવહારમાં મોટાભાગના દસ્તાવેજો તેના મૂળ તત્વ સાથે એક જ સરખામણી કર્યા પછી ઢગલાનું પુનઃનિર્માણ કર્યા વિના કાઢી શકાય છે. કોન્ટુરમાં વિકસિત અને ઉપયોગમાં લેવાતા ઝેબ્રા ઇન-મેમરી ડોક્યુમેન્ટ ડેટાબેઝમાં આવા વર્ગીકરણનો અમલ કરવામાં આવે છે.

કાર્ય 3. રાજ્ય સ્વેપ

સ્થાનાંતરિત રાજ્યો માટે સૌથી કાર્યક્ષમ અલ્ગોરિધમનો પ્રસ્તાવ મૂકવો જરૂરી હતો:

તમારી ટીમને N નોડ્સના વિતરિત ક્લસ્ટર માટે ફેન્સી સ્ટેટ એક્સચેન્જ મિકેનિઝમ વિકસાવવાનું કામ સોંપવામાં આવ્યું છે. i-th નોડની સ્થિતિ (i+1)-th નોડમાં સ્થાનાંતરિત થવી જોઈએ, N-th નોડની સ્થિતિ પ્રથમ નોડમાં સ્થાનાંતરિત થવી જોઈએ. જ્યારે બે ગાંઠો તેમના રાજ્યોને પરમાણુ રીતે વિનિમય કરે છે ત્યારે એકમાત્ર સપોર્ટેડ ઑપરેશન એ સ્ટેટ સ્વેપ છે. તે જાણીતું છે કે રાજ્ય સ્વેપમાં M મિલિસેકન્ડનો સમય લાગે છે. દરેક નોડ કોઈપણ સમયે એક રાજ્ય સ્વેપમાં ભાગ લેવા સક્ષમ છે.

ક્લસ્ટરમાં તમામ ગાંઠોની સ્થિતિને સ્થાનાંતરિત કરવામાં કેટલો સમય લાગે છે?

ઉકેલનું વિશ્લેષણ (ટેક્સ્ટ)

સરફેસ સોલ્યુશન: પ્રથમ અને બીજા તત્વની સ્થિતિઓનું વિનિમય કરો, પછી પ્રથમ અને ત્રીજા, પછી પ્રથમ અને ચોથા, અને તેથી વધુ. દરેક વિનિમય પછી, એક તત્વની સ્થિતિ ઇચ્છિત સ્થિતિમાં હશે. તમારે O(N) ક્રમચયો બનાવવા પડશે અને O(N M) સમય પસાર કરવો પડશે.

રેખીય સમય લાંબો છે, તેથી તમે તત્વોની સ્થિતિઓને જોડીમાં બદલી શકો છો: પ્રથમ બીજા સાથે, ત્રીજો ચોથા સાથે, અને તેથી વધુ. દરેક રાજ્ય વિનિમય પછી, દરેક બીજા તત્વ યોગ્ય સ્થિતિમાં હશે. તમારે O(lg N) ક્રમચયો બનાવવા પડશે અને O(M lg N) સમય પસાર કરવો પડશે.

જો કે, શિફ્ટને વધુ કાર્યક્ષમ બનાવવાનું શક્ય છે - રેખીયમાં નહીં, પરંતુ સતત સમયમાં. આ કરવા માટે, પ્રથમ પગલા પર, તમારે પ્રથમ તત્વની સ્થિતિને છેલ્લા એક સાથે, બીજાને ઉપાંત્ય સાથે, વગેરે સાથે વિનિમય કરવાની જરૂર છે. છેલ્લા તત્વની સ્થિતિ યોગ્ય સ્થિતિમાં હશે. અને હવે આપણે બીજા તત્વની સ્થિતિને છેલ્લા એક સાથે, ત્રીજા તત્વની ઉપાંત્ય સાથે, અને તેથી વધુની જરૂર છે. વિનિમયના આ રાઉન્ડ પછી, તમામ તત્વોની સ્થિતિ યોગ્ય સ્થિતિમાં હશે. કુલ O(2M) ~ O(1) ક્રમચયો હશે.

આવા ઉકેલથી ગણિતશાસ્ત્રીને આશ્ચર્ય થશે નહીં કે જે હજુ પણ યાદ રાખે છે કે પરિભ્રમણ એ બે અક્ષીય સમપ્રમાણતાઓની રચના છે. માર્ગ દ્વારા, તે એક દ્વારા નહીં, પરંતુ K < N પોઝિશન્સ દ્વારા પાળી માટે નજીવી રીતે સામાન્યકૃત છે. (કોમેન્ટમાં લખો કે કેવી રીતે બરાબર.)

શું તમને કોયડાઓ ગમ્યા? શું તમે અન્ય ઉકેલો જાણો છો? ટિપ્પણીઓમાં શેર કરો.

અને અંતે અહીં કેટલીક ઉપયોગી લિંક્સ છે:

• વિશે વધુ જાણો ઈન્ફ્રાસ્ટ્રક્ચર વિકાસ સમોચ્ચમાં
• આંતરિક રેકોર્ડ જુઓ અહેવાલો સાથે ફ્લાયર વિતરિત સિસ્ટમો વિશે
• વિડિઓ પ્રવચનો શ્રેણી જુઓસામાન્ય લોકો માટે અસામાન્ય ગાણિતીક નિયમો»
• અમારા પર સબ્સ્ક્રાઇબ કરો ટેલિગ્રામમાં ચેનલ

સોર્સ: www.habr.com