[JAVA] Espressioni regolari stile xml

[VICIUS]

Originariamente inviato da Vincenzo1968

Ma che cacchio dici? l'NFA ha il backtracking. Che cacchio dici? Leggiti l'articolo che ho postato e vedrai la differenza che c'è tra nfa e dfa. Leggiti il libro di Hopcroft e vedrai. Vedrai vedrai.

Un automa a stati finiti è deterministico se tutte le coppie (stato, simbolo di ingresso) producono una singola transizione allo stato successivo. Per gli automi non deterministici questo non è vero e quindi ci possono essere più transizioni.

Il backtracking non è una caratteristica degli nfa ma semplicemente una tecnica usata dalle varie librerie che implementano le regexp per trovare tutte le possibili soluzioni. Rileggiti articolo e libro che non hai capito bene.

Originariamente inviato da Vincenzo1968

In quanto al "premature optimization" ti vorrei far notare che Knuth viene spesso, come in questo caso, citato a sproposito.

Premature optimization is the root of all evil è una frase di Knuth che si trova all'interno di un articolo in cui l'autore si spinge a considerare come buono l'uso del famigerato goto pur di migliorare le prestazioni.
In quell'articolo l'autore scrive che ama il codice leggibile e ben ordinato ma non ama per niente il codice inefficiente.

Cosa c'entra knuth?

Originariamente inviato da Vincenzo1968

Vorrei vedere, nel caso di file xml di grosse dimensioni, le regexp in confronto al dfa superottimizzato come quello prodotto dagli strumenti suindicati...

Un automa a stati finiti deve scorrere tutti i caratteri uno alla volta per trovare tutti i match nel file xml. Si tratta di una soluzione lineare O(n) che dipende solo dalla dimensione del file quindi piuttosto efficiente.

La regexp dipende tantissimo dall'implementazione ma in java dovrebbe procedere così:
1. La parte iniziale "<title>" è composta da soli litteral. Può usare boyer-moore per cercare la prima occorrenza da cui partire con il match. Mi pare di ricordare che come algoritmo sia O(n/m) quindi più efficiente del normale automa.
2. Una volta trovato l'inizio del tag può fare la parte centrale di cattura del contenuto senza backtracking. [^<]+ è un semplice ciclo for.
3. Una volta catturato il contenuto esegue il test per "</title>" anche qui si tratta di soli litteral quindi ciclo for.
4. Se fa match riparte dal punto 1 partendo con la ricerca dopo </title> perché ormai il testo è stato consumato. Se non c'è stato parte dalla posizione successiva al <title> perché le () introducono backtracking.

L'uso di boyer-moore per trovare l'inizio dei match ed il fatto che il resto equivale in sostanza ad un dfa mi fa pensare che la regexp potrebbe essere più performante o in sostanza equivalente.

[Vincenzo1968]

Si ma

http://www.hwupgrade.it/forum/showpo...1&postcount=40

[VICIUS]

Originariamente inviato da Vincenzo1968

http://msdn.microsoft.com/en-us/library/0yzc2yb0.aspx

The .NET Framework regular expression engine is a backtracking regular expression matcher that incorporates a traditional Nondeterministic Finite Automaton (NFA) engine such as that used by Perl, Python, Emacs, and Tcl. This distinguishes it from faster, but more limited, pure regular expression Deterministic Finite Automaton (DFA) engines such as those found in awk, egrep, or lex

Conferma ogni singola parola che ho scritto. Il matcher di c# fa uso di backtracking e di un nfa. Non è l'automa ma il matcher ad usarlo.

[Vincenzo1968]

http://algs4.cs.princeton.edu/54regexp/

[Vincenzo1968]

https://github.com/knowitall/openregex

Implementation

Regular expressions are evaluated using Thomson NFA, which is fast and not have the pathological cases that most regular exprsesion libraries have. For more information about Thomson NFA in comparison to recurseive backtracking, read http://swtch.com/~rsc/regexp/regexp1.html. Future work may involve compiling NFAs to DFAs.

Future Work

Compile to DFA.
Use parser combinators for parsing regular expressions.

[VICIUS]

Originariamente inviato da Vincenzo1968

http://algs4.cs.princeton.edu/54regexp/

Classici pattern patologici. Nel primo caso è l'alternazione unita al * mentre nel secondo è il doppio * interno ed esterno a far saltare il tutto. Risolverli è bovino. Basta usare l'atomic grouping o i possesive quantifiers a seconda dei gusti personali.

Originariamente inviato da Vincenzo1968

https://github.com/knowitall/openregex

Implementation

Regular expressions are evaluated using Thomson NFA, which is fast and not have the pathological cases that most regular exprsesion libraries have. For more information about Thomson NFA in comparison to recurseive backtracking, read http://swtch.com/~rsc/regexp/regexp1.html. Future work may involve compiling NFAs to DFAs.

Future Work

Compile to DFA.
Use parser combinators for parsing regular expressions.

Ennesima riconferma di quello che scrivevo. Dfa e nfa sono equivalenti.

[Vincenzo1968]

Minchia si, equivalenti sono(in un occhio si e in un occhio no):



Proprio uguali uguali.



RegExpVicius.java:

import java.util.regex.Pattern;
import java.util.regex.Matcher;

// <title>Mio libro</title><year>2012</year><home>Mia casa</home>

public class RegExpVicius {

    public static void main(String[] args) {
		int x;
        String xml = "<title>Mio libro</title><year>2012</year><home>Mia casa</home>";

        Pattern TITLE = Pattern.compile("<title>([^<]+)</title>");
		
        x = 0;
        while ( x < 100000000 ) {
			Matcher matcher = TITLE.matcher(xml);
			while (matcher.find()) {
				if ( x < 3 )
					System.out.println("Titolo: " + matcher.group(1));
			}
			x++;
		}
    }
}

RegExpVincenzo1968.java:

import java.io.Console;

public class RegExpVincenzo1968
{	
    public static void main(String[] args)
    {
		int x;
        String xml = "<title>Mio libro</title><year>2012</year><home>Mia casa</home>";        
        
		CParser parser = new CParser();			
		                
        x = 0;
        while ( x < 100000000 )
        {			
			if ( parser.Parse(xml) )
				if ( x < 3 )
				System.out.println(parser.GetValue());
			
			x++;
		}
    }    
}

Le classi CLexer e CParser sono un adattamento di quelle che avevo postato nel thread sulle espressioni aritmetiche:

http://www.hwupgrade.it/forum/showpo...96&postcount=7

Chi fosse interessato ai sorgenti mi contatti via pm

Il mio dfa non è nemmeno ottimizzato. Non ho nemmeno minimizzato gli stati



Vicius, Vicius! L'nfa è una illusione. L'nfa Java una doppia illusione.(semi cit.)

EDIT: Non capisco perché mi si sminchia l'indentazione. Il codice è perfettamente indentato. Mah!

[wingman87]

Originariamente inviato da Vincenzo1968

EDIT: Non capisco perché mi si sminchia l'indentazione. Il codice è perfettamente indentato. Mah!

Perché un po' è indentato con i tab e un po' con gli spazi

[VICIUS]

Originariamente inviato da Vincenzo1968

Vicius, Vicius! L'nfa è una illusione. L'nfa Java una doppia illusione.(semi cit.)

Ci sono diverse cose che non vanno in quel codice che hai postato. Poi potrei farti vedere come portare il tempo di esecuzione sotto i 3 secondi (sarebbe un po' imbrogliare ). Però francamente non ne ho più voglia. Pensavo, anzi no speravo, che col tempo ti saresti un po' aperto cercando di crescere ma vedo non ti interessa. Rimani pure nel tuo piccolo mondo.

[Vincenzo1968]

Originariamente inviato da wingman87

Perché un po' è indentato con i tab e un po' con gli spazi

No è indentato solo con i tab. Forse la cosa è dovuta al fatto che Geany, non so perché, mi aggiunge un sacco di tab alla fine di ogni riga(e non capisco con quale criterio: ci sono righe senza tab alla fine e righe con un fottìo di tab ).

Quindi io da me il codice lo vedo perfettamente indentato. Quando lo copincollo qui, evidentemente tutti quei tab a fine riga combinano il casino.

[Vincenzo1968]

Originariamente inviato da VICIUS

Ci sono diverse cose che non vanno in quel codice che hai postato. Poi potrei farti vedere come portare il tempo di esecuzione sotto i 3 secondi (sarebbe un po' imbrogliare ). Però francamente non ne ho più voglia. Pensavo, anzi no speravo, che col tempo ti saresti un po' aperto cercando di crescere ma vedo non ti interessa. Rimani pure nel tuo piccolo mondo.

Che schifìo c'è nel codice che ho postato? E' semplicemente il codice che hai postato tu racchiuso all'interno di un ciclo while che itera per 100000000(leggasi: cento milioni) di volte.

[sottovento]

Originariamente inviato da Vincenzo1968

EDIT: Non capisco perché mi si sminchia l'indentazione. Il codice è perfettamente indentato. Mah!

Aprilo in gvim e scrivi:

:1,$s/\t/    /g

Cosi' sostituisci tutti i tab con spazi.

Dopo di che, scrivi:

:se expandtab

Questo fa in modo che i tuoi tab vengano automaticamente rimpiazzati con l'adeguato numero di spazi durente l'editing.

[Vincenzo1968]

Originariamente inviato da sottovento

Aprilo in gvim e scrivi:

:1,$s/\t/    /g

Cosi' sostituisci tutti i tab con spazi.

Dopo di che, scrivi:

:se expandtab

Questo fa in modo che i tuoi tab vengano automaticamente rimpiazzati con l'adeguato numero di spazi durente l'editing.

No ma il problema non sono i tab in sè. Sono i tab a fine riga.
Per esempio:

\tif (x > 0)

me lo ritrovo così:

\tif (x > 0)\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t

Vedi tutti quei tab(\t) alla fine?

È fastidioso anche quando debbo aggiungere del codice alla fine della riga. Mi sposto nella riga, premo il tasto "Fine" e mi ritrovo a millemila chilometri di distanza. Mi tocca eliminarli con backspace. Alla fine mi fa male il ditino.

Non c'è modo, con Vim, di eliminare del tutto i tab a fine riga anziché sostituirli con spazi? Ma i tab all'inizio della riga me li deve lasciare.

[The_ouroboros]

Originariamente inviato da Vincenzo1968

No ma il problema non sono i tab in sè. Sono i tab a fine riga.
Per esempio:

\tif (x > 0)

me lo ritrovo così:

\tif (x > 0)\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t

Vedi tutti quei tab(\t) alla fine?

È fastidioso anche quando debbo aggiungere del codice alla fine della riga. Mi sposto nella riga, premo il tasto "Fine" e mi ritrovo a millemila chilometri di distanza. Mi tocca eliminarli con backspace. Alla fine mi fa male il ditino.

Non c'è modo, con Vim, di eliminare del tutto i tab a fine riga anziché sostituirli con spazi? Ma i tab all'inizio della riga me li deve lasciare.

%s/\t*$//g

[Vincenzo1968]

Comunque:

http://infolab.stanford.edu/~ullman/ialc.html

http://www.amazon.com/gp/product/032...27CA8DP7KDKZ87


Il testo tratta l'argomento da un punto di vista pratico, non formale. Se preferite qualcosa di più formale, più rigoroso, dovete procurarvi la prima edizione. Ma non è per tutti: dovete avere delle solide basi matematiche. Io, per esempio, non riuscirei a leggerlo. Occhio! Be careful!

http://shop.oreilly.com/product/9780596528126.do


Su quest'ultimo si veda:

- il par. 4.6: NFA, DFA and POSIX
- il par 4.6.3.1: DFA efficiency: you get consistent, clean power.

[Vincenzo1968]

Ottimizzato codice. Minimizzati stati dell'automa. Sostituiti if statement con switch statement.

Nuovi tempi:






NFA...

[Vincenzo1968]

http://www.hwupgrade.it/forum/showpo...&postcount=130

Originariamente inviato da VICIUS

Ma anche no.

È vero che ho sparato la lettura dei file su thread multipli ma l'ho fatto solo per divertimento. Non credo di aver ottenuto un incremento di prestazioni con quello.

Piuttosto eliminando la regex per la pulizia dei file e passando a nio ho potuto costruirmi in anticipo i bytebuffer che avrei usato poi durante la scrittura, mappare in memoria i file da leggere, gestirmi il buffering a mano ed allocare i buffer fuori dal heap.

Usando collectins.shuffle al posto di Random dovrei aver anche aiutato il processore che di sicuro prima sbarellava a causa degli accessi completamente casuali alla memoria.