Miglior algoritmo per filtrare valori array in base ad altro array

[scitrek]

Ciao a tutti

Il mio problema riguarda il miglior modo di filtrare i valori di un array in base a quelli di un altro array con strpos. In poche parole devo eliminare da array2 tutte le stringhe che "contengono" una delle stringhe presenti in array1.

Ho scritto un classico codice con due foreach uno dentro l'altro che per ogni elemento di array1 scorre array2 confrontando i valori con strpos. Mi chiedevo se esistesse un metodo migliore (piu' veloce, meno pesante) per fare la stessa operazione. Ci sono vantaggi a usare, ad esempio, array_filter() o array_walk() per questo scopo?

Grazie!

[badaze]

Devi eliminare tutta la stringa oppure solo la parte che combacia con quella del primo array ?

[scitrek]

Lo scopo e' quello di ottenere una lista di stringhe "bonificate" (si tratta di keyword) quindi in caso di match elimino l'intero elemento.

Ho trovato questo interessante articolo da cui si evince che per piccoli array non c'e' praticamente differenza mentre per grandi array foreach sembra essere il metodo piu veloce: https://leve.rs/blog/benchmark-analy...p-array-loops/

[scitrek]

Giusto per dare un'idea delle dimensioni (e del motivo per cui sto cercando di ottimizzare), in media lo script deve processare 160 milioni di iterazioni (ad esempio per comparare un file da 1000 KWs con uno da 160k). Di solito, girando in locale su un computer non potentissimo, ci impiega circa 15-16 minuti.

[badaze]

1000 KWs stanno per 1.000.000 di parole e 160 k per 160.000 parole ?

[satifal]

Dovendo in ogni caso scorrere completamente due array di N ed M elementi credo sia impossibile individuare un algoritmo con complessità inferiore a O(N x M)
Andrebbero piuttosto riviste le strutture dati.

[scitrek]

@badaze

No, KWs starebbe per keywords.


@satifal

No, certo. Pensavo potesse esserci qualche vantaggio a usare funzioni interne di PHP invece di due cicli, come spesso accade per altre operazioni. In che senso andrebbero riviste le strutture dati?

[satifal]

@satifal

No, certo. Pensavo potesse esserci qualche vantaggio a usare funzioni interne di PHP invece di due cicli, come spesso accade per altre operazioni.

Qualsiasi funzione interna del PHP, per quanto ottimizzata, dovrebbe comunque scorrere l'eventuale o gli eventuali array portando in ogni caso la complessità ad O(N^2)

In che senso andrebbero riviste le strutture dati?

Se ti ritrovi a dover scorrere due array per individuare le stringhe da scartare probabilmente sarebbe opportuno intervenire a monte, ma non conoscendo la logica del tuo applicativo non posso esserti d'aiuto in tal senso.

[scitrek]

Certo, la complessità è uguale, ma in genere le funzioni interne, non basandosi su un linguaggio interpretato, sono più veloci e meglio ottimizzate, no? Voglio dire, è più efficiente un preg_replace() o una sua emulazione in PHP?

Purtroppo non è che ci sia molta logica, lo scopo dell'applicativo è quello di prendere due liste di keyword ed eliminare dalla seconda tutte le keyword che contengono al loro interno keyword presenti nella prima. Al momento lo faccio verificando le stringhe tramite stripos() ma sto cercando anche un modo che mi permetta di individuare keyword intere all'interno delle stringhe della seconda lista (ad esempio, far si che "posa" venga individuato in "lunga posa" ma non in "mariposa").

[badaze]

Se il primo array è composto da una sola parola e se il secondo è privo di punteggiatura allora potresti fare come da esempio senza ricorrere alle regexp.

<?php 
$kw = array();
$kw[] = 'patto';
$kw[] = 'pluto';
$ls = array();
$ls[] = 'l impatto è stato violente';
$ls[] = 'il patto dei lupi';
$ls[] = 'oddio il plutonium';
$ls[] = 'il cane di topolino si chiama pluto in Francese';
$count_kw = count($kw);
$count_ls = count($ls);
foreach($kw as $keyword) {
 print "current keyword = $keyword</br>";
 $keyword1 = ' '.$keyword.' ';
 reset($ls);
 foreach($ls as $key => $phrase) {
  $phrase1 = ' '.$phrase.' ';
  if ($phrase1 != str_ireplace($keyword1,"",$phrase1)) {
   print "&nbsp;&nbsp;<strong>scelto : '$keyword' in '$phrase'</strong><br/>";
   //---- scelto allora lo tolgo dalla lista
   unset($ls[$key]);
  } else {
    print "&nbsp;&nbsp;scartato : '$keyword' in '$phrase'<br/>";
  } //
 }
}
?>