Il modo più veloce per trovare oggetti da una raccolta corrispondente alla condizione sul membro stringa

https://stackoverflow.com/questions/97329

01-07-2019
|

Domanda

Supponiamo di avere una raccolta (che si tratti di un array, di un elenco generico o di qualunque cosa sia il più veloce soluzione a questo problema) di una certa classe, chiamiamola così ClassFoo:

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
}

Supponiamo che ci saranno circa 50.000 elementi nella raccolta, tutti in memoria.Ora voglio ottenere il più velocemente possibile tutte le istanze della collezione che obbediscono ad una condizione sul suo membro bar, ad esempio in questo modo:

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

Come posso ottenere i risultati il più velocemente possibile?Dovrei prendere in considerazione alcune tecniche di indicizzazione e strutture dati avanzate?

Il dominio dell'applicazione per questo problema è un completamento automatico, che riceve una query e fornisce come risultato una raccolta di suggerimenti.Supponiamo che la condizione non diventi più complessa di così.Supponiamo anche che ci saranno molte ricerche.

Soluzione

Con il vincolo che la clausola condizionale può essere "qualsiasi cosa", sei limitato a scansionare l'intero elenco e applicare la condizione.

Se sono presenti limitazioni sulla clausola condizionale, è possibile organizzare i dati per gestire le query in modo più efficiente.

Ad esempio, l'esempio di codice con il dizionario "byFirstLetter" non aiuta affatto con una query "endsWith".

Quindi, tutto dipende da quali query vuoi fare su quei dati.

Nei database, questo problema è il peso del "query optimization".In un database tipico, se si dispone di un database senza indici, ovviamente ogni query sarà una scansione della tabella.Man mano che aggiungi indici alla tabella, l'ottimizzatore può utilizzare tali dati per creare piani di query più sofisticati per ottenere meglio i dati.Questo è essenzialmente il problema che stai descrivendo.

Una volta che hai un sottoinsieme più concreto dei tipi di query, puoi prendere una decisione migliore su quale sia la struttura migliore.Inoltre, è necessario considerare la quantità di dati.Se hai un elenco di 10 elementi ciascuno di meno di 100 byte, una scansione di tutto potrebbe essere la cosa più veloce che puoi fare dato che hai una quantità di dati così piccola.Ovviamente ciò non è scalabile fino a 1 milione di elementi, ma anche le tecniche di accesso intelligenti comportano un costo in termini di installazione, manutenzione (come la manutenzione dell'indice) e memoria.

MODIFICARE, in base al commento

Se si tratta di un completamento automatico, se i dati sono statici, ordinali e utilizza una ricerca binaria.Non diventerai davvero più veloce di così.

Se i dati sono dinamici, archiviali in un albero bilanciato e cercalo.Questa è effettivamente una ricerca binaria e ti consente di continuare ad aggiungere i dati in modo casuale.

Tutto il resto è una specializzazione su questi concetti.

Altri suggerimenti

var Answers = myList.Where(item => item.bar.StartsWith(query) || item.bar.EndsWith(query));

questo è il più semplice secondo me, dovrebbe essere eseguito piuttosto rapidamente.

Non sono sicuro di aver capito...Tutto quello che puoi fare è ottimizzare la regola, questa è la parte che deve essere più veloce.Non è possibile accelerare il ciclo senza semplicemente aggiungere più hardware.

Potresti eseguire la parallelizzazione se disponi di più core o macchine.

Non sto utilizzando Java in questo momento, ma vorrei pensare alle seguenti cose.

Come stai creando la tua lista?Forse puoi crearlo già ordinato in modo da ridurre i tempi di confronto.

Se stai semplicemente eseguendo un ciclo diretto attraverso la tua raccolta, non vedrai molta differenza tra memorizzarla come array o come elenco collegato.

Per archiviare i risultati, a seconda di come li raccogli, la struttura potrebbe fare la differenza (ma supponendo che le strutture generiche di Java siano intelligenti, non lo farà).Come ho detto, non sono sul mio Java, ma presumo che l'elenco collegato generico manterrebbe un puntatore di coda.In questo caso, non farebbe davvero la differenza.Qualcuno con una maggiore conoscenza dell'array sottostante rispetto all'implementazione dell'elenco collegato e di come finisce per apparire nel codice byte potrebbe probabilmente dirti se l'aggiunta a un elenco collegato con un puntatore di coda o l'inserimento in un array è più veloce (suppongo che l'array ).D'altra parte, dovresti conoscere la dimensione del tuo set di risultati o sacrificare un po' di spazio di archiviazione e renderlo grande quanto l'intera raccolta su cui stai eseguendo l'iterazione se desideri utilizzare un array.

Potrebbe essere utile anche ottimizzare la query di confronto individuando quale confronto ha maggiori probabilità di essere vero ed eseguirlo prima.cioè:Se in generale il 10% delle volte un membro della raccolta inizia con la tua query e il 30% delle volte un membro termina con la query, ti consigliamo di eseguire prima il confronto finale.

Per il tuo esempio particolare, ordinare la raccolta sarebbe d'aiuto in quanto potresti eseguire il comando binario al primo elemento che inizia con query e terminare anticipatamente quando raggiungi quello successivo che non lo fa;potresti anche produrre una tabella di puntatori agli elementi della raccolta ordinati in base al contrario di ciascuna stringa per la seconda clausola.

In generale, se conosci in anticipo la struttura della query, puoi ordinare la tua raccolta (o creare diversi indici ordinati per la tua raccolta se sono presenti più clausole) in modo appropriato;in caso contrario, non sarai in grado di fare meglio della ricerca lineare.

Se si tratta di qualcosa in cui si compila l'elenco una volta e poi si eseguono molte ricerche (migliaia o più), è possibile creare una sorta di dizionario di ricerca che associa i valori inizia/termina con i loro valori effettivi.Sarebbe una ricerca veloce, ma utilizzerebbe molta più memoria.Se non stai facendo molte ricerche o sai che ripopolarai l'elenco almeno con una certa frequenza, sceglierei la query LINQ suggerita da CQ.

Puoi creare una sorta di indice e potrebbe diventare più veloce.

Possiamo costruire un indice come questo:

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

Quindi usalo in questo modo:

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

Ora forse non dobbiamo scorrere tanti ClassFoo come nel tuo esempio, ma dobbiamo mantenere aggiornato l'indice.Non vi è alcuna garanzia che sia più veloce, ma è sicuramente più complicato.

Dipende.Tutti i tuoi oggetti verranno sempre caricati in memoria?Hai un limite finito di oggetti che possono essere caricati?Le tue query dovranno considerare oggetti che non sono ancora stati caricati?

Se la raccolta dovesse diventare grande, utilizzerei sicuramente un file index.

In effetti, se la raccolta può raggiungere una dimensione arbitraria e non sei sicuro di riuscire a inserirla tutta in memoria, esaminerei un ORM, un database in memoria o un altro database incorporato.Mi viene in mente XPO di DevExpress per ORM o SQLite.Net per database in memoria.

Se non vuoi arrivare a questo punto, crea un semplice indice costituito dalla mappatura dei riferimenti ai membri "bar" ai riferimenti alle classi.

Se l'insieme dei criteri possibili è fisso e piccolo, è possibile assegnare una maschera di bit a ciascun elemento dell'elenco.La dimensione della maschera di bit è la dimensione dell'insieme di criteri.Quando crei un elemento/lo aggiungi alla lista, controlli quali criteri soddisfa e poi imposti i bit corrispondenti nella maschera di bit di questo elemento.Far corrispondere gli elementi dall'elenco sarà facile come far corrispondere le loro maschere di bit con la maschera di bit di destinazione.Un metodo più generale è il filtro Bloom.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow