efficace di ricerca sopra un iteratore php

Question

Ho un iteratore personalizzato (TokenIterator per la precisione, che itera, beh, il codice php token). Gli articoli sono oggetti semplici ( "sacchi di proprietà" con alcuni metodi di normalizzazione aggiunto)

Devo implementare funzionalità di ricerca, che devono trovare se 1. un iteratore contiene un'altra o 2. due (o più) iteratori si sovrappongono (con qualche parametrizzazione).

Al momento io uso approccio ingenuo (1) -. O (NxM) ricerca doppio anello, e (2) non è ancora implementata

Prima di iniziare a reimplementare davvero intelligenti algoritmi di stringa di ricerca Vorrei sapere se esiste qualche effettiva attuazione di questo? Forse qualcosa sepolto in qualche quadro o libreria generica di riutilizzare? E quale algoritmo sarà più adatto qui?

Answer 1

La prima cosa che viene in mente è che si sta parlando di operazioni di set, per le quali gli iteratori non sono senza dubbio la soluzione migliore.

Non so se c'è qualche soluzione esistente per il vostro problema, ma, come una soluzione generale, userei tabelle hash. Per esempio, costruire una tabella hash utilizzando i segni della prima serie (lo chiamerò impostato da ora in poi, dal momento che mi sento Iterator non è la parola migliore) e si può farlo in Theta (N), e quindi provare a inserire l'altro insieme nella stessa tabella di hash. La prima volta che si ottiene una collisione, saprete c'è una sovrapposizione. Naturalmente questo funziona bene se lo spazio hash è ampio e la funzione hash garantisce una quantità trascurabile di collisioni, tuttavia è sempre possibile codice qualche tipo di soluzione.

PHP riportati array associativi (che sono una forma di tabelle hash) è possibile creare una matrice avente i token come le chiavi, che di nuovo può essere fatto in Theta (N), e quindi utilizzare array_key_exists. E 'assolutamente possibile che array_key_exists non è altro che una scansione lineare del elenco delle chiavi, come io non sono familiarità con internals di PHP, ma sono abbastanza sicuro che se gli array associativi sono implementati come tabelle hash, si dovrebbe essere attuato molto di più efficiente rispetto a una scansione lineare.

Answer 2

Se i vostri iteratori possono essere colate di array, è possibile utilizzare array_diff e array_intersect. In caso contrario, è necessario implementare ciò che queste funzioni fanno sotto il cofano - passeggiata sopra le vostre strutture e confrontare. Poiché i dati di eseguire iterazioni non è ordinato né si sa nient'altro su di esso, non avete altra scelta.