Trova una stringa nella lista di stringhe

Question

Trova una stringa nella lista di stringhe

#1 da (4 voti)

1

Sfondo:

Sto scrivendo un'applicazione per un piccolo dispositivo incorporato. C'è una lista statica di stringhe: attualmente circa 500 stringhe e la lunghezza della stringa è di 12 caratteri in media. L'elenco potrebbe aumentare in futuro. Quando l'applicazione si avvia, l'elenco di stringhe verrà analizzato una volta. Niente più aggiunte, cancellazioni alla lista. La ricerca () verrà chiamata un numero elevato di volte.

Devo trovare se una stringa di input è presente nell'elenco. Attualmente sto ordinando e memorizzando le stringhe in un array. Sto usando la ricerca binaria per trovare la stringa. Il caso peggiore è 0 (log n) e la complessità dello spazio è 0 (12 * n) (??).

Domanda:

C'è un approccio migliore? So che i tavoli hash sono più veloci. Ma sono preoccupato per la memoria extra. Posso creare una tabella hash di dimensioni n. Ma avrei bisogno di una funzione Perfect hash . Qualche suggerimento su come ottenere una tale funzione di hash? È solo una prova ed un errore? Qualsiasi altra struttura dati che potrebbe essere migliore?

c data-structures algorithms string-matching

posta psy 03.08.2018 - 22:34

fonte

1 risposta

Leggi altre domande sui tag c data-structures algorithms string-matching

Simulazione del confronto senza l'utilizzo di primitive di confronto SQLAlchemy e DDD: è il proprio schema?

score 4 · Accepted Answer

La tua ricerca binaria è probabilmente abbastanza buona. Approcci alternativi porteranno a molta più complessità, probabilmente per un piccolo guadagno.

Ci sono un paio di approcci di ottimizzazione che puoi provare:

Una struttura di dati trie potrebbe comportare un sovraccarico significativo dello spazio, ma consentirà di determinare l'appartenenza al set in un'operazione O (k) (con k la lunghezza dell'input).
Invece di eseguire una ricerca binaria su tutte le possibili stringhe, puoi partizionarle usando una funzione di hash economica. Se i dati sono distribuiti in modo appropriato, potrebbe essere sufficiente utilizzare il primo carattere come funzione di hash.
Se ti aspetti che molte stringhe non si trovino nel set da testare, puoi utilizzare un test di appartenenza rapido approssimativo come un filtro Bloom. Un filtro bloom è composto da più funzioni hash e un vettore bit. Tutti i membri del set vengono sottoposti a hash con ciascuna funzione di hash e viene impostato il bit indicato dalla funzione di hash. Per verificare l'appartenenza si hash la stringa di input e si controlla se i bit corrispondenti sono impostati. In caso contrario, l'input non è nell'insieme. Se i bit sono impostati, l'input potrebbe essere nel set e dovrai ricorrere a un test di appartenenza esatto.

Una proprietà interessante dei filtri bloom è che le loro dimensioni e il loro overhead computazionale sono completamente configurabili, ma queste proprietà influenzano anche la qualità del filtro.

Ovviamente puoi combinare approcci.

Le funzioni di hash perfette suonano bene, ma non sono usate frequentemente nella pratica: costruire la funzione di hash è complicato e esistono alternative abbastanza buone per molti casi d'uso.