Dato il formato standard del numero di telefono nordamericano: (Prefisso) Exchange - Abbonato, l'insieme di possibili numeri è di circa 6 miliardi. Tuttavia, abbattere efficacemente i nodi nelle sezioni elencate sopra produrrebbe meno di 12000 nodi distinti che possono essere disposti in raggruppamenti per ottenere tutti i numeri possibili.
Questo sembra un problema già risolto.
Lo farebbe tramite un grafico o un albero?
Un commento che hai inserito nella domanda:
It was an easier question to ask, instead of qualifying. Let's just say that there are much more than 5, but still less than 6 billion. :-)
Quindi sembra che tu abbia intenzione di memorizzare tutti i numeri di telefono validi correnti, nell'intervallo compreso tra (000) 000-0000 e (999) 999-9999. Quindi il set di possibili numeri è 10.000.000.000, o, 10 miliardi.
Questo numero può essere immediatamente ridotto a meno di 8 miliardi, dal momento che la prima cifra in un prefisso non può essere un 0 o 1, il prefisso non può terminare in "11" e i numeri 555 sono riservati, così come alcune altre regole.
Poiché sono disponibili solo un massimo di 8 miliardi di euro e si menzionano la memorizzazione di 5-6 miliardi di dollari, propongo la memorizzazione molto più efficiente in termini di spazio dei 2-3 miliardi di numeri inutilizzati.
Per generare un elenco di numeri validi, è necessario eseguire il ciclo numerico di tutte le combinazioni e saltare i numeri nell'elenco di numeri non validi. Oppure, controlla semplicemente per vedere che un numero non è nei numeri non validi del negozio, per sapere se è valido.
Un albero Trie o un Radix ha più probabilità di essere il più efficiente in termini di spazio pur mantenendo una velocità di ricerca / inserimento / rimozione rapida.
Se i miei calcoli sono corretti, un array di bit per ogni numero di telefono dovrebbe richiedere circa 1,2 GB di memoria. Basta impostare il bit per ogni numero di telefono che è valido.
Se lo facessi per la massima efficienza della memoria, potresti fare di meglio.
Inizia con il prefisso - Non so quanti siano effettivamente utilizzati, ma supponendo che sia necessario memorizzare tutti i valori a 3 cifre.
Presumibilmente i codici di scambio sono compilati in ordine, quindi ti aspetteresti che quelli più bassi vengano utilizzati in più aree rispetto a quelli più alti. Quindi potresti usare una codifica run-length per contrassegnare le sequenze che sono in uso.
Infine, i numeri di telefono effettivi verranno utilizzati o meno a caso, quindi utilizzerei un campo di bit per indicare quale dei 9999 possibili numeri è attivo. A un bit / numero è necessario solo 1K per memorizzare ciascun set.
Il grafico non è adatto a questo, l'implementazione richiede più memoria di albero e in questo caso non fornisce alcuna funzionalità aggiuntiva.
Alberi prefisso? Questi sono molto efficienti per la ricerca ma la rappresentazione della memoria non è ottimizzata per le dimensioni. In realtà sono molto inefficienti per la memoria. Possono anche essere utilizzati per comprimere i dati e scriverli sul disco ma la rappresentazione della memoria richiede molta più memoria dei dati stessi.
Se organizzi i gruppi in modo che solo 3 ultime cifre siano memorizzate nella struttura ad albero, sarebbero comunque 3x4 + 1 byte per ogni numero (puntatore 3x4 byte + 1 byte per i dati). ~ 78 GB solo per 3 ultime cifre di ogni numero (se ricordo correttamente i dettagli di implementazione). Quale richiederà 64 puntatori di bit invece di 32b ... quindi ~ 140 GB di ram.
Quindi il problema (secondo me) è che per albero per ogni suffisso in ogni gruppo hai ancora bisogno di almeno un puntatore a 32 bit (che probabilmente si rivelerà essere 64 bit perché avresti bisogno di allocare > 4GB per i dati).
A mio parere il modo più efficiente sarà un array o 12000 puntatori da strutturare come
char[x] prefix;
DWORD* suffixes;
int n_count;
quindi prefisso, es. 43333 suffisso es. 19821982 => number is 4333319821982 (n_count - > numero di numeri)
Memorizza i numeri senza separatori per risparmiare spazio, un suffisso dopo l'altro (ad esempio il numero 1 è suffisso + 0, il numero 2 è suffisso + 1) e puoi cercare in modo efficiente, se lo hai ordinato.
In questo modo ci vorrebbe solo 4 (DWORD) * 6 miliardi di suffissi = 24 GB di memoria + dimensione di 12k puntatori + prefissi che è irrilevante
Quindi invece di (almeno!) 6 miliardi di puntatori a 64 bit avresti (al massimo!) 6b di suffissi a 32 bit.
Ma probabilmente i numeri sono continui, quindi puoi provare l'array di (start_suffix, end_suffix) invece di memorizzare tutti i suffissi dovrebbero richiedere molto meno.
Leggi altre domande sui tag data-structures algorithms