Modo ottimale per implementare questa specifica tabella di ricerca in C #?

Question

Modo ottimale per implementare questa specifica tabella di ricerca in C #?

#1 da (4 voti)
#2 da (1 voti)
#3 da (1 voti)

2

Voglio creare una tabella di ricerca per questi dati:

Le "variabili di input" (ciò che è usato per "cercare") sono 4 doppi differenti che possono assumere ciascuno 1 di 200 numeri (i numeri vanno da 1-1000 ma ci sono solo 200 numeri possibili che ognuno può essere ( questi 200 numeri possibili che ognuno di loro può essere sono noti a me)) i doppi sono tutti e 2 i decimali. Se uno qualsiasi dei quattro fosse cambiato, cambierebbe leggermente le variabili di output. C'è anche 1 intero (enum in realtà) che può assumere un valore compreso tra 1 e 5.

C'è una condizione su 3 delle variabili di input che (1 / x + 1 / y + 1 / z deve essere inferiore a 1.02). Potrebbe essere usato in un algoritmo di hashing?

Le "variabili di output" (cosa viene restituito) sono ~ 30 doppie (per lo più 2 cifre decimali, ma una ha 10 posizioni decimali). (sarà impacchettato in un oggetto) compreso tra 1 e 1000 (2 posizioni decimali).

Mi aspetto che ci siano ~ 150 milioni di record.

Devo usare un dizionario grande e caricarlo in memoria, quindi avvio il programma?

Un Database e LINQ sarebbero i migliori?

Posso usare Trees o Hashing in qualche modo per velocizzarlo?

Non ho mai dovuto creare una LUT così grande prima, in cui la velocità è un fattore importante.

Chiarificazione: a causa della condizione che (1 / x + 1 / y + 1 / z deve essere inferiore a 1,02, vedi sopra) ci sono solo ~ 150 milioni di combinazioni di variabili di input. Non ~ (200) ^ 4.

Aggiornamento:

Ho esaminato alcune statistiche (valori minimi e massimi osservati e scoperto alcune relazioni) per le mie variabili di input e ho scoperto che se chiamiamo i 4 input doppi A, B, C, D: A and B have ~200 possible values each, C has ~50 possible values, and D has ~120 possible values

Di questi, ci sono diverse relazioni che indicano che ci sono solo ~ 27 milioni di combinazioni di questi piuttosto che i ~ 150 milioni che avevo inizialmente pensato. Quindi ci saranno circa 27 milioni di record nella LUT. C'è anche sicuramente una relazione che non sono stato in grado di capire tra (A, B, C) e D che farà scendere anche il numero di combinazioni.

Sarebbe ottimale eseguire LUT da RAM ora che ho ridotto le voci da 150 a 27 milioni (e probabilmente inferiori)?

Ora che fino a 27 milioni li conserverebbero come interi moltiplicandoli per 100 (2 posizioni decimali), sarebbe ancora ottimale?

Poiché suggerito da DocBrown , dovrei memorizzare i doppi come valori (moltiplicarli per 100 perché hanno 2 posizioni decimali ) e quindi combinare i 5 diversi valori (4 doppi (vedi sopra) e 1 enum (valore: 1-5)) in un tasto per la LUT.

Come fare in modo che avrò un valore unico per ciascuna combinazione delle mie 5 variabili di input (i 5 ints) E questo metodo è aperto all'espansione di ciascuna delle variabili di input, cioè dovrei aver bisogno di espandere il doppio Le combinazioni di C a 70 anziché a 50 I avranno bisogno di valori chiave univoci per le nuove voci che sono il risultato del numero espanso di combinazioni totali delle variabili di input.

c# database hashing linq speed

posta janderson 22.12.2013 - 15:09

fonte

3 risposte

Leggi altre domande sui tag c# database hashing linq speed

Qual è il modo più efficace per scoprire i dispositivi su una rete? Come gestire quando un utente elimina l'oggetto mentre l'altro lo apre in modalità di modifica in una webapp?

score 4 · Answer 1

I duplicati con 2 posizioni decimali possono essere facilmente memorizzati in un numero intero (moltiplicare ogni uno per 100). Se si mappano le 5 variabili di input in un indice da 0 a 200 (o 1-5 per la quinta), è necessario un massimo di 5 byte per memorizzarle tutte. Per i tuoi record di output, da quello che scrivi valuto avrai bisogno di circa 4 byte per valore, forse 8 per l'ultimo, per un totale di 29 * 4 + 8 = 124 byte. Aggiungere gli ex 5 byte e aggiungere un overhead interno, avrete bisogno di 150 rotondi per record in totale. Moltiplicare questo valore con 150 milioni di record indica che avrete bisogno di almeno 22 GB per conservare tutti i dati in memoria. E questo non sarà diverso se stai usando una struttura hash o una struttura ad albero.

Se hai a disposizione una macchina a 64 bit per l'elaborazione con così tanta memoria principale, puoi provare a gestirla senza un database, ma se utilizzi un PC standard tipico, tenderei ad usare un database per quello (almeno, al giorno d'oggi, tra 5 o 10 anni quando il "PC standard" viene fornito con > 64 GB di RAM, la situazione potrebbe essere diversa). E non usare i doppi direttamente per l'indicizzazione, mapparli prima agli interi nell'intervallo 0, ..., 200, combinarli in un numero intero a 5 byte e usare quel valore come chiave indicizzata.

score 1 · Answer 2

Idealmente una LUT dovrebbe essere veloce da referenziare ma può essere lenta da generare. Sfortunatamente non penso che il tuo scenario sarà rapido nel fare riferimento. Date cinque diverse variabili di input, ciò richiederebbe una sorta di meccanismo di hash che garantisce un valore unico per ogni combinazione possibile. Questo non sarà molto veloce da generare.

Penso che esaminare le strutture ad albero sia la soluzione migliore.

Forse un "albero" in cui ognuno dei tuoi elementi di input è usato come un indice in un LUT più piccolo che poi fa riferimento a un altro LUT .... ecc., fino a raggiungere il LUT finale che ti fornisce i dati di output.

Dalla descrizione dei tuoi input sembra che potresti avere fino a 8 miliardi di record (200 ^ 4) * 5.

score 1 · Answer 3

Suppongo qui che il problema sia di sola lettura e che se qualcosa cambia, puoi fermarti e ricostruire a livello di codice il tuo indice. Innanzitutto, vorrei considerare la codifica del tuo spazio di input come una serie di permutazioni, proprio come sta parlando di Doc Brown. Tuttavia, guarderei cambiare l'output in modo che sia un indirizzo. Questo ha alcuni vantaggi. Se la lunghezza dell'output varia, questo rende le larghezze fisse per le ricerche perché la larghezza degli indirizzi non varia. Permette inoltre di inviare l'output allo storage secondario come il disco ecc. In modo che il sistema operativo possa gestire il caching per le ricerche. Aggiunge uno strato di riferimento indiretto, che non è così buono in qualche modo, ma se il tuo output viene ripetuto può anche permetterti di puntare alla stessa risposta. Diamo un'occhiata ad alcuni numeri. Innanzitutto, lo spazio di input ha qualcosa come 200 * 200 * 50 * 120 = 240.000.000 voci nello spazio completo, non solo lo spazio utilizzato. In secondo luogo, lo spazio di output è approssimativamente 27.000.000 * 30 * 8 (per un full double - ma questo potrebbe forse migliorare), che ci dà 6,48 GB di dati. Questo può essere risolto con spazio di riserva di 5 byte. Quindi ora arriviamo ad un punto critico: gli alberi? array? Gli alberi sono fantastici per molte cose e, a seconda del modello di utilizzo, possono essere fantastici. Ma è davvero difficile battere gli array se si adattano alla memoria. Se usiamo gli alberi, dobbiamo solo memorizzare le voci per i 27 milioni di ingressi effettivamente utilizzati. Tuttavia, il costo nascosto degli alberi è la ricerca multipla di livelli di riferimento indiretto. (Ma B-Trees può essere una buona opzione se non ti piace quello che dico dopo ...) Ma se usiamo gli array per la velocità, abbiamo bisogno di memorizzare puntatori ai nostri dati per tutti i 240 milioni di voci. Ma per essere onesti, 5 byte * 240 milioni danno ~ 1,2 GB che possono essere contenuti in memoria anche su una macchina modesta per la tua ricerca principale su storage secondario.

Quindi il sistema completo sarebbe simile a questo.

Per creare la tabella di ricerca, fai quanto segue:

1) Scansiona tutti i tuoi dati e crea elenchi di ciascun input univoco per ogni variabile, ad esempio 200 per A, 198 per B, ecc.

2) Per ogni variabile di input, crea un dizionario che prende l'input per un int crescente. Questi dizionari dovrebbero essere le strutture di dati più veloci che si possono ottenere per le piccole ricerche. Dato il piccolo numero di valori, un array ordinato usando la ricerca binaria potrebbe non essere una cattiva scelta. L'utilizzo di questo contro un albero può consentire una migliore localizzazione della cache, ma potresti voler condurre alcuni esperimenti su questo.

3) Crea l'array di ricerca e il file di output. Per ogni input, rilascia l'offset del file di output corrente (5 byte) e aggiungi l'output al file di output. La chiave è appena creata facendo qualcosa di simile a questo (valore A) * (numero di B * numero di C * numero di D's) + (valore B) * (numero di C * numero di D's) + (valore C) (numero di D's ) + (valore D)

Per effettuare una ricerca:

1) Calcola la chiave dagli input come spiegato sopra utilizzando i dizionari di piccole dimensioni per ogni singola variabile di input e quindi calcolando la chiave tramite la matematica.

2) Indice nella matrice.

3) Carica oggetto da disco / memoria secondaria. Se puoi inserirlo nella RAM, fa bene a te. In caso contrario, dovremo semplicemente fidarci della cache del disco del sistema operativo.

Sono sicuro che c'è una risposta più intelligente là fuori di sicuro. Ma quello che mi piace di questo approccio è che potrei codificarlo velocemente e farlo funzionare sulla mia scatola a casa senza un server. Quella memoria secondaria può essere qualsiasi cosa ti sia disponibile, e questo vale molto.

Inoltre, dato il tipo di lavoro svolto qui, raccomanderei senz'altro un linguaggio non gestito su un linguaggio gestito per consentire un accesso veloce e non sicuro alla memoria - le lingue non gestite non sono la risposta per tutti i problemi, ma qui sembra una buona idea. Allo stesso modo, il problema sembra specializzato e limitato abbastanza che un database non è probabilmente la soluzione migliore, poiché con un piccolo aggiustamento possiamo più o meno garantire che almeno la ricerca primaria possa rientrare nella RAM.