ද්විමය සෙවුම සහ අනෙකුත් සෙවුම් යෝජනා ක්‍රම කෙසේද?
එවැනි එක් එක් මෙහෙයුම සඳහා O(n) කාලයක් ගත කරමින්, ඇතුළත් කිරීම් සහ මකාදැමීමේ මෙහෙයුම් නැවත ලබා ගැනීම සමඟ අන්තර් සම්බන්ධිත වන විට ද්විමය සෙවුම් සහිත අනුපිළිවෙලට අරා ඉතා අකාර්යක්ෂම විසඳුමකි. මීට අමතරව, විශේෂයෙන් මූලද්‍රව්‍ය බොහෝ විට අරාව තුළට ඇතුළු කරන විට වර්ග කළ අරාව මතක භාවිතය සංකීර්ණ කළ හැකිය. වඩාත් කාර්යක්ෂම ඇතුළත් කිරීම් සහ මකාදැමීමට සහාය වන වෙනත් දත්ත ව්‍යුහයන් තිබේ. ද්විමය සෙවුම නිවැරදිව ගැලපීම සහ සාමාජිකත්වය සැකසීමට භාවිතා කළ හැක (ඉලක්ක අගයක් අගයන් එකතුවක තිබේද යන්න තීරණය කිරීම). වේගවත් නිවැරදි ගැලපීම සහ සාමාජිකත්වය සැකසීමට සහාය වන දත්ත ව්‍යුහයන් ඇත. කෙසේ වෙතත්, වෙනත් බොහෝ සෙවුම් යෝජනා ක්‍රම මෙන් නොව, ද්විමය සෙවීම කාර්යක්ෂම ආසන්න ගැලපීම සඳහා භාවිතා කළ හැක, සාමාන්‍යයෙන් අගයන්හි වර්ගය හෝ ව්‍යුහය නොසලකා O(log n) කාලය තුළ එවැනි ගැලපීම් සිදු කරයි. මීට අමතරව, කුඩාම සහ විශාලතම මූලද්‍රව්‍ය සොයා ගැනීම වැනි සමහර මෙහෙයුම් ඇත, ඒවා වර්ග කළ අරාවක් මත කාර්යක්ෂමව සිදු කළ හැක. රේඛීය සෙවීම: රේඛීය සෙවීම යනු ඉලක්ක අගය සොයා ගන්නා තෙක් සෑම වාර්තාවක්ම පරීක්ෂා කරන සරල සෙවුම් ඇල්ගොරිතමයකි. රේඛීය සෙවුම සම්බන්ධිත ලැයිස්තුවක් මත සිදු කළ හැක, එය අරාවකට වඩා වේගයෙන් ඇතුළු කිරීමට සහ මකා දැමීමට ඉඩ සලසයි. ද්වීමය සෙවුම රේඛීය සෙවීමට වඩා වේගවත් වේ, අරාව කෙටි නම් හැර, අරාව කලින් වර්ග කළ යුතුය. Quicksort සහ merge sort වැනි මූලද්‍රව්‍ය සංසන්දනය කිරීම මත පදනම් වූ සියලුම වර්ග කිරීමේ ඇල්ගොරිතම සඳහා, නරකම අවස්ථාවක අවම වශයෙන් O(nlog n) සැසඳීම් අවශ්‍ය වේ. රේඛීය සෙවුම මෙන් නොව, කාර්යක්ෂම ආසන්න ගැලපීම සඳහා ද්විමය සෙවුම භාවිතා කළ හැක. වර්ග කළ අරාවක් මත කාර්යක්ෂමව කළ හැකි නමුත් වර්ග නොකළ අරාවක කුඩාම සහ විශාලතම මූලද්‍රව්‍යය සෙවීම වැනි මෙහෙයුම් තිබේ. ගස්: ද්විමය සෙවුම් ගස් සොයන්නේ ද්විමය සෙවීමට සමාන ඇල්ගොරිතමයක් භාවිතා කරමිනි. ද්විමය සෙවුම් ගසක් යනු ද්විමය සෙවීමේ මූලධර්මය මත ක්‍රියා කරන ද්විමය ගස් දත්ත ව්‍යුහයකි. ගසෙහි වාර්තා අනුපිළිවෙලට සකස් කර ඇති අතර, සාමාන්‍ය ලඝුගණක කාලයක් ගත කරමින්, ද්විමය සෙවුමට සමාන ඇල්ගොරිතමයක් භාවිතයෙන් ගසෙහි ඇති සෑම වාර්තාවක්ම සෙවිය හැක. ද්විමය සෙවුම් ගස්වල ඇතුළත් කිරීම සහ මකා දැමීම සඳහා සාමාන්‍ය ලඝුගණක කාලයක් අවශ්‍ය වේ. මෙය රේඛීය කාල ඇතුළත් කිරීම සහ වර්ග කළ අරා මකාදැමීමට වඩා වේගවත් විය හැකි අතර, පරාසය සහ ආසන්න විමසුම් ඇතුළුව වර්ග කළ අරාවක කළ හැකි සියලුම මෙහෙයුම් සිදු කිරීමේ හැකියාව ද්විමය ගස් රඳවා තබා ගනී. කෙසේ වෙතත්, ද්විමය සෙවුම් ගස් බොහෝ විට අසම්පූර්ණ ලෙස සමතුලිත වන බැවින් ද්විමය සෙවීම සාමාන්‍යයෙන් සෙවුම් සඳහා වඩාත් කාර්යක්ෂම වේ, ද්විමය සෙවීමට වඩා තරමක් නරක කාර්ය සාධනයක් ඇති කරයි. මෙය සමතුලිත ද්විමය සෙවුම් ගස්, තමන්ගේම නෝඩ් සමතුලිත කරන ද්විමය සෙවුම් ගස් සඳහා පවා අදාළ වේ, මන්ද ඔවුන් කලාතුරකින් හැකි අවම මට්ටම් සහිත ගසක් නිපදවන බැවිනි. සමතුලිත ද්විමය සෙවුම් ගස් හැර, දරුවන් දෙදෙනෙකු සිටින අභ්‍යන්තර නෝඩ් කිහිපයක් සමඟ ගස දැඩි ලෙස අසමතුලිත විය හැක, එහි ප්‍රතිඵලයක් ලෙස සාමාන්‍ය සහ නරකම සෙවුම් කාලය n සංසන්දනය වෙත ළඟා වේ. ද්විමය සෙවුම් ගස් වර්ග කළ අරාවලට වඩා වැඩි ඉඩක් ගනී. ද්විමය සෙවුම් ගස් දෘඪ තැටිවල ගබඩා කර ඇති බාහිර මතකය තුළ වේගවත් සෙවීමට ඉඩ සලසයි, මන්ද ද්විමය සෙවුම් ගස් ගොනු පද්ධති තුළ කාර්යක්ෂමව ව්‍යුහගත කළ හැකිය. B-tree මෙම ගස් සංවිධානය කිරීමේ ක්‍රමය සාමාන්‍යකරණය කරයි. දත්ත සමුදායන් සහ ගොනු පද්ධති වැනි දිගු කාලීන ගබඩා කිරීම් සංවිධානය කිරීමට B-trees නිතර භාවිතා වේ. හෑෂ් කිරීම: ආශ්‍රිත අරා ක්‍රියාත්මක කිරීම සඳහා, හෑෂ් ශ්‍රිතයක් භාවිතයෙන් වාර්තා වෙත යතුරු සිතියම්ගත කරන දත්ත ව්‍යුහයක් වන හෑෂ් වගු, සාමාන්‍යයෙන් වර්ග කළ වාර්තා අරාවක ද්විමය සෙවීමට වඩා වේගවත් වේ.බොහෝ හැෂ් වගු ක්‍රියාත්මක කිරීම් සඳහා සාමාන්‍යයෙන් ක්‍රමක්‍රම කළ නියත කාලයක් අවශ්‍ය වේ.කෙසේ වෙතත්, අසාර්ථක සෙවුමකදී ලබා දී ඇති එකම තොරතුරු වන්නේ ඉලක්කය කිසිදු වාර්තාවක නොතිබීම නිසා, ඊළඟ-කුඩාම, ඊළඟ-විශාලම සහ ළඟම යතුර ගණනය කිරීම වැනි ආසන්න ගැලපීම් සඳහා hashing ප්‍රයෝජනවත් නොවේ. එවැනි ගැලපීම් සඳහා ද්විමය සෙවුම වඩාත් සුදුසු වේ, ලඝුගණක කාලය තුළ ඒවා සිදු කරයි. ද්විමය සෙවුම ද ආසන්න ගැලපීම් සඳහා සහය දක්වයි. කුඩාම සහ විශාලතම මූලද්‍රව්‍යය සොයා ගැනීම වැනි සමහර මෙහෙයුම් වර්ග කළ අරා මත කාර්යක්ෂමව කළ හැකි නමුත් හැෂ් වගු මත නොවේ. සාමාජික ඇල්ගොරිතම සකසන්න: සෙවීමට අදාළ ගැටළුවක් වන්නේ සාමාජිකත්වය සැකසීමයි. ද්විමය සෙවුම වැනි සෙවීම් කරන ඕනෑම ඇල්ගොරිතමයක් සාමාජිකත්වය සැකසීම සඳහා ද භාවිතා කළ හැක. කට්ටල සාමාජිකත්වය සඳහා වඩාත් නිශ්චිතව ගැලපෙන වෙනත් ඇල්ගොරිතම තිබේ. බිට් අරාව යනු සරලම, යතුරු පරාසය සීමා වූ විට ප්‍රයෝජනවත් වේ. එය බිටු එකතුවක් සංයුක්තව ගබඩා කරයි, සෑම බිට් එකක්ම යතුරු පරාසය තුළ තනි යතුරක් නියෝජනය කරයි. Bit arrays ඉතා වේගවත් වන අතර, O(1) කාලය පමණක් අවශ්‍ය වේ. Judy 1 වර්ගයේ Judy array 64-bit යතුරු කාර්යක්ෂමව හසුරුවයි. ආසන්න ප්‍රතිඵල සඳහා, බ්ලූම් ෆිල්ටර්, හැෂිං මත පදනම් වූ තවත් සම්භාවිතා දත්ත ව්‍යුහයක්, බිට් අරාවක් සහ බහු හෑෂ් ශ්‍රිත භාවිතයෙන් යතුරු කේතනය කිරීමෙන් යතුරු කට්ටලයක් ගබඩා කරයි. බ්ලූම් ෆිල්ටර බොහෝ අවස්ථාවලදී බිට් අරාවලට වඩා බොහෝ ඉඩ-කාර්යක්ෂම වන අතර එය මන්දගාමී නොවේ: k hash ශ්‍රිත සමඟින්, සාමාජික විමසුම් සඳහා O(k) කාලය පමණක් අවශ්‍ය වේ. කෙසේ වෙතත්, බ්ලූම් ෆිල්ටර් ව්‍යාජ ධනාත්මක වලින් පීඩා විඳිති. වෙනත් දත්ත ව්‍යුහයන්: වර්ග කළ අරා සඳහා ලබා ගත හැකි සෙවීම් සහ අනෙකුත් මෙහෙයුම් යන දෙකටම සමහර අවස්ථාවලදී ද්විමය සෙවුම වැඩිදියුණු කළ හැකි දත්ත ව්‍යුහයන් පවතී. උදාහරණයක් ලෙස, van Emde Boas ගස්, විලයන ගස්, උත්සාහයන් සහ bit arrays වැනි විශේෂිත දත්ත ව්‍යුහයන් මත ද්විමය සෙවීමට වඩා සෙවුම්, ආසන්න ගැලපීම් සහ ක්‍රියාන්විතයන් වඩාත් කාර්යක්ෂමව සිදු කළ හැක. මෙම විශේෂිත දත්ත ව්‍යුහයන් සාමාන්‍යයෙන් වේගවත් වන්නේ ඒවා යම් ගුණාංගයක් (සාමාන්‍යයෙන් කුඩා නිඛිල වන යතුරු) සහිත යතුරුවල ගුණවලින් ප්‍රයෝජන ගන්නා නිසා පමණක් වන අතර, එම ගුණාංගය නොමැති යතුරු සඳහා කාලය හෝ අවකාශය වැය වේ. යතුරු ඇණවුම් කළ හැකි තාක්, මෙම මෙහෙයුම් සෑම විටම යතුරු නොතකා වර්ග කළ අරාවක් මත අවම වශයෙන් කාර්යක්ෂමව සිදු කළ හැකිය. Judy arrays වැනි සමහර ව්‍යුහයන්, කාර්යක්ෂමතාව සහ ආසන්න ගැලපීම සිදු කිරීමේ හැකියාව රඳවා ගනිමින් මෙය අවම කිරීම සඳහා ප්‍රවේශයන් වල එකතුවක් භාවිතා කරයි.
ද්වීමය සෙවුම සමඟින් අනුපිළිවෙළට සකසන ලද අරා, ඇතුළත් කිරීම් සහ මකාදැමීමේ මෙහෙයුම් නැවත ලබා ගැනීම සමඟ සම්බන්ධ වූ විට ඉතා අකාර්යක්ෂම විසඳුමකි. මීට අමතරව, විශේෂයෙන් මූලද්‍රව්‍ය බොහෝ විට අරාව තුළට ඇතුළු කරන විට වර්ග කළ අරාව මතක භාවිතය සංකීර්ණ කළ හැකිය. ද්වීමය සෙවුම රේඛීය සෙවීමට වඩා වේගවත් වේ, අරාව කෙටි නම් හැර, අරාව කලින් වර්ග කළ යුතුය. ද්විමය සෙවුම් ගස් බොහෝ විට අසම්පූර්ණ ලෙස සමතුලිත වන බැවින් ද්විමය සෙවීම් සාමාන්‍යයෙන් සෙවීම සඳහා වඩාත් කාර්යක්ෂම වේ, ද්විමය සෙවීමට වඩා තරමක් නරක කාර්ය සාධනයක් ඇති කරයි. හෑෂ් ශ්‍රිතයක් භාවිතයෙන් වාර්තා සඳහා යතුරු සිතියම්ගත කරන දත්ත ව්‍යුහයක්, සාමාන්‍යයෙන් වර්ග කළ වාර්තා පෙළක ද්විමය සෙවීමට වඩා වේගවත් වේ.