+ Rispondi al Thread
Visualizzazione dei risultati da 1 a 4 su 4

Discussione: [Regex] - Algoritmo di Thompson.

  1. #1
    Dev-01 non è in linea Scolaretto
    Post
    439

    [Regex] - Algoritmo di Thompson.

    Buongiorno a tutti,

    di recente ho letto un articolo sull'argomento in oggetto (chiedo scusa ma non ricordo il link) ed ho scoperto che esiste una differenza sostanziale fra le prestazioni fornite, ad esempio, tra .net e/o altri linguaggi normalmente compilati e l'algoritmo di Thompson del quale veniva fornito il sorgente commentato a corredo (in C).

    Il problema pare risiedere nell'implementazione del motore che processa le stringhe.

    Dai grafici riportati nell'articolo si evinceva che le prestazioni di una ricerca basata su regex con uno degli algoritmi più diffusi diminuivano in maniera esponenziale (in secondi/decine di secondi) ad ogni incremento unitario della stringa sulla quale eseguire la ricerca mentre il tempo utilizzato dall'algoritmo di Thompson a parità di altri vincoli (lunghezza stringa sorgente/regex) partiva da alcuni microsecondi e andava aumentando in maniera lineare.

    Nel caso di MS.net il jit deve inizialmente compilare il codice ma dopo il tempo impiegato per la compilazione, volendo processare una grande quantità di stringhe, un algoritmo efficiente non dovrebbe presentare tanta differenza in termini di prestazioni o sbaglio? E se sbaglio, perché?

    Forse l'algoritmo fornito è male implementato?
    Anche voi avete notato queste "penose" prestazioni? E, se si, come avete risolto?

  2. #2
    Dev-01 non è in linea Scolaretto
    Post
    439
    Ho trovato il link dell'articolo, potrebbe essere utile anche a prescindere da una eventuale risposta:

    Regular Expression Matching Can Be Simple And Fast

  3. #3
    L'avatar di Windows M
    Windows M non è in linea Scolaretto
    Post
    319
    Ciao, credo che la risposta a tutte le tue domande sia in questa parte dell'articolo che hai linkato:
    The C implementation just described was not written with performance in mind. Even so, a slow implementation of a linear-time algorithm can easily outperform a fast implementation of an exponential-time algorithm once the exponent is large enough. Testing a variety of popular regular expression engines on a so-called pathological regular expression demonstrates this nicely.
    Ovvero che, indipendentemente dal linguaggio di implementazione, un algoritmo di complessità polinomiale non ottimizzato è spesso più veloce, al caso pessimo, dei migliori algoritmi di complessità esponenziale anche se fortemente ottimizzati.
    In realtà questa affermazione è vera solo se vale quanto scritto in grassetto, ovvero nei casi patologici, altrimenti l'implementazione backtrack impiega (di solito) tempi ragionevoli - pur restando una pessima implementazione

    Quindi:
    -
    Nel caso di MS.net il jit deve inizialmente compilare il codice ma dopo il tempo impiegato per la compilazione, volendo processare una grande quantità di stringhe, un algoritmo efficiente non dovrebbe presentare tanta differenza in termini di prestazioni o sbaglio? E se sbaglio, perché?
    In teoria hai ragione, ovvero se la macchina virtuale del linguaggio è del tipo JIT hai solo l'overhead allo startup e il resto dell'esecuzione *dovrebbe* avere tempi paragonabili ad un linguaggio compilato: nella pratica non so quanto questo sia vero e quanto sia "pubblicità".

    -
    Forse l'algoritmo fornito è male implementato?
    Se ti riferisci all'implementazione fornita dai linguaggi probabilmente è scelta progettuale "di comodo" in modo da minimizzare il codice scritto e, allo stesso tempo, avere un algoritmo che funzioni mediamente bene.

    -
    Anche voi avete notato queste "penose" prestazioni? E, se si, come avete risolto?
    Uso poco linguaggi interpretati ed ancor meno le regex, però immagino che nei casi in cui sia necessario processare stringhe grandi con particolari regex che fanno "comportare male" l'algoritmo di default valga la pena reimplementare la gestione delle regex oppure usare librerie esterne.

    Se ti interessa approfondire l'algoritmo di Thompson (ed in generale la teoria degli automi) ti consiglio il Dragon Book (Aho & al. Compilers: Principles, Techniques, and Tools), se vuoi approfondire la questione delle "prestazioni" dei vari algoritmi devi focalizzarti sulle basi della Teoria della complessità (che viene introdotta in qualunque libro di algoritmi, come il CLRS - Introduction to algorithms).
    Se in un primo momento l'idea non è assurda, allora non c'è nessuna speranza che si realizzi. [Albert Einstein]

    A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. [G.H.Hardy]

  4. #4
    Dev-01 non è in linea Scolaretto
    Post
    439
    Ciao e grazie per la risposta, le precisazioni e le ottime indicazioni.

    Il Dragon Book 2 v.2 (è quello?) lo sto leggendo proprio in questo periodo ma è in inglese per cui avrò un bel po di lavoro da fare.

    se vuoi approfondire la questione delle "prestazioni" dei vari algoritmi devi focalizzarti sulle basi della Teoria della complessità (che viene introdotta in qualunque libro di algoritmi, come il CLRS - Introduction to algorithms).
    Certo che si!!!


    Grazie 1000...

+ Rispondi al Thread

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi