Ho una matrice ordinata molto grande, memorizzata sul disco. Posso accedere in modo casuale a qualsiasi elemento.
Voglio renderlo ordinato di livello per accelerare la ricerca binaria lì. L'idea è presa in prestito da:
Se faccio così, credo che sarò in grado di utilizzare la cache del disco molto meglio.
Tuttavia, non vedo un modo semplice per creare ordinamenti di livello senza usare la coda. Poiché i dati sono immutabili, non ho bisogno di una soluzione rapida.
Qualsiasi idea sarà apprezzata.
Il riordino può essere fatto in modo "zoppo", ad es. stampa livello per livello.
Non sono riuscito a rimuovere la ricorsione, ma non è necessaria una coda.
Anche perché stiamo lavorando con un array, non è necessario toccarlo più di N volte - ad es. tocchiamo ogni elemento solo una volta.
Ecco l'implementazione concettuale che elenca solo i primi livelli, ma l'idea è chiara.
Implementazione in C ++, ma C sarebbe quasi il simile.
#include <cstdio>
void reorder(size_t const start, size_t const end, size_t const level, size_t const clevel = 0){
if (start >= end){
printf("NULL\n");
return;
}
size_t const mid = start + ((end - start) >> 1);
if (clevel == level){
// here we touch the array
printf("%zu\n", mid);
return;
}
reorder(start, mid, level, clevel + 1);
reorder(mid + 1, end, level, clevel + 1);
}
void reorder(size_t const size, size_t const maxLevels){
for(size_t level = 0; level < maxLevels; ++level)
reorder(0, size, level);
}
int main(){
reorder(20, 4);
}
Ecco un altro esempio:
Leggi altre domande sui tag array binary-tree