දින කිහිපයකට පෙර සිදු විය හයිඩ්රා සමුළුව. JUG.ru සමූහයේ යාලුවෝ සිහින කථිකයන්ට ආරාධනා කළහ (ලෙස්ලි ලැම්පෝට්! ක්ලිෆ් ක්ලික්! මාටින් ක්ලෙප්මන්!) බෙදා හරින ලද පද්ධති සහ පරිගණකකරණය සඳහා දින දෙකක් කැප කළහ. කොන්ටූර් සමුළුවේ හවුල්කරුවන් තිදෙනාගෙන් කෙනෙකි. අපි කුටියේ කතා කළා, බෙදා හරින ලද ගබඩා ගැන කතා කළා, බිංගෝ සෙල්ලම් කළා, ප්‍රහේලිකා විසඳුවා.

මෙය ඔවුන්ගේ පාඨයේ කතුවරයාගෙන් Kontur ස්ථාවරයේ කාර්යයන් පිළිබඳ විශ්ලේෂණයක් සහිත සටහනකි. හයිඩ්‍රා හි සිටියේ කවුද - මෙය ඔබේ ප්‍රසන්න අත්දැකීම මතක තබා ගැනීමට හේතුවයි, එසේ නොවූයේ - ඔබේ මොළය දිගු කිරීමට අවස්ථාවක් ලොකු ඕ- අංකනය.

ඔවුන්ගේ තීරණය ලිවීමට flipchart ස්ලයිඩ වලට කඩා දැමූ සහභාගිවන්නන් පවා සිටියහ. මම විහිළු කරන්නේ නැහැ - ඔවුන් මෙම කඩදාසි තොගය සත්‍යාපනය සඳහා භාර දුන්නා:

සම්පූර්ණ කාර්යයන් තුනක් විය:

• බර තුලනය සඳහා බර අනුව අනුරූ තෝරා ගැනීම ගැන
• මතකයේ ඇති දත්ත ගබඩාවකට එරෙහිව විමසුම් ප්‍රතිඵල වර්ග කිරීම ගැන
• මුදු ස්ථලකය සහිත බෙදා හරින ලද පද්ධතියක රාජ්ය මාරු කිරීම මත

කාර්යය 1. ClusterClient

බෙදා හරින ලද පද්ධතියක N බරැති අනුරූ වලින් K කාර්යක්ෂමව තෝරා ගැනීම සඳහා ඇල්ගොරිතමයක් යෝජනා කිරීම අවශ්‍ය විය:

විශාල වශයෙන් බෙදා හරින ලද N නෝඩ් පොකුරක් සඳහා සේවාදායක පුස්තකාලයක් සංවර්ධනය කිරීම ඔබේ කණ්ඩායමට පැවරී ඇත. පුස්තකාලය නෝඩ් හා සම්බන්ධ විවිධ පාරදත්ත (උදා, ඒවායේ ප්‍රමාදයන්, 4xx/5xx ප්‍රතිචාර අනුපාත ආදිය) නිරීක්ෂණය කර ඒවාට පාවෙන ලක්ෂ්‍ය බර W1..WN පවරනු ඇත. සමගාමී ක්‍රියාත්මක කිරීමේ උපාය මාර්ගයට සහාය වීම සඳහා, පුස්තකාලයට N නෝඩ් වල K අහඹු ලෙස තෝරා ගැනීමට හැකි විය යුතුය - තෝරා ගැනීමේ අවස්ථාවක් නෝඩයක බරට සමානුපාතික විය යුතුය.

නෝඩ් කාර්යක්ෂමව තෝරා ගැනීමට ඇල්ගොරිතමයක් යෝජනා කරන්න. විශාල O අංකනය භාවිතයෙන් එහි ගණනය කිරීමේ සංකීර්ණත්වය තක්සේරු කරන්න.

සියල්ල ඉංග්‍රීසියෙන් ඇත්තේ ඇයි?

මක්නිසාද යත් මෙම ස්වරූපයෙන් සම්මන්ත්‍රණයට සහභාගී වූවන් ඔවුන් සමඟ සටන් කළ නිසා සහ හයිඩ්‍රා හි නිල භාෂාව ඉංග්‍රීසි වූ බැවිනි. කාර්යයන් මේ ආකාරයෙන් පෙනුණි:

කඩදාසි සහ පැන්සල ගන්න, සිතන්න, වහාම ස්පොයිලර් විවෘත කිරීමට ඉක්මන් නොවන්න 🙂

විසඳුම විශ්ලේෂණය (වීඩියෝ)

5:53 ට ආරම්භ, විනාඩි 4 ක් පමණි:

Flipchart සමඟ සිටින අය ඔවුන්ගේ විසඳුම ඉදිරිපත් කළ ආකාරය මෙන්න:

විසඳුම විශ්ලේෂණය (පෙළ)

පහත විසඳුම මතුපිට පිහිටා ඇත: සියලුම අනුරූවල බර එකතු කරන්න, 0 සිට සියලුම බරවල එකතුවට අහඹු සංඛ්‍යාවක් ජනනය කරන්න, ඉන්පසු 0 සිට (i-1) වන අනුරූ බර එකතුව i-replica තෝරන්න. අහඹු අංකයකට වඩා අඩු වන අතර, 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 සඳහා.

එය මෙම ඇල්ගොරිතම වේ කේතය තුළ ක්රියාත්මක කර ඇත ව්‍යාපෘතියෙන් ClusterClient පුස්තකාල "නැගෙනහිර". (එහි, ගස 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) දක්වා අඩු වනු ඇත, නරකම අවස්ථාව එලෙසම පවතිනු ඇත.

කෙසේ වෙතත්, ඔබට එය වඩාත් කාර්යක්ෂමව කළ හැකිය - ඇල්ගොරිතම භාවිතා කරන්න binary heap streaming. මෙම අවස්ථාවෙහිදී, පළමු N+S ලේඛන min- හෝ max-heap වෙත එකතු කරනු ලැබේ (වර්ග කිරීමේ දිශාව අනුව), ඉන්පසු සෑම ඊළඟ ලේඛනයක්ම වත්මන් අවම හෝ උපරිම ලේඛනය අඩංගු ගසේ මූලයට සංසන්දනය කරනු ලැබේ. සහ අවශ්ය නම් ගසට එකතු කරනු ලැබේ. . මෙම අවස්ථාවෙහිදී, නරකම අවස්ථාවෙහි ඇති සංකීර්ණත්වය, ඔබ නිරන්තරයෙන් ගස නැවත ගොඩනඟා ගැනීමට සිදු වන විට, O (M lg M) වේ, ඉක්මන් තේරීමේදී මෙන් සාමාන්යයෙන් සංකීර්ණත්වය O (M) වේ.

කෙසේ වෙතත්, ගොඩ ප්‍රවාහය ප්‍රායෝගිකව එහි මූල මූලද්‍රව්‍යය සමඟ එක් සැසඳීමෙන් පසු ගොඩ නැවත ගොඩනැංවීමකින් තොරව බොහෝ ලේඛන ඉවත දැමිය හැකි නිසා වඩාත් කාර්යක්ෂම වේ. Kontur හි සංවර්ධනය කර භාවිතා කරන ලද Zebra in-memory ලේඛන දත්ත ගබඩාවේ එවැනි වර්ග කිරීම ක්‍රියාත්මක වේ.

කාර්යය 3. රාජ්ය හුවමාරු

තත්වයන් මාරු කිරීම සඳහා වඩාත් කාර්යක්ෂම ඇල්ගොරිතම යෝජනා කිරීම අවශ්ය විය:

බෙදා හරින ලද N නෝඩ් පොකුරක් සඳහා විසිතුරු රාජ්‍ය හුවමාරු යාන්ත්‍රණයක් සංවර්ධනය කිරීම ඔබේ කණ්ඩායමට පැවරී ඇත. i-th node හි තත්වය (i+1)-th node වෙත මාරු කළ යුතුය, N-th node හි තත්වය පළමු node වෙත මාරු කළ යුතුය. නෝඩ් දෙකක් තම තත්ත්‍වයන් පරමාණුකව හුවමාරු කරන විට ඇති එකම සහය දක්වන ක්‍රියාව වන්නේ රාජ්‍ය හුවමාරුවයි. රාජ්‍ය හුවමාරුවක් M මිලි තත්පර ගත වන බව දන්නා කරුණකි. සෑම නෝඩයකටම ඕනෑම මොහොතක තනි රාජ්‍ය හුවමාරුවකට සහභාගී විය හැක.

පොකුරක් තුළ ඇති සියලුම නෝඩ් වල තත්වයන් මාරු කිරීමට කොපමණ කාලයක් ගතවේද?

විසඳුම විශ්ලේෂණය (පෙළ)

මතුපිට විසඳුම: පළමු සහ දෙවන මූලද්‍රව්‍යයේ ප්‍රාන්ත හුවමාරු කරන්න, පසුව පළමු සහ තෙවන, පසුව පළමු සහ සිව්වන, සහ යනාදිය. එක් එක් හුවමාරුවෙන් පසුව, එක් මූලද්රව්යයක තත්වය අපේක්ෂිත ස්ථානයේ පවතිනු ඇත. O(N) permutations සාදා O(N M) කාලය ගත කිරීමට සිදුවේ.

රේඛීය කාලය දිගු වේ, එබැවින් ඔබට මූලද්‍රව්‍යවල තත්වයන් යුගල වශයෙන් හුවමාරු කර ගත හැකිය: පළමුවැන්න දෙවැන්න, තෙවනුව සිව්වන සහ යනාදිය. එක් එක් රාජ්ය හුවමාරුවෙන් පසුව, සෑම දෙවන මූලද්රව්යයක්ම නිවැරදි ස්ථානයේ පවතිනු ඇත. ඔබට O(lg N) ප්‍රගමන සාදා O(M lg N) කාලය ගත කළ යුතුය.

කෙසේ වෙතත්, මාරුව වඩාත් කාර්යක්ෂම කිරීමට හැකි වේ - රේඛීයව නොව, නිරන්තර කාලය තුළ. මෙය සිදු කිරීම සඳහා, පළමු පියවරේදී, ඔබ පළමු මූලද්‍රව්‍යයේ තත්වය අවසාන එක සමඟ හුවමාරු කර ගත යුතුය, දෙවැන්න අවසාන කොටස සමඟ යනාදිය. අවසාන මූලද්රව්යයේ තත්වය නිවැරදි ස්ථානයේ පවතිනු ඇත. දැන් අපි දෙවන මූලද්‍රව්‍යයේ තත්වය අවසාන එක සමඟත්, තුන්වන එක අවසාන කොටස සමඟත් යනාදිය හුවමාරු කර ගත යුතුයි. මෙම හුවමාරු වටයෙන් පසුව, සියලුම මූලද්රව්යවල තත්වයන් නිවැරදි ස්ථානයේ පවතිනු ඇත. සම්පූර්ණ වශයෙන් O(2M) ~ O(1) ප්‍රගමනයන් ඇත.

භ්රමණයක් යනු අක්ෂීය සමමිතික දෙකක සංයුතියක් බව තවමත් මතක තබා ගන්නා ගණිතඥයෙකු එවැනි විසඳුමක් කිසිසේත් පුදුමයට පත් නොවනු ඇත. මාර්ගය වන විට, එය එකකින් නොව, K <N තනතුරු මගින් මාරු කිරීම සඳහා සුළු වශයෙන් සාමාන්යකරණය කර ඇත. (හරියටම කොහොමද කියලා කමෙන්ට් වල ලියන්න.)

ඔබ ප්‍රහේලිකා වලට කැමතිද? ඔබ වෙනත් විසඳුම් දන්නවාද? අදහස් බෙදාගන්න.

අවසානයේ ප්‍රයෝජනවත් සබැඳි කිහිපයක් මෙන්න:

• ගැන වැඩි විස්තර දැනගන්න යටිතල පහසුකම් සංවර්ධනය සමෝච්ඡය තුළ
• අභ්යන්තරයේ වාර්තා බලන්න වාර්තා සහිත පත්‍රිකාව බෙදා හරින ලද පද්ධති ගැන
• වීඩියෝ දේශන මාලාව නරඹන්නසාමාන්ය මිනිසුන් සඳහා අසාමාන්ය ඇල්ගොරිතම»
• අපගේ වෙත දායක වන්න ටෙලිග්‍රාම් හි නාලිකාව

මූලාශ්රය: www.habr.com