[Vari] Contest 19: Full Text Search(e non solo).

[Vincenzo1968]

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:

B.1:
Si realizzi un programmino che, data in input una stringa di ricerca, indichi l'esatta posizione (riga e colonna) nel file creato al punto A.

Si prendano separatamente i tempi per la creazione dell'indice e quelli per la ricerca.

Se volete utilizzare un algoritmo brute force, senza creare l'indice, siete liberi di farlo.

L'esempio qui: http://www.hwupgrade.it/forum/showpo...&postcount=180


Punto B.2:

Si scriva un programmino simile a quello presente nella distribuzioni Linux per contare i caratteri, le parole, le righe, la riga più lunga e la parola più lunga(quest'ultima cosa il comando wc non la fa):

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:

il
lo
la
i
gli
le

Col suddetto file passato come argomento, il programmino dovrà escludere dal conteggio le parole "il", "lo", "la", "i", "gli", "le".

------------------------------------------------------------------------------------------------------------------------------------------------------

E, a cura dell'utente Marco.r:
Punto C:
Catene Markoviane. In preparazione.

[Vincenzo1968]

Per esempio, se abbiamo questi file in input:

File 1:

file 1 riga 1
file 1      riga 2
file 1 riga 3

File 2:

file 2 riga 1

file 2           riga 2
file 2 riga 3

File 3:

file 3 riga 1
     file 3        riga 2
file 3 riga 3

Il file risultante dovrà essere, per esempio, così:

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

Come vedete, nel file di output, sono stati eliminati gli spazi superflui e le righe vuote.
Le righe debbono risultare disposte in modo casuale. Una nuova esecuzione del programma darà, ovvviamente, una nuova disposizione delle righe.

Per esempio:

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

[Vincenzo1968]

Dall'incipit del Cap. IV de I Promessi Sposi di Alessandro Manzoni:

Il sole non era ancor tutto apparso sull'orizzonte, quando il padre Cristoforo uscì dal suo convento di Pescarenico, per salire alla casetta dov'era aspettato.

Dall'incipit del Cap. VIII di Quer pasticiaccio brutto de via Merulana di Carlo Emilio Gadda:

Il sole non aveva ancora la minima intenzione di apparire all'orizzonte che già il brigadiere Pestalozzi usciva(in motocicletta) dalla caserma degli erre erre ci ci di Marino per catapultarsi alla bottega-laboratorio dove non era minimamente aspettato, almeno in quanto brigadiere fungente.

[AnonimoVeneziano]

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?

[Tommo]

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

[AnonimoVeneziano]

Originariamente inviato da Tommo

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

Non puoi sperare di usare la STL e di andare veloce ...

[Tommo]

Originariamente inviato da AnonimoVeneziano

Non puoi sperare di usare la STL e di andare veloce ...

In realtà il problema era che non esiste un modo per assegnare memoria preesistente a std::string, e quindi non avrei potuto usare il "trucco" che ha tagliato di 10 volte il tempo...
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

[AnonimoVeneziano]

Se qualcuno avesse avuto gli stessi dubbi riguardo al testo del contest queste sono state le risposte di Vincenzo alle mie domande:

Quando l'output è maggiore dell'input si riparte dall'inizio. Si prendono tutti i file e si ricomincia a mescolare le righe(di tutti i file) fino a quando il file di output non raggiunge la dimensione voluta.
Non ho capito bene la prima domanda. Considera che nell'esempio ho mescolato le righe a mano; il programma lo devo ancora finire.

T'ho scritto in privato perché m'hanno sospeso e non posso postare nel thread. Potresti cortesemente postare tu la mia risposta?
Al limite specifica che te l'ho chiesto io tramite pm.

A quel punto ho riformulato la mia prima domanda e lui ha risposto che si , bisogna identificare ogni riga e mescolarle insieme (le righe vanno da newline a newline)

[The_ouroboros]

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.

[VICIUS]

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.

➜ Contest  time java contest.Generate file -D5GiB
java contest.Generate file -D5GiB  78.23s user 159.79s system 98% cpu 4:01.87 total

Non ho potuto provare la versione di tommo perché stdafx.h cozza un po' con osx e linux. Fare un confronto sullo stesso hardware sarebbe interessante ma non credo che ci sia una grande differenza tra i due. Una vota passato una certa dimensione il limite dovrebbe essere il disco.

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.

[Vincenzo1968]

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?

[Vincenzo1968]

Originariamente inviato da VICIUS

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.

➜ Contest  time java contest.Generate file -D5GiB
java contest.Generate file -D5GiB  78.23s user 159.79s system 98% cpu 4:01.87 total

Non ho potuto provare la versione di tommo perché stdafx.h cozza un po' con osx e linux. Fare un confronto sullo stesso hardware sarebbe interessante ma non credo che ci sia una grande differenza tra i due. Una vota passato una certa dimensione il limite dovrebbe essere il disco.

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.

Io sono riuscito a compilare la versione di Tommo su Linux ma ho dovuto togliere i file afx e inserire manualmente gli include.

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.

[Vincenzo1968]

[Vincenzo1968]

Ah dimenticavo: il tempo dev'essere espresso in secondi.

Quindi non

825 ms

ma

0.825 secondi

"secondi" scritto per esteso, non abbreviato "s.".

[VICIUS]

Originariamente inviato da Vincenzo1968

I package di java proprio non ti entrano in testa . I file .class devono stare nella cartella contest. Devi lanciarlo da fuori dando il nome completo contest.Generate.

[Vincenzo1968]

Originariamente inviato da VICIUS

I package di java proprio non ti entrano in testa . I file .class devono stare nella cartella contest. Devi lanciarlo da fuori dando il nome completo contest.Generate.

[Vincenzo1968]

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?

[VICIUS]

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.

[Vincenzo1968]

Non è standard. Mo debbo arrangiarmi con le macro per la compilazione condizionale.

Che debbo usare per GCC/Linux?

[Vincenzo1968]

Originariamente inviato da VICIUS

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.

Ok. Se non funziona nemmeno così le urla le sentirete fin lassù al nord.