Incremento della cartella bilanciata

Question

Incremento della cartella bilanciata

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

-1

Voglio mappare un numero intero (diciamo 32 bit) su un percorso valido. Il numero intero è un valore di autoincremento memorizzato nel database.

Inoltre, non voglio che nessuna cartella abbia più di N sottocartelle. Questo perché in WIN-NTFS (ad esempio) dopo un numero specifico (circa 1000) le cose stanno andando molto lentamente.

Quindi ho ideato un modello in cui ogni intero è mappato a hex groupped in due cifre. Ciò crea 4 cartelle per ogni intero

Ad esempio:

1 -> '00/00/00/01'
2000 -> '00/00/07/D0'
70000 -> '00/01/11/70'
etc

Tutto bello e bene.

Ma se si nota dopo aver creato le prime 257 voci

the folder '00/00/00' will have 256 entries ('00' to 'FF')
folder '00/00/01' will have one entry
folder '00/00' will have 2 entries ('00' and '01')
and last folder '00' will have just one entry.

Il grafico è altamente sbilanciato, il SO per trovare finalmente la cartella '00 / 00/00/55 'dovrà cercare tra 1 + 1 + 2 + 256 = 260 voci. Se il grafico fosse bilanciato sarebbe una ricerca di 4 * Pow (257,1 / 4) = ~ 16 voci

E la mia domanda è:

È comunque possibile trasformare il numero intero A in un intero A che ha le seguenti proprietà:

È la trasformazione 1: 1
Può essere invertito (per ogni A 'posso trovare facilmente A)
Per ogni 1..N, creando cartelle usando il valore esadecimale A ', ciascuna cartella non ha più di voci Pow (N, 1/4)

EDIT: Ho provato i due codici. Il problema è che le funzioni di crypt emettono l'intera gamma a 32 bit. Voglio dire dopo 1000 incrementi e dopo ogni byte ha un valore casuale, la cartella radice ha 256 diversi valori (sottocartelle) e ognuno di essi ha 1 o 2 voci. È la stessa situazione con cui ho iniziato. È solo inverso

algorithms

posta Panos Theof 22.12.2015 - 11:59

fonte

3 risposte

Leggi altre domande sui tag algorithms

modo migliore per caricare i dati per milioni di utenti Estensione ipotetica alla sintassi di inizializzazione della proprietà C #

score 1 · Answer 1

Inizia con operazione modulo . Questo ti dà X cartelle per iniziare. Man mano che i tuoi ID crescono, aggiungi un offset. Un esempio, gruppi di 10 cartelle, 10 file per cartella:

id < 100 : id % 10
Folders F0 through F9 -> Files are added in order, one in each, 
then two, then... all the way to 10.

id >= 100 && id < 200: (id % 10) + 10
Folders F10 through F19 -> Files are added in order, et cetera

id >= 200 && id < 300: (id % 10) + 20
Folder F20 through F39

Etc...

Ovviamente vorrete un modulo diverso (numero di cartelle per gruppo) e file per cartella (1000?).

score 1 · Answer 2

Non è del tutto ovvio, ma il tipo di algoritmo che stai cercando è chiamato una curva di riempimento dello spazio . Lo spazio qui è lo spazio dei nomi delle cartelle.

XKCD ha avuto un esempio 2D molto tempo fa. Mostra come i primi 4 file finirebbero in /00/00 in /01/01 e i primi 16 in in /00/00 in /03/03 . Espandendo l'algoritmo, i primi 256 file terminano in /00/00 in /0F/0F .

In un esempio 3D, una curva di riempimento dello spazio mappa le prime 8 voci da /00/00/00/ a /01/01/01 e il primo 64 a /00/00/00/ a /03/03/03 . L'espansione in N dimensioni è semplice da lì, ma come ho detto nel commento soffre di ricerca di dischi eccessivi.

score 1 · Answer 3

Questa non è una risposta diretta ma non si adatta a un commento. Voglio solo elaborare il commento di MSalters: internamente, NTFS fa già ciò che stai cercando di fare.

È un'errata impressione che l'enorme cartella NTFS sia lenta. L'impressione sbagliata è in genere dovuta al modo in cui alcuni utenti interagiscono con la cartella: Windows File Explorer, che carica tutte le voci quando viene aperta una cartella e si suppone che sia lenta. Tuttavia, se si esegue una query su un file con un nome specifico, è istantaneo. Ora puoi chiedere, anche se il programma può sempre accedere alla cartella con il nome del file specificato, per quanto riguarda la manutenzione e il supporto, ad esempio un membro del supporto deve verificare l'esistenza di un file? In tal caso, vai alla riga di comando e "cd" nella cartella, usa "nomefile dir". Il risultato è ancora istantaneo. Ovviamente, se provi "dir * 21", ti verrà servita la performance "table-scan".

Una volta ho lavorato a un progetto che riguardava un'enorme cartella NTFS. Andava tutto bene fino a quando qualche manager ha deciso di dividere la cartella in cartelle più piccole. Inutile dire che complicò inutilmente il programma e rallentò sia il programma che me quando ho bisogno di supporto. In cambio, più sviluppatori e utenti si sentivano a loro agio con la cartella quando avevano bisogno di cercare un file in quella cartella, che in realtà è un motivo valido per dividere una cartella NTFS.