Ho bisogno di aiuto per creare un albero non binario (o qualche altra struttura dati che risolverà meglio il mio problema)

Question

Ho bisogno di aiuto per creare un albero non binario (o qualche altra struttura dati che risolverà meglio il mio problema)

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

0

Ho una decina di elenchi di numeri e alcune stringhe. Ogni elenco ha circa < = 30K linee. Ogni riga di un elenco ha un numero distinto.

Ho bisogno di costruire un modo efficace per trovare tutte le linee in ogni elenco che ha lo stesso numero di "controllo" (o chiave per i ragazzi di dB) e confrontare ciò che è nelle loro parti di stringa. Sto scrivendo questo in Java.

Consentitemi di dare un esempio reale di ciò che sto cercando di fare ..... Ho dieci elenchi ciascuno contenenti circa 30.000 di record. Ogni record appare come 901234 (chiave) - 1.0987 (float) -kadfnfj (Description String) -01/01/01 (data) e tutte le liste hanno record simili alcune chiavi potrebbero essere disponibili in alcune liste ma non garantite! .. Voglio per trovare un modo per cercare tra tutti gli elenchi per una particolare chiave e confrontare il valore float dell'operatore. A causa delle dimensioni degli elenchi, sono preoccupato per l'utilizzo della memoria e, a causa del numero di record, sono preoccupato per l'efficienza della struttura dati utilizzata.

Ho pensato di usare gli alberi ma le mie cellule cerebrali ora sono bruciate. Ho bisogno di aiuto.

data-structures data comparison

posta EDO 31.10.2012 - 15:35

fonte

3 risposte

Leggi altre domande sui tag data-structures data comparison

Infrastruttura necessaria per progetti di grandi dimensioni con molti componenti che comunicano tramite IPC Come creare un riquadro Button / Switch-Like dove puoi calpestarlo e modificarne il valore?

score 3 · Answer 1

Idealmente si userebbe un database. Lasciate che il database gestisca rapidamente la ricerca del valore. Se hai un database piccolo e leggero (mysql e simile) accessibile, usalo.

Se non si dispone di una tabella che è possibile utilizzare da un DBA per eseguire questa operazione, esistono altre soluzioni di database. Quello che mi è più familiare è BDB (Berkeley DataBase).

Usando la versione con licenza Sleepycat, questo è gratuito. BDB memorizza i suoi dati su disco e non li memorizza interamente nella memoria in una sola volta.

La parte più difficile di questo disegno sono i dati memorizzati per ogni chiave (in un certo senso, questo è il problema per qualsiasi cosa).

Se si è disposti a spendere spazio su disco, una considerazione sarebbe quella di utilizzare il filesystem stesso come un database. Per i dati 901234(key)- 1.0987(float)-kadfnfj(Description String)-01/01/01(date) , dovresti scrivere un file nella directory .../9/0/1/2/3/4/901234/ con le informazioni che stai memorizzando. L'accesso al filesystem non è male e rende anche banale il fatto che altre applicazioni accedano ai dati.

Se è così, se hai familiarità con altri linguaggi di "scripting" (perl, python, ecc ...) questi possono essere più adatti all'attività (lavorare con le stringhe e il file system) semplicemente per spezzare il grande file nelle loro linee componenti.

score 2 · Answer 2

Per prima cosa, scrivi qualcosa che funzioni. Puoi semplicemente dividere la linea per tenere la chiave e il float e metterla in Map; Mappa separata per ogni 30K-list. Quindi avrai alcune mappe da chiavi intere per rendere mobili i valori. O qualcosa di così semplice.

Se funzionerà, misurerà se è troppo lento e quindi cercherà di trovare strutture dati / algortihms migliori. Direi che per i record 30K, una mappa contenente i dati in memoria sarebbe sufficiente.

score -1 · Answer 3

Il metodo ideale per accedere a una determinata chiave sarebbe l'accesso diretto dove usi la chiave per darti l'indirizzo. In Java non si hanno indirizzi di memoria diretti, ma si ottengono array indicizzati in modo da poter usare l'indice di array come indirizzo di memoria. Questo dovrebbe essere molto più veloce di qualsiasi metodo di attraversamento.