|
|
|
|
Strumenti |
13-01-2013, 12:57 | #1 | ||
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
[Vari] Contest 19: Full Text Search(e non solo).
Scaricate i file di input da qui:
https://github.com/hwupgradecontest/...ree/master/All Si tratta di una serie di opere letterarie che ho preso da qui: http://www.liberliber.it/ Grazie a Msangi e The_Ouroboros, il link su github dove potete mettere i vostri sorgenti: https://github.com/hwupgradecontest/contest19 Per aggiungere il proprio codice du github: The_Ouroboros: http://www.hwupgrade.it/forum/showpo...&postcount=784 Vicius: https://github.com/hwupgradecontest/README Punto A: Il programma dovrà leggere i file .txt fondendoli e creandone uno solo delle dimensioni specificate dall'utente. Il file di output sarà poi utilizzato per il Punto B: algoritmi di Full Text Seach. La fusione dei vari file txt va effettuata prendendo le singole righe di ogni file di input e mescolandole, in modo casuale, con quelle di tutti gli altri file. Vanno escluse, nel file di output, le righe vuote. Vanno inoltre eliminati gli spazi superflui. Due o più spazi consecutivi andranno sostituiti con uno spazio solo. Le tabulazioni vanno sostituite con uno spazio. Per il punto B utilizzeremo il programma che si rivelerà il migliore dal punto di vista delle prestazioni ma soprattutto dalla qualità dell'output. Il programma, CUI o GUI, a vostra scelta, dovrà dunque permettere all'utente di specificare il nome del file di output e la dimensione. Nel caso l'utente scelga una dimensione maggiore di quella del totale dei file di input, si ricominci dal primo file e via via con tutti gli altri, mescolando sempre in modo casuale le righe. Esempio(CUI): Punto B: Da definire più in la. Ci occuperemo degli algoritmi per la Full Text Seach e confronteremo le prestazioni(e la qualità dei risultati) con alcuni programmi che vanno per la maggiore nel settore: Lucene, Zettair, Indri. Punto B.1: Quote:
Punto B.2: Quote:
Le parole dovranno essere parole di senso compiuto. "---------" o "........" o "£$%*/*&&&" non sono parole di senso compiuto. "parola", "ciao", "hello" invece si, sono parole di senso compiuto. Si veda, inoltre, questo post(grazie a msangi): http://www.hwupgrade.it/forum/showpo...&postcount=618. E questo(grazie a clockover): http://www.hwupgrade.it/forum/showpo...&postcount=645 Punto B.3 Si modifichi il programmino di cui al punto B.2 in modo da fargli accettare due argomenti dalla riga di comando(oltre al nome del file): 1) Il parametro "-L=d" dove d sta per la dimensione minima delle parole che l'utente desidera per il conteggio. Per esempio, -L=5 significa che l'utente desidera che vengano conteggiate le parole con lunghezza >= 5. 2) Il parametro "-F=file" dove file sta per il nome di un file specificato dall'utente dove sono listati, una parola per riga, le parole che l'utente desidera escludere dalla ricerca. Per esempio: Codice:
il lo la i gli le ------------------------------------------------------------------------------------------------------------------------------------------------------ E, a cura dell'utente Marco.r: Punto C: Catene Markoviane. In preparazione. Ultima modifica di Vincenzo1968 : 20-02-2013 alle 18:25. Motivo: Aggiornato link file input |
||
13-01-2013, 13:29 | #2 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Per esempio, se abbiamo questi file in input:
File 1: Codice:
file 1 riga 1 file 1 riga 2 file 1 riga 3 Codice:
file 2 riga 1 file 2 riga 2 file 2 riga 3 Codice:
file 3 riga 1 file 3 riga 2 file 3 riga 3 Codice:
file 3 riga 2 file 2 riga 2 file 3 riga 1 file 3 riga 3 file 1 riga 3 file 1 riga 1 file 2 riga 3 file 2 riga 1 file 1 riga 2 Le righe debbono risultare disposte in modo casuale. Una nuova esecuzione del programma darà, ovvviamente, una nuova disposizione delle righe. Per esempio: Codice:
file 3 riga 1 file 1 riga 3 file 3 riga 3 file 1 riga 2 file 2 riga 2 file 1 riga 1 file 2 riga 3 file 3 riga 2 file 2 riga 1 Ultima modifica di Vincenzo1968 : 17-01-2013 alle 10:48. |
13-01-2013, 13:51 | #3 | ||
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Dall'incipit del Cap. IV de I Promessi Sposi di Alessandro Manzoni:
Quote:
Quote:
Ultima modifica di Vincenzo1968 : 17-01-2013 alle 10:06. |
||
14-01-2013, 09:29 | #4 |
Senior Member
Iscritto dal: Aug 2001
Città: San Francisco, CA, USA
Messaggi: 13826
|
Leggendo il contest una cosa non mi è chiara.
Dici che il programma deve mischiare insieme le righe dei due file in ordine casuale, ma nell'esempio mescoli i file anche partendo da metà di quella che io considererei una riga (un qualcosa che va da newline a newline), quindi vorrei capire: qual'è la tua idea di riga in questo caso? Ciao EDIT: Un altra cosa che non ho capito bene è cosa succede quando l'output è maggiore dell'input. Cosa intendi per "si ricomincia dal primo file" ? Intendi che riscrive il testo in ordine dal primo file in poi o intendi che si resetta il mescolamento e si riparte a mescolare i file?
__________________
GPU Compiler Engineer Ultima modifica di AnonimoVeneziano : 14-01-2013 alle 09:39. |
14-01-2013, 15:54 | #5 |
Senior Member
Iscritto dal: Feb 2006
Messaggi: 1304
|
Vi anticipo già 50 ms per un file da 2 mb
Ero partito usando C++11 e la stl eccetera, e per quanto sia diventata parecchio veloce in sè mi forzava a copiare la memoria in giro... sotto 500 ms non si scendeva. Il buon vecchio C è ancora imbattuto EDIT: ok, 43 ms e sto, almeno sul mio SSD. Un'esecuzione usa ~40 ms per fopen/fread, ~2 ms per fare il parsing dei file e ~0.1 ms per scrivere l'output (questo grazie allo SSD che è una bestia ), probabilmente nel caso dello SSD sarebbe molto più veloce leggendo tutti i file in parallelo, ma d'altra parte nel caso di un HDD meccanico sarebbe molto peggio, e vincerebbe alla grande accorpare tutti i files in un file solo per minimizzare il seek time. Odio un pò sti problemi che esce Vincenzo1968 perchè finiscono sempre a fare a botte con l'HD Ultima modifica di Tommo : 14-01-2013 alle 16:20. |
14-01-2013, 16:18 | #6 |
Senior Member
Iscritto dal: Aug 2001
Città: San Francisco, CA, USA
Messaggi: 13826
|
Non puoi sperare di usare la STL e di andare veloce ...
__________________
GPU Compiler Engineer |
14-01-2013, 16:22 | #7 | |
Senior Member
Iscritto dal: Feb 2006
Messaggi: 1304
|
Quote:
ma come dicevo, a pari algoritmo non sono più lente di C, e di sicuro il codice esce molto più bello a vedersi (e la condivisione di memoria che ho usato è come chiedere bug a manetta ) EDIT: ecco il codice main.cpp LineBuffer.h common_header.h EDIT2: ho provato a farlo girare su un disco in rete (lag come se piovesse, 13 mb/s max) e come previsto ci mette quasi 1.6 secondi... un dettaglio interessante però è che già alla 3a run ci metteva solo 66 ms, il che prova che Windows è abbastanza furbo da mettere in cache i file usati di recente sul disco più veloce Ultima modifica di Tommo : 14-01-2013 alle 17:36. |
|
14-01-2013, 16:44 | #8 | |
Senior Member
Iscritto dal: Aug 2001
Città: San Francisco, CA, USA
Messaggi: 13826
|
Se qualcuno avesse avuto gli stessi dubbi riguardo al testo del contest queste sono state le risposte di Vincenzo alle mie domande:
Quote:
__________________
GPU Compiler Engineer |
|
16-01-2013, 14:53 | #9 |
Senior Member
Iscritto dal: May 2007
Città: Veneto
Messaggi: 6731
|
Comunicazione di servizio da Vincenzo1968:
http://classes.soe.ucsc.edu/ism293/S...mp_3_Lemur.pdf http://ciir.cs.umass.edu/~strohman/indri/ http://www.lemurproject.org/lemur/In...ryLanguage.php http://myweb.uiowa.edu/cgharris/images/indri.pdf Serviranno per il punto B.
__________________
Apple Watch Ultra + iPhone 15 Pro Max + Rog Ally |
17-01-2013, 10:07 | #10 |
Senior Member
Iscritto dal: Oct 2001
Messaggi: 11471
|
Questa la mia versione in Java: Generate.java.
A leggere tutti i file da disco ci mette circa 800ms. Per creare un file di 5 gb ci impiega poco più di 4 minuti. Codice:
➜ Contest time java contest.Generate file -D5GiB java contest.Generate file -D5GiB 78.23s user 159.79s system 98% cpu 4:01.87 total Si potrebbe passare a nio per evitare di scopiazzare stringhe qua e là. Eliminare la regex e ripulirsi a mano il testo. Ed usare un executor per distribuire il lavoro tra i vari core. Ma non credo ne valga la pena. |
17-01-2013, 10:22 | #11 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Ragazzi, una cortesia:
per facilitare il compito agli utenti che volessere provare i programmi postati(e soprattutto a me che devo scaricare i sorgenti di tutti e stilare le classifiche), bisognerebbe zippare i sorgenti e metterli su un sito di file sharing. Ce ne sono un fottìo. Uno dei miei preferiti è: http://www.filedropper.com/ Non richiede iscrizione e soprattutto, quando uno clicca sul link per scaricare il file, non bisogna aspettare i maledetti trenta secondi di pubblicità(c'è solo da inserire 4 caratteri per il riconoscimento umano). Edit: Ho visto ora che nel link di Vicius c'è il link diretto che permette di scaricare il file compresso. Ma, se il programma è composto da più file sorgenti? Ultima modifica di Vincenzo1968 : 17-01-2013 alle 10:31. |
17-01-2013, 10:30 | #12 | |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Quote:
Quindi ragazzuoli, quando utilizzate Visual Studio, create un progetto vuoto altrimenti vengono inseriti gli afx e poi li debbo modificare a mano(per compilarli su Linux). A meno che non decidiate che la vostra versione debba girare solo su Windows. Comunque il file prodotto dalla versione di Tommo ha qualche problemino(lascia qualche riga vuota e qualche spazio superfluo). Lo sta sistemando. Ultima modifica di Vincenzo1968 : 17-01-2013 alle 10:57. |
|
17-01-2013, 10:55 | #13 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
|
17-01-2013, 11:17 | #14 | ||
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Ah dimenticavo: il tempo dev'essere espresso in secondi.
Quindi non Quote:
Quote:
|
||
17-01-2013, 11:33 | #15 |
Senior Member
Iscritto dal: Oct 2001
Messaggi: 11471
|
|
17-01-2013, 12:44 | #16 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
|
17-01-2013, 12:52 | #17 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Spiegatemi una cosa. Le funzioni per la gestione dei file in C a 64 bit sono standard(e quindi posso tranquillamente compilare e in Windows e in Linux)?
Per esempio, la funzione "_ftelli64" è standard o è specifica del compilatore Microsoft? |
17-01-2013, 12:56 | #18 |
Senior Member
Iscritto dal: Oct 2001
Messaggi: 11471
|
Quando hai compilato i sorgenti ti deve aver creato due file class. Il primo è Generate.class che è il programma principale. E poi c'è anche un Generate$1.class che è la classe anonima creata per TXT_FILES.
|
17-01-2013, 13:26 | #19 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Non è standard. Mo debbo arrangiarmi con le macro per la compilazione condizionale. Che debbo usare per GCC/Linux? |
17-01-2013, 13:28 | #20 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Ok. Se non funziona nemmeno così le urla le sentirete fin lassù al nord.
|
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 03:37.