Mga istruktura ng datos at mga algorithm: isang kumpletong gabay para sa mga programmer

Informatec Digital » Kayamanan » Mga istruktura ng datos at mga algorithm: isang kumpletong gabay para sa mga programmer

Algorithm at istruktura ng data Ang mga ito ay dalawang piraso na magkakasama na parang isang palaisipan: ang isa ay nagbabalangkas sa proseso ng paglutas ng problema, at ang isa naman ay tumutukoy kung saan at paano natin iniimbak ang impormasyon. Bagama't maaaring parang akademiko, ang pagiging dalubhasa sa pares na ito ang siyang nagpapaiba sa isang code na gumagana lamang mula sa isa na lumilipad at sumusukat nang hindi nasisira.

Kung gusto mong mag-aral ng propesyonal na programming, maghanda para sa mga teknikal na panayam, o tumigil na lang sa pag-eensayo tulad ng LeetCode at Codewars, kailangan mo ng matibay na pundasyon sa... mga istruktura ng datos at mga algorithmSa buong artikulong ito, makikita mo kung ano ang mga ito, kung bakit sila napakahalaga, anong mga pangunahing uri ang umiiral, anong mga pangunahing operasyon ang kanilang isinasagawa at anong mga tanong ang karaniwang lumalabas sa mga pagsusulit at proseso ng pagpili.

Ano ang mga istruktura ng datos at mga algorithm?

isang istraktura ng data Ito, sa madaling salita, ay isang partikular na paraan ng pag-oorganisa at pag-iimbak ng impormasyon sa memorya upang magamit ito nang mahusay. Ang organisasyong ito ay hindi basta-basta: direkta nitong tinutukoy kung aling mga operasyon ang mabilis at alin ang nagiging magastos (maglagay, maghanap, magbura, sumubaybay, atbp.).

Kapag pinili mo ang tamang istruktura ng datos, kayang pamahalaan ng iyong programa malaking dami ng data nang hindi pinagpapawisan; kapag mali ang iyong napili, kahit ang isang maliit na application ay maaaring maging mabagal, kumonsumo ng masyadong maraming memorya, o maging imposibleng mapanatili sa paglipas ng panahon.

Isang algorithm Ito ay isang may hangganan at maayos na pagkakasunod-sunod ng mahusay na tinukoy na mga hakbang na nagbabago ng mga input tungo sa mga output upang malutas ang isang partikular na problema. Ito ay parang isang recipe ng pagluluto: sinasabi nito sa iyo kung ano ang gagawin, sa anong pagkakasunud-sunod, at sa ilalim ng anong mga kondisyon, ngunit hindi nito iniisip kung paano mo iimbak ang mga sangkap sa refrigerator, na siyang magiging bahagi ng istruktura ng datos.

Sa agham pangkompyuter, ang bawat algorithm ay dinisenyo na isinasaalang-alang ang uri ng datos na gagamitin nito. Ang pagpili ng istruktura ng datos ay hindi isang maliit na detalye: Ang istruktura at algoritmo ay magkaugnayAt ang maliliit na pagbabago sa isa sa dalawang bahagi ay maaaring mapalakas o makabawas sa pagganap.

Mula sa isang teoretikal na pananaw, pinasikat ng mga may-akda tulad ni Niklaus Wirth ang ideya noon pang dekada 70 na mga algorithm + mga istruktura ng datos = mga programaPagkalipas ng ilang dekada, nananatili itong totoo: hindi mahalaga kung nagprograma ka sa Java, Python, C++ o kung galing ka sa isang bootcamp, ang kakailanganin mo sa mga panayam at seryosong proyekto ay ang pag-alam kung paano pumili at pagsamahin nang maayos ang parehong elemento.

Bakit napakahalaga ng mga ito sa programming?

Sa anumang aplikasyon sa totoong mundo, gaano man ito kasimple, palagi kang gumagamit ng datos: mga suweldo, produkto, gumagamit, transaksyon, ruta, dokumentoMga talaan ng log, atbp. Ang tanong ay hindi kung hahawakan mo ba ang data, kundi kung paano mo ito aayusin upang ang iyong code ay mabilis, malinaw, at madaling panatilihin.

Ang mga istruktura ng datos ay ginagamit upang mag-imbak ng impormasyon sa maayos at magkakaugnay na paraan ayon sa problema. Hindi ito pareho Kailangang laging i-access ang unang elemento, maghanap gamit ang key, mag-traverse nang sunod-sunod, maglagay sa gitna, o madalas magbura; mas akma ang bawat pattern ng paggamit sa ibang istruktura.

Sa kanilang bahagi, pinapayagan ng mga algorithm ang iproseso nang mahusay ang datos na iyon: pagbukud-bukurin ang mga ito, salain ang mga ito, maghanap ng mga elemento, maghanap ng mga pinakamainam na ruta, tumuklas ng mga pattern gamit ang data mining, i-optimize ang mga mapagkukunan, atbp. Maraming problemang tila mahirap ang nagiging walang kabuluhan kapag nahanap mo ang tamang kombinasyon ng algorithm at istruktura ng datos.

Sa mga teknikal na panayam para sa pagbuo ng software, bihirang magtanong ng isang tanong na hindi direktang tumutugon sa mga paksang ito. Minsan ang tanong ay tahasang binabanggit ang istruktura, tulad ng "kung bibigyan ng binary tree…", at sa ibang pagkakataon ay ipinahihiwatig ito: "gusto naming bilangin kung ilang aklat ang mayroon ang bawat may-akda," na nagmumungkahi ng paggamit ng isang hash table o mapa ng key-value.

Bukod pa rito, ang pormal at propesyonal na pagsasanay ay kadalasang umiikot sa larangang ito. Maraming unibersidad at programa sa mas mataas na edukasyon ang nagsasama ng isang asignaturang... Mga istruktura at algorithm ng data, na may opisyal na programa, mga kinakailangan, mga sesyon ng teorya at pagsasanay, mga pagsusulit at mga takdang-aralin, dahil ito ay itinuturing na isang pangunahing asignatura para sa sinumang software engineer.

Mga kinakailangan at kinakailangang pundasyon

Para masulit ang pag-aaral ng mga istruktura at algorithm ng datos, makakatulong na magkaroon ng kaunting pamilyar sa isang pangkalahatang-layunin na lengguwahe ng programming, tulad ng Java, Python o C++Hindi mo kailangang maging isang guru, ngunit kailangan mong maging komportable sa mga pangunahing konsepto tulad ng mga variable, uri ng data, kondisyonal, loop, function, at pagpapasa ng parameter.

Malaki rin ang maitutulong nito upang maunawaan ang ideya ng pagiging kumplikado ng algoritmo at Big O notation: kung paano lumalaki ang oras ng pagpapatupad o paggamit ng memorya habang tumataas ang laki ng data (n). Ang pag-alam kung paano makilala ang pagkakaiba sa pagitan ng O(1), O(log n), O(n), O(n log n), at O(n²) ay nagbibigay-daan sa iyo na ihambing ang mga alternatibo nang may mahusay na paghatol at bigyang-katwiran ang iyong mga desisyon.

Isa pang mahalagang aspeto ay ang kaunting pakikipag-away sa paglutas ng problemaMga pagsasanay sa structured programming, maliliit na hamon sa lohika, simpleng kata, atbp. Kung mas sasanayin mo ang iyong "ilong" na hatiin ang isang problema sa mga hakbang, mas madaling makita kung aling istruktura ng datos ang akma sa bawat kaso.

May ilang kurikulum na malinaw na nagsasaad mga kinakailangan o pangunahing kinakailangan Para sa kursong Data Structures and Algorithms, kailangan mong nakapasa sa Programming Fundamentals, Programming I, o Discrete Mathematics. May katuturan ito: kung walang matibay na pundasyon sa basic programming at kaunting lohika, madaling mabigo sa asignaturang ito.

Sa wakas, ang pagkakaroon ng kaunting pamilyar sa mga praktikal na kapaligiran sa totoong mundo (tulad ng maliliit na proyekto sa web, script, o mga application ng console) ay tumutulong sa iyo na mas mailarawan kung para saan mo gagamitin ang bawat istruktura, sa halip na tingnan ito bilang isang bagay na puro akademiko lamang.

Mga karaniwang ginagamit na istruktura ng datos

Sa agham pangkompyuter, maraming istruktura ng datosGayunpaman, mayroong isang grupo ng mga "pangunahing" tungkulin na paulit-ulit na inuulit: mga array (vector), stack, queue, linked list, tree, graph, try, at hash table. Ang pag-unawa kung paano sila gumagana, kung anong mga operasyon ang kanilang inaalok, at ang kanilang karaniwang mga gastos ay susi sa maayos na pag-usad ng programming.

Pupunta na kami ngayon suriin ang bawat isa, kasama ang pangunahing ideya nito, mga tipikal na operasyon at mga halimbawa ng mga problemang karaniwang lumalabas sa mga klase, pagsasanay, at mga panayam sa trabaho para sa mga developer.

Mga Array

Ang hanay Ito ang pinakasimpleng linear na istruktura ng datos at isa sa mga pinakamalawak na ginagamit. Binubuo ito ng isang magkakasunod na bloke ng memorya na nag-iimbak ng isang koleksyon ng mga elemento ng parehong uri, na maa-access sa pamamagitan ng isang integer index, karaniwang nagsisimula sa zero.

Isipin ang isang array na may sukat na 4 na naglalaman ng mga halagang 1, 2, 3, at 4. Ang bawat posisyon ay may index (0, 1, 2, 3) at maaari mong direktang ma-access ang anumang elemento gamit ang index nito sa pare-parehong oras na O(1). Ginagawa nitong napaka-epektibo ang mga array para sa random na pagbabasa.

Mayroong dalawang pangunahing kategorya: mga one-dimensional array (isang hanay ng mga elemento) at mga array na multidimensional (halimbawa, mga matrice, na mga array ng mga array). Maraming mga lengguwahe ng programming ang nag-aalok ng parehong variant nang native o may bahagyang pagkakaiba sa syntax at performance.

Ang mga pangunahing operasyon sa isang array ay karaniwang:

• Ipasok: paglalagay ng isang elemento sa isang partikular na posisyon, na sa mga static array ay maaaring may kasamang paglilipat ng iba pang mga elemento.
• Kunin: pag-access sa elemento sa isang ibinigay na indeks, karaniwang O(1).
• Burahin: burahin o markahan bilang alisan ng laman ang elemento sa isang partikular na posisyon, kadalasan sa pamamagitan ng paglilipat ng mga elemento pakaliwa.
• Sukat: tingnan kung ilang elemento ang nakaimbak o ang pinakamataas na kapasidad ng array.

Sa mga panayam at pagsusulit, ang mga pagsasanay na tulad nito ay karaniwan. hanapin ang pangalawang minimum ng isang arrayPaghahanap ng unang hindi umuulit na integer, pagsasama ng dalawang nakaayos nang array, o muling pagsasaayos ng mga positibo at negatibong numero habang pinapanatili ang ilang partikular na katangian. Ang lahat ng ito ay nakasalalay sa index access at linear o double traversals.

Mga Stack

Ang baterya Ito ay isang linear na istruktura ng datos na sumusunod sa prinsipyo ng LIFO: Huling Pasok, Unang Labas. Isipin ang isang tumpok ng mga libro na nakapatong sa isa't isa: maaari ka lamang kumuha o maglagay ng mga libro mula sa itaas.

Ang pag-uugaling ito ay nangangahulugan na Ina-access lang natin ang elementong nasa itaas ng stackHindi natin maaaring tanggalin ang gitnang elemento nang hindi muna inaalis ang mga elemento sa itaas nito. Ginagawa nitong isang mainam na istruktura ito para sa pagmomodelo ng mga kasaysayan ng aksyon (undo), mga tawag sa nested function, nabigasyon (back/forward), atbp.

Ang mga karaniwang operasyon ng stack ay:

• Itulak: maglagay ng bagong aytem sa itaas.
• Pop: kunin at ibalik ang elemento sa itaas, na binabawasan ang laki ng stack.
• Itaas o silip: tingnan ang elemento sa itaas nang hindi ito binubura.
• ayEmpty: tingnan kung walang laman ang baterya.

Sa konteksto ng mga panayam, makikita ang mga sumusunod na problema: suriin ang mga ekspresyon sa notasyong postfix (RPN), pag-uuri ng mga elemento gamit lamang ang mga stack, o pagsuri kung ang isang string ng mga panaklong (at iba pang mga simbolo) ay wastong nabalanse gamit ang push at pop.

Sa pagsasagawa, maraming panloob na implementasyon ng mga wika (halimbawa, ang stack ng tawag sa sistema) ay gumagana kasunod ng mga prinsipyong ito, kahit na hindi natin ito direktang nakikita.

Mga pila

Ang buntot Isa itong linear na istruktura ng datos, ngunit sa halip na sundin ang prinsipyo ng LIFO, ginagamit nito ang modelo ng FIFO: Unang Pasok, Unang Labas. Ang pinakamalinaw na pagkakatulad ay ang isang pila ng mga taong naghihintay sa isang ticket booth sa sinehan.

Sa isang karaniwang pila, ang mga elemento ay Nagdadagdag sila sa dulo at bumabawi sa simulaUnang dumating, unang mapaglilingkuran, kaya mainam ito para sa pamamahala ng mga nakabinbing gawain, proseso ng operating system, mga kahilingan sa server, mga pila sa pag-print, atbp.

Kabilang sa mga pangunahing operasyon sa pila ang:

• Enqueue: maglagay ng bagong aytem sa dulo ng pila.
• Dequeue: tanggalin at ibalik ang elementong matatagpuan sa simula.
• Harap o itaas: tingnan ang unang aytem nang hindi ito inaalis.
• ayEmpty: tingnan kung walang laman ang pila.

Sa mga hamon sa programming, karaniwan sa kanila na tanungin ka, halimbawa, magpatupad ng isang stack gamit ang dalawang pila, baligtarin ang unang k elemento ng isang pila nang hindi binabago ang natitira, o bumuo ng mga binary na numero mula 1 hanggang n gamit ang FIFO na gawi ng pila.

Bukod sa pangunahing buntot, may mga baryasyon tulad ng pabilog na buntot, ang priority queue o double queues (deque), na nag-aalok ng mga karagdagang operasyon at nagpapabuti sa performance sa ilang partikular na sitwasyon.

mga naka-link na listahan

Ang naka-link na listahan Ang linked list ay isa ring linear na istruktura, ngunit sa loob nito ay ibang-iba ito sa mga array. Sa halip na gumamit ng magkakasunod na bloke ng memorya, ito ay binubuo ng mga sparse node na konektado sa isa't isa sa pamamagitan ng mga reference o pointer.

Ang bawat node ay karaniwang naglalaman ng dalawang bahagi: ang data na itatago at isang pointer (o ilan) na nakaturo sa susunod na node sa pagkakasunod-sunod (at, sa kaso ng mga listahang doble ang pagkakaugnay, gayundin sa nauna). Ang listahan ay pinamamahalaan sa pamamagitan ng isang sanggunian sa ulo nito, na nakaturo sa unang node, at sa mas kumplikadong mga listahan, isang sanggunian sa buntot ang pinapanatili rin.

Mayroong dalawang pangunahing variant:

• listahang magkakaugnay nang paisa-isa: ang bawat node ay nakaturo lamang sa susunod; ang landas ay karaniwang nasa iisang direksyon.
• listahang doble ang pagkakaugnayAng bawat node ay nakaturo sa susunod at nakaraang node, na nagpapadali sa mga bidirectional traversal at mas mahusay na mga operasyon sa pagtanggal.

Ang mga karaniwang operasyon sa mga naka-link na listahan ay kinabibilangan ng:

• IpasokSaUlo: maglagay ng bagong node sa simula ng listahan.
• IpasokSaDulo: magdagdag ng node sa dulo, ina-update ang pila kung mayroon man.
• alisin: tanggalin ang isang partikular na node, inaayos ang mga pointer ng mga kalapit na node.
• TanggalinSaUlo: burahin ang unang node at ilipat ang ulo sa susunod.
• Maghanap: bagtasin ang listahan upang maghanap ng isang partikular na halaga.
• ayEmpty: suriin kung ang head ay null at samakatuwid ang listahan ay walang mga elemento.

Ang mga ganitong problema ay laganap sa mga klase at panayam baligtarin ang isang naka-link na listahan, tukuyin kung mayroong isang siklo (karaniwan ay gamit ang algorithm na "tortoise and hare"), kunin ang node N sa pamamagitan ng pagbibilang mula sa dulo, o alisin ang mga duplicate na node, na palaging maingat na ginagamit ang mga pointer.

Ang mga linked list ay malawakang ginagamit upang ipatupad mga hash table na may kadenamga listahan ng katabing mga graph, at mga dynamic na istruktura ng datos kung saan ang mga elemento ay madalas na ipinapasok at binubura.

Puno

Isang puno Ito ay isang hierarchical na istruktura ng datos na binubuo ng mga node na konektado sa pamamagitan ng mga gilid. Hindi tulad ng mga pangkalahatang graph, ang isang puno ay walang mga siklo: palaging mayroong ugat, mga anak, mga magulang, mga kapatid, mga dahon, mga antas, at mga subtree, na may organisasyong uri ng "pamilya" o "organisasyon tsart".

Ang mga puno ay lubhang kapaki-pakinabang kapag gusto natin kumakatawan sa mga hierarchical na relasyon o hatiin ang isang problema sa mas maliliit na subproblema: mga file system, menu, mga istruktura ng DOM sa mga browser, mga decision tree sa artificial intelligence, atbp.

Maraming uri ng puno, kabilang ang:

• N-ary na Puno: ang bawat node ay maaaring magkaroon ng pabagu-bago (at posibleng malaki) na bilang ng mga anak.
• Balanseng puno: pinapanatili ang mga sanga nito sa parehong lalim upang maiwasan ang pagbaba ng pagganap.
• Puno ng binaryo: ang bawat node ay may maximum na dalawang anak (kaliwa at kanan).
• Binary Search Tree (BST): binary tree na may katangiang lahat ng nasa kaliwa ng isang node ay mas maliit at lahat ng nasa kanan ay mas malaki (ayon sa ilang pamantayan sa pag-aayos).
• Puno ng AVL, pula-itim, 2-3 at iba pang mga variantIto ay mga balanseng puno ng paghahanap na ginagarantiyahan ang mahusay na mga limitasyon sa pagiging kumplikado sa mga operasyon ng pagpasok, pagtanggal, at paghahanap.

Sa pagsasagawa, ang mga pinakamadalas na ginagamit sa mga pagsasanay ay ang binary tree at puno ng paghahanap ng binaryKabilang sa mga karaniwang problema ang pagkalkula ng taas ng puno, paghahanap ng k-th maximum value sa isang BST, paglilista ng mga node sa isang tiyak na distansya mula sa ugat, o pagtukoy sa mga ninuno ng isang partikular na node.

Bukod pa rito, ang mga traversal algorithm (preorder, inorder, postorder, level by level) ay mahalaga sa maraming kasunod na proseso: sorted printing, expression evaluation, tree serialization at deserialization, atbp.

Mga graph

Isang grap Binubuo nito ang konsepto ng isang puno sa pamamagitan ng pagpapahintulot sa mga siklo at maraming arbitraryong koneksyon sa pagitan ng mga node. Binubuo ito ng isang hanay ng mga vertex (node) at isang hanay ng mga gilid na nag-uugnay sa mga pares ng mga vertex, minsan ay may kaugnay na timbang o gastos.

Mayroong ilang mga uri ng mga graph: hindi nakadirekta (ang mga gilid ay walang direksyon, ang ugnayan ay bidirectional) at nakadirekta (Ang mga gilid ay may panimulang punto at destinasyon). Maaari rin itong uriin bilang may timbang o walang timbang, konektado o hindi konektado, mayroon o walang mga siklo, atbp.

Sa code, ang mga graph ay karaniwang kinakatawan sa dalawang pangunahing paraan:

• Matris ng katabing: isang matrix kung saan ang cell ay nagpapahiwatig kung mayroong gilid sa pagitan ng vertex i at j (at posibleng ang bigat ng koneksyon).
• Listahan ng katabing lugar: para sa bawat vertex, isang listahan ng mga kalapit nito ang iniimbak, na nakakatipid ng memorya sa mga sparse graph.

Ang pinakaklasikong mga algorithm ng traversal ay ang Paghahanap sa pinakamalawak na bahagi (BFS) at malalimang paghahanap (DFS)Parehong ginagamit ang mga ito bilang pangunahing bloke ng pagbuo para sa maraming problema: pagsuri kung ang isang graph ay konektado, pagtukoy ng mga siklo, paghahanap ng mga konektadong bahagi, atbp.

Sa mga teknikal na pagsusulit, karaniwan na hilingin sa iyo na ipatupad ang BFS at DFS, suriin kung ang isang graph ay bumubuo ng isang puno, bilangin ang bilang ng mga gilid, o maghanap pinakamaikling landas sa pagitan ng dalawang node (halimbawa, sa isang mapa ng mga lungsod) gamit ang mga variant tulad ng Dijkstra o BFS sa mga unweighted graph.

Mga puno ng pagsubok o prefix

Ang pagsubok Ang (o prefix tree) ay isang hugis-tree na istruktura ng datos na na-optimize para sa paghawak ng mga string ng karakter, lalong kapaki-pakinabang kapag nagtatrabaho sa mga diksyunaryo ng salita, mga sistema ng autocomplete, o mga paghahanap ng prefix.

Sa isang pagsubok, ang bawat node ay karaniwang kumakatawan sa isang karakter, at ang mga landas mula sa ugat patungo sa ilang partikular na node ay minarkahan kumpletong salitaAng mga node ng huling salita ay karaniwang minarkahan sa anumang paraan (halimbawa, gamit ang isang Boolean indicator) upang maiba ang mga ito mula sa mga simpleng unlapi.

Kung itatago natin ang mga salitang "top", "thus", at "their" sa isang trie, ibabahagi natin ang bahagi ng unang landas para sa lahat ng mga nagsisimula sa parehong mga letra, na nagbibigay-daan para sa mga paghahanap at mungkahi sa pamamagitan ng unlapi sa napaka-epektibong oras, proporsyonal sa haba ng salitang hinahanap natin at hindi sa kabuuang bilang ng mga salitang nakaimbak.

Kabilang sa mga karaniwang operasyon at problema sa mga pagsubok ang: bilangin kung ilang salita ang nakaimbak, i-print ang lahat ng salita sa leksikograpiyang pagkakasunud-sunod, pagbukud-bukurin ang mga elemento ng isang array sa pamamagitan ng pagpasok sa isang trie, bumuo ng mga wastong salita mula sa isang hanay ng mga letra o bumuo ng mga istrukturang katulad ng isang diksyunaryong T9.

Sa mga konteksto ng panayam, hindi ito ang pinakasimpleng istrukturang hihilingin nila, ngunit regular itong lumalabas sa mga kumpanyang nakikipagtulungan sa mga paghahanap, word processing, o mga sistema ng mungkahi.

Mga talahanayan ng hash at hashing

Pag-hash Ito ay isang pamamaraan para sa pagtatalaga ng isang numeric key (hash) sa bawat piraso ng datos sa isang deterministikong paraan, upang maiimbak at makuha natin ang mga elemento sa halos pare-parehong oras, gamit ang key na iyon bilang isang indeks sa isang panloob na istruktura, karaniwang isang array.

La hash table Ito ang istruktura ng datos na gumagamit ng mekanismong ito. Ang bawat elemento ay iniimbak bilang pares ng key-value: ang key ay binabago sa isang table index gamit ang isang hash function, at ang value (o isang reference dito) ay iniimbak doon. Sa ibang pagkakataon, para maghanap, i-hash lang muli ang key at i-access ang kaukulang posisyon.

Ang pagganap ng isang hash table ay lubos na nakasalalay sa tatlong salik: ang pag-andar ng hash napili (dapat mong ipamahagi nang maayos ang mga susi upang maiwasan ang konsentrasyon), ang laki ng mesa (ang hindi sapat na laki ay nagdudulot ng maraming banggaan) at ang pamamaraan para sa pamamahala ng mga banggaan (pag-uugnay gamit ang mga naka-link na listahan, bukas na pag-address, atbp.). Ito ay katulad ng isang indeks sa databasekung saan ang pagpapasya sa angkop na istruktura ay nagpapabuti sa mga paghahanap at pag-access.

Ang mga karaniwang pagsasanay sa hash programming ay kadalasang nangangailangan, halimbawa, maghanap ng mga simetrikong pares sa isang arrayMuling binubuo ang kumpletong itineraryo ng isang biyahe mula sa mga indibidwal na flight, mabilis na sinusuri kung ang isang array ay isang subset ng isa pa, o bineberipika kung ang dalawang array ay magkahiwalay, lahat sa pamamagitan ng pagsasamantala sa tinatayang O(1) na paghahanap ng hash table.

Sa karamihan ng mga modernong wika, ang mga istrukturang tulad ng mapa, diksyunaryo, hash map o hash set Umaasa sila sa mga hash table sa loob, bagama't may inaalok na high-level interface sa programmer.

Paano nauugnay ang mga algorithm at istruktura ng datos

Ang pagpili ng istruktura ng datos ay direktang tumutukoy kung aling mga algorithm ang may katuturan at kung ano ang magiging kasalimuotan ng mga ito. Isang linear search algorithm sa isang listahang hindi nakaayos Isa-isa itong umuulit sa mga elemento; kung babaguhin natin ang istruktura sa isang balanseng search tree o hash table, mas maganda ang magiging resulta.

Halimbawa, kung gusto mong paulit-ulit na maghanap ng mga susi sa isang malaking koleksyon, iimbak ang data sa isang hash table o binary search tree Nagbibigay-daan ito sa iyo na magdisenyo ng mga search algorithm na mas mabilis kaysa sa kung gagamit ka ng isang simpleng unsorted array. Ganito rin ang naaangkop sa mga priority queues at heaps para sa scheduling o shortest path algorithms.

Sa kabaligtaran, kapag nagdidisenyo ng isang algorithm, madalas mong napagtatanto na kailangan mo ng ilang partikular na katangian: index access, mabilis na pagpapasok sa simula, hierarchical traversals, prefix searches, atbp. Ang mga pangangailangang ito ang gumagabay sa iyong pagpili ng istruktura. mga array, listahan, puno, graph, hash table, mga pagsubok...

Ang angkop na kombinasyon ng algorithm at istruktura ng datos ang siyang nagbibigay-daan para sa mga kumplikadong aplikasyon na maging mahusay at mapapalawakKung walang matibay na pundasyon, ang mga solusyon ay may posibilidad na maging mabagal, mahirap intindihin at panatilihin, o imposibleng iakma habang lumalaki ang dami ng impormasyon.

Samakatuwid, ang pagiging dalubhasa sa mga algorithm at istruktura ng datos ay hindi isang halos kailangang-kailangan na pangangailangan para sa sinumang naghahangad na maging isang mahusay at mapagkumpitensyang programmer sa merkado ng trabaho ngayon.

Paano matutunan ang mga istruktura ng datos at mga algorithm

Maraming tao ang nahihirapan kapag sinusubukan nilang matuto nang mag-isa gamit ang mga platform tulad ng LeetCode o CodewarsKaraniwang nagsisimula sa mga "madaling" ehersisyo at hindi pa rin alam kung saan lalapit sa problema, nauuwi sa paghahanap ng solusyon at hindi malinaw kung paano ito uulitin pagkatapos.

Ang isang praktikal na pamamaraan ay karaniwang pinagsasama ang ilang sangkap: mahusay na teoretikal na paliwanag Ang bawat istruktura at algoritmo ay may kasamang mga biswal na halimbawa, maraming ginabayang pagsasanay, at, kung maaari, suporta mula sa isang taong may karanasan upang matulungan kang pinuhin ang iyong mga kasanayan sa paglutas ng problema.

Sa mundong nagsasalita ng Espanyol, may mga propesyonal na may malawak na karanasan na nakapag-ambag sa pagpapadali ng pagkatuto na ito. Ang isang halimbawa ay ang gawain ng Mga guro na may karanasan sa negosyo at edukasyon na naglathala ng mga libro at kurso tungkol sa mga pangunahing kaalaman sa programming, Java, mga istruktura ng datos, at mga hamon sa programming gamit ang mga laro, na ginagawang naa-access ang mga konseptong ito sa isang masaya at naaangkop na paraan sa mga totoong proyekto.

Karaniwan din para sa mga akademya at mga sentro ng pagsasanay na magsama ng mga partikular na modyul sa mga istruktura ng datos at mga algorithm sa loob ng kanilang mga programa para sa mga web developer o mga programmer ng aplikasyon. Sa maraming pagkakataon, isang partikular na pamamaraan ang binibigyang-diin. napaka-praktikal at nakabatay sa proyekto, na may mga pagsasanay na lalong tumataas ang kahirapan at kunwa ng mga tipikal na teknikal na problema sa panayam.

Kung ikaw ay natigil, makakatulong ang pagsunod sa isang nakabalangkas na ruta: magsimula sa mga array at listahan, dumadaan sa mga stack at queue, pagkatapos ay mga tree at mga pangunahing graph, at sa huli ay mga hash table at pagsubok, palaging nagpapalitan ng teoretikal na paliwanag, maliliit na halimbawa ng code at maraming indibidwal na pagsasanay.

Kapag naghahanda para sa mga panayam, ipinapayong suriin hindi lamang ang mga istruktura kundi pati na rin ang mga brute force algorithm at ang mga kaugnay na klasikal na algorithm (mga traversal, paghahanap, pag-uuri, simpleng backtracking, pangunahing dynamic programming) at tiyaking maipapaliwanag mo nang malakas kung bakit mo pinili ang isang partikular na istruktura at kung ano ang pagiging kumplikado ng iyong solusyon.

Sa paglipas ng panahon at ilang pagkakapare-parehoAng tila pader sa unang tingin ay nagiging isang hanay ng mga pamilyar na kagamitan na halos likas mong ginagamit kapag nahaharap sa mga bagong problema.

Ang mahusay na pag-unawa sa kung ano ang mga algorithm, kung paano gumagana ang mga pangunahing istruktura ng datos, at kung paano sila nauugnay sa isa't isa ay magbibigay-daan sa iyo upang magsulat ng mga programa. mas mabilis, mas malinaw at mas matatagMagbubukas ito ng mga pinto para sa iyo sa mahihirap na proseso ng pagpili at titiyakin na ang iyong mga proyekto, akademiko man o propesyonal, ay nakabatay sa isang matibay na pundasyon na may kinabukasan.