හෙලෝ, හබ්ර්! ලිපියේ පරිවර්තනයක් මම ඔබේ අවධානයට ඉදිරිපත් කරමි
"සම්බන්ධතා දත්ත සමුදායක් ක්රියා කරන්නේ කෙසේද".

සම්බන්ධක දත්ත සමුදායන් ගැන කතා කරන විට, මට යමක් අතුරුදහන් වී ඇතැයි සිතීම වළක්වා ගත නොහැක. ඒවා සෑම තැනකම භාවිතා වේ. කුඩා හා ප්‍රයෝජනවත් SQLite සිට බලවත් Teradata දක්වා විවිධ දත්ත සමුදායන් තිබේ. නමුත් දත්ත සමුදාය ක්‍රියා කරන ආකාරය විස්තර කරන ලිපි කිහිපයක් පමණි. "howdoesarelationaldatabasework" භාවිතයෙන් ඔබට ඔබම සෙවිය හැකි අතර එහි ප්‍රතිඵලය අඩුයි. එපමණක්ද නොව, මෙම ලිපි කෙටි වේ. ඔබ නවතම ඝෝෂාකාරී තාක්ෂණයන් (BigData, NoSQL හෝ JavaScript) සොයන්නේ නම්, ඒවා ක්‍රියා කරන ආකාරය පැහැදිලි කරන වඩාත් ගැඹුරු ලිපි ඔබට හමුවනු ඇත.

විශ්ව විද්‍යාල පාඨමාලා, පර්යේෂණ පත්‍රිකා සහ පොත් වලින් පිටත විස්තර කිරීමට නොහැකි තරම් පැරණි සහ නීරසද?

සංවර්ධකයෙකු ලෙස, මට නොතේරෙන දෙයක් භාවිතා කිරීමට මම වෛර කරමි. තවද දත්ත සමුදායන් වසර 40 කට වැඩි කාලයක් භාවිතා කර ඇත්නම්, එයට හේතුවක් තිබිය යුතුය. වසර ගණනාවක් පුරා, මම දිනපතා භාවිතා කරන මෙම අමුතු කළු පෙට්ටි සැබවින්ම තේරුම් ගැනීමට පැය සිය ගණනක් ගත කළෙමි. සම්බන්ධතා දත්ත සමුදායන් ඔවුන් නිසා ඉතා රසවත් ප්රයෝජනවත් සහ නැවත භාවිතා කළ හැකි සංකල්ප මත පදනම්ව. ඔබ දත්ත සමුදායක් අවබෝධ කර ගැනීමට උනන්දුවක් දක්වන්නේ නම්, නමුත් මෙම පුළුල් මාතෘකාව ගැන සොයා බැලීමට කිසි විටෙකත් කාලය හෝ නැඹුරුවක් නොතිබුනේ නම්, ඔබ මෙම ලිපිය රස විඳිය යුතුය.

මෙම ලිපියේ මාතෘකාව පැහැදිලි වුවද, මෙම ලිපියේ අරමුණ දත්ත සමුදාය භාවිතා කරන්නේ කෙසේද යන්න තේරුම් ගැනීම නොවේ. එබැවින්, සරල සම්බන්ධතා ඉල්ලීමක් සහ මූලික විමසුම් ලියන්නේ කෙසේදැයි ඔබ දැනටමත් දැන සිටිය යුතුය RAW; එසේ නොමැතිනම් ඔබට මෙම ලිපිය නොතේරෙනු ඇත. ඔබ දැනගත යුතු එකම දෙය එයයි, මම ඉතිරිය පැහැදිලි කරන්නම්.

මම ඇල්ගොරිතමවල කාල සංකීර්ණත්වය (BigO) වැනි පරිගණක විද්‍යාවේ මූලික කරුණු කිහිපයක් සමඟින් ආරම්භ කරමි. ඔබගෙන් සමහරෙකු මෙම සංකල්පයට වෛර කරන බව මම දනිමි, නමුත් එය නොමැතිව ඔබට දත්ත සමුදාය තුළ ඇති සංකීර්ණතා තේරුම් ගැනීමට නොහැකි වනු ඇත. මෙය විශාල මාතෘකාවක් බැවින්, මම අවධානය යොමු කරන්නම් මම හිතන දේ වැදගත්: දත්ත සමුදාය ක්‍රියාකරන ආකාරය SQL විමසීමක් කළා. මම හඳුන්වා දෙන්නම් මූලික දත්ත සමුදා සංකල්පඑවිට ලිපිය අවසානයේ ඔබට කබාය යටතේ සිදුවන්නේ කුමක්ද යන්න පිළිබඳ අදහසක් ඇත.

මෙය බොහෝ ඇල්ගොරිතම සහ දත්ත ව්‍යුහයන් ඇතුළත් දිගු හා තාක්ෂණික ලිපියක් බැවින්, එය කියවීමට ඔබේ කාලය ගන්න. සමහර සංකල්ප තේරුම් ගැනීමට අපහසු විය හැක; ඔබට ඒවා මඟ හැර සාමාන්‍ය අදහස ලබා ගත හැක.

ඔබ අතර වැඩි දැනුමක් ඇති අය සඳහා, මෙම ලිපිය කොටස් 3 කට බෙදා ඇත:

• පහළ මට්ටමේ සහ ඉහළ මට්ටමේ දත්ත සමුදා සංරචක පිළිබඳ දළ විශ්ලේෂණය
• විමසුම් ප්‍රශස්තකරණ ක්‍රියාවලිය පිළිබඳ දළ විශ්ලේෂණය
• ගනුදෙනු සහ බෆර් සංචිත කළමනාකරණය පිළිබඳ දළ විශ්ලේෂණය

අාපසු මුලටම

වසර ගණනාවකට පෙර (දුරින්, ඈතින් පිහිටි මන්දාකිණියක...), සංවර්ධකයින්ට ඔවුන් කේතනය කරන මෙහෙයුම් ගණන හරියටම දැනගත යුතු විය. ඔවුන්ගේ මන්දගාමී පරිගණකවල CPU සහ මතකය නාස්ති කිරීමට ඔවුන්ට නොහැකි වූ නිසා ඔවුන් ඔවුන්ගේ ඇල්ගොරිතම සහ දත්ත ව්‍යුහයන් හදවතින්ම දැන සිටියහ.

මෙම කොටසේදී, දත්ත සමුදාය අවබෝධ කර ගැනීම සඳහා අත්‍යවශ්‍ය වන මෙම සංකල්ප කිහිපයක් මම ඔබට මතක් කරමි. මම සංකල්පය ද හඳුන්වා දෙන්නෙමි දත්ත සමුදා දර්ශකය.

O(1) එදිරිව O(n2)

වර්තමානයේ, බොහෝ සංවර්ධකයින් ඇල්ගොරිතම වල කාල සංකීර්ණත්වය ගැන තැකීමක් නොකරයි ... ඔවුන් හරි!

නමුත් ඔබ බොහෝ දත්ත සමඟ ගනුදෙනු කරන විට (මම දහස් ගණනක් කතා නොකරමි) හෝ ඔබ මිලි තත්පර වලින් අරගල කරන්නේ නම්, මෙම සංකල්පය තේරුම් ගැනීම ඉතා වැදගත් වේ. ඔබට සිතාගත හැකි පරිදි, දත්ත සමුදායන් අවස්ථා දෙකටම මුහුණ දිය යුතුය! කාරණය තේරුම් ගැනීමට අවශ්‍ය ප්‍රමාණයට වඩා වැඩි කාලයක් ගත කිරීමට මම ඔබට ඉඩ නොදෙමි. මෙය අපට පසුව පිරිවැය මත පදනම් වූ ප්‍රශස්තකරණය පිළිබඳ සංකල්පය තේරුම් ගැනීමට උපකාරී වනු ඇත (පිරිවැය මුල් කරගත් ප්‍රශස්තිකරණය).

සංකල්පය

ඇල්ගොරිතමයේ කාල සංකීර්ණත්වය ලබා දී ඇති දත්ත ප්‍රමාණයක් සඳහා ඇල්ගොරිතමයක් සම්පූර්ණ කිරීමට කොපමණ කාලයක් ගතවේද යන්න බැලීමට භාවිතා කරයි. මෙම සංකීර්ණත්වය විස්තර කිරීම සඳහා, අපි විශාල O ගණිතමය අංකනය භාවිතා කරමු.මෙම අංකනය භාවිතා කරනුයේ දී ඇති යෙදවුම් ගණනකට ඇල්ගොරිතමයකට කොපමණ මෙහෙයුම් අවශ්‍යද යන්න විස්තර කරන ශ්‍රිතයක් සමඟිනි.

උදාහරණයක් ලෙස, "මෙම ඇල්ගොරිතමයට සංකීර්ණ O(some_function())" යැයි මා පවසන විට, එයින් අදහස් වන්නේ යම් දත්ත ප්‍රමාණයක් සැකසීමට ඇල්ගොරිතමයට යම්_function(a_certain_amount_of_data) මෙහෙයුම් අවශ්‍ය බවයි.

ඒ සමගම වැදගත් වන්නේ දත්ත ප්‍රමාණය නොවේ**, එසේ නොමැති නම් ** දත්ත පරිමාව වැඩි වීමත් සමඟ මෙහෙයුම් ගණන වැඩි වන ආකාරය. කාල සංකීර්ණත්වය නිශ්චිත මෙහෙයුම් සංඛ්‍යාවක් සපයන්නේ නැත, නමුත් ක්‍රියාත්මක කිරීමේ කාලය තක්සේරු කිරීමට හොඳ ක්‍රමයකි.

මෙම ප්‍රස්ථාරයෙන් ඔබට විවිධ වර්ගයේ ඇල්ගොරිතම කාල සංකීර්ණ සඳහා යෙදවුම් දත්ත ප්‍රමාණය එදිරිව මෙහෙයුම් ගණන දැකිය හැක. මම ඒවා ප්‍රදර්ශනය කිරීමට ලඝුගණක පරිමාණයක් භාවිතා කළෙමි. වෙනත් වචන වලින් කිවහොත්, දත්ත ප්‍රමාණය ඉක්මනින් බිලියන 1 සිට 1 දක්වා වැඩි වේ. අපට එය දැකිය හැකිය:

• O(1) හෝ නියත සංකීර්ණත්වය නියතව පවතී (එසේ නොමැති නම් එය නියත සංකීර්ණත්වය ලෙස හඳුන්වනු නොලැබේ).
• O(ලඝු(n)) බිලියන ගණනක දත්ත සමඟ පවා අඩු මට්ටමක පවතී.
• නරකම දුෂ්කරතාවය - O(n2), මෙහි මෙහෙයුම් ගණන වේගයෙන් වර්ධනය වේ.
• අනෙක් සංකූලතා දෙක ඉක්මනින් වැඩි වේ.

උදාහරණ

කුඩා දත්ත ප්‍රමාණයක් සමඟ, O(1) සහ O(n2) අතර වෙනස නොසැලකිය හැකිය. උදාහරණයක් ලෙස, මූලද්‍රව්‍ය 2000 ක් සැකසීමට අවශ්‍ය ඇල්ගොරිතමයක් ඔබ සතුව ඇතැයි සිතමු.

• O(1) ඇල්ගොරිතම ඔබට මෙහෙයුම් 1ක් වැය වේ
• O(log(n)) ඇල්ගොරිතම ඔබට මෙහෙයුම් 7ක් වැය වේ
• O(n) ඇල්ගොරිතම ඔබට මෙහෙයුම් 2ක් වැය වේ
• O(n*log(n)) ඇල්ගොරිතම ඔබට මෙහෙයුම් 14ක් වැය වේ
• O(n2) ඇල්ගොරිතම මඟින් ඔබට මෙහෙයුම් 4ක් වැය වේ

O(1) සහ O(n2) අතර වෙනස විශාල බව පෙනේ (මෙහෙයුම් මිලියන 4) නමුත් ඔබට උපරිම වශයෙන් 2 ms අහිමි වනු ඇත, ඔබේ ඇස් ඇසිපිය හෙළීමට කාලයයි. ඇත්ත වශයෙන්ම, නවීන ප්‍රොසෙසර වලට සැකසිය හැක තත්පරයකට මෙහෙයුම් මිලියන සිය ගණනක්. බොහෝ තොරතුරු තාක්ෂණ ව්‍යාපෘතිවල කාර්ය සාධනය සහ ප්‍රශස්තකරණය ප්‍රශ්නයක් නොවන්නේ එබැවිනි.

මා කී පරිදි, විශාල දත්ත ප්‍රමාණයක් සමඟ වැඩ කිරීමේදී මෙම සංකල්පය දැන ගැනීම තවමත් වැදගත් වේ. මෙවර ඇල්ගොරිතමයට මූලද්‍රව්‍ය 1 ක් සැකසීමට සිදුවුවහොත් (එය දත්ත සමුදායක් සඳහා එතරම් නොවේ):

• O(1) ඇල්ගොරිතම ඔබට මෙහෙයුම් 1ක් වැය වේ
• O(log(n)) ඇල්ගොරිතම ඔබට මෙහෙයුම් 14ක් වැය වේ
• O(n) ඇල්ගොරිතම මඟින් ඔබට මෙහෙයුම් 1ක් වැය වේ
• O(n*log(n)) ඇල්ගොරිතමයට ඔබට මෙහෙයුම් 14ක් වැය වේ
• O(n2) ඇල්ගොරිතම මඟින් ඔබට මෙහෙයුම් 1ක් වැය වේ

මම ගණිතය කර නැත, නමුත් O(n2) ඇල්ගොරිතම සමඟ ඔබට කෝපි එකක් (දෙකක් පවා) පානය කිරීමට කාලය ඇති බව මම කියමි. ඔබ දත්ත පරිමාවට තවත් 0 ක් එකතු කළහොත්, ඔබට නිදා ගැනීමට කාලය තිබේ.

අපි ගැඹුරට යමු

යොමුව සඳහා:

• හොඳ හැෂ් වගු සෙවීමක් O(1) හි මූලද්‍රව්‍යයක් සොයා ගනී.
• හොඳින් සමතුලිත ගසක් සෙවීම O(log(n)) හි ප්‍රතිඵල නිපදවයි.
• අරාවක් සෙවීම O(n) හි ප්‍රතිඵල නිපදවයි.
• හොඳම වර්ග කිරීමේ ඇල්ගොරිතම වල සංකීර්ණ O(n*log(n)) ඇත.
• නරක වර්ග කිරීමේ ඇල්ගොරිතමයක සංකීර්ණ O(n2) ඇත.

සටහන: පහත කොටස් වලින් අපි මෙම ඇල්ගොරිතම සහ දත්ත ව්‍යුහයන් දකිමු.

ඇල්ගොරිතම කාල සංකීර්ණතා වර්ග කිහිපයක් තිබේ:

• සාමාන්‍ය සිද්ධි දර්ශනය
• හොඳම අවස්ථාව
• සහ නරකම අවස්ථාව

කාල සංකීර්ණත්වය බොහෝ විට නරකම අවස්ථාවයි.

මම කතා කළේ ඇල්ගොරිතමයේ කාල සංකීර්ණත්වය ගැන පමණි, නමුත් සංකීර්ණත්වය ද අදාළ වේ:

• ඇල්ගොරිතමයේ මතක පරිභෝජනය
• තැටි I/O පරිභෝජන ඇල්ගොරිතම

ඇත්ත වශයෙන්ම, n2 ට වඩා නරක සංකූලතා ඇත, උදාහරණයක් ලෙස:

• n4: මෙය භයානකයි! සඳහන් කරන ලද සමහර ඇල්ගොරිතම වල මෙම සංකීර්ණත්වය ඇත.
• 3n: මෙය ඊටත් වඩා නරක ය! මෙම ලිපියේ මැදින් අප දකින ඇල්ගොරිතම වලින් එකක මෙම සංකීර්ණත්වය ඇත (සහ එය බොහෝ දත්ත සමුදායන්හි සැබවින්ම භාවිතා වේ).
• factorial n: කුඩා දත්ත ප්‍රමාණයකින් වුවද ඔබේ ප්‍රතිඵල ඔබට කිසිදා නොලැබෙනු ඇත.
• nn: ඔබ මෙම සංකීර්ණතාවයට මුහුණ දෙන්නේ නම්, මෙය සැබවින්ම ඔබගේ ක්‍රියාකාරකම් ක්ෂේත්‍රය දැයි ඔබෙන්ම අසාගත යුතුය...

සටහන: මම ඔබට විශාල O තනතුරේ සැබෑ නිර්වචනය ලබා දුන්නේ නැත, අදහසක් පමණි. ඔබට මෙම ලිපිය කියවිය හැකිය විකිපීඩියා සැබෑ (අසමමිතික) අර්ථ දැක්වීම සඳහා.

MergeSort

ඔබට එකතුවක් වර්ග කිරීමට අවශ්‍ය වූ විට ඔබ කරන්නේ කුමක්ද? කුමක් ද? ඔබ sort() ශ්‍රිතය අමතන්න... හරි, හොඳ පිළිතුරක්... නමුත් දත්ත සමුදායක් සඳහා, මෙම sort() ශ්‍රිතය ක්‍රියා කරන ආකාරය ඔබ තේරුම් ගත යුතුය.

හොඳ වර්ග කිරීමේ ඇල්ගොරිතම කිහිපයක් ඇත, එබැවින් මම වඩාත් වැදගත් දේ කෙරෙහි අවධානය යොමු කරමි: ඒකාබද්ධ වර්ගය. දත්ත වර්ග කිරීම දැන් ප්‍රයෝජනවත් වන්නේ මන්දැයි ඔබට නොතේරෙනු ඇත, නමුත් ඔබ විමසුම් ප්‍රශස්තිකරණ කොටසෙන් පසුව කළ යුතුය. එපමනක් නොව, ඒකාබද්ධ කිරීමේ වර්ග කිරීම අවබෝධ කර ගැනීම අපට පසුව හැඳින්වෙන පොදු දත්ත සමුදාය සම්බන්ධ කිරීමේ මෙහෙයුම තේරුම් ගැනීමට උපකාරී වනු ඇත ඒකාබද්ධ කිරීම එක්වන්න (ඒකාබද්ධ සංගමය).

ඒකාබද්ධ කරන්න

බොහෝ ප්‍රයෝජනවත් ඇල්ගොරිතම මෙන්, ඒකාබද්ධ කිරීමේ වර්ග කිරීම උපක්‍රමයක් මත රඳා පවතී: N/2 ප්‍රමාණයේ වර්ග කළ අරා 2ක් N-මූලද්‍රව්‍ය අනුපිළිවෙලට සකසන ලද අරාවකට ඒකාබද්ධ කිරීම සඳහා වැය වන්නේ N මෙහෙයුම් සඳහා පමණි. මෙම මෙහෙයුම ඒකාබද්ධ කිරීම ලෙස හැඳින්වේ.

සරල උදාහරණයකින් මෙයින් අදහස් කරන්නේ කුමක්දැයි බලමු:

මෙම රූපයෙන් දැක්වෙන්නේ අවසාන වශයෙන් වර්ග කරන ලද 8-මූලද්‍රව්‍ය අරාව සෑදීමට, ඔබට අවශ්‍ය වන්නේ 2-මූලද්‍රව්‍ය අරා මත එක් වරක් පමණක් පුනරාවර්තනය කළ යුතු බවයි. 4-මූලද්‍රව්‍ය අරා දෙකම දැනටමත් වර්ග කර ඇති බැවින්:

• 1) ඔබ වත්මන් මූලද්‍රව්‍ය දෙකම අරා දෙකකින් සංසන්දනය කරයි (ආරම්භයේදී ධාරාව = පළමු)
• 2) ඉන්පසු කුඩාම එක ගන්න, එය මූලද්‍රව්‍ය 8ක අරාවකට දමන්න
• 3) සහ ඔබ කුඩාම මූලද්‍රව්‍යය ගත් අරාවේ ඊළඟ මූලද්‍රව්‍ය වෙත යන්න
• ඔබ එක් අරාවක අවසාන මූලද්‍රව්‍යයට ළඟා වන තෙක් 1,2,3 නැවත නැවත කරන්න.
• එවිට ඔබ අනෙකුත් අරාවේ ඉතිරි මූලද්‍රව්‍ය 8 මූලද්‍රව්‍ය අරාවකට දමන්න.

4-මූලද්‍රව්‍ය අරා දෙකම වර්ග කර ඇති නිසා මෙය ක්‍රියා කරයි, එබැවින් ඔබට එම අරාව තුළ "ආපසු යන්න" අවශ්‍ය නොවේ.

දැන් අපි උපක්‍රමය තේරුම් ගත් පසු, ඒකාබද්ධ කිරීම සඳහා මගේ ව්‍යාජ කේතය මෙන්න:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Merge sort මගින් ගැටලුවක් කුඩා ගැටළු වලට කැඩී පසුව මුල් ගැටලුවේ ප්‍රතිඵලය ලබා ගැනීම සඳහා කුඩා ගැටළු වල ප්‍රතිඵල සොයා ගනී (සටහන: මෙම ඇල්ගොරිතම බෙදීම සහ ජය ගැනීම ලෙස හැඳින්වේ). ඔබට මෙම ඇල්ගොරිතම නොතේරෙන්නේ නම්, කරදර නොවන්න; මට ඒක මුලින්ම දැක්කම තේරුනේ නෑ. එය ඔබට උදව් කළ හැකි නම්, මම මෙම ඇල්ගොරිතම ද්වි-අදියර ඇල්ගොරිතමයක් ලෙස දකිමි:

• අංශ අදියර, එහිදී අරාව කුඩා අරාවකට බෙදා ඇත
• විශාල අරාවක් සෑදීමට කුඩා අරාවන් (යුනියන් භාවිතා කරමින්) එකතු කරන අවස්ථාව වර්ගීකරණ අදියර වේ.

බෙදීමේ අදියර

බෙදීමේ අදියරේදී, අරාව පියවර 3 කින් ඒකීය අරා වලට බෙදා ඇත. විධිමත් පියවර ගණන log(N) වේ (N=8, log(N) = 3).

මම මෙය දන්නේ කෙසේද?

මම දක්ෂයෙක්! වචනයෙන් - ගණිතය. අදහස නම් සෑම පියවරක්ම මුල් අරාවේ ප්‍රමාණය 2න් බෙදයි. පියවර ගණන යනු ඔබට මුල් අරාව දෙකට බෙදිය හැකි වාර ගණනයි. ලඝුගණකයේ නියම නිර්වචනය මෙයයි (පාදම 2).

වර්ග කිරීමේ අදියර

වර්ග කිරීමේ අදියරේදී, ඔබ ඒකීය (තනි-මූලද්‍රව්‍ය) අරාවන්ගෙන් ආරම්භ කරන්න. සෑම පියවරකදීම ඔබ ඒකාබද්ධ කිරීමේ මෙහෙයුම් කිහිපයක් යොදන අතර සම්පූර්ණ පිරිවැය N = 8 මෙහෙයුම් වේ:

• පළමු අදියරේදී ඔබට මෙහෙයුම් 4 බැගින් වැය වන ඒකාබද්ධ කිරීම් 2 ක් ඇත
• දෙවන පියවරේදී ඔබට මෙහෙයුම් 2 බැගින් වැය වන ඒකාබද්ධ කිරීම් 4ක් ඇත
• තුන්වන පියවරේදී ඔබට මෙහෙයුම් 1ක් වැය වන ඒකාබද්ධ කිරීම් 8ක් ඇත

ලඝු (N) පියවර ඇති බැවින්, මුළු පිරිවැය එන් * log(N) මෙහෙයුම්.

ඒකාබද්ධ කිරීමේ ආකාරයේ වාසි

මෙම ඇල්ගොරිතම මෙතරම් බලවත් වන්නේ ඇයි?

නිසා:

• මතක පියසටහන අඩු කිරීමට ඔබට එය වෙනස් කළ හැක, එවිට ඔබ නව අරාවන් නිර්මාණය නොකරන නමුත් ආදාන අරාව කෙලින්ම වෙනස් කළ හැක.

සටහන: මෙම වර්ගයේ ඇල්ගොරිතම ලෙස හැඳින්වේ in-ස්ථානය (අමතර මතකය නොමැතිව වර්ග කිරීම).

• ඔබට සැලකිය යුතු තැටි I/O උඩින් බරක් නොගෙන එකවර තැටි ඉඩ සහ කුඩා මතක ප්‍රමාණයක් භාවිතා කිරීමට එය වෙනස් කළ හැක. දැනට සකසමින් පවතින කොටස් පමණක් මතකයට පැටවීමයි අදහස. ඔබට මෙගාබයිට් 100ක මතක බෆරයක් සහිත බහු-ගිගාබයිට් වගුවක් වර්ග කිරීමට අවශ්‍ය වූ විට මෙය වැදගත් වේ.

සටහන: මෙම වර්ගයේ ඇල්ගොරිතම ලෙස හැඳින්වේ බාහිර වර්ගය.

• බහු ක්‍රියාවලි/නූල්/සේවාදායක මත ධාවනය කිරීමට ඔබට එය වෙනස් කළ හැක.

උදාහරණයක් ලෙස, බෙදා හරින ලද ඒකාබද්ධ වර්ග කිරීම ප්‍රධාන සංරචක වලින් එකකි Hadoop (එය විශාල දත්තවල ව්‍යුහයකි).

• මෙම ඇල්ගොරිතමයට ඊයම් රත්රන් බවට පත් කළ හැකිය (ඇත්ත වශයෙන්ම!).

මෙම වර්ග කිරීමේ ඇල්ගොරිතම බොහෝ (සියල්ලම නොවේ නම්) දත්ත සමුදායන්හි භාවිතා වේ, නමුත් එය එකම එක නොවේ. ඔබට වැඩි විස්තර දැන ගැනීමට අවශ්‍ය නම්, ඔබට මෙය කියවිය හැකිය පර්යේෂණ කටයුතු, එය පොදු දත්ත සමුදා වර්ග කිරීමේ ඇල්ගොරිතමවල වාසි සහ අවාසි සාකච්ඡා කරයි.

Array, Tree සහ Hash Table

දැන් අපි කාලය සංකීර්ණත්වය සහ වර්ග කිරීම පිළිබඳ අදහස තේරුම් ගෙන ඇති නිසා, මම ඔබට දත්ත ව්‍යුහ 3ක් ගැන කිව යුතුයි. මෙය වැදගත් වන්නේ ඔවුන් නිසාය නවීන දත්ත සමුදායේ පදනම වේ. මම සංකල්පය ද හඳුන්වා දෙන්නෙමි දත්ත සමුදා දර්ශකය.

අරාව

ද්විමාන අරාවක් යනු සරලම දත්ත ව්‍යුහයයි. වගුවක් අරාවක් ලෙස සැලකිය හැකිය. උදාහරණ වශයෙන්:

මෙම 2-මාන අරාව පේළි සහ තීරු සහිත වගුවකි:

• සෑම පේළියක්ම ආයතනයක් නියෝජනය කරයි
• තීරු වස්තුව විස්තර කරන ගුණාංග ගබඩා කරයි.
• සෑම තීරුවක්ම නිශ්චිත වර්ගයක දත්ත ගබඩා කරයි (පූර්ණ සංඛ්‍යාව, නූල්, දිනය...).

දත්ත ගබඩා කිරීම සහ දෘශ්‍යකරණය කිරීම සඳහා මෙය පහසු වේ, කෙසේ වෙතත්, ඔබට නිශ්චිත අගයක් සොයා ගැනීමට අවශ්‍ය වූ විට, මෙය සුදුසු නොවේ.

උදාහරණයක් ලෙස, ඔබට එක්සත් රාජධානියේ සේවය කරන සියලුම පිරිමින් සොයා ගැනීමට අවශ්‍ය නම්, එම පේළිය එක්සත් රාජධානියට අයත් දැයි තීරණය කිරීමට ඔබ එක් එක් පේළිය දෙස බැලිය යුතුය. එය ඔබට N ගනුදෙනු සඳහා වැය වේකොහෙද N - පේළි ගණන, එය නරක නැත, නමුත් වේගවත් මාර්ගයක් තිබිය හැකිද? දැන් අපට ගස් ගැන හුරුපුරුදු වීමට කාලයයි.

සටහන: බොහෝ නවීන දත්ත සමුදායන් වගු කාර්යක්ෂමව ගබඩා කිරීම සඳහා දිගු අරා සපයයි: ගොඩ-සංවිධානාත්මක වගු සහ දර්ශක-සංවිධානාත්මක වගු. නමුත් මෙය තීරු සමූහයක නිශ්චිත කොන්දේසියක් ඉක්මනින් සොයා ගැනීමේ ගැටලුව වෙනස් නොකරයි.

දත්ත සමුදා ගස සහ දර්ශකය

ද්විමය සෙවුම් ගසක් යනු විශේෂ දේපලක් සහිත ද්විමය ගසකි, එක් එක් නෝඩයේ යතුර විය යුත්තේ:

• වම් උප වෘක්ෂයේ ගබඩා කර ඇති සියලුම යතුරු වලට වඩා විශාලයි
• දකුණු උප වෘක්ෂයේ ගබඩා කර ඇති සියලුම යතුරු වලට වඩා අඩුය

අපි බලමු මේකෙන් අදහස් කරන්නේ මොකක්ද කියලා

අදහස

මෙම ගසෙහි N = 15 මූලද්රව්ය ඇත. අපි කියමු මම 208 සොයනවා කියලා:

• මම ආරම්භ කරන්නේ යතුර 136 වන මූලයෙන්. 136<208 සිට, මම නෝඩ් 136 හි දකුණු උප ට්‍රී එක දෙස බලමි.
• 398>208 එබැවින් මම නෝඩ් 398 හි වම් උප වෘක්ෂය දෙස බලමි
• 250>208 එබැවින් මම නෝඩ් 250 හි වම් උප වෘක්ෂය දෙස බලමි
• 200<208, ඒ නිසා මම node 200 හි දකුණු උප වෘක්ෂය දෙස බලමි. නමුත් 200 ට නිවැරදි උප ගසක් නොමැත, අගය නොපවතී (මක්නිසාද එය පවතී නම්, එය නිවැරදි උපට්‍රී 200 හි පවතිනු ඇත).

දැන් අපි හිතමු මම 40ක් හොයනවා කියලා

• මම ආරම්භ කරන්නේ යතුර 136 වන මූලයෙන්. 136 > 40 සිට, මම node 136 හි වම් උප වෘක්ෂය දෙස බලමි.
• 80 > 40, එබැවින් මම node 80 හි වම් උප වෘක්ෂය දෙස බලමි
• 40= 40, node පවතී. මම නෝඩය තුළ ඇති පේළි හැඳුනුම්පත ලබාගෙන (පින්තූරයේ නොවේ) ලබා දී ඇති පේළි හැඳුනුම්පත සඳහා වගුව දෙස බලමි.
• පේළි හැඳුනුම්පත දැන ගැනීමෙන් මට වගුවේ ඇති දත්ත හරියටම දැන ගැනීමට ඉඩ සලසයි, එබැවින් මට එය ක්ෂණිකව ලබා ගත හැක.

අවසානයේදී, සෙවීම් දෙකටම ගස තුළ ඇති මට්ටම් ගණන මට වැය වේ. ඔබ ඒකාබද්ධ කිරීම ගැන කොටස හොඳින් කියවා බැලුවහොත්, log(N) මට්ටම් ඇති බව ඔබට පෙනෙනු ඇත. එය හැරෙනවා, සෙවුම් පිරිවැය ලොගය (N), නරක නැහැ!

අපි අපේ ගැටලුව වෙත ආපසු යමු

නමුත් මෙය ඉතා වියුක්තයි, එබැවින් අපි අපගේ ගැටලුව වෙත ආපසු යමු. සරල නිඛිලයක් වෙනුවට, පෙර වගුවේ කෙනෙකුගේ රට නියෝජනය කරන තන්තුවක් සිතන්න. මේසයේ "රට" ක්ෂේත්‍රය (තීරුව 3) අඩංගු ගසක් ඔබ සතුව ඇතැයි කියමු:

• UK වල වැඩ කරන්නේ කවුද කියලා දැනගන්න ඕනේ නම්
• මහා බ්‍රිතාන්‍යය නියෝජනය කරන නෝඩය ලබා ගැනීමට ඔබ ගස දෙස බලන්න
• "UKnode" තුළ ඔබ එක්සත් රාජධානියේ සේවක වාර්තා ඇති ස්ථානය සොයා ගනු ඇත.

ඔබ අරාව සෘජුවම භාවිතා කරන්නේ නම් මෙම සෙවීමට N මෙහෙයුම් වෙනුවට log(N) මෙහෙයුම් සඳහා වැය වේ. ඔබ දැන් ඉදිරිපත් කළ දේ දත්ත සමුදා දර්ශකය.

ඔබට යතුරු (එනම් ක්ෂේත්‍ර කණ්ඩායම්) සංසන්දනය කිරීමට ශ්‍රිතයක් ඇති තාක් ඕනෑම ක්ෂේත්‍ර සමූහයක් සඳහා (තන්තුව, අංකය, රේඛා 2, අංකය සහ තන්තුව, දිනය...) දර්ශක ගසක් සෑදිය හැක. යතුරු අතර පිළිවෙල (දත්ත සමුදායේ ඇති ඕනෑම මූලික වර්ග සඳහා මෙය සිදු වේ).

B+Tree Index

මෙම ගස නිශ්චිත අගයක් ලබා ගැනීම සඳහා හොඳින් ක්‍රියා කරන අතර, ඔබට අවශ්‍ය විට විශාල ගැටලුවක් තිබේ අගයන් දෙකක් අතර බහු මූලද්‍රව්‍ය ලබා ගන්න. මෙය O(N) සඳහා වැය වනු ඇත, මන්ද ඔබට ගසෙහි ඇති එක් එක් නෝඩය දෙස බලා එය මෙම අගයන් දෙක අතර තිබේ දැයි පරීක්ෂා කිරීමට සිදුවනු ඇත (උදා: ගසේ ඇණවුම් කළ ගමන් මාර්ගයක් සමඟ). එපමණක් නොව, ඔබ සම්පූර්ණ ගස කියවිය යුතු බැවින් මෙම මෙහෙයුම තැටිය I/O හිතකාමී නොවේ. කාර්යක්ෂමව ක්‍රියාත්මක කිරීමට ක්‍රමයක් අප සොයා ගත යුතුය පරාසයක ඉල්ලීම. මෙම ගැටළුව විසඳීම සඳහා නවීන දත්ත සමුදායන් B+Tree නමින් පෙර ගසෙහි නවීකරණය කරන ලද අනුවාදයක් භාවිතා කරයි. B+Tree ගසක:

• පහළම නෝඩ් (කොළ) පමණි ගබඩා තොරතුරු (අදාළ වගුවේ පේළි පිහිටීම)
• ඉතිරි නෝඩ් මෙහි ඇත මාර්ගගත කිරීම සඳහා නිවැරදි නෝඩයට සෙවීම අතරතුර.

ඔබට පෙනෙන පරිදි, මෙහි තවත් නෝඩ් (දෙවරක්) ඇත. ඇත්ත වශයෙන්ම, ඔබට අමතර නෝඩ්, "තීරණ නෝඩ්" ඇත, එය ඔබට නිවැරදි නෝඩය සොයා ගැනීමට උපකාරී වනු ඇත (ආශ්‍රිත වගුවේ පේළි පිහිටීම ගබඩා කරයි). නමුත් සෙවුම් සංකීර්ණත්වය තවමත් O(log(N)) වේ (තවත් එක මට්ටමක් ඇත). ලොකු වෙනස ඒකයි පහළ මට්ටමේ ඇති නෝඩ් ඔවුන්ගේ අනුප්රාප්තිකයන්ට සම්බන්ධ වේ.

මෙම B+Tree සමඟ, ඔබ 40 සහ 100 අතර අගයන් සොයන්නේ නම්:

• ඔබට අවශ්‍ය වන්නේ ඔබ පෙර ගස සමඟ කළාක් මෙන් 40 (හෝ 40 නොපවතියි නම් 40 ට පසු ආසන්නතම අගය) සොයා බැලීමයි.
• ඉන්පසු ඔබ 40ට ළඟා වන තෙක් සෘජු උරුමක්කාර සබැඳි භාවිතයෙන් උරුමක්කාරයන් 100ක් එකතු කරන්න.

ඔබ M අනුප්‍රාප්තිකයින් සොයා ගත් බවත් ගසට N නෝඩ් ඇති බවත් කියමු. නිශ්චිත නෝඩයක් සෙවීමට පෙර ගස මෙන් ලොග් (N) වැය වේ. නමුත් ඔබ මෙම නෝඩය ලබා ගත් පසු, ඔබට M මෙහෙයුම් වලදී ඔවුන්ගේ අනුප්‍රාප්තිකයින් වෙත යොමු කිරීම් සමඟ M අනුප්‍රාප්තිකයින් ලැබෙනු ඇත. මෙම සෙවීමට වැය වන්නේ M+log(N) පමණි පෙර ගසේ N මෙහෙයුම් හා සසඳන විට මෙහෙයුම්. එපමණක් නොව, ඔබට සම්පූර්ණ ගස කියවීමට අවශ්‍ය නැත (M+log(N) nodes පමණි), එනම් අඩු තැටි භාවිතයයි. M කුඩා (උදා පේළි 200) සහ N විශාල (පේළි 1) නම්, විශාල වෙනසක් ඇත.

නමුත් මෙහි නව ගැටළු තිබේ (නැවත!). ඔබ දත්ත සමුදායේ පේළියක් එකතු කරන්නේ නම් හෝ මකා දැමුවහොත් (සහ ඒ නිසා සම්බන්ධිත B+Tree දර්ශකයේ):

• ඔබ B+Tree තුළ ඇති නෝඩ් අතර පිළිවෙලක් පවත්වා ගත යුතුය, එසේ නොමැතිනම් ඔබට වර්ග නොකළ ගසක් තුළ ඇති නෝඩ් සොයා ගැනීමට නොහැකි වනු ඇත.
• ඔබට හැකි අවම මට්ටම් සංඛ්‍යාව B+Tree හි තබාගත යුතුය, එසේ නොමැතිනම් O(log(N)) කාල සංකීර්ණතාව O(N) බවට පත්වේ.

වෙනත් වචන වලින් කිවහොත්, B+Tree ස්වයං-ඇණවුම් සහ සමබර විය යුතුය. වාසනාවකට මෙන්, මෙය ස්මාර්ට් මකා දැමීම සහ ඇතුළු කිරීමේ මෙහෙයුම් සමඟ කළ හැකිය. නමුත් මෙය පිරිවැයකින් පැමිණේ: B+ ගසක ඇතුළත් කිරීම් සහ මකාදැමීම් පිරිවැය O(log(N)) වේ. ඒකයි සමහර අය එහෙම අහලත් ඇති බොහෝ දර්ශක භාවිතා කිරීම හොඳ අදහසක් නොවේ. ඇත්තටම, ඔබ වගුවක පේළියක් වේගයෙන් ඇතුළු කිරීම/යාවත්කාලීන කිරීම/මැකීම මන්දගාමී කරයිමන්ද දත්ත සමුදාය එක් එක් දර්ශකය සඳහා මිල අධික O(log(N)) මෙහෙයුමක් භාවිතා කරමින් වගුවේ දර්ශක යාවත්කාලීන කිරීමට අවශ්‍ය වේ. එපමනක් නොව, දර්ශක එකතු කිරීම යනු වැඩි වැඩ බරකි ගනුදෙනු කළමනාකරු (ලිපියේ අවසානයේ විස්තර කෙරේ).

වැඩි විස්තර සඳහා, ඔබට විකිපීඩියා ලිපිය බලන්න පුළුවන් B+ගස. ඔබට දත්ත ගබඩාවක B+Tree ක්‍රියාත්මක කිරීමේ උදාහරණයක් අවශ්‍ය නම්, බලන්න මෙම ලිපිය и මෙම ලිපිය ප්‍රමුඛ MySQL සංවර්ධකයෙකුගෙන්. ඔවුන් දෙදෙනාම InnoDB (MySQL එන්ජිම) දර්ශක හසුරුවන ආකාරය කෙරෙහි අවධානය යොමු කරයි.

සටහන: පාඨකයෙකු මට පැවසුවේ, පහත් මට්ටමේ ප්‍රශස්තකරණයන් හේතුවෙන්, B+ ගස සම්පූර්ණයෙන්ම සමතුලිත විය යුතු බවයි.

Hashtable

අපගේ අවසාන වැදගත් දත්ත ව්‍යුහය වන්නේ හැෂ් වගුවයි. ඔබට ඉක්මනින් අගයන් සෙවීමට අවශ්‍ය විට මෙය ඉතා ප්‍රයෝජනවත් වේ. එපමනක් නොව, හැෂ් වගුවක් අවබෝධ කර ගැනීම, හෑෂ් ජොයින් (hash join) ලෙස හැඳින්වෙන පොදු දත්ත සමුදා සම්බන්ධ කිරීමේ මෙහෙයුමක් පසුව තේරුම් ගැනීමට අපට උපකාර වනු ඇත. hash join) මෙම දත්ත ව්‍යුහය සමහර අභ්‍යන්තර දේවල් ගබඩා කිරීමට ද දත්ත සමුදාය භාවිතා කරයි (උදා. අගුළු මේසය හෝ බෆර් තටාකය, අපි මේ සංකල්ප දෙකම පසුව බලමු).

හැෂ් වගුවක් යනු මූලද්‍රව්‍යයක් එහි යතුරෙන් ඉක්මනින් සොයා ගන්නා දත්ත ව්‍යුහයකි. හැෂ් වගුවක් තැනීම සඳහා ඔබ නිර්වචනය කළ යුතුය:

• යතුර ඔබේ මූලද්රව්ය සඳහා
• හැෂ් ශ්‍රිතය යතුරු සඳහා. ගණනය කරන ලද යතුරු හෑෂ් මඟින් මූලද්‍රව්‍යවල පිහිටීම ලබා දෙයි (නැමති කොටස් ).
• යතුරු සංසන්දනය කිරීමේ කාර්යය. ඔබ නිවැරදි කොටස සොයාගත් පසු, මෙම සංසන්දනය භාවිතා කර කොටස තුළ ඔබ සොයන මූලද්‍රව්‍යය සොයාගත යුතුය.

සරල උදාහරණයක්

අපි පැහැදිලි උදාහරණයක් ගනිමු:

මෙම හැෂ් වගුවේ කොටස් 10ක් ඇත. මම කම්මැලි නිසා, මම කොටස් 5 ක් පමණක් පින්තාරු කළෙමි, නමුත් ඔබ දක්ෂ බව මම දනිමි, එබැවින් මම ඔබට අනෙක් 5 තනිවම පින්තාරු කිරීමට ඉඩ දෙමි. මම යතුරේ 10 මොඩියුලය හැෂ් ශ්‍රිතයක් භාවිතා කළෙමි. වෙනත් වචන වලින් කිවහොත්, මම එහි කොටස සොයා ගැනීමට මූලද්‍රව්‍යයේ යතුරේ අවසාන ඉලක්කම් පමණක් ගබඩා කරමි:

• අවසාන ඉලක්කම් 0 නම්, මූලද්රව්යය 0 කොටසට වැටේ,
• අවසාන ඉලක්කම් 1 නම්, මූලද්රව්යය 1 කොටසට වැටේ,
• අවසාන ඉලක්කම් 2 නම්, මූලද්රව්යය 2 ප්රදේශයට වැටේ,
• ...

මම භාවිතා කළ සංසන්දනාත්මක කාර්යය වන්නේ නිඛිල දෙකක් අතර සමානාත්මතාවයයි.

ඔබට මූලද්‍රව්‍ය 78 ලබා ගැනීමට අවශ්‍ය යැයි සිතමු:

• හැෂ් වගුව 78 සඳහා හැෂ් කේතය ගණනය කරයි, එය 8 වේ.
• හැෂ් වගුව 8 වන කොටස දෙස බලන අතර එය සොයා ගන්නා පළමු මූලද්‍රව්‍යය 78 වේ.
• ඇය 78 අයිතමය ඔබ වෙත ආපසු එයි
• සෙවීම සඳහා වැය වන්නේ මෙහෙයුම් 2 ක් පමණි (එකක් හැෂ් අගය ගණනය කිරීමට සහ අනෙක කොටස තුළ ඇති මූලද්‍රව්‍යය සොයා බැලීමට).

දැන් අපි කියමු ඔබට මූලද්‍රව්‍ය 59 ලබා ගැනීමට අවශ්‍ය බව:

• හැෂ් වගුව 59 සඳහා හැෂ් කේතය ගණනය කරයි, එය 9 වේ.
• හැෂ් වගුව 9 වන කොටසෙහි සෙවුම් කරයි, පළමු මූලද්‍රව්‍යය 99 වේ. 99!=59 සිට, මූලද්‍රව්‍ය 99 වලංගු මූලද්‍රව්‍යයක් නොවේ.
• එකම තර්කනය භාවිතා කරමින්, දෙවන මූලද්‍රව්‍යය (9), තෙවන (79), ..., අවසාන (29) ගනු ලැබේ.
• මූලද්රව්යය හමු නොවීය.
• සෙවීම සඳහා මෙහෙයුම් 7 ක් වැය විය.

හොඳ හැෂ් ක්‍රියාකාරිත්වය

ඔබට පෙනෙන පරිදි, ඔබ සොයන වටිනාකම අනුව, පිරිවැය සමාන නොවේ!

මම දැන් යතුරේ හැෂ් ශ්‍රිතය මොඩියුල 1 වෙනස් කළහොත් (එනම්, අවසාන ඉලක්කම් 000 ගෙන), 000 කොටසේ මූලද්‍රව්‍ය නොමැති බැවින් දෙවන සෙවීම සඳහා වැය වන්නේ මෙහෙයුම 6ක් පමණි. සැබෑ අභියෝගය වන්නේ ඉතා කුඩා මූලද්‍රව්‍ය සංඛ්‍යාවක් අඩංගු බාල්දි නිර්මාණය කරන හොඳ හැෂ් ශ්‍රිතයක් සොයා ගැනීමයි.

මගේ උදාහරණයේ, හොඳ හැෂ් ශ්‍රිතයක් සොයා ගැනීම පහසුය. නමුත් මෙය සරල උදාහරණයකි, යතුර වන විට හොඳ හැෂ් ශ්‍රිතයක් සොයා ගැනීම වඩාත් අපහසු වේ:

• තන්තුව (උදාහරණයක් ලෙස - අවසාන නම)
• පේළි 2 (උදාහරණයක් ලෙස - අවසාන නම සහ මුල් නම)
• පේළි 2 සහ දිනය (උදාහරණයක් ලෙස - අවසන් නම, මුල් නම සහ උපන් දිනය)
• ...

හොඳ හැෂ් ශ්‍රිතයක් සමඟ, හැෂ් වගු සෙවීම් සඳහා O(1) වැය වේ.

Array vs හැෂ් වගුව

array එකක් භාවිතා නොකරන්නේ ඇයි?

හ්ම්, හොඳ ප්‍රශ්නයක්.

• හැෂ් වගුව විය හැක අර්ධ වශයෙන් මතකයට පටවා ඇත, සහ ඉතිරි කොටස් තැටියේ පැවතිය හැක.
• අරාවක් සමඟ ඔබ මතකයේ එක ළඟ අවකාශය භාවිතා කළ යුතුය. ඔබ විශාල මේසයක් පටවන්නේ නම් ප්රමාණවත් අඛණ්ඩ ඉඩක් සොයා ගැනීම ඉතා අපහසුය.
• හැෂ් වගුවක් සඳහා, ඔබට අවශ්‍ය යතුර තෝරාගත හැක (උදාහරණයක් ලෙස, රට සහ පුද්ගලයාගේ අවසාන නම).

වැඩි විස්තර සඳහා, ඔබට ලිපිය කියවිය හැකිය ජාවාහැෂ්මැප්, හෑෂ් වගුවක් කාර්යක්ෂමව ක්‍රියාත්මක කිරීමකි; මෙම ලිපියෙන් ආවරණය වන සංකල්ප තේරුම් ගැනීමට ඔබට ජාවා තේරුම් ගැනීමට අවශ්‍ය නොවේ.

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