Bookmark and Share
You are here: Home Documentazione Ricette Il problema di Josephus: soluzione in 6 righe
Document Actions

Il problema di Josephus: soluzione in 6 righe
medio

Risoluzione di un classico problema informatico, il problema di Josephus, utilizzando Python e la classe deque.

Il problema

Il problema di Josephus è un classico problema risolvibile da un programma.

Qui riassumo il problema:

Flavius Josephus era uno storico romano di origine ebraiche. Durante la guerra giudaico/romana del primo secolo A.C si trovò in una grotta con i suoi soldati, 40 uomini in tutto, circondato da truppe romane nemiche. Decisero di togliersi la vita disponendosi in un cerchio e contando un uomo ogni tre. Ogni uomo contato si suicidava . . . Josephus, non volendo morire, si posizionò all'ultimo posto.

Nella versione generalizzata del problema ci sono n soldati numerati da 1 a n e ogni k soldati uno viene eliminato. Il conto comincia con il primo soldato. L'algoritmo deve estrarre il numero dell'ultimo sopravvissuto.

Altre soluzioni

Navigando su internet mi sono imbattuto in questo problema: veniva utilizzato come metro di paragone delle performance di vari linguaggi. In questo confronto python era risultato tra i più lenti. Ho quindi analizzato il sorgente (86 righe!!!)  ed ho notato che, chi la scritto non ha idea di come utilizzare python: ha reimplementato una lista linkata mentre in python esiste il tipo list.

Cercando ancora su internet mi sono imbattuto  in una serie di possibili soluzioni più sensate. La performance di queste è 10 volte migliore con 8 volte meno codice (circa una decina di righe).

Ho pensato che era possibile fare meglio. Le operazioni di eliminazione di elementi all'interno di una lista possono avere impatti significativi sulle performance. La lista internamente è implementata come un array e, quindi, ogni operazione all'inizio o all'interno prevede lo spostamento di tutti gli elementi successivi (devono infatti essere consecutivi). 

Una soluzione basata sulla classe deque

La soluzione proposta utilizza invece il modulo deque. Questo implementa una coda con due "ingressi" (double ended queue). Questa si presta per operazioni FIFO (first in first out) in quanto è ottimizzata per inserire o rimuovere elementi da entrambi gli estremi. Ecco la soluzione:

from collections import deque
from itertools import repeat
def jose_deque(n,m):
    soldiers=deque(range(m))
    killed=[]
    for n in repeat(1,m):
        killed.append(soldiers.popleft())
        soldiers.rotate(-n)
    return killed[-1]

La deque ha un utile metodo per ruotare gli elementi della coda. In pratica metto l'elemento 0 della coda tra gli uccisi e ruoto m elementi in fondo alla coda. Continuo così per n volte. Utilizzo repeat anzichè xrange in quanto è risultato un po' più veloce.

Totale:6 righe

Le performance

Le performance di quest'ultimo algoritmo non sono brillanti come avevo sperato ! risulta circa il doppio più lento della soluzione proposta qui! (merito delle elevate performance delle list e dello slicing). in ogni caso circa è 5 volte più veloce di questa.

Rimane se non altro la migliore a lunghezza del codice e leggibilità :-)

Alla prossima !

by Maurizio Lupo last modified 2009-07-22 16:34
 

Supporto

Ottieni un
aiuto veloce e mirato sul forum, gratis!

partecipa al forum

 

Segui le icone

 

Livelli di difficoltà

livello guruSolo per i "guru"!
livello avanzatoPer configuratori e sviluppatori
livello medioPer chi ha già familiarità
livello basePer tutti!

 

I video

video

Il documento è supportato da un video!