Python bisect: Guida all’Algoritmo di Bisezione degli Array

Introduzione

Il modulo bisect di Python offre strumenti per mantenere una lista ordinata senza doverla riordinare dopo ogni inserimento. Questo è particolarmente utile quando si gestiscono liste lunghe con operazioni di confronto costose, migliorando l’efficienza rispetto alle ricerche lineari o ai riordinamenti frequenti.

Funzioni Principali del Modulo bisect

Il modulo bisect fornisce diverse funzioni chiave:

• bisect_left(a, x, lo=0, hi=len(a), *, key=None): Restituisce il punto di inserimento per x nella lista a per mantenere l’ordine ordinato. Se x è già presente, il punto di inserimento sarà prima delle occorrenze esistenti.
• bisect_right(a, x, lo=0, hi=len(a), *, key=None): Simile a bisect_left(), ma restituisce un punto di inserimento dopo le occorrenze esistenti di x in a.
• insort_left(a, x, lo=0, hi=len(a), *, key=None): Inserisce x nella lista a in ordine ordinato, prima delle occorrenze esistenti di x.
• insort_right(a, x, lo=0, hi=len(a), *, key=None): Simile a insort_left(), ma inserisce x dopo le occorrenze esistenti.

Esempi Pratici

Inserimento in una Lista Ordinata

Supponiamo di avere una lista ordinata e vogliamo inserire un nuovo elemento mantenendo l’ordine:

import bisect

# Lista ordinata
lista = [10, 20, 30, 40, 50]

# Nuovo elemento da inserire
nuovo_elemento = 35

# Trova la posizione di inserimento
posizione = bisect.bisect_left(lista, nuovo_elemento)

# Inserisce l'elemento nella posizione trovata
bisect.insort_left(lista, nuovo_elemento)

print(lista)

Output:

[10, 20, 30, 35, 40, 50]

Ricerca Binaria in una Lista Ordinata

Il modulo bisect può essere utilizzato per implementare una ricerca binaria efficiente:

import bisect

def ricerca_binaria(lista, elemento):
    posizione = bisect.bisect_left(lista, elemento)
    if posizione != len(lista) and lista[posizione] == elemento:
        return posizione
    else:
        return -1

# Lista ordinata
lista = [5, 10, 15, 20, 25]

# Elemento da cercare
elemento = 15

# Esegue la ricerca binaria
risultato = ricerca_binaria(lista, elemento)

print(f'Elemento trovato in posizione: {risultato}')

Output:

Elemento trovato in posizione: 2

Assegnazione di Valori Basata su Intervalli

È possibile utilizzare bisect per mappare valori a intervalli specifici:

import bisect

def assegna_valore(punteggio, intervalli=[60, 70, 80, 90], voti='FDCBA'):
    i = bisect.bisect(intervalli, punteggio)
    return voti[i]

# Lista di punteggi
punteggi = [55, 65, 75, 85, 95]

# Assegna voti ai punteggi
voti = [assegna_valore(p) for p in punteggi]

print(voti)

Output:

['F', 'D', 'C', 'B', 'A']

Utilizzo con Oggetti Personalizzati

Il modulo bisect può essere utilizzato con oggetti personalizzati definendo il metodo __lt__:

import bisect

class Persona:
    def __init__(self, nome, eta):
        self.nome = nome
        self.eta = eta

    def __lt__(self, altra):
        return self.eta < altra.eta

    def __repr__(self):
        return f'{self.nome} ({self.eta})'

# Lista di persone ordinate per età
persone = [
    Persona('Alice', 30),
    Persona('Bob', 25),
    Persona('Charlie', 35)
]

# Ordina la lista
persone.sort()

# Nuova persona da inserire
nuova_persona = Persona('David', 28)

# Inserisce la nuova persona mantenendo l'ordine
bisect.insort_left(persone, nuova_persona)

print(persone)

Output:

[Bob (25), David (28), Alice (30), Charlie (35)]

Considerazioni sulle Prestazioni

Le funzioni di ricerca del modulo bisect operano in tempo O(log n), rendendole efficienti per l’individuazione di punti di inserimento in liste ordinate. Tuttavia, le funzioni di inserimento (insort_left e insort_right) hanno una complessità O(n) a causa del costo dell’operazione di inserimento stessa.

Riferimenti

Per approfondire il modulo bisect e le sue applicazioni, puoi consultare le seguenti risorse:

• Documentazione ufficiale di Python sul modulo bisect

Conclusione

Il modulo bisect è uno strumento potente per gestire liste ordinate in Python, offrendo funzioni efficienti per l’inserimento e la ricerca. La sua comprensione e utilizzo possono migliorare significativamente le prestazioni delle applicazioni che richiedono operazioni frequenti su dati ordinati.