Rilasciato · in miglioramento
Algorithm
Come funzionano array, liste concatenate, stack, code e tabelle hash, quanto costa ogni operazione e come scegliere la struttura giusta.
Una struttura dati è un modo di disporre i dati in memoria insieme alle operazioni che su quella disposizione risultano economiche. Questo argomento copre le cinque strutture su cui si basa quasi ogni programma: array e array dinamici, liste concatenate, stack, code e deque, tabelle hash. Spiega anche la memoria contigua rispetto a quella collegata, le funzioni hash, le collisioni e il fattore di carico.
La struttura scelta decide se un'operazione costa O(1) oppure O(n). Realizzare una coda togliendo elementi dall'inizio di una lista, o verificare l'appartenenza scorrendo una lista, rende un programma molto più lento quando i dati crescono. Sapere che cosa sono davvero list, deque, dict e set in Python, vector, deque e unordered_map in C++, ArrayList, ArrayDeque e HashMap in Java, e Array, Map e Set in TypeScript aiuta a evitare queste trappole, ed è la prima cosa che verificano i colloqui tecnici.
Conviene iniziare seguendo a mano ogni struttura su un piccolo esempio per vedere che cosa si sposta in memoria. Poi si implementano uno stack, una coda con buffer circolare e una mappa hash con concatenamento separato, si riassumono i costi in una tabella e li si misura con un timer. Infine si affrontano esercizi in cui l'abilità principale è scegliere la struttura adatta.
Gli array offrono accesso O(1) per indice e un buon uso della cache; le liste concatenate consentono inserimenti e cancellazioni O(1) accanto a un nodo già noto.
Un array dinamico cresce di un fattore costante e copia gli elementi, quindi le rare aggiunte costose restano in media O(1).
Uno stack estrae l'elemento più recente, una coda il più vecchio. Deque e buffer circolari rendono O(1) le operazioni a entrambe le estremità.
Una tabella hash associa le chiavi a bucket per ricerche O(1) in media, risolve le collisioni ad esempio con il concatenamento e si ingrandisce quando il fattore di carico supera una soglia.
Una mappa hash con concatenamento separato: l'hash della chiave modulo il numero di bucket sceglie il bucket, per una chiave già presente si sostituisce solo il valore e, quando il fattore di carico supera 0,75, i bucket raddoppiano e tutte le coppie vengono reinserite. Lo script mostra anche una lista usata come stack e una deque usata come coda.
data_structures.py
from collections import deque
class HashMap:
"""Separate chaining: each bucket is a list of (key, value) pairs."""
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.size > 0.75 * len(self.buckets): # load factor limit
old = self.buckets
self.buckets = [[] for _ in range(2 * len(old))]
for pairs in old:
for k, v in pairs:
self._bucket(k).append((k, v))
def get(self, key, default=None):
for k, v in self._bucket(key):
if k == key:
return v
return default
stack = [1, 2, 3]
stack.append(4)
print("stack pop:", stack.pop()) # 4 (LIFO)
queue = deque([1, 2, 3])
queue.append(4)
print("queue popleft:", queue.popleft()) # 1 (FIFO)
ages = HashMap()
for name, age in [("ada", 36), ("alan", 41), ("grace", 85)]:
ages.put(name, age)
ages.put("ada", 37)
print("ada:", ages.get("ada"), "size:", ages.size) # ada: 37 size: 3
python data_structures.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Strutture dati di base.
Fai domande, condividi la tua esperienza e scambia opinioni su Strutture dati di base.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.