Strutture dati e algoritmo in Python: tutto ciò che devi sapere

Le strutture dati e gli algoritmi in Python sono due dei concetti più fondamentali nell'informatica. Sono strumenti indispensabili per qualsiasi programmatore. Le strutture dati in Python si occupano dell'organizzazione e dell'archiviazione dei dati nella memoria mentre un programma li sta elaborando. D'altra parte, gli algoritmi Python si riferiscono all'insieme dettagliato di istruzioni che aiutano nell'elaborazione dei dati per uno scopo specifico.

In alternativa, si può dire che diverse strutture di dati sono logicamente utilizzate da algoritmi per elaborare un particolare problema di analisi dei dati. Che si tratti di un problema del mondo reale o di una tipica domanda relativa alla codifica, la comprensione delle strutture dati e degli algoritmi in Python è fondamentale se si desidera trovare una soluzione accurata. In questo articolo troverai una discussione dettagliata sui diversi algoritmi e strutture dati Python. Se sei interessato a saperne di più su Python, dai un'occhiata ai nostri corsi di scienza dei dati .

Ulteriori informazioni: Le sei strutture dati più comunemente utilizzate in R

Cosa sono le strutture dati in Python?

Le strutture dati sono un modo per organizzare e memorizzare i dati; spiegano la relazione tra i dati e le varie operazioni logiche che possono essere eseguite sui dati. Ci sono molti modi in cui le strutture di dati possono essere classificate. Un modo è classificarli in tipi di dati primitivi e non primitivi.

Mentre i tipi di dati primitivi includono Integers, Float, Strings e Boolean, i tipi di dati non primitivi sono Array, List, Tuple, Dictionary, Sets e Files. Alcuni di questi tipi di dati non primitivi, come List, Tuple, Dictionaries e Sets, sono integrati in Python. C'è un'altra categoria di strutture dati in Python che è definita dall'utente; cioè, gli utenti li definiscono. Questi includono Stack, Queue, Linked List, Tree, Graph e HashMap.

Strutture dati primitive

Queste sono le strutture di dati di base in Python che contengono valori di dati puri e semplici e fungono da elementi costitutivi per la manipolazione dei dati. Parliamo dei quattro tipi primitivi di variabili in Python:

• Interi: questo tipo di dati viene utilizzato per rappresentare dati numerici, ovvero numeri interi positivi o negativi senza punto decimale. Dì, -1, 3 o 6.
• Float: float significa "numero reale a virgola mobile". Viene utilizzato per rappresentare numeri razionali, di solito contenenti un punto decimale come 2,0 o 5,77. Poiché Python è un linguaggio di programmazione tipizzato dinamicamente, il tipo di dati archiviato in un oggetto è mutevole e non è necessario dichiarare esplicitamente il tipo della variabile.
• Stringa: questo tipo di dati indica una raccolta di alfabeti, parole o caratteri alfanumerici. Viene creato includendo una serie di caratteri all'interno di una coppia di virgolette doppie o singole. Per concatenare due o più stringhe, è possibile applicare ad esse l'operazione '+'. Ripetizione, giunzione, capitalizzazione e recupero sono alcune delle altre operazioni su String in Python. Esempio: 'blu', 'rosso', ecc.
• Booleano: questo tipo di dati è utile nelle espressioni di confronto e condizionali e può assumere i valori VERO o FALSO.

Saperne di più: frame di dati in Python

Strutture di dati non primitive integrate

A differenza delle strutture dati primitive, i tipi di dati non primitivi non solo memorizzano valori, ma una raccolta di valori in formati diversi. Diamo un'occhiata alle strutture dati non primitive in Python:

• • Elenchi: questa è la struttura dati più versatile in Python ed è scritta come un elenco di elementi separati da virgole racchiusi tra parentesi quadre. Una lista può essere composta da elementi sia eterogenei che omogenei. Alcuni dei metodi applicabili su una List sono index(), append(), extend(), insert(), remove(), pop(), ecc. Le liste sono modificabili; cioè il loro contenuto può essere modificato, mantenendo intatta l'identità.

Fonte

• Tuple: le tuple sono simili alle liste ma sono immutabili. Inoltre, a differenza delle Liste, le Tuple sono dichiarate tra parentesi invece che tra parentesi quadre. La caratteristica dell'immutabilità indica che una volta che un elemento è stato definito in una tupla, non può essere cancellato, riassegnato o modificato. Garantisce che i valori dichiarati della struttura dati non vengano manipolati o sovrascritti.

Fonte

• Dizionari: i dizionari sono costituiti da coppie chiave-valore. La "chiave" identifica un articolo e il "valore" memorizza il valore dell'articolo. I due punti separano la chiave dal suo valore. Gli elementi sono separati da virgole, con il tutto racchiuso tra parentesi graffe. Sebbene le chiavi siano immutabili (numeri, stringhe o tuple), i valori possono essere di qualsiasi tipo.

Fonte

• Set: i set sono una raccolta non ordinata di elementi unici. Come gli elenchi, gli insiemi sono modificabili e scritti tra parentesi quadre, ma non possono essere uguali due valori. Alcuni metodi Set includono count(), index(), any(), all(), ecc.

Fonte

• Liste vs. Array – Non esiste un concetto integrato di array in Python. Gli array possono essere importati utilizzando il pacchetto NumPy prima di inizializzarli. Per saperne di più su NumPy, puoi dare un'occhiata al nostro tutorial python su NumPy . Liste e matrici sono per lo più simili tranne una differenza: mentre le matrici sono raccolte di soli elementi omogenei, le liste includono elementi sia omogenei che eterogenei.

Checkout: tipi di albero binario

Strutture dati definite dall'utente in Python

Il prossimo passo nella nostra discussione sulle strutture dati e sugli algoritmi in Python è una breve panoramica delle diverse strutture dati definite dall'utente:

• Stack: gli stack sono strutture di dati lineari in Python. La conservazione degli elementi negli Stack si basa sui principi di First-In/Last-Out (FILO) o Last-In/First-Out (LIFO). In Stacks, l'aggiunta di un nuovo elemento a un'estremità è accompagnata dalla rimozione di un elemento dalla stessa estremità. Le operazioni 'push' e 'pop' vengono utilizzate rispettivamente per inserimenti e cancellazioni. Altre funzioni relative a Stack sono empty(), size() e top(). Gli stack possono essere implementati utilizzando moduli e strutture dati dalla libreria Python: list, collections.deque e queue.LifoQueue.
• Coda – Simile a Stack, le code sono strutture di dati lineari. Tuttavia, gli articoli vengono archiviati in base al principio FIFO (First In/First Out). In una coda, l'elemento aggiunto meno di recente viene rimosso per primo. Le operazioni relative alla coda includono Accodamento (aggiunta di elementi), Eliminazione dalla coda (eliminazione di elementi), Anteriore e Posteriore. Come Stacks, le code possono essere implementate utilizzando moduli e strutture dati dalla libreria Python: list, collections.deque e queue.
• Albero: gli alberi sono strutture di dati non lineari in Python e sono costituiti da nodi collegati da bordi. Le proprietà di un albero sono che un nodo è designato come nodo radice, diverso dalla radice, ogni altro nodo ha un nodo padre associato e ogni nodo può avere un numero arbitrario di nodi figli. Una struttura dati albero binaria è una struttura i cui elementi non hanno più di due figli.
• Elenco collegato: una serie di elementi di dati uniti tra loro tramite collegamenti è definita elenco collegato in Python. È anche una struttura dati lineare. Ogni elemento di dati in un elenco collegato è connesso a un altro tramite il puntatore. Poiché la libreria Python non contiene elenchi collegati, vengono implementati utilizzando il concetto di nodi. Gli elenchi collegati hanno un vantaggio rispetto agli array in quanto hanno una dimensione dinamica, con facilità di inserimento/eliminazione di elementi.
• Grafico: un grafico in Python rappresenta graficamente un insieme di oggetti, con alcune coppie di oggetti collegate da collegamenti. I vertici rappresentano gli oggetti che sono interconnessi e i collegamenti che uniscono i vertici sono definiti bordi. Il tipo di dati del dizionario Python può essere utilizzato per presentare i grafici. In sostanza, le 'chiavi' del dizionario rappresentano i vertici, ei 'valori' indicano le connessioni o gli spigoli tra i vertici.
• HashMaps/Tabelle hash: in questo tipo di struttura dati, una funzione hash genera l'indirizzo o il valore dell'indice dell'elemento dati. Il valore dell'indice funge da chiave per il valore dei dati consentendo un accesso più rapido ai dati. Come nel tipo di dati del dizionario, le tabelle hash hanno coppie chiave-valore, ma una funzione di hash genera la chiave.

Cosa sono gli algoritmi in Python?

Gli algoritmi Python sono un insieme di istruzioni che vengono eseguite per ottenere la soluzione a un determinato problema. Poiché gli algoritmi non sono specifici del linguaggio, possono essere implementati in diversi linguaggi di programmazione. Nessuna regola standard guida la scrittura di algoritmi. Sono dipendenti da risorse e problemi, ma condividono alcuni costrutti di codice comuni, come il controllo di flusso (if-else) e i loop (do, while, for). Nelle sezioni seguenti, discuteremo brevemente degli algoritmi di Tree Traversal, Sorting, Searching e Graph.

Algoritmi di attraversamento degli alberi

L'attraversamento è un processo di visita di tutti i nodi di un albero, a partire dal nodo radice. Un albero può essere attraversato in tre modi diversi:

– L'attraversamento in ordine implica la visita prima del sottoalbero a sinistra, seguito dalla radice e quindi dal sottoalbero di destra.

– Nell'attraversamento del preordine, il primo da visitare è il nodo radice, seguito dal sottoalbero sinistro e, infine, dal sottoalbero destro.

– Nell'algoritmo di attraversamento post-ordine, viene visitato per primo il sottoalbero sinistro, quindi viene visitato il sottoalbero destro, con il nodo radice visitato per ultimo.

Ulteriori informazioni: Come creare un albero decisionale perfetto

Algoritmi di ordinamento

Gli algoritmi di ordinamento indicano i modi per disporre i dati in un formato particolare. L'ordinamento garantisce che la ricerca dei dati sia ottimizzata a un livello elevato e che i dati vengano presentati in un formato leggibile. Diamo un'occhiata ai cinque diversi tipi di algoritmi di ordinamento in Python:

• Ordinamento a bolle: questo algoritmo si basa sul confronto in cui si verificano scambi ripetuti di elementi adiacenti se sono in un ordine errato.
• Unisci ordinamento: in base all'algoritmo divide et impera, unisci ordinamento divide l'array in due metà, le ordina e quindi le combina.
• Ordinamento per inserimento: questo ordinamento inizia con il confronto e l'ordinamento dei primi due elementi. Quindi, il terzo elemento viene confrontato con i due elementi precedentemente ordinati e così via.
• Ordinamento shell: è una forma di ordinamento per inserimento, ma qui vengono ordinati gli elementi lontani. Viene ordinato un grande sottoelenco di un determinato elenco e la dimensione dell'elenco viene progressivamente ridotta fino a quando tutti gli elementi non vengono ordinati.
• Ordinamento selezione: questo algoritmo inizia trovando il valore minimo da un elenco di elementi e lo inserisce in un elenco ordinato. Il processo viene quindi ripetuto per ciascuno degli elementi rimanenti nell'elenco che non è ordinato. Il nuovo elemento che entra nell'elenco ordinato viene confrontato con i suoi elementi esistenti e posizionato nella posizione corretta. Il processo continua finché tutti gli elementi non vengono ordinati.

Algoritmi di ricerca

Gli algoritmi di ricerca aiutano a controllare e recuperare un elemento da diverse strutture di dati. Un tipo di algoritmo di ricerca applica il metodo della ricerca sequenziale in cui l'elenco viene attraversato in sequenza e ogni elemento viene verificato (ricerca lineare). In un altro tipo, la ricerca a intervalli, gli elementi vengono ricercati in strutture di dati ordinate (ricerca binaria). Diamo un'occhiata ad alcuni degli esempi:

• Ricerca lineare: in questo algoritmo, ogni elemento viene ricercato in sequenza uno per uno.
• Ricerca binaria: l'intervallo di ricerca viene diviso ripetutamente a metà. Se l'elemento da cercare è inferiore alla componente centrale dell'intervallo, l'intervallo viene ristretto alla metà inferiore. Altrimenti, si restringe alla metà superiore. Il processo viene ripetuto finché non viene trovato il valore.

Algoritmi dei grafici

Ci sono due metodi per attraversare i grafici usando i loro bordi. Questi sono:

• Depth-first Traversal (DFS) – In questo algoritmo, un grafico viene attraversato in un movimento in profondità. Quando qualsiasi iterazione affronta un vicolo cieco, viene utilizzato uno stack per passare al vertice successivo e avviare una ricerca. DFS è implementato in Python utilizzando i tipi di dati impostati.
• Width-first Traversal (BFS) – In questo algoritmo, un grafo viene attraversato in un movimento in ampiezza. Quando qualsiasi iterazione affronta un vicolo cieco, viene utilizzata una coda per passare al vertice successivo e avviare una ricerca. BFS è implementato in Python utilizzando la struttura dei dati della coda.

Analisi dell'algoritmo

• A Priori Analysis – Rappresenta un'analisi teorica dell'algoritmo prima della sua implementazione. L'efficienza di un algoritmo viene misurata presumendo che i fattori, come la velocità del processore, siano costanti e non abbiano conseguenze sull'algoritmo.
• Un'analisi posteriore: si riferisce all'analisi empirica dell'algoritmo dopo la sua implementazione. Un linguaggio di programmazione viene utilizzato per implementare l'algoritmo selezionato, seguito dalla sua esecuzione su un computer. Questa analisi raccoglie statistiche, come il tempo e lo spazio necessari per l'esecuzione dell'algoritmo.

Conclusione

Che tu sia un veterano della programmazione o un principiante, non puoi ignorare le strutture dati e gli algoritmi in Python . Questi concetti sono fondamentali quando si eseguono operazioni sui dati ed è necessario ottimizzare l'elaborazione dei dati. Mentre le strutture dei dati aiutano nell'organizzazione delle informazioni, gli algoritmi forniscono le linee guida per risolvere il problema dell'analisi dei dati. Insieme, forniscono agli informatici un modo per elaborare le informazioni fornite come dati di input.

Se sei curioso di conoscere la scienza dei dati, dai un'occhiata al programma Executive PG in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1 -on-1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.