"അടുക്ക് (ദത്തസങ്കേതം)" എന്ന താളിന്റെ പതിപ്പുകൾ തമ്മിലുള്ള വ്യത്യാസം
Content deleted Content added
No edit summary |
→അടുക്കുകൾ അൽഗോരിതങ്ങളിൽ: ലേഖനത്തിന്റെ ഒരു കരടുരൂപം ഏതാണ്ട് പൂർത്തിയായി. ഇനി വൈപുല്യമേറ്റലേ വേണ്ടൂ. |
||
വരി 1:
ഒരു പ്രത്യേക ക്രമത്തിൽ രേഖീയമായോ ബഹുരേഖീയമായോ അടുക്കിവച്ച വസ്തുക്കളുടെ കൂട്ടത്തെ പ്രതിനിധീകരിക്കുവാനുപയോഗിക്കുന്ന ഒരു [[ഡാറ്റാ സ്ട്രക്‌ച്ചർ|ദത്തസങ്കേതമാണ്]] ([[:en:Data_structure|Data Structure]]) അടുക്ക് ([[:en:Array_data_structure|Array]]). [[കമ്പ്യൂട്ടർ ശാസ്ത്രം|കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിലെ]] അടിസ്ഥാനപരമായ ഒരു ദത്തസങ്കേതം കൂടിയാണിത്. അടുക്കിലെ വസ്തുക്കൾ സംഖ്യകളോ, അക്ഷരങ്ങളോ, വാക്കുകളോ, മറ്റടുക്കുകൾ തന്നെയുമോ ആവാം. ഒരടുക്കിലെ എല്ലാ വസ്തുക്കളും ഒരേ തരത്തിലുള്ളവയായിരിക്കണം എന്ന നിർബ്ബന്ധമേയുള്ളൂ. അടുക്കിലെ ഓരോ വസ്തുവിനെയും അതിന്റെ സ്ഥാനാങ്കം ([[:en:Array_data_structure#Element_identifier_and_addressing_formulas|Index]]) വച്ചാണ് കുറിയ്ക്കുന്നത്. ഒരടുക്കിനെ കടലാസ്സിൽ പ്രതിനിധീകരിക്കുമ്പോൾ നേരെ ഒറ്റ വരിയിൽ അടുക്കിലെ അംഗങ്ങളെ രേഖപ്പെടുത്തുകയും ഇടത്തേ അറ്റത്തെ അംഗത്തെ 1 എന്ന സ്ഥാനാങ്കം കൊണ്ട് കുറിക്കുകയും ചെയ്യുന്നു. ഉദാഹരണത്തിന് 23, 82, 91, 0, -1, 78 എന്നിങ്ങനെ ആറു സംഖ്യകളുള്ള അടുക്കിലെ 23 എന്ന അംഗത്തിനെ 1 എന്ന സ്ഥാനാങ്കം വച്ചും -1 എന്ന അംഗത്തിനെ 5 എന്ന സ്ഥാനാങ്കം വച്ചും കുറിക്കുന്നു.
അടുക്കുകൾ എപ്പോഴും രേഖീയമായിക്കൊള്ളണമെന്നില്ല. ഒന്നിലധികം പരിമാണങ്ങളുള്ള അടുക്കുകളും ([[:en:Array_data_type#Multi-dimensional_arrays|Multidimensional arrays]]) സർവ്വസാധാരണമാണ്. ഒരു ക്ലാസുമുറിയിലെ ഹാജർ പട്ടികയെ കമ്പ്യൂട്ടർ മെമ്മറിയിൽ സൂക്ഷിക്കാൻ രണ്ടു പരിമാണങ്ങളുള്ള ഒരടുക്ക് ഉപയോഗിക്കാവുന്നതാണ്. ഒരു പരിമാണം വച്ച് വിദ്യാർത്ഥിനികളുടെ പേരുകളും മറ്റേ പരിമാണം വച്ച് അദ്ധ്യയനമാസത്തിലെ ദിവസങ്ങളും സൂചിപ്പിക്കാം. ഇങ്ങനെയുള്ള അടുക്കുകളിലെ അംഗങ്ങളെ കുറിക്കാനുള്ള സ്ഥാനാങ്കങ്ങളിൽ രണ്ട് ഭാഗങ്ങളുണ്ടായിരിക്കും. ക്ലാസുമുറി ഉദാഹരണത്തിലേക്ക് മടങ്ങുകയാണെങ്കിൽ, കനി എന്ന പെൺകുട്ടിയുടെ പതിനഞ്ചാം തിയ്യതിയിലെ ഹാജർനിലയെ കുറിക്കുവാൻ (കനി, 15) എന്ന ഇരട്ടസ്ഥാനാങ്കം ഉപയോഗിക്കാം.
ഒരു സ്ഥാനാങ്കത്താൽ സൂചിപ്പിക്കപ്പെടുന്ന ഒരംഗത്തെ ലഭിക്കാൻ ഒരു സ്ഥിരസമയം മതിയാകും എന്നതാണ് അടുക്കിന്റെ ഏറ്റവും പ്രധാനപ്പെട്ട പ്രത്യേകത. വിശദമായിപ്പറയുകയാണെങ്കിൽ, അടുക്കിലെ ഒരു നിശ്ചിതസ്ഥാനത്തെ അംഗത്തെ എടുക്കുവാനുള്ള സമയം അടുക്കിന്റെ വലുപ്പമനുസരിച്ച് മാറുന്ന ഒന്നല്ല. കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിന്റെ ഭാഷയിൽ, അടുക്കിലെ സ്ഥാനാങ്കം തന്നിട്ടുണ്ടെങ്കിൽ, ആ സ്ഥാനാങ്കം കുറിക്കുന്ന അംഗത്തെ ലഭിക്കുവാൻ / എടുക്കുവാൻ <math>O(1)</math> സമയമേ വേണ്ടൂ.
വരി 11:
പൊതുവിൽ പറഞ്ഞാൽ, <math>k</math> പരിമാണങ്ങളുള്ള <math>B[1..n_1][1..n_2][1..n_3]..[1..n_k]</math> എന്ന അടുക്കിലെ വസ്തുക്കളുടെ എണ്ണം <math>n_1 \times n_2 \times n_3 \times \dots \times n_k </math>ആണ്. ഇതിലെ ഒരു നിശ്ചിത അംഗത്തെ കുറിക്കുവാൻ <math>B[x_1][x_2]\dots[x_k]</math> എന്ന പ്രതീകമുപയോഗിക്കാം.
=== അടുക്കുകളും അൽഗോരിതങ്ങളും ===
പല [[അൽഗൊരിതം|അൽഗോരിതങ്ങളിലും]] ദത്തസങ്കേതമായി അടുക്കുകളാണ് ഉപയോഗിക്കുന്നത്. സ്ഥാനാങ്കങ്ങളാൽ സൂചിതമായ അംഗങ്ങളെ എടുക്കാൻ സ്ഥിരസമയം മതിയാകും എന്ന പ്രത്യേകതയാണ് ഈ അഭികാമ്യതയ്ക്ക് നിദാനം. മറ്റു സാധാരണ ദത്തസങ്കേതങ്ങളെ നിർമ്മിക്കാനും അടുക്കുകൾ ഉപയോഗിക്കാറുണ്ട്. അടുക്കുകളുമായി ബന്ധപ്പെട്ട അൽഗോരിതങ്ങളും ദത്തസങ്കേതങ്ങളും അവയെപ്പറ്റിയുള്ള ലഘു വിരണങ്ങളും അടങ്ങുന്ന ഒരു ചെറു പട്ടിക താഴെക്കൊടുത്തിരിക്കുന്നു.
* [[ബൈനറി തിരയൽ]]: പ്രത്യേകിച്ച് ക്രമമൊന്നുമില്ലാതെ അംഗങ്ങൾ ചേർത്തിരിക്കുന്ന ഒരടുക്കിൽ ഒരു നിശ്ചിതവസ്തു ഉണ്ടോ എന്ന് തിരയാൻ അടുക്കിലെ ഓരോ അംഗത്തെയും എടുത്ത് പരിശോധിക്കേണ്ടി വരും. <math>n</math> അംഗങ്ങളുള്ള ഒരടുക്കിൽ ഇപ്രകാരം തിരയുന്നതിനുള്ള സമയസങ്കീർണ്ണത ([[:en:Time_complexity|Time Complexity]]) <math>O(n)</math> ആണ്. എന്നാൽ കൂടുംക്രമത്തിലോ കുറയുംക്രമത്തിലോ അംഗങ്ങൾ അടുക്കിയ ഒരടുക്കിൽ ([[:en:Sorted_array|Sorted Array]]) ഈ ജോലി വെറും <math>O(\log n)</math> സമയത്തിനുള്ളിൽ പൂർത്തിയാക്കാം. അങ്ങനെ ചെയ്യാനുപയോഗിക്കുന്ന ഒരൽഗോരിതമാണ് ദ്വയാംശത്തിരച്ചിൽ, അഥവാ [[ബൈനറി തിരയൽ]].
* പ്രാമുഖ്യതാ വരി ([[:en:Priority_queue|Priority queue]]): പല അൽഗോരിതങ്ങളിലും ഉപയോഗിച്ചുവരുന്ന ഒരു ദത്തസങ്കേതമാണ് പ്രാമുഖ്യതാവരികൾ. ഒരുകൂട്ടം ജോലികളും ഓരോ ജോലിക്കും ഓരോ പ്രാധാന്യസംഖ്യകളുമുണ്ടെങ്കിൽ (Priorities), ഓരോ സമയത്തും ശേഷിച്ച ജോലികളിൽ ഏറ്റവും പ്രധാനമായ ജോലിയെ സ്ഥിരസമയത്തിൽ (<math>O(1)</math> സമയത്തിൽ) തിരഞ്ഞെടുക്കാനുള്ള ഒരുപാധിയായാണ് പ്രാമുഖ്യതാവരികളെ ഉപയോഗിക്കുന്നത്. പ്രാമുഖ്യതാ വരികളെ മെമ്മറിയിൽ അടുക്കുകളുപയോഗിച്ച് നിർമ്മിക്കാറുണ്ട്.
* [[സ്റ്റാക്ക് (ഡാറ്റാ സ്ട്രക്‌ച്ചർ)|സ്റ്റാക്ക്]], [[ക്യൂ (ഡാറ്റാ സ്ട്രക്‌ച്ചർ)|ക്യൂ]] എന്നീ ദത്തസങ്കേതങ്ങളെയും അടുക്കുകൾ വച്ച് നിർമ്മിക്കാം.
[[വർഗ്ഗം:കമ്പ്യൂട്ടിങ്ങ്‌]]
| |||