Elenco dei tag di hashing per eseguire una ricerca più rapida

1

Ho una lista di elementi. Ogni oggetto ha varie proprietà. Ogni oggetto può essere taggato, come taggare un post qui. Al momento, i tag sono rappresentati utilizzando una proprietà Tags , ovvero una stringa e assomiglia a tag1:tag2:...:tagN .

Un utente può cercare un elemento in base ai suoi tag (ad esempio, procurami elementi con tag2 e tagN ). Per fare questo ho bisogno di scansionare la lista completa degli oggetti e, anche peggio, ho bisogno di dividere la proprietà Tags e cercare se quei tag sono presenti.

Quello che sto cercando è una sorta di filtro di hashing o un algoritmo migliore per eseguire questo tipo di ricerca. Tieni presente che, se la ricerca di tag2 significherebbe darmi elementi con solo tag2 la ricerca sarebbe più semplice, purtroppo ciò che significa in realtà è darmi elementi che contengano tag2 , quindi la divisione (almeno, per ora) è obbligatoria.

Modificheremo la rappresentazione da tag1:tag2:...:tagN a una migliore, al fine di fornire una ricerca più rapida. Forse senza una struttura di ricerca o qualcosa del genere.

    
posta BAD_SEED 14.09.2018 - 15:22
fonte

1 risposta

1

Avere Tags come stringa ti costringe ad analizzarlo sempre e sempre per ogni Item e per ogni ricerca. Se i tag non vengono visualizzati in un ordine predefinito, dovrai anche attraversarlo più volte.

Miglioramenti a livello di elemento

Miglioramento 1: crea Tags un elenco ordinato di stringhe. Se cerchi più tag, ordinali pure. Dovresti quindi attraversare i tag cercando il primo tag. Se viene trovato, puoi continuare con il secondo tag (a partire dall'elemento successivo).

Miglioramento 2: crea Tags un insieme di stringhe. Quindi è ancora più efficiente perché la tua lingua / libreria utilizzeranno un accesso efficiente agli elementi, certamente in O (log n) . La maggior parte delle lingue offre persino alcuni tipi di hash che consentono un accesso O (1) (ad es. C ++ std::unordered_set , java HashSet o C # HashSet ).

Miglioramento 3: invece di eseguire l'hashing delle stesse stringhe del tag di ricerca per ogni singolo elemento, gestire i tag come una chiave intera, utilizzando un dizionario per mappare le stringhe del tag alle chiavi del tag. Quindi Tags finirebbe come set di Tag

Miglioramenti a livello di raccolta:

Fino ad ora, abbiamo semplicemente migliorato le prestazioni della ricerca di tag in un elemento. Tuttavia, tutte queste soluzioni richiedevano ancora la ricerca di ogni singolo articolo.

Miglioramento 4: Rendi Tag e Item entità correlate che impongono la navigabilità bidirezionale. Quindi Item avrebbe ancora un set di tag, ma ogni Tag avrebbe una raccolta di Item . Questo sfrutta notevolmente lo spazio di ricerca: ordina l'elenco dei tag da quello con la più piccola raccolta di oggetti ai più grandi. Cerca gli oggetti nella collezione del primo. Quindi passa attraverso gli oggetti trovati per guardare se corrispondono agli altri.

Miglioramento 5: Puoi anche creare intersezioni tra più raccolte (specialmente se sono ordinate). Tuttavia, se hai elenchi di articoli molto grandi.

Se hai raccolte enormi

L'approccio proposto funziona molto bene, ma era più concepito per l'elaborazione in memoria. Se hai un numero enorme di oggetti e tag, potresti aver bisogno di un db.

Se si utilizza un DB relazionale, la relazione tra tag e elementi (da molte a molte associazioni) sarà una tabella a sé stante. La buona notizia è che il motore db ottimizzerà questo tipo di ricerche utilizzando strategie simili e anche più elaborate, in modo che sia ultra-efficiente.

    
risposta data 15.09.2018 - 17:03
fonte

Leggi altre domande sui tag