അടുക്ക് (ദത്തസങ്കേതം)

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Array_(data_structure)

രേഖീയമായോ ബഹുരേഖീയമായോ അടുക്കിവച്ച വസ്തുക്കളുടെ കൂട്ടത്തെ പ്രതിനിധീകരിക്കുവാനുപയോഗിക്കുന്ന ഒരു ദത്തസങ്കേതമാണ് (Data Structure) അടുക്ക് (Array). കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിലെ അടിസ്ഥാനപരമായ ഒരു ദത്തസങ്കേതം കൂടിയാണിത്. അടുക്കിലെ വസ്തുക്കൾ സംഖ്യകളോ, അക്ഷരങ്ങളോ, വാക്കുകളോ, മറ്റടുക്കുകൾ തന്നെയുമോ ആവാം. ഒരടുക്കിലെ എല്ലാ വസ്തുക്കളും ഒരേ തരത്തിലുള്ളവയായിരിക്കണം എന്ന നിർബ്ബന്ധമേയുള്ളൂ. അടുക്കിലെ ഓരോ വസ്തുവിനെയും അതിന്റെ സ്ഥാനാങ്കം (Index) വച്ചാണ് കുറിയ്ക്കുന്നത്. ഒരടുക്കിനെ കടലാസ്സിൽ പ്രതിനിധീകരിക്കുമ്പോൾ നേരെ ഒറ്റ വരിയിൽ അടുക്കിലെ അംഗങ്ങളെ രേഖപ്പെടുത്തുകയും ഇടത്തേ അറ്റത്തെ അംഗത്തെ 1 എന്ന സ്ഥാനാങ്കം കൊണ്ട് കുറിക്കുകയും ചെയ്യുന്നു. ഉദാഹരണത്തിന് 23, 82, 91, 0, -1, 78 എന്നിങ്ങനെ ആറു സംഖ്യകളുള്ള അടുക്കിലെ 23 എന്ന അംഗത്തിനെ 1 എന്ന സ്ഥാനാങ്കം വച്ചും -1 എന്ന അംഗത്തിനെ 5 എന്ന സ്ഥാനാങ്കം വച്ചും കുറിക്കുന്നു.

അടുക്കുകൾ എപ്പോഴും രേഖീയമായിക്കൊള്ളണമെന്നില്ല. ഒന്നിലധികം പരിമാണങ്ങളുള്ള അടുക്കുകളും (Multidimensional arrays) സർവ്വസാധാരണമാണ്. ഒരു ക്ലാസുമുറിയിലെ ഹാജർ പട്ടികയെ കമ്പ്യൂട്ടർ മെമ്മറിയിൽ സൂക്ഷിക്കാൻ രണ്ടു പരിമാണങ്ങളുള്ള ഒരടുക്ക് ഉപയോഗിക്കാവുന്നതാണ്. ഒരു പരിമാണം വച്ച് വിദ്യാർത്ഥിനികളുടെ പേരുകളും മറ്റേ പരിമാണം വച്ച് അദ്ധ്യയനമാസത്തിലെ ദിവസങ്ങളും സൂചിപ്പിക്കാം. ഇങ്ങനെയുള്ള അടുക്കുകളിലെ അംഗങ്ങളെ കുറിക്കാനുള്ള സ്ഥാനാങ്കങ്ങളിൽ രണ്ട് ഭാഗങ്ങളുണ്ടായിരിക്കും. ക്ലാസുമുറി ഉദാഹരണത്തിലേക്ക് മടങ്ങുകയാണെങ്കിൽ, കനി എന്ന പെൺകുട്ടിയുടെ പതിനഞ്ചാം തിയ്യതിയിലെ ഹാജർനിലയെ കുറിക്കുവാൻ (കനി, 15) എന്ന ഇരട്ടസ്ഥാനാങ്കം ഉപയോഗിക്കാം.

ഒരു സ്ഥാനാങ്കത്താൽ സൂചിപ്പിക്കപ്പെടുന്ന ഒരംഗത്തെ ലഭിക്കാൻ ഒരു സ്ഥിരസമയം മതിയാകും എന്നതാണ് അടുക്കിന്റെ ഏറ്റവും പ്രധാനപ്പെട്ട പ്രത്യേകത. വിശദമായിപ്പറയുകയാണെങ്കിൽ, അടുക്കിലെ ഒരു നിശ്ചിതസ്ഥാനത്തെ അംഗത്തെ എടുക്കുവാനുള്ള സമയം അടുക്കിന്റെ വലിപ്പമനുസരിച്ച് മാറുന്ന ഒന്നല്ല. കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിന്റെ ഭാഷയിൽ, അടുക്കിലെ സ്ഥാനാങ്കം തന്നിട്ടുണ്ടെങ്കിൽ, ആ സ്ഥാനാങ്കം കുറിക്കുന്ന അംഗത്തെ ലഭിക്കുവാനോ എടുക്കുവാനോ $O(1)$സമയമേ വേണ്ടൂ.

ഔപചാരിക നിർവ്വചനം

അടുക്കുകളെ ഇംഗ്ലീഷിലെ വലിയക്ഷരങ്ങൾ വച്ചാണ് പൊതുവേ കുറിക്കുന്നത്. ഉദാഹരണത്തിന് $A[1..100]$എന്ന ചിഹ്നം $100$അംഗങ്ങളുള്ള ഒരു രേഖീയ അടുക്കിനെ സൂചിപ്പിക്കുന്നു. അതിലെ $25$ആമത്തെ അംഗത്തെ കുറിക്കാൻ $A[25]$എന്ന പ്രതീകം ഉപയോഗിക്കാം. രണ്ടു പരിമാണങ്ങളുള്ള ഒരു അടുക്കിനെ ഇതുപോലെത്തന്നെ $A[1..100][1..200]$എന്ന പ്രതീകം വച്ച് സൂചിപ്പിക്കാം. ഈ അടുക്കിന് $100$വരികളും $200$നിരകളുമുണ്ട്. ഇതിലെ മൊത്തം അംഗങ്ങളുടെ എണ്ണം $100\times 200=20000$ആണ്. ഇതിലെ മുപ്പതാമത്തെ വരിയിലെ നാൽപ്പത്തഞ്ചാമത്തെ അംഗത്തെ $A[30][45]$എന്നു കുറിക്കുന്നു.

പൊതുവിൽ പറഞ്ഞാൽ, $k$പരിമാണങ്ങളുള്ള $B[1..n_{1}][1..n_{2}][1..n_{3}]..[1..n_{k}]$എന്ന അടുക്കിലെ വസ്തുക്കളുടെ എണ്ണം $n_{1}\times n_{2}\times n_{3}\times \dots \times n_{k}$ആണ്. ഇതിലെ ഒരു നിശ്ചിത അംഗത്തെ കുറിക്കുവാൻ $B[x_{1}][x_{2}]\dots [x_{k}]$എന്ന പ്രതീകമുപയോഗിക്കാം.

അടുക്കുകളും അൽഗോരിതങ്ങളും

പല അൽഗോരിതങ്ങളിലും ദത്തസങ്കേതമായി അടുക്കുകളാണ് ഉപയോഗിക്കുന്നത്. സ്ഥാനാങ്കങ്ങളാൽ സൂചിതമായ അംഗങ്ങളെ എടുക്കാൻ സ്ഥിരസമയം മതിയാകും എന്ന പ്രത്യേകതയാണ് ഈ അഭികാമ്യതയ്ക്ക് നിദാനം. മറ്റു സാധാരണ ദത്തസങ്കേതങ്ങളെ നിർമ്മിക്കാനും അടുക്കുകൾ ഉപയോഗിക്കാറുണ്ട്. അടുക്കുകളുമായി ബന്ധപ്പെട്ട അൽഗോരിതങ്ങളും ദത്തസങ്കേതങ്ങളും അവയെപ്പറ്റിയുള്ള ലഘു വിരണങ്ങളും അടങ്ങുന്ന ഒരു ചെറു പട്ടിക താഴെക്കൊടുത്തിരിക്കുന്നു.

• ബൈനറി തിരയൽ: പ്രത്യേകിച്ച് ക്രമമൊന്നുമില്ലാതെ അംഗങ്ങൾ ചേർത്തിരിക്കുന്ന ഒരടുക്കിൽ ഒരു നിശ്ചിതവസ്തു ഉണ്ടോ എന്ന് തിരയാൻ അടുക്കിലെ ഓരോ അംഗത്തെയും എടുത്ത് പരിശോധിക്കേണ്ടി വരും. $n$ അംഗങ്ങളുള്ള ഒരടുക്കിൽ ഇപ്രകാരം തിരയുന്നതിനുള്ള സമയസങ്കീർണ്ണത (Time Complexity) $O(n)$ആണ്. എന്നാൽ കൂടുംക്രമത്തിലോ കുറയുംക്രമത്തിലോ അംഗങ്ങളെ ക്രമീകരിച്ച ഒരടുക്കിൽ (Sorted Array) ഈ ജോലി വെറും $O(\log n)$സമയത്തിനുള്ളിൽ പൂർത്തിയാക്കാം. അങ്ങനെ ചെയ്യാനുപയോഗിക്കുന്ന ഒരൽഗോരിതമാണ് ദ്വയാംശത്തിരച്ചിൽ, അഥവാ ബൈനറി തിരയൽ.
• പ്രാമുഖ്യതാ വരി (Priority queue): പല അൽഗോരിതങ്ങളിലും ഉപയോഗിച്ചുവരുന്ന ഒരു ദത്തസങ്കേതമാണ് പ്രാമുഖ്യതാവരികൾ. ഒരുകൂട്ടം ജോലികളും ഓരോ ജോലിക്കും ഓരോ പ്രാധാന്യസംഖ്യകളുമുണ്ടെങ്കിൽ (Priorities), ഓരോ സമയത്തും ശേഷിച്ച ജോലികളിൽ ഏറ്റവും പ്രധാനമായ ജോലിയെ സ്ഥിരസമയത്തിൽ ($O(1)$സമയത്തിൽ) തിരഞ്ഞെടുക്കാനുള്ള ഒരുപാധിയായാണ് പ്രാമുഖ്യതാവരികളെ ഉപയോഗിക്കുന്നത്. പ്രാമുഖ്യതാ വരികളെ മെമ്മറിയിൽ അടുക്കുകളുപയോഗിച്ച് നിർമ്മിക്കാറുണ്ട്.
• സ്റ്റാക്ക്, ക്യൂ എന്നീ ദത്തസങ്കേതങ്ങളെയും അടുക്കുകൾ വച്ച് നിർമ്മിക്കാം.