Si, hai pienamente ragione. Ieri ho giusto concluso pensieri del genere.
Come primo approccio all'argomento ho voluto valutare i tempi di esecuzione che si ottengono utilizzando rigidamente l'algoritmo proposto nel Tuo primo post e quello da me implementato (in variante), ottenendo risultati che confermano in pieno quanto da Te esposto.
Contrariamente a quanto mi aspettavo, la variante da me proposta non migliora i tempi di esecuzione, peggiorandoli leggermente, anzi, ciò a causa delle comparazioni nella funzione "V()", che hanno una notevole incidenza, mentre implementare in "U()" la cancellazione e restituzione comporta una tempistica molto più breve di quanto mi aspettassi, segue il codice delle funzioni nei due casi e le tempistiche medie riscontrate:
algoritmo proposto da @melfnt nel 1°post:
Codice: Seleziona tutto
def V(v):
global visitate
if v in visitate:
visitate.remove(v)
visitate.append(v)
def U():
global visitate
# se esiste, cancella la pagina corrente
if visitate:
visitate.pop()
# ricontrolla e restituisce la pagina precedente
if visitate:
return visitate[-1]
return None
Tempi :
============== RESTART: /home/nuzzo/my_script/test/pyt/melnf.py ==============
V = 4 TVM = 0.0000041723 U = 3 TUM = 0.0000011126 TME = 0.0000052849
Output = c b a
V = 6 TVM = 0.0000039339 U = 5 TUM = 0.0000006676 TME = 0.0000046015
Output = a d d c a
V = 5 TVM = 0.0000041485 U = 3 TUM = 0.0000010331 TME = 0.0000051816
Output = d c a
V = 4 TVM = 0.0000043511 U = 5 TUM = 0.0000006199 TME = 0.0000049710
Output = b a
V = 12 TVM = 0.0000036359 U = 8 TUM = 0.0000003874 TME = 0.0000040233
Output = a b a c e f a d
mia implementazione :
Codice: Seleziona tutto
def V(v):
global corrente, visitate
if v in visitate:
visitate.remove(v)
if corrente and v != corrente:
visitate.append(corrente)
corrente = v
def U():
global visitate
if visitate:
return visitate.pop()
return None
tempi :
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
V = 4 TVM = 0.0000038147 U = 3 TUM = 0.0000010331 TME = 0.0000048478
Output = c b a
V = 6 TVM = 0.0000043313 U = 5 TUM = 0.0000005722 TME = 0.0000049035
Output = a d d c a
V = 5 TVM = 0.0000045300 U = 3 TUM = 0.0000009537 TME = 0.0000054836
Output = d c a
V = 4 TVM = 0.0000042319 U = 5 TUM = 0.0000004292 TME = 0.0000046611
Output = b a
V = 12 TVM = 0.0000040531 U = 8 TUM = 0.0000003576 TME = 0.0000044107
Output = a b a c e f a d
Devo dire che son rimasto molto sorpreso dalla apparente "incoerenza" delle tempistiche medie (tutti i tempi riportati sono medie), tant'è che ho voluto eseguire una valutazione di cosa succede ad ogni singola esecuzione, questo è un esempio del maggiore input per l'algorimo alla base del Tuo post :
Codice: Seleziona tutto
Input : a - V_TIME = 0.0000071526
Input : b - V_TIME = 0.0000143051
Input : c - V_TIME = 0.0000216961
Input : d - V_TIME = 0.0000293255
Input : a - V_TIME = 0.0000376701
Input : c - V_TIME = 0.0000467300
Output : a - U_TIME = 0.0000081062
Input : b - V_TIME = 0.0000553131
Input : e - V_TIME = 0.0000629425
Output : b - U_TIME = 0.0000078678
Output : a - U_TIME = 0.0000073910
Input : f - V_TIME = 0.0000705719
Input : e - V_TIME = 0.0000777245
Input : c - V_TIME = 0.0000858307
Input : b - V_TIME = 0.0000929832
Output : c - U_TIME = 0.0000081062
Output : e - U_TIME = 0.0000073910
Output : f - U_TIME = 0.0000078678
Output : a - U_TIME = 0.0000083447
Output : d - U_TIME = 0.0000078678
V = 12 TVM = 0.0000077486 U = 8 TUM = 0.0000009835 TME = 0.0000087321
Output = a b a c e f a d
È evidente la difficiltà che si ha nella valutazione di tempistiche in nano-secondi, e la pesante difficoltà derivante dall'utilizzo di funzioni pre-costituite nel linguaggio ... La Tua affermazione che python non è un linguaggio adatto a tal genere di valutazioni è più che condivisibile : sulla stessa macchina, programma e funzione di hanno differenze temporali sino ad un fattore 10.
a completare il discorso, per l'input dati ho utilizzato un file CSV così fatto :
Codice: Seleziona tutto
a;b;c;d;;;
a;b;;c;d;e;;f;;;
a;b;c;d;b;;;
a;b;c;;;;;a;
a;b;c;d;a;c;;b;e;;;f;e;c;b;;;;;
mentre il processo di valutazione impostato e comune ad entrambi gli algoritmi è il seguente :
Codice: Seleziona tutto
if __name__ == '__main__':
f = None
try:
f = open('melfn.input', 'r')
testo = f.read().split()
except FileNotFoundError:
print('File non trovato')
exit(1)
finally:
if f:
f.close()
for riga in testo:
v_num = 0
v_time = 0.0
u_num = 0
u_time = 0.0
for elem in riga.split(';'):
if elem:
v_num += 1
i_time = time.time()
V(elem)
f_time = time.time()
v_time += (f_time - i_time)
else:
u_num += 1
i_time = time.time()
corrente = U()
f_time = time.time()
u_time = (f_time - i_time)
if corrente:
output += corrente + ' '
# calcolo i tempi medi di esecuzione
v_time = v_time / v_num
u_time = u_time / u_num
output = 'V = %d TVM = %.10f U = %d TUM = %.10f TME = %.10f\nOutput = %s' % (
v_num, v_time, u_num, u_time, v_time + u_time, output
)
print(output)
output = ''
Ovviamente, con gli opportuni import e variabili globali.
In conclusione, il problema in esame non è un discorso così semplice ed è da affrontarsi con linguaggi di livello quanto più basso possibile, strati software ridondanti come presenti in python falsano sin troppo le valutazioni e rendono necessaria una conoscenza ben approfondita per affrontarlo ... in linea di massima "se funziona" è il massimo ottenibile da conoscenze tipo la mia.
Grazie del codice segnalato, mi servirà per procedere su questo interessante argomento ma è, necessariamente, un discorso lungo.
in merito al "far di meglio", pur sempre nella mia empiricità : sostituendo le funzioni "U(), V()" con questa :
Codice: Seleziona tutto
def visit(v):
global visitate
if v:
if v in visitate:
visitate.remove(v)
visitate.append(v)
else:
if visitate: visitate.pop()
if visitate:
return visitate[-1]
return None
richiamata così :
Codice: Seleziona tutto
for riga in testo:
e_num = 0
e_time = 0.0
for elem in riga.split(';'):
e_num += 1
i_time = time.time()
corrente = visit(elem)
f_time = time.time()
e_time += (f_time - i_time)
if corrente:
output += corrente + ' '
# calcolo tempo medio di esecuzione
e_time = e_time / e_num
output = 'Elementi = %d TME = %.10f - Output = %s' % (
e_num, e_time, output
)
print(output)
output = ''
si hanno tempi medi di esecuzione, apparentemente, leggermente più brevi
Codice: Seleziona tutto
============= RESTART: /home/nuzzo/my_script/test/pyt/melnf_2.py =============
Elementi = 7 TME = 0.0000047343 - Output = c b a
Elementi = 11 TME = 0.0000039447 - Output = a d d c a
Elementi = 8 TME = 0.0000042617 - Output = d c a
Elementi = 9 TME = 0.0000040796 - Output = b a
Elementi = 20 TME = 0.0000037789 - Output = a b a c e f a d
... probabilmente, dovuti al fatto che le verifiche vengono effettuata sulla sola esistenza di contenuti nella lista "visitate". In seguito, spero, di riuscire a definire quanto esattamente succede ... caldo e mare permettendo