Supponiamo di avere un file che contiene tutti gli interi rappresentabili per un'architettura (quindi, su una macchina a 64 bit, conterrebbe tutti gli interi rappresentabili a 64-bit).
Tuttavia, non tutti i numeri interi sono effettivamente presenti e l'obiettivo è trovare quelli mancanti. Per un solo intero mancante, non è troppo difficile. Ma cosa si dovrebbe fare se mancano più interi?
Probabilmente non è possibile memorizzare l'intero insieme di numeri interi in memoria. Ad esempio, un tipo Uint in C # richiede 4 byte di memoria e ne hai circa 4,2 miliardi, quindi avrai bisogno di 17.179.869.180 byte di memoria o di 17.1 gig di memoria solo per memorizzare tutti i numeri. Se possibile, inizializzare una lista ordinata con tutte le possibilità e quindi elaborare il file rimuovendo le voci dalla lista così come sono state trovate. Alla fine, se tutti i numeri sono presenti, l'elenco risultante conterrà zero voci.
Un altro approccio dovrebbe utilizzare una sorta di memoria persistente come un database. Carica tutti i 4,2 miliardi di record (numeri) nella tabella. Una riga per ogni numero. La chiave primaria è il numero.
Quindi avviare l'elaborazione del file utilizzando gli aggiornamenti batch per eliminare i record dei numeri nel file. Ci sarebbe voluto un po ', ma alla fine tutti i miliardi di record nel file sarebbero stati elaborati.
In questo caso, per elaborare l'intero file ci vuole pochissima memoria perché l'elenco è persistente. Il database potrebbe nasconderlo comunque, ma da un punto di programma molto useremmo con pochissime risorse.
Se parliamo di long, i requisiti sono ancora più grandi poiché i valori superiori per long (Int64) sono 9.223.372.036.854.775,807. Questa è una quantità enorme di dati da elaborare e mantenere. La memoria non sarebbe un'opzione e persino l'uso dell'archiviazione persistente non sarebbe fattibile a causa della quantità di possibilità.
È possibile suddividere l'intero elenco di numeri in partizioni e potenzialmente elaborare l'intero set su una farm di server che ogni server tiene traccia di un intervallo di numeri trovati. Potrebbe essere possibile se non avessi limiti di risorse.
Bene, una soluzione semplice è ordinarli.
Che non è poi così difficile dato che il loro valore ti dice dove metterli. Potrebbe non essere l'approccio più veloce, ma gestisce tutti i casi a condizione che non abbiamo o non si preoccupano per i doppiogiochisti. Non dirmi che non possiamo fare una seconda lista perché abbiamo ottenuto questa dannata lista in qualche modo. Quindi fanculo, ne facciamo un altro. Questa volta ordinati. E lo stiamo facendo in O (n).
Se lo spazio è una preoccupazione piuttosto che il tempo e la semplicità, allora la seconda lista può essere resa 64 volte più piccola della prima, esprimendo l'esistenza di un numero con un bit. Trovato un 3? Vai al terzo bit e accendilo. Al termine, tutto ciò che devi fare è trovare gli zeri. Questo in pratica comprime la lista ordinata. Risparmia spazio ma costa tempo.
Ma ci sono un sacco di casi d'angolo sfruttabili che potrebbero valer la pena filtrare prima di decidere cosa fare.
In primo luogo vorrei confermare se potessi assumere che tutti i numeri siano unici. Se è così, posso dire esattamente quanti numeri mancano semplicemente contando i numeri memorizzati e confrontandoli con il numero previsto di numeri. Una volta ottenuto quel numero, ho un'idea migliore su come regolare il mio approccio e su quali casi angolari da inseguire. In grossi problemi come questo, spesso è una buona idea iniziare con alcune indagini veloci prima di iniziare un processo che devi sperare che funzioni durante il fine settimana.
64 bit è un numero arbitrario di bit. Potremmo avere esattamente la stessa discussione su 8 bit o 256 bit. Alcune volte vale la pena sapere quanto è difficile un problema.
In memoria creerei un elenco di 2 colonne
basso, alto
il primo numero diventa basso
quindi uno per uno
questo sarà come n (log n) e pensa che lo spazio sarà come log n
testato e funziona
la dimensione della lista sale e poi scende
public void FindMissing()
{
List<LowHigh> llist = new List<LowHigh>();
Int32 num;
int highCount = 0;
LowHigh lh;
LowHigh lhNext = new LowHigh(UInt16.MaxValue);
LowHigh lhPrev = new LowHigh(0);
Random rand = new Random();
List<Int32> testInts = new List<Int32>() { 1, 2, 4, 5, 3 };
for (UInt32 i = 0; i < UInt16.MaxValue * 2; i++)
//foreach (UInt16 i in testInts)
{
num = rand.Next(UInt16.MaxValue);
//num = i;
if(i % 1000 == 0)
System.Diagnostics.Debug.WriteLine(num);
if (llist.Count == 0)
{
llist.Add(new LowHigh(num));
}
else
{
for (UInt16 j = 0; j < llist.Count; j++)
{
lh = llist[j];
if (j < llist.Count - 1)
lhNext = llist[j + 1];
if (j > 0)
lhPrev = llist[j - 1];
if (j == 0 && num < lh.Low)
{
llist.Insert(0, new LowHigh(num));
break;
}
else if (num >= lh.Low && num <= lh.High)
break;
else if (num == lh.Low - 1)
{
lh.Low = num;
if (j > 0)
{
if (lh.Low == lhPrev.High || lh.Low == lhPrev.High + 1)
{
lh.Low = lhPrev.Low;
llist.RemoveAt(j - 1);
}
}
break;
}
else if (num == lh.High + 1)
{
lh.High = num;
//System.Diagnostics.Debug.WriteLine(lh.Low + " " + lh.High);
if (j < llist.Count - 1)
{
if (lh.High == lhNext.Low || lh.High == lhNext.Low - 1)
{
lh.High = lhNext.High;
llist.RemoveAt(j + 1);
}
}
break;
}
else if (j < llist.Count - 1 && num > lh.High && num < lhNext.Low - 1)
{
llist.Insert(j + 1, new LowHigh(num));
break;
}
else if (j == llist.Count - 1)
{
llist.Add(new LowHigh(num));
break;
}
}
if (llist.Count > highCount)
highCount = llist.Count;
}
//foreach (LowHigh lhr in llist)
// System.Diagnostics.Debug.WriteLine(lhr.Low + " " + lhr.High);
//System.Diagnostics.Debug.WriteLine("");
}
System.Diagnostics.Debug.WriteLine(highCount);
foreach (LowHigh lhr in llist)
System.Diagnostics.Debug.WriteLine(lhr.Low + " " + lhr.High);
System.Diagnostics.Debug.WriteLine("");
}
Leggi altre domande sui tag algorithms