Ricerca di primo bit impostato in un enorme bitmap

Question

domanda

Intervista:

In uno slot di parcheggio che può contenere milione di auto, è necessario trovare un posto auto gratuito . Non vi è alcuna condizione su dove possa essere la fessura, cioè, il parcheggio può avere più ingressi e trovare uno slot vicino all'ingresso, ecc., Non importa. La domanda era: che tipo di struttura dei dati dovrebbe essere usata e quale sarebbe la complessità delle varie operazioni.

Ho suggerito di utilizzare un array di bit di milioni di bit, con 0/1 per lo slot preso/libero, quindi per trovare il punto libero la domanda tradotta per trovare il primo bit impostato. Non dare per scontato nulla su quante macchine ci sono, ecc., Ad esempio, la matrice di bit potrebbe essere scarsa o densa.

Qual è il modo più veloce per trovare un bit impostato in un'enorme bitmap? Ho suggerito la ricerca binaria + efficiente ffs() per parola come schema.

Answer 1

si può andare in questo modo:

Conservare l'indice dell'ultimo slot libero in una variabile e quindi alla ricerca di quella successiva non eseguire la scansione del bitmap fin dall'inizio, ma da questo valore.

Se è necessario liberare spazio, assegnarlo all'ultimo indice.

std::vector<bool> può essere il vostro array di bit, quindi non avrete bisogno di gestire i bit da soli (i bool sono impacchettati internamente).

È possibile introdurre una struttura mip-mapped:

``std::vector<bool>`` Bitmap; 
``std::vector<bool>`` Bitmap2; // half-sized 
``std::vector<bool>`` Bitmap4; // 1/4 
``std::vector<bool>`` Bitmap8; // 1/8 
// etc 

I valori free nelle matrici di livello superiore e la situazione in cui l'array di livello inferiore ha slot liberi. È possibile utilizzare la ricerca binaria per attraversare questa struttura.

Answer 2

Un milione di numeri interi a 32 bit richiede circa 4 MB di memoria. Quindi direi che tieni una lista di slot gratuiti. Ogni volta che entra una macchina, estrai un oggetto dall'elenco e lo assegni. Ogni volta che un'auto parte, inserisci il numero di slot liberato nell'elenco.

Come ci si sempre e solo essere manipolare la fine della lista (quindi questo è di fatto utilizzato come struttura stack o LIFO), questo ti dà ottimale O (1) le prestazioni sia per la ricerca di uno slot libero e per il ritorno uno slot per lo stato libero. Se lo fai su un livello basso con un pezzo grezzo di memoria, avrai bisogno di un puntatore che indichi la fine corrente dell'elenco. La ricerca di uno slot diminuisce quel puntatore e ne restituisce il valore. Il ritorno di uno slot assegna il puntatore e lo incrementa successivamente.

Se si decide di aggiungere ulteriori requisiti in seguito, è possibile eseguire alcune manipolazioni dei dati, ad es. trasformarlo in un heap. Con una grande mappa di bit 0/1, tali estensioni non sarebbero possibili.