Topic: ottimizzare in count  (Letto 65 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline simone13

  • python unicellularis
  • *
  • Post: 6
  • Punti reputazione: 0
    • Mostra profilo
ottimizzare in count
« il: Novembre 22, 2018, 17:25 »
buona sera, il mio algoritmo in questo  caso è corretto ma ha bisogno di essere ottimizzato perché non passa alcuni test del mio professore solo perché supera il tempo limite. avevo pensato di ottimizzarlo togliendo la funzione count, ma non so come, ovviamente se da questo forum viene fuori un altro modo sarei molto felice di provarlo.. non so come ottimizzarlo mi potreste dare una mano per favore? grazie mille per la disponibilità il mio codice è il seguente con il comando lasciato dal prof.:
'''
I messaggi scambiati all'interno di un forum sono stati sottoposti ad uno studio.
Dai  vari post  sono state estrapolate parole significative e questi dati sono stati poi
raccolti in un  file di testo.
Nel file, l'inizio di ciascun post e' marcato da una linea che contiene  la stringa
"<POST>" e un intero utilizzato come identificativo del post (che nel seguito dovete lasciare come stringa).
la stringa e l'identificativo possono essere preceduti e seguiti da un numero arbitrario (anche 0) di spazi.
Le parole estrapolate  dal  post sono  nelle linee successive (zero  o piu' parole per
linea) fino alla linea che marca il prossimo post
o la fine del file.
Come esempio si veda il file "fp1.txt".
 
Per ognuna delle parole estrapolate si vogliono ora ricavare le seguenti informazioni:
I1) Il numero totale di occorrenze della parola nei post,
I2) il numero di post in cui la parola compare,
I3) la coppia (occorrenze, post) dove nella seconda coordinata si ha l'identificativo del post
in cui la parola e' comparsa piu' spesso e nella prima il numero di volte che vi e' comparsa,
(nel caso di  diversi post con pari numero massimo di occorrenze della parola va considerato
il post con l'identificativo minore in ordine lessicografico).
Bisogna costruire una tabella avente una riga per ognuna delle differenti parole
utilizzate nel forum. La tabella deve avere 4 colonne 
In una colonna  comparira' la parola e nelle altre tre  le informazioni I1), I2) e I3) dette prima.
Le righe della colonna devono essere ordinate rispetto all'informazione I1) decrescente, a parita'
del valore I1 vanno ordinate rispetto  alla cardinalita' decrescente dell'insieme degli itentificativi
ed a parita', rispetto all'ordine lessicografico delle parole.

Scrivere una funzione es2(fposts) che prende in input  il
percorso del file di testo contenente le estrapolazioni dei post del forum
e restituisce la tabella.
La tabella va restituita sotto forma di lista di dizionari dove
ciascun dizionario ha 4 chiavi: 'parola', 'I1','I2' e 'I3' e ad ogni chiave e'
associata la relativa informazione attinente la parola.
Ad esempio per il file di testo fp1.txt la funzione restituira' la lista:
[{'I1': 6, 'I2': 3, 'I3': (3, '30'), 'parola': 'hw1'},
 {'I1': 3, 'I2': 2, 'I3': (2, '30'), 'parola': 'python'},
 {'I1': 2, 'I2': 1, 'I3': (2,  '1'), 'parola': 'hw2'},
 {'I1': 1, 'I2': 1, 'I3': (1, '21'), 'parola': '30'},
 {'I1': 1, 'I2': 1, 'I3': (1, '30'), 'parola': 'monti'},
 {'I1': 1, 'I2': 1, 'I3': (1,  '1'), 'parola': 'spognardi'},
 {'I1': 1, 'I2': 1, 'I3': (1, '21'), 'parola': 'sterbini'}
 ]

NOTA: il timeout previsto per questo esercizio è di 3 secondi per ciascun test.

ATTENZIONE: quando consegnate il programma assicuratevi che sia nella codifica UTF8
(ad esempio editatelo dentro Spyder o usate Notepad++)
'''
       

def es2(fposts):
    '''Implementare la funzione qui'''
    with open(fposts, "r", encoding="UTF-8") as post:
        lista_finale=[]
        x= post.read()
        x= x.replace("<post>", "<post> ").replace("\n"," ").split("<post>")
        x= x[1:]
        diz={}
    for riga in x:
        diz[riga.split()[0]]= riga.split()[1:]
    parole=[]
    for e in diz.values():
        for q in e:
            parole.append(q)
    for parola in set(parole):       
        diz_finale= {}
        count=0
        for i in range(len(parole)):
            if parola== parole[i]:
                count+=1
        diz_finale["I1"]= count
        contatore=0
        massimo=-1
        for r in sorted(diz.keys()):
            if parola in diz[r]:
                contatore+=1
                z=diz[r].count(parola)
            else:
                z=0
            if z > massimo:
                massimo=z
                tupla=z,r
        diz_finale["I2"]= contatore
        diz_finale["I3"]= tupla
        diz_finale["parola"]= parola
        lista_finale.append(diz_finale)
    return sorted(lista_finale, key= lambda elem: (-elem["I1"], -elem["I2"], elem["parola"]))

Offline RicPol

  • python sapiens sapiens
  • ******
  • Post: 2.821
  • Punti reputazione: 9
    • Mostra profilo
Re:ottimizzare in count
« Risposta #1 il: Novembre 23, 2018, 16:47 »
Il codice è molto opaco (nomi di variabili incomprensibili, nessun commento...) e quindi non è che si capisca molto a una prima lettura. Se il problema è che ci mette troppo tempo, posso capire. A occhio stai ciclando un sacco di volte sulle stesse cose. Dovresti semplificare: l'ideale sarebbe ciclare una volta sola (ovvero mentre leggi il file sorgente riga per riga) e fare i conteggi man mano che incontri le parole.

Tra le altre cose, alla riga 73 e sgg, tu stai ciclando sulle chiavi di un dizionario. Ora, non è impossibile farlo (tanto è vero che lo fai), ma in genere non usi un dizionario per ciclarci sopra. Un dizionario è una struttura-dati pensata per accedere a una chiave, non per ciclare sulle chiavi. Se cicli sulle chiavi di un dizionario, in qualunque scenario, stai probabilmente facendo una cosa sbagliata. Ora, nello specifico tu stai seguendo un pattern del genere:

>>> d = {'a':0, 'b':0}
>>> s = 'acbbaaccdabdd'
>>> for char in s:
...     for key in d.keys():
...       if char == key:
...         d[char] += 1
...         break
...     else:
...       d[char] = 1
...
>>> d
{'a': 4, 'b': 3, 'c': 3, 'd': 3}

Ora, anche se questa cosa "funziona" ovviamente, è un antipattern quando si lavora con i dizionari. La soluzione giusta è semplicemente accedere alla chiave e intercettare l'eventuale errore:

>>> d = {'a':0, 'b':0}
>>> s = 'acbbaaccdabdd'
>>> for char in s:
...     try:
...         d[char] += 1
...     except KeyError:
...         d[char] = 1
...
>>> d
{'a': 4, 'b': 3, 'c': 3, 'd': 3}

Senza iterare le chiavi del dizionario. Questo pattern è abbastanza comune da meritare uno strumento apposito collections.defaultdict https://docs.python.org/3/library/collections.html#defaultdict-examples

Offline simone13

  • python unicellularis
  • *
  • Post: 6
  • Punti reputazione: 0
    • Mostra profilo
Re:ottimizzare in count
« Risposta #2 il: Novembre 23, 2018, 19:55 »
grazie mille, scusa per il codice incomprensibile ma avendo iniziato da due mesi a programmare non ho l'abitudine di commentare i passi e cose del genere. proverò con questo modo grazie mille