Structuri de date și algoritm în Python: tot ce trebuie să știți

Structurile de date și algoritmii din Python sunt două dintre cele mai fundamentale concepte în informatică. Sunt instrumente indispensabile pentru orice programator. Structurile de date din Python se ocupă de organizarea și stocarea datelor în memorie în timp ce un program le procesează. Pe de altă parte, algoritmii Python se referă la setul detaliat de instrucțiuni care ajută la prelucrarea datelor pentru un anumit scop.

Alternativ, se poate spune că diferite structuri de date sunt utilizate în mod logic de algoritmi pentru a rezolva o anumită problemă de analiză a datelor. Fie că este o problemă din lumea reală sau o întrebare tipică legată de codificare, înțelegerea structurilor de date și a algoritmilor în Python este crucială dacă doriți să veniți cu o soluție precisă. În acest articol, veți găsi o discuție detaliată despre diferiți algoritmi Python și structuri de date. Dacă sunteți interesat să aflați mai multe despre Python, consultați cursurile noastre de știință a datelor .

Aflați mai multe: Cele șase structuri de date cele mai frecvent utilizate în R

Ce sunt structurile de date în Python?

Structurile de date sunt o modalitate de organizare și stocare a datelor; ele explică relația dintre date și diverse operații logice care pot fi efectuate asupra datelor. Există multe moduri în care structurile de date pot fi clasificate. O modalitate este de a le clasifica în tipuri de date primitive și non-primitive.

În timp ce tipurile de date primitive includ Integers, Float, Strings și Boolean, tipurile de date non-primitive sunt Array, List, Tuples, Dictionary, Sets and Files. Unele dintre aceste tipuri de date non-primitive, cum ar fi Listă, Tupluri, Dicționare și Seturi, sunt încorporate în Python. Există o altă categorie de structuri de date în Python care este definită de utilizator; adică utilizatorii le definesc. Acestea includ Stack, Queue, Linked List, Tree, Graph și HashMap.

Structuri de date primitive

Acestea sunt structurile de date de bază în Python care conțin valori de date pure și simple și servesc drept blocuri de construcție pentru manipularea datelor. Să vorbim despre cele patru tipuri primitive de variabile din Python:

• Numerele întregi – Acest tip de date este folosit pentru a reprezenta date numerice, adică numere întregi pozitive sau negative fără virgulă. Spune, -1, 3 sau 6.
• Float – Float înseamnă „număr real în virgulă mobilă”. Este folosit pentru a reprezenta numere raționale, care conțin de obicei un punct zecimal, cum ar fi 2,0 sau 5,77. Deoarece Python este un limbaj de programare tip dinamic, tipul de date pe care un obiect îl stochează este mutabil și nu este nevoie să precizați tipul variabilei dvs. în mod explicit.
• Șir – Acest tip de date denotă o colecție de alfabete, cuvinte sau caractere alfanumerice. Este creat prin includerea unei serii de caractere într-o pereche de ghilimele duble sau simple. Pentru a concatena două sau mai multe șiruri de caractere, li se poate aplica operația „+”. Repetarea, splicing, capitalizarea și preluarea sunt câteva dintre celelalte operațiuni cu șiruri din Python. Exemplu: „albastru”, „roșu” etc.
• Boolean – Acest tip de date este util în comparație și expresii condiționale și poate prelua valorile TRUE sau FALSE.

Aflați mai multe: Cadre de date în Python

Structuri de date non-primitive încorporate

Spre deosebire de structurile de date primitive, tipurile de date neprimitive nu stochează doar valori, ci și o colecție de valori în diferite formate. Să aruncăm o privire asupra structurilor de date non-primitive din Python:

• • Liste – Aceasta este cea mai versatilă structură de date din Python și este scrisă ca o listă de elemente separate prin virgulă, cuprinse între paranteze drepte. O listă poate consta atât din elemente eterogene, cât și din elemente omogene. Unele dintre metodele aplicabile pe o Listă sunt index(), append(), extend(), insert(), remove(), pop(), etc. Listele sunt modificabile; adică conținutul lor poate fi modificat, păstrând identitatea intactă.

Sursă

• Tupluri – Tuplurile sunt similare cu Listele, dar sunt imuabile. De asemenea, spre deosebire de Liste, tuplurile sunt declarate între paranteze în loc de paranteze drepte. Caracteristica imuabilității denotă că odată ce un element a fost definit într-un tuplu, acesta nu poate fi șters, reatribuit sau editat. Se asigură că valorile declarate ale structurii de date nu sunt manipulate sau suprascrise.

Sursă

• Dicționare – Dicționarele constau din perechi cheie-valoare. „Cheia” identifică un articol, iar „valoarea” stochează valoarea articolului. Două puncte separă cheia de valoarea sa. Elementele sunt separate prin virgule, cu totul cuprins între paranteze. În timp ce cheile sunt imuabile (numere, șiruri de caractere sau tupluri), valorile pot fi de orice tip.

Sursă

• Seturi – Seturile sunt o colecție neordonată de elemente unice. La fel ca Listele, seturile sunt modificabile și sunt scrise între paranteze drepte, dar nu există două valori identice. Unele metode Set includ count(), index(), any(), all(), etc.

Sursă

• Liste vs. Arrays – Nu există un concept încorporat de Arrays în Python. Matricele pot fi importate folosind pachetul NumPy înainte de a le inițializa. Pentru a afla mai multe despre NumPy, puteți consulta tutorialul nostru python NumPy . Listele și tablourile sunt în mare parte similare, cu excepția unei diferențe - în timp ce tablourile sunt colecții de elemente omogene, Listele includ atât elemente omogene, cât și eterogene.

Checkout: Tipuri de arbore binar

Structuri de date definite de utilizator în Python

Următoarea discuție despre structurile și algoritmii de date în Python este o scurtă prezentare a diferitelor structuri de date definite de utilizator:

• Stive – Stivele sunt structuri de date liniare în Python. Stocarea articolelor în stive se bazează pe principiile First-In/Last-Out (FILO) sau Last-In/First-Out (LIFO). În Stacks, adăugarea unui nou element la un capăt este însoțită de eliminarea unui element de la același capăt. Operațiile „push” și „pop” sunt folosite pentru inserări și respectiv ștergeri. Alte funcții legate de Stack sunt empty(), size() și top(). Stivele pot fi implementate folosind module și structuri de date din biblioteca Python – list, collections.deque și queue.LifoQueue.
• Queue – Similar cu Stivele, Cozile sunt structuri de date liniare. Cu toate acestea, articolele sunt stocate pe baza principiului First-In/ First- Out (FIFO). Într-o coadă, articolul care a fost adăugat cel mai puțin recent este eliminat primul. Operațiunile legate de coadă includ Enqueue (adăugarea elementelor), Queue (ștergerea elementelor), Front și Rear. La fel ca Stacks, Queues pot fi implementate folosind module și structuri de date din biblioteca Python – list, collections.deque și queue.
• Arborele – Arborii sunt structuri de date neliniare în Python și constau din noduri conectate prin muchii. Proprietățile unui arbore sunt că un nod este desemnat nodul rădăcină, altul decât rădăcina, fiecare alt nod are asociat un nod părinte și fiecare nod poate avea un număr arbitrar de noduri copii. O structură de date arbore binar este una ale cărei elemente nu au mai mult de doi copii.
• Lista legată – O serie de elemente de date unite împreună prin legături este denumită Listă legată în Python. Este, de asemenea, o structură de date liniară. Fiecare element de date dintr-o listă legată este conectat la altul folosind pointerul. Deoarece biblioteca Python nu conține Liste Linked, acestea sunt implementate folosind conceptul de noduri. Listele legate au un avantaj față de Arrays prin faptul că au o dimensiune dinamică, cu ușurință de inserare/ștergere a elementelor.
• Graph – Un grafic în Python reprezintă pictural un set de obiecte, cu unele perechi de obiecte conectate prin legături. Nodurile reprezintă obiectele care sunt interconectate, iar legăturile care unesc vârfurile sunt denumite muchii. Tipul de date dicționar Python poate fi folosit pentru a prezenta grafice. În esență, „cheile” dicționarului reprezintă vârfurile, iar „valorile” indică conexiunile sau marginile dintre vârfuri.
• HashMaps/Hash Tables – În acest tip de structură de date, o funcție Hash generează adresa sau valoarea indexului elementului de date. Valoarea indexului servește ca cheie pentru valoarea datelor, permițând accesul mai rapid la date. Ca și în tipul de date din dicționar, Tabelele Hash au perechi cheie-valoare, dar o funcție de hashing generează cheia.

Ce sunt algoritmii în Python?

Algoritmii Python sunt un set de instrucțiuni care sunt executate pentru a obține soluția la o anumită problemă. Deoarece algoritmii nu sunt specifici limbajului, ei pot fi implementați în mai multe limbaje de programare. Nicio regulă standard nu ghidează scrierea algoritmilor. Acestea depind de resurse și de probleme, dar împărtășesc câteva constructe de cod comune, cum ar fi controlul fluxului (if-else) și bucle (do, while, for). În secțiunile următoare, vom discuta pe scurt despre traversarea arborilor, sortarea, căutarea și algoritmii grafici.

Algoritmi de traversare a arborilor

Traversarea este un proces de vizitare a tuturor nodurilor unui Arbore, începând de la nodul rădăcină. Un copac poate fi traversat în trei moduri diferite:

– Parcurgerea în ordine implică vizitarea mai întâi a subarborele din stânga, urmată de rădăcină și apoi de subarborele din dreapta.

– În traversarea precomandă, primul care va fi vizitat este nodul rădăcină, urmat de subarborele din stânga și, în final, subarborele din dreapta.

– În algoritmul de traversare post-comandă, se vizitează mai întâi subarborele din stânga, apoi se vizitează subarborele din dreapta, nodul rădăcină fiind vizitat ultimul.

Aflați mai multe: Cum să creați un arbore decizional perfect

Algoritmi de sortare

Algoritmii de sortare indică modalitățile de aranjare a datelor într-un anumit format. Sortarea asigură că căutarea datelor este optimizată la un nivel înalt și că datele sunt prezentate într-un format care poate fi citit. Să ne uităm la cele cinci tipuri diferite de algoritmi de sortare în Python:

• Bubble Sort – Acest algoritm se bazează pe o comparație în care există schimburi repetate de elemente adiacente dacă acestea sunt într-o ordine incorectă.
• Merge Sort – Pe baza algoritmului de împărțire și cucerire, Merge sort împarte matricea în două jumătăți, le sortează și apoi le combină.
• Sortare prin inserție – Această sortare începe cu compararea și sortarea primelor două elemente. Apoi, al treilea element este comparat cu cele două elemente sortate anterior și așa mai departe.
• Shell Sort – Este o formă de sortare prin inserție, dar aici sunt sortate elementele îndepărtate. O sub-listă mare a unei liste date este sortată, iar dimensiunea listei este redusă progresiv până când toate elementele sunt sortate.
• Selection Sort – Acest algoritm începe prin a găsi valoarea minimă dintr-o listă de elemente și o pune într-o listă sortată. Procesul se repetă apoi pentru fiecare dintre elementele rămase din listă care nu este sortată. Noul element care intră în lista sortată este comparat cu elementele sale existente și plasat în poziția corectă. Procesul continuă până când toate elementele sunt sortate.

Algoritmi de căutare

Algoritmii de căutare ajută la verificarea și preluarea unui element din diferite structuri de date. Un tip de algoritm de căutare aplică metoda căutării secvenţiale în care lista este parcursă secvenţial şi fiecare element este verificat (căutare liniară). În alt tip, căutarea pe intervale, elementele sunt căutate în structuri de date sortate (căutare binară). Să ne uităm la câteva dintre exemple:

• Căutare liniară – În acest algoritm, fiecare articol este căutat secvenţial unul câte unul.
• Căutare binară – Intervalul de căutare este împărțit în mod repetat la jumătate. Dacă elementul de căutat este mai mic decât componenta centrală a intervalului, intervalul este restrâns la jumătatea inferioară. În caz contrar, se îngustează la jumătatea superioară. Procesul se repetă până când se găsește valoarea.

Algoritmi grafici

Există două metode de parcurgere a graficelor folosind marginile lor. Acestea sunt:

• Depth-first Traversal (DFS) – În acest algoritm, un grafic este parcurs într-o mișcare în profunzime. Când orice iterație se confruntă cu o fundătură, se folosește o stivă pentru a merge la următorul vârf și a începe o căutare. DFS este implementat în Python folosind tipurile de date setate.
• Breadth-first Traversal (BFS) – În acest algoritm, un grafic este parcurs într-o mișcare în lățime. Când orice iterație se confruntă cu o fundătură, se folosește o coadă pentru a merge la următorul vârf și a începe o căutare. BFS este implementat în Python folosind structura de date în coadă.

Analiza algoritmului

• Analiză a priori – Aceasta reprezintă o analiză teoretică a algoritmului înainte de implementarea acestuia. Eficiența unui algoritm este măsurată prin presupunerea că factori, cum ar fi viteza procesorului, sunt constanți și nu au nicio consecință asupra algoritmului.
• O analiză posterioară – Aceasta se referă la analiza empirică a algoritmului după implementarea acestuia. Un limbaj de programare este folosit pentru a implementa algoritmul selectat, urmat de executarea acestuia pe un computer. Această analiză colectează statistici, cum ar fi timpul și spațiul necesar pentru rularea algoritmului.

Concluzie

Indiferent dacă sunteți un veteran în programare sau nou la aceasta, nu puteți ignora structurile de date și algoritmii din Python . Aceste concepte sunt cruciale atunci când efectuați operațiuni pe date și trebuie să optimizați procesarea datelor. În timp ce structurile de date ajută la organizarea informațiilor, algoritmii oferă linii directoare pentru a rezolva problema analizei datelor. Împreună, ele oferă oamenilor de știință informatică o modalitate de procesare a informațiilor date ca date de intrare.

Dacă sunteți curios să aflați despre știința datelor, consultați programul Executive PG în știința datelor de la IIIT-B și upGrad, care este creat pentru profesioniști care lucrează și oferă peste 10 studii de caz și proiecte, ateliere practice practice, mentorat cu experți din industrie, 1 -on-1 cu mentori din industrie, peste 400 de ore de învățare și asistență profesională cu firme de top.