[PUZZLE] history

Linguaggi di programmazione: php, perl, python, C, bash, ecc.

[PUZZLE] history

Messaggioda melfnt » mercoledì 1 agosto 2018, 10:09

Questa discussione non è una richiesta di aiuto, bensì il testo di un problema stimolante, che metterà alla prova le vostre abilità!
Postate la vostra soluzione qua sotto, vi sfido a trovarne una il più efficiente possibile!

PROBLEMA
Si vuole implementare un gestore della "history" del browser. Le funzionalità richieste sono:
- V page richiamata quando si visita una pagina.
- U per tornare indietro alla pagina precedente. La funzione U deve restituire la pagina visitata immediatamente prima a quella corrente.

Si assuma per semplicità che le pagine siano identificate da stringhe alfanumeriche.

Tutte le pagine visitate devono essere memorizzate mantenendo l'ordinamento, in modo che se viene utilizzata la funzione U più di una volta, le pagine vengono restituite nell'ordine inverso rispetto a quello in cui sono state visitate.

Per esempio, la sequenza di operazioni:
Codice: Seleziona tutto
V a
V b
V c
V d
U
U
U


produce questo output: c b a

Ovviamente le funzioni U e V possono essere interallacciate, per esempio la sequenza di operazioni:
Codice: Seleziona tutto
V a
V b
U
V c
V d
V e
U
V f
U
U
U


produce questo output: a d d c a
Si noti come la funzione U, oltre che restituire la pagina immediatamente prima a quella corrente, "cancella" la pagina corrente dalla history.

Se una pagina già presente nella history viene visitata nuovamente, dovrà essere memorizzata una sola volta (nella posizione più recente) e quindi potrà essere restituita o cancellata solo una volta dalla funzione U.
Per esempio, consideriamo la seguente sequenza di operazioni, nella quale viene visitata più volte la pagina b:
Codice: Seleziona tutto
V a
V b
V c
V d
V b
U
U
U

l'output è il seguente: d c a
Per la motivazione detta prima, l'ultima pagina in output è una a e non una b.

Se la history è vuota, la funzione U non produce alcun output; la sequenza di operazioni:
Codice: Seleziona tutto
V a
V b
V c
U
U
U
U
V a
U


produce il seguente output: b a

si scriva un programma in un linguaggio di programmazione a piacere che implementi le funzionalità U e V, rispettando le specifiche descritte sopra. Supponendo che ci siano n pagine nella history, si spedifichi la complessità in tempo delle due funzionalità.

Formato dell'input
Il file di input è composto da una sequenza di operazioni, una per riga. Ogni operazione ha il formato V page oppure U.

Formato dell'output
Il file di output è composto da una sola riga, contenente le pagine risultanti dall'esecuzione delle operazioni presenti sul file di input, separate da uno spazio.

Esempi
INPUT 1
Codice: Seleziona tutto
V a
V b
V c
V d
U
U
U


OUTPUT ATTESO 1:
Codice: Seleziona tutto
c b a


INPUT 2:
Codice: Seleziona tutto
V a
V b
U
V c
V d
V e
U
V f
U
U
U


OUTPUT ATTESO 2:
Codice: Seleziona tutto
a d d c a


INPUT 3:
Codice: Seleziona tutto
V a
V b
V c
V d
V b
U
U
U


OUTPUT ATTESO 3:
Codice: Seleziona tutto
d c a


INPUT 4:
Codice: Seleziona tutto
V a
V b
V c
U
U
U
U
V a
U


OUTPUT ATTESO 4:
Codice: Seleziona tutto
b a


INPUT 5:
Codice: Seleziona tutto
V a
V b
V c
V d
V a
V c
U
V b
V e
U
U
V f
V e
V c
V b
U
U
U
U
U


OUTPUT ATTESO 5:
Codice: Seleziona tutto
a b a c e f a d
melfnt
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1269
Iscrizione: ottobre 2011

Re: [PUZZLE] history

Messaggioda nuzzopippo » mercoledì 1 agosto 2018, 18:32

melfnt Immagine ha scritto:Questa discussione non è una richiesta di aiuto, bensì il testo di un problema stimolante, che metterà alla prova le vostre abilità!


beh, @melfnt, la mia abilità NON include la capacità di ottimizzazione (sono scarso) ma, letta la traccia ho pensato : con le liste è uno scherzo!
unico dubbio che ho avuto è stato su ciò che intendevi con "otput", ma solo per poco, leggendo credo di averlo capito.

Dato che mezz'ora fa ho visto che ancora nessuno ha proposto niente, propongo due righe di python, linguaggio che, stentatamente, sto cercando di apprendere, per nulla ottimizzate, in attesa di cose migliori :)

questo codice :
Codice: Seleziona tutto
corrente = ''
visitate = []
output = ''

def V(v):
    global corrente, visitate
    if v in visitate:
        visitate.remove(v)
    if v != corrente:
        visitate.append(corrente)
    corrente = v

def U():
    global visitate
    if visitate:
        return visitate.pop()
    return None

def visita(v=None):
    global corrente, output
    if v:
        V(v)
    else:
        corrente = U()
        if corrente:
            output += corrente + ' '

if __name__ == '__main__':
    while True:
        ins = input('Visito? : ')
        if ins == 'fine':
            break
        else:
            visita(ins)
    print(output)


ha questo output :
Codice: Seleziona tutto
Python 3.5.2 (default, Nov 23 2017, 16:37:01)
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>>
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
Visito? : a
Visito? : b
Visito? : c
Visito? : d
Visito? :
Visito? :
Visito? :
Visito? : fine
c b a
>>>
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
Visito? : a
Visito? : b
Visito? :
Visito? : c
Visito? : d
Visito? : e
Visito? :
Visito? : f
Visito? :
Visito? :
Visito? :
Visito? : fine
a d d c a
>>>
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
Visito? : a
Visito? : b
Visito? : c
Visito? : d
Visito? : b
Visito? :
Visito? :
Visito? :
Visito? : fine
d c a
>>>
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
Visito? : a
Visito? : b
Visito? : c
Visito? :
Visito? :
Visito? :
Visito? :
Visito? : a
Visito? :
Visito? : fine
b a
>>>

conforme a quanto da Te posto. Risponde al problema posto?

Certamente, non userei mai tre variabili globali se non per esercizio, conterrei il necessario in una classe e per il resto definirei dei metodi, ma l'ossatura logica sarebbe quella.

[edit] mi accorgo ora di aver dimenticato di testare la validità di "corrente" prima di aggiungerlo alla lista ... poco male, uno spazio iniziale in più ;)
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1127
Iscrizione: ottobre 2006

Re: [PUZZLE] history

Messaggioda melfnt » mercoledì 1 agosto 2018, 19:35

nuzzopippo Immagine ha scritto:
melfnt Immagine ha scritto:Questa discussione non è una richiesta di aiuto, bensì il testo di un problema stimolante, che metterà alla prova le vostre abilità!


beh, @melfnt, la mia abilità NON include la capacità di ottimizzazione (sono scarso) ma, letta la traccia ho pensato : con le liste è uno scherzo!
unico dubbio che ho avuto è stato su ciò che intendevi con "otput", ma solo per poco, leggendo credo di averlo capito.

Dato che mezz'ora fa ho visto che ancora nessuno ha proposto niente, propongo due righe di python, linguaggio che, stentatamente, sto cercando di apprendere, per nulla ottimizzate, in attesa di cose migliori :)


In realtà per gli standard di questo forum mi sarei aspettato tempi di risposta molto più lunghi :)

questo codice :
Codice: Seleziona tutto
corrente = ''
visitate = []
output = ''

def V(v):
    global corrente, visitate
    if v in visitate:
        visitate.remove(v)
    if v != corrente:
        visitate.append(corrente)
    corrente = v

def U():
    global visitate
    if visitate:
        return visitate.pop()
    return None

def visita(v=None):
    global corrente, output
    if v:
        V(v)
    else:
        corrente = U()
        if corrente:
            output += corrente + ' '

if __name__ == '__main__':
    while True:
        ins = input('Visito? : ')
        if ins == 'fine':
            break
        else:
            visita(ins)
    print(output)


ha questo output :
Codice: Seleziona tutto
Python 3.5.2 (default, Nov 23 2017, 16:37:01)
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>>
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
Visito? : a
Visito? : b
Visito? : c
Visito? : d
Visito? :
Visito? :
Visito? :
Visito? : fine
c b a
>>>
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
Visito? : a
Visito? : b
Visito? :
Visito? : c
Visito? : d
Visito? : e
Visito? :
Visito? : f
Visito? :
Visito? :
Visito? :
Visito? : fine
a d d c a
>>>
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
Visito? : a
Visito? : b
Visito? : c
Visito? : d
Visito? : b
Visito? :
Visito? :
Visito? :
Visito? : fine
d c a
>>>
============== RESTART: /home/nuzzo/my_script/test/pyt/menf.py ==============
Visito? : a
Visito? : b
Visito? : c
Visito? :
Visito? :
Visito? :
Visito? :
Visito? : a
Visito? :
Visito? : fine
b a
>>>

conforme a quanto da Te posto. Risponde al problema posto?



A meno di casi subdoli che non sono riuscito a vedere sì.
Nota che non era necessario fare la distinzione fra corrente e pagine visitate, ma potevi anche usare l'ultimo elemento della lista come corrente.

Passiamo ora al calcolo della complessità: se ci sono n elementi nella history, quante operazioni impiegano le funzioni U() e V() ?
Si può fare di meglio?

(:
melfnt
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1269
Iscrizione: ottobre 2011

Re: [PUZZLE] history

Messaggioda nuzzopippo » giovedì 2 agosto 2018, 7:29

melfnt Immagine ha scritto:Nota che non era necessario fare la distinzione fra corrente e pagine visitate, ma potevi anche usare l'ultimo elemento della lista come corrente.

Nel mio empirico ragionamento, ho escluso la pagina correntemente visitata dalla lista perché avrebbe implicato un maggior numero di confronti ed un doppio pop in U() ... ma il mio è, appunto, un ragionamento empirico.

melfnt Immagine ha scritto:Passiamo ora al calcolo della complessità: se ci sono n elementi nella history, quante operazioni impiegano le funzioni U() e V() ?
Si può fare di meglio?


Viene, quindi, qui richiesta una formalizzazione rigorosa secondo concetti tipo quelli espressi in questo pdf.

Purtroppo, devo prima acquisire tali concetti, non presenti nel mio modello culturale scolastico : media superiore di quando il concetto "algoritmo" non si trattava ed imperavano regolo calcolatore e manuali logaritmici. Sarà interessante (e credo utile) farlo ma mi si perdoni se tarderò un po', il tempo è tiranno.

Sarà, comunque, interessante (ed istruttivo) veder trattare altre proposte, magari in altri linguaggi con diverse potenzialità ... ho visto, qui, molti utenti affrontare piacevolmente discorsi del genere, spero intervengano a loro volta anche qui.
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1127
Iscrizione: ottobre 2006

Re: [PUZZLE] history

Messaggioda melfnt » sabato 4 agosto 2018, 12:13

nuzzopippo Immagine ha scritto:
melfnt Immagine ha scritto:Passiamo ora al calcolo della complessità: se ci sono n elementi nella history, quante operazioni impiegano le funzioni U() e V() ?
Si può fare di meglio?


Viene, quindi, qui richiesta una formalizzazione rigorosa secondo concetti tipo quelli espressi in questo pdf.



In realtà mi basta un ragionamento anche molto meno formale, purché corretto :)

Purtroppo, devo prima acquisire tali concetti, non presenti nel mio modello culturale scolastico : media superiore di quando il concetto "algoritmo" non si trattava ed imperavano regolo calcolatore e manuali logaritmici. Sarà interessante (e credo utile) farlo ma mi si perdoni se tarderò un po', il tempo è tiranno.

Sarà, comunque, interessante (ed istruttivo) veder trattare altre proposte, magari in altri linguaggi con diverse potenzialità ... ho visto, qui, molti utenti affrontare piacevolmente discorsi del genere, spero intervengano a loro volta anche qui.


Ti do una mano io, ma prima una premessa di carattere generale: penso che il python non sia il miglior linguaggio per fare l'analisi degli algoritmi, perché ci sono un sacco di funzioni builtin già implementate che "nascondono" la complessità delle operazioni svolte.
Giusto per fare un esempio, tu hai usato le liste, l'operatore pop() e l'operatore in. Se l'unico requisito è che il programma funzioni, non importa sapere come sono implementate le liste e i due operatori, cosa che invece è necessario conoscere se si vuole calcolare la complessità dell'algoritmo utilizzato.

Partiamo dalla funzione U(), che è più semplice da analizzare:
Codice: Seleziona tutto
def U():
    global visitate
    if visitate:
        return visitate.pop()
    return None


L'if è una operazione, così come il return. Come dicevo all'inizio, per sapere quanto costa la pop() bisogna sapere come sono implementate le liste in python. Ti rimando al codice sorgente se vuoi approfondire, per ora ti basta sapere che sono array dinamici: vengono allocate con una certa dimensione iniziale, quando si riempie vengono allocati altri elementi, eccetera.
Con questo tipo di implementazione, per estrarre ed eliminare l'ultimo elemento basta accedere all'ultimo elemento dell'array, marcarlo come "vuoto" diminuendo la dimensione della lista di uno e restituirlo.
Il numero di operazioni da eseguire (diciamo 3) è indipendente dal numero di pagine presenti nella history. Se la lista ha 10 elementi, la U() impiega 3 operazioni. Se la lista ha 100 elementi, 3 operazioni. Un milione, un miliardo, mille miliardi di elementi, sempre 3 operazioni.
Questa è quella che si chiama una funzione che ha complessità costante; la sua classe di complessità si indica con O(1) (l'uno significa che il numero di operazioni da eseguire non dipende da n).

Passiamo ora alla V():
Codice: Seleziona tutto
def V(v):
    global corrente, visitate
    if v in visitate:
        visitate.remove(v)
    if v != corrente:
        visitate.append(corrente)
    corrente = v

Anche qui non ci sono cicli espliciti, quindi basta capire quante operazioni impiegano gli operatori in, remove e append.
Sempre assumendo che le liste in Python sono implementate come sopra, per cercare un elemento in una lista (operatore in) l'unica cosa possibile è scorrerla tutta fino a quando si trova l'elemento cercato oppure fino a quando non si arriva in fondo (codice sorgente). Al caso pessimo, quindi, se la lista ha n elementi eseguiremo n operazioni.
Per cancellare un elemento (operatore remove) possiamo cercarlo nella lista e non appena lo troviamo facciamo scorrere tutti gli altri elementi di una posizione a sinistra. in questo modo l'elemento cercato viene cancellato senza lasciare "buchi".
La append, invece, funziona in maniera simile alla pop.

Sia in che remove impiegano quindi n operazioni, quindi la V() appartiene alla classe di funzioni di complessità lineare ( indicata con O(n) ), il che significa che se la history contiene n pagine, il numero di operazioni da eseguire è proporzionale a n per una certa costante.

Quindi, per ora il "record" è:
U in O(1) e V in O(n).

Chi riuscirà a fare di meglio?
(:
melfnt
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1269
Iscrizione: ottobre 2011

Re: [PUZZLE] history

Messaggioda nuzzopippo » domenica 5 agosto 2018, 9:58

melfnt Immagine ha scritto:.... penso che il python non sia il miglior linguaggio per fare l'analisi degli algoritmi, perché ci sono un sacco di funzioni builtin già implementate che "nascondono" la complessità delle operazioni svolte.

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.

melfnt Immagine ha scritto:Chi riuscirà a fare di meglio?
(:


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 ;)
Avatar utente
nuzzopippo
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1127
Iscrizione: ottobre 2006

Re: [PUZZLE] history

Messaggioda melfnt » martedì 7 agosto 2018, 18:20

nuzzopippo Immagine ha scritto:
melfnt Immagine ha scritto:.... penso che il python non sia il miglior linguaggio per fare l'analisi degli algoritmi, perché ci sono un sacco di funzioni builtin già implementate che "nascondono" la complessità delle operazioni svolte.

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.



È per questo che noi scienziati seri utilizziamo l'analisi della complessità per valutare la bontà degli algoritmi, che astrae da un sacco di cose: linguaggio utilizzato, macchina su cui lo fai girare...
Anche il modo che hai usato per calcolare i tempi può essere fuorviante: probabilmente il programma impiega di più per leggere l'input che per fare i calcoli richiesti.

melfnt Immagine ha scritto:Chi riuscirà a fare di meglio?
(:


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 ;)


Queste sono solo micro-ottimizzazioni (quelle che farebbero gli ingegneri :P) in effetti così risparmi una chiamata di funzione, che è molto costosa soprattutto nei linguaggi interpretati.
Se cambi linguaggio puoi ottimizzate il codice risparmiando anche la metà del tempo, ma da un punto di vista teorico questo miglioramento è insignificante.
La cosa importante è che il numero di operazioni da eseguire per la V() cresce linearmente rispetto al numero di pagine nella history: più pagine aggiungi, più tempo impiegherai per le tue ricerche. Per esempio, se fai una V() con un certo numero di pagine, e poi un'altra V() con il doppio delle pagine, la seconda impiegherà circa il doppio del tempo (può essere 1ms vs 2ms oppure 5s vs 10s, non importa).
Dico che non importa perché, se riesci a scrivere una funzione che ha complessità costante (come per esempio la U), indipendentemente dal numero di pagine ci metterai sempre lo stesso tempo.

Quindi, quando scrivo "chi può fare di meglio?" non mi riferisco a microottimizzazioni o cambi di linguaggi (che ci stanno), quanto piuttosto alla progettazione di un altro algoritmo di complessità minore.
Nota che così facendo non è avvantaggiato chi conosce un linguaggio più efficiente, ma siamo tutti sullo stesso piano: accetto soluzioni anche in pseudocodice

;)
melfnt
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1269
Iscrizione: ottobre 2011

Re: [PUZZLE] history

Messaggioda Eresia » domenica 12 agosto 2018, 19:57

edit: Con rust ho pensato qualcosa del genere, nello specifico
funzione view (V) = legge un vettore temporaneo con dentro una lista delle pagine visitate, tenendo per ultimo l'attuale (preso in input n[stack])
funzione chrono(U) = legge un vettore temporaneo, elimina l'ultima referenza (heap), copia l'ultimo valore post-eliminazione (meno quello eliminato) e lo mette su una variabile temporanea (stack), la ritorna al main che a sua volta la copia in un nuovo vettore (heap)

Quasi sicuramente si può fare di meglio, ma dato che sto studiando ancora il linguaggio al momento mi è venuta in mente questa soluzione

Codice: Seleziona tutto
use std::io;

fn main() {
   let mut _tmp: Vec<char> = Vec::new();
   let mut history: Vec<char> = Vec::new();

   loop {
      println!("Valore: ");
      let mut input = String::new();
      io::stdin().read_line(&mut input)
         .expect("Errore di lettura");

      let a: char = input.trim().parse::<char>()
         .expect("Inserisci un numero valido!");

      if a == '<' {
         if _tmp.len() * std::mem::size_of::<char>() > 0 {
            let y: char = chrono(&mut _tmp);
            history.push(y);
         } else {
            println!("Errore");
            break;
         }
      } else if a == 'Q' {
         _tmp.reverse();
         println!("{:?}", history);
         break;
      } else {
         view(&mut _tmp, a);
      }
   }
}

fn view(v: &mut Vec<char>, n: char) -> &mut Vec<char> {
   if v.contains(&n) {
      let index = v.iter().position(|&r| r == n).unwrap();
      v.remove(index);
   }
   v.push(n);
   
   v
}

fn chrono(v: &mut Vec<char>) -> char {
   v.pop();
   let _tmp: char = v[v.len()-1];
   
   _tmp
}


output:
Codice: Seleziona tutto
kinetic@delivermi ~/RUST/tutorial $ cargo run
   Compiling tutorial v0.1.0 (file:///home/kinetic/RUST/tutorial)
    Finished dev [unoptimized + debuginfo] target(s) in 1.06s
     Running `target/debug/tutorial`
Valore: a
Valore: b
Valore: c
Valore: d
Valore: <
Valore: <
Valore: <
Valore: Q
['c', 'b', 'a'] @ U-TIME: 0.000000403
kinetic@delivermi ~/RUST/tutorial $ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.02s
     Running `target/debug/tutorial`
Valore: a
Valore: b
Valore: <
Valore: c
Valore: d
Valore: e
Valore: <
Valore: f
Valore: <
Valore: <
Valore: <
Valore: Q
['a', 'd', 'd', 'c', 'a'] @ U-TIME: 0.000000382
kinetic@delivermi ~/RUST/tutorial $ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.02s
     Running `target/debug/tutorial`
Valore: a
Valore: b
Valore: c
Valore: d
Valore: b
Valore: <
Valore: <
Valore: <
Valore: Q
['d', 'c', 'a'] @ U-TIME: 0.000000393
Avatar utente
Eresia
Scoppiettante Seguace
Scoppiettante Seguace
 
Messaggi: 282
Iscrizione: giugno 2006
Distribuzione: Solus
Sesso: Maschile


Torna a Programmazione

Chi c’è in linea

Visualizzano questa sezione: 0 utenti registrati e 2 ospiti