Find string in text

di il
10 risposte

Find string in text

Ciao,

per verificare la mancanza di una dicitura all'interno di un file XML, normalmente utilizzo una StringList nel seguente modo:

sl := TStringList.Create;
try
  sl.LoadFromFile(path);
  for i := 0 to Length(array) - 1 do
  	if not sl.Text.Contains(array[i]) then
  	  ...
finally
  sl.Free;

Ora mi trovo con un file XML con 114.000 righe (12MB) che freeza l'interfaccia. Il comportamento non cambia utilizzando ContainsStr oppure Pos, come nel seguente codice:

sl := TStringList.Create;
try
  sl.LoadFromFile(path);
  for i := 0 to Length(array) - 1 do
    if Pos(array[i], sl.Text) > 0 then
      Continue
    else
      ...
finally
  sl.Free;

Qualcuno conosce una soluzione performante per verificare la presenza/mancanza di una dicitura all'interno di una quantità di testo cosi grande?

Ale

10 Risposte

  • Re: Find string in text

    https://stackoverflow.com/questions/33410136/how-to-check-if-a-string-contains-a-substring-in-delphi

  • Re: Find string in text

    Grazie della tua risposta, Andrea. : )

    Avevo già provato ContainsStr, anche ContainsText, ma purtroppo non ho potuto notare un cambiamento significante nella performance riguardo l'uso di Pos oppure StringList.Text.Contains().

    Ale

  • Re: Find string in text

    Concettualmente esiste un sistema “piu' efficiente” per controllare SE una stringa, all'interno di un SET di stringhe, e' contenuta in un'altra stringa:

    https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

    https://en.wikipedia.org/wiki/Commentz-Walter_algorithm

    https://elvedit.com/journals/IJACSIT/wp-content/uploads/2014/09/IJACSIT-3402-AoMSPMA.pdf

    Potresti provare con l' ESPRESSIONE REGOLARE:

    <s1>|<s2>|…|<sn>

    (cioe' metti le strighe in OR) la quale create un AUTOMA A STATI FINITI che per sua natura testa in modo EFFICIENTE TUTTE le stringhe del SET contemporaneamente.

    In alternativa dovresti implementare uno dei due algoritmi indicati precedentemente

    https://yurichev.com/mirrors/Knuth-Morris-Pratt/Maxime%20Crochemore%20-%20Jewels%20of%20Stringology%20(2002).pdf 

    Ma e' robbbba per “smanettoni” della peggior specie: 
    quello che stanno davanti al computer senza mangiare per giorni

     ;-)

  • Re: Find string in text

    Grazie della risposta, Miglio. Indagherò sugli algoritmi indicati.

    Parte del problema è sicuramente la mancante preelaborazione del testo che è un mix tra codice XML, HTML e PHP. Attualmente carico il file senza elaborarlo e cerco la stringa con Contains oppure Pos, ma potrebbe valer la pena analizzare più profondamente il file di sorgente per eventualmente filtrare parti trascurabili durante il caricamento; anche l'esclusione dei tag ridurebbe il workload e creerebbe in più stringhe separate. Poi, probabilmente, il tempo guadagnato nella ricerca si perde nel precedente filtraggio. : )

    Da quando ho visto la velocità di TStringList confronto TMemo utilizzo esclusivamente TStringList per processare alti volumi di testo. Probabilmente, in casi come l'attuale, ci sono metodi più perfomanti, motivo della mia domanda iniziale.

    Ale

  • Re: Find string in text

    26/04/2024 - al.delphi ha scritto:


    Ora mi trovo con un file XML con 114.000 righe (12MB) che freeza l'interfaccia.

    A mio avviso, una prima cosa che potresti fare è evitare di caricare tutto il file, visto che è voluminoso, ma leggerlo riga per riga in modo da risparmiare memoria.

    Crea un TFileStream aprendo il file in questione per la lettura e usa la classe TStreamReader per leggere il file (usando il costruttore Create che si aspetta un generico Stream) riga per riga (usando ReadLine) alla ricerca del testo che ti interessa.

    Verifica poi quali sono le performance di questa procedura: se si velocizza ma non a sufficienza per evitare il blocco dell'interfaccia, valutiamo se è necessario passare ad altra soluzione (tipo quelle proposte) con l'obiettivo di incrementare le prestazioni, oppure se i tempi sono accettabili ma il “freeze” dell'interfaccia rimane la sola problematica fastidiosa, si può eseguire questa operazione all'interno di un thread separato.

  • Re: Find string in text

    Ciao, Alka. Grazie dei suggerimenti.

    Avevo già provato di eseguire la procedure all'interno di un ITask, ma al termine del processo si è bloccata l'applicazione, presumo perché uno dei componenti utilizzati non è thread safe.

    Per il momento ho bypassato il problema del freez in modo quick & dirty inserendo Application.ProcessMessages nel loop di verifica insieme a una ProgressBar. L'interfaccia così non freeza più e l'utente vede che l'operazione procede. Preferirei velocizzare la ricerca, quindi proverò anche l'approccio suggerito con TFileStream.

    Ale

  • Re: Find string in text

    28/04/2024 - al.delphi ha scritto:


    Avevo già provato di eseguire la procedure all'interno di un ITask, ma al termine del processo si è bloccata l'applicazione, presumo perché uno dei componenti utilizzati non è thread safe.

    Dipende da come hai realizzato la cosa: riporta l'esempio di codice che hai scritto.

    L'essere “non thread safe” non vuol dire che non è possibile usare un componente all'interno di un thread, bensì che il componente non può essere usato da più thread contemporaneamente, accedendo al suo stato o invocandone i metodi da più thread, appunto.

  • Re: Find string in text

    27/04/2024 - Alka ha scritto:


    A mio avviso, una prima cosa che potresti fare è evitare di caricare tutto il file, visto che è voluminoso, ma leggerlo riga per riga in modo da risparmiare memoria.

    Piu' no che si: risparmi memoria MA 20M caratteri potrebbero essere 40MByte, non sono questa gran quantita' di memoria, almeno sui PC moderni, che hanno qualche DECINE di GB di ram.
    Inoltre, analizzando una riga alla volta SI SUPPONE che il testo sia COMPLETAMENTE contenuto nella riga e non distribuito su piu' righe. OVVIAMENTE, questo dipende da che cosa si sta' cercando. MA e' una cosa da considerare

    ;-)

    @al.delphi come ti hanno detto, la “thread safety” NON CENTRA NULLA!

  • Re: Find string in text

    28/04/2024 - migliorabile ha scritto:


    Piu' no che si: risparmi memoria MA 20M caratteri potrebbero essere 40MByte, non sono questa gran quantita' di memoria, almeno sui PC moderni

    La questione è che i 20 MB di caratteri potrebbero diventare 40 MB, 100 MB, 500 MB di caratteri.

    In linea generale, se i volumi raggiungono queste dimensioni, non è difficile ipotizzare che possano anche aumentare in futuro, quindi in ottica di “prepararsi al peggio”, può aver senso a prescindere mettersi in condizioni di non esaminare interamente il file ma solo parzialmente.

    28/04/2024 - migliorabile ha scritto:


    Inoltre, analizzando una riga alla volta SI SUPPONE che il testo sia COMPLETAMENTE contenuto nella riga e non distribuito su piu' righe.

    Trattandosi di un documento XML, è lecito ipotizzare che - sia che si tratti di un testo o del nome di un elemento - questo non sia spezzato su più righe, altrimenti ciò invaliderebbe anche la validità formale del documento.

    Certo, se il documento XML è tutto su una riga, allora concordo che non ci sia nulla da fare in questo senso, o meglio che la soluzione vada cercata in altro modo, magari entrando nel merito del formato XML e adottando un “approccio SAX” sullo stesso, caricando byte un poco alla volta bufferizzando e “muovendosi” tra gli elementi.

    Sono tutti aspetti da considerare, ma prima bisogna capire lo stato dell'arte e la fonte del problema principale, perché onestamente dubito che il blocco della applicazione sia dovuta alla ricerca di testo in 20 MB di caratteri, ma su questo solo l'autore della discussione può illuminare.

  • Re: Find string in text

    Se può essere utile alla causa, in questa pagina si parla di una “challenge” per leggere e fare il parsing di un file CSV da circa 16GB.

    Questo è il “post accompagnatorio” (in inglese):

    Do you know the 1BRC - 1 billion rows challenge?
    It is a challenge of reading 1 billion (1,000,000,000) of CSV data (around 16GB file) containing weather station names and temperatures as fast as possible, compute the min/max/mean of each station, and return it as sorted text.
    It started as a Java challenge, then others came in, in Rust, Go, C++...
    My proposal in object pascal takes around 730ms on my Core i5 desktop computer.

    Anche se l'esigenza qui è diversa, magari le nozioni indicate possono fornire spunti utili per “aggredire” il problema delle performance nella lettura e ricerca all'interno del testo. :)

Devi accedere o registrarti per scrivere nel forum
10 risposte