Considera il problema della randomizzazione di un set di dati così grande da non entrare nemmeno nella memoria. Questo articolo descrive come farlo facilmente e (relativamente) velocemente in Python.
Al giorno d’oggi non è affatto raro trovare set di dati che vengono misurati in gigabyte, o addirittura terabyte, in termini di dimensioni. Tutti questi dati possono aiutare moltissimo nel processo di formazione per creare solidi modelli di machine learning. Ma come è possibile randomizzare set di dati così grandi?
Immagina di avere un set di dati molto grande con un elemento per riga in un file. I dettagli dei dati sono irrilevanti per i nostri obiettivi qui. Il set di dati potrebbe essere costituito da righe in un file CSV (valori separati da virgola) o TSV (valori separati da tabulazione), oppure ciascuna riga potrebbe essere un oggetto JSON o un elenco di valori X, Y, Z di un punto in un punto di grandi dimensioni nuvola. Tutto ciò di cui abbiamo bisogno è che il set di dati sia formattato con un elemento per riga.
Per i file contenenti set di dati più piccoli, è possibile randomizzare il file (chiamato “shuffling”) in memoria utilizzando una semplice funzione Python come questa:
import randomdef shuffle_in_memory(filename_in, filename_out):
# Shuffle a file, line-by-line
with open(filename_in) as fp:
lines = fp.readlines()
# Randomize them in place:
random.shuffle(lines)
# Write the new order out:
with open(filename_out, "w") as fp:
fp.writelines(lines)
IL riproduzione casuale_in_memoria() La funzione accetta un nome file di input e un nome file di output, mescola le righe in memoria utilizzando la funzione incorporata casuale.shuffle(), e scrive i dati randomizzati. Come suggerisce il nome, questa funzione richiede che tutte le righe del file siano caricate in memoria contemporaneamente.
Per testare questa funzione, creiamo alcuni file di prova. La funzione crea_file() prende le linee numeriche che desideri nel file di test. La funzione creerà il file e restituirà il nome del file.
import osdef make_file(lines):
filename = "test-%s.txt" % lines
print("Making test file '%s'..." % filename)
with open(filename, "w") as fp:
for i in range(lines):
fp.write(f"Line {i}\n")
print("Done!")
return filename
Ad esempio, per creare un file denominato “test-1000.txt” con 100 righe, avrà il seguente aspetto:
filename_in = make_file(1000)
Dopo aver eseguito questa funzione, dovresti trovare nella tua directory corrente un file denominato “test-1000.txt” con 1.000 righe di testo, come:
Line 0
Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
...
Per testare il nostro riproduzione casuale_in_memoria() funzione, nomineremo un file di output, salveremo la stringa nella variabile nomefile_oute richiamare la funzione:
filename_out = "test-randomized-1000.txt"
shuffle_in_memory(filename_in, filename_out)
Ora, dovrebbe esserci un secondo file nella tua directory chiamato “test-randomized-1000.txt”. Dovrebbe avere esattamente la stessa dimensione di “test-1000.txt” con esattamente le stesse righe, ma in ordine casuale:
Line 110
Line 592
Line 887
Line 366
Line 52
Line 22
Line 891
Line 83
Line 931
Line 408
...
Ok, ora arriviamo alla grande domanda: cosa fare se abbiamo un file molto grande? Facciamone uno di medie dimensioni con, diciamo, 10 milioni di righe. (Per la maggior parte dei computer questo è ancora abbastanza piccolo da poter essere randomizzato in memoria, ma è sufficientemente grande per esercitarsi.) Come prima, creiamo il file di input con una chiamata a crea_file():
filename_in_big = make_file(10_000_000)
L’operazione richiederà alcuni secondi. Successivamente dovresti avere un file chiamato “test-10000000.txt” nella tua directory. Dovrebbe iniziare come prima, ma avrà 10 milioni di righe. Il file è di circa 128 MB.
Come randomizzarlo? Se non vogliamo utilizzare tutta la nostra RAM, o non ne abbiamo abbastanza, possiamo utilizzare il disco rigido. Ecco un algoritmo ricorsivo basato su un problema simile, l’ordinamento. La seguente funzione riproduzione casuale() si basa sull’algoritmo Merge Sort.
Innanzitutto, controlla se un file è abbastanza piccolo da poter essere mescolato in memoria (il caso base nel gergo delle funzioni ricorsive). Il parametro limite_memoria è dato in byte. Se la dimensione del file è inferiore a limite_memoriaquindi verrà mescolato in memoria. Se è troppo grande, viene suddiviso casualmente in un numero di file più piccoli e ciascuno di questi viene mescolato ricorsivamente. Infine, i contenuti dei file mescolati più piccoli vengono riuniti insieme.
Ecco la funzione:
import tempfiledef shuffle(filename_in, filename_out, memory_limit, file_split_count,
depth=0, debug=False):
if os.path.getsize(filename_in) < memory_limit:
if debug: print(" " * depth, f"Level {depth + 1}",
"Shuffle in memory...")
shuffle_in_memory(filename_in, filename_out)
else:
if debug: print(
" " * depth, f"Level {depth + 1}",
f"{os.path.getsize(filename_in)} is too big;",
f"Split into {file_split_count} files..."
)
# Split the big file into smaller files
temp_files = (tempfile.NamedTemporaryFile('w+', delete=False)
for i in range(file_split_count))
for line in open(filename_in):
random_index = random.randint(0, len(temp_files) - 1)
temp_files(random_index).write(line)
# Now we shuffle each smaller file
for temp_file in temp_files:
temp_file.close()
shuffle(temp_file.name, temp_file.name, memory_limit,
file_split_count, depth+1, debug)
# And merge back in place of the original
if debug: print(" " * depth, f"Level {depth + 1}",
"Merge files...")
merge_files(temp_files, filename_out)
Se si trattasse di un algoritmo di ordinamento, uniremmo nuovamente i file insieme in modo accurato per creare un ordinamento ordinato. Tuttavia, per il mescolamento, non ci interessa unirli in un ordine particolare poiché li vogliamo randomizzati. IL unisci_file() la funzione quindi assomiglia a:
def merge_files(temp_files, filename_out):
with open(filename_out, "w") as fp_out:
for temp_file in temp_files:
with open(temp_file.name) as fp:
line = fp.readline()
while line:
fp_out.write(line)
line = fp.readline()
Si noti che stiamo attenti a non leggere tutte le righe dei file in memoria tutte in una volta. Proviamolo assegnando che il limite per lo spostamento della memoria sia esattamente la dimensione del file. Poiché la dimensione del file non è inferiore a 128.888.890, verrà suddivisa in un numero di file più piccoli. Per questo esempio, suddividiamo il file grande in 2, ognuno dei quali sarà sufficientemente piccolo da poter essere mescolato in memoria:
filename_out_big = "test-randomized-10000000.txt"
shuffle(filename_in_big, filename_out_big, 128_888_890, 2, debug=True)
Questa chiamata produce il seguente output:
Level 1 128888890 is too big; Split into 2 files...
Level 2 Shuffle in memory...
Level 2 Shuffle in memory...
Level 1 Merge files...
E il contenuto del file risultante “test-randomized-10000000.txt” dovrebbe avere 10 milioni di righe, tutte randomizzate. Un test migliore sarebbe ridurre la memoria necessaria per essere molto più piccola del file da randomizzare e suddividere i file troppo grandi in più di 2. Diciamo che vogliamo utilizzare solo circa 1 MB di RAM e suddividere i file in 20 file più piccoli:
shuffle(filename_in_big, filename_out_big, 1_000_000, 20, debug=True)
Questo esempio utilizzerà non più di 1 MB di RAM e scomporrà ricorsivamente i sottofile più grandi, 20 alla volta.
Questo algoritmo funzionerà su file di qualsiasi dimensione (beh, hai bisogno di spazio su disco sufficiente!). Maggiore è la quantità di memoria che puoi allocare per riproduzione casuale_in_memoria() più velocemente funzionerà. Se il numero di file più piccoli è troppo grande, passerai troppo tempo ad aprire e chiudere i file. Puoi provare numeri diversi per limite_memoriama ho avuto fortuna con un numero compreso tra 20 e 200. Più grande è il file iniziale, probabilmente vorrai più sottofile.
Esistono anche altri algoritmi che puoi utilizzare. Avevo grandi speranze di scrivere tutte le righe in un database SQLite, SELEZIONANDOLE in ordine casuale, ma non era più veloce del codice sopra.
import sqlite3def shuffle_sql(filename_in, filename_out, memory_limit, depth=0, debug=False):
if os.path.getsize(filename_in) < memory_limit:
if debug: print(" " * depth, f"Level {depth + 1}",
"Shuffle in memory...")
shuffle_in_memory(filename_in, filename_out)
else:
if debug: print(
" " * depth, f"Level {depth + 1}",
f"{os.path.getsize(filename_in)} is too big;",
f"Writing to SQLite database..."
)
temp_db = tempfile.NamedTemporaryFile(delete=False)
connection = sqlite3.connect(temp_db.name)
cursor = connection.cursor()
cursor.execute("""
CREATE TABLE IF NOT EXISTS lines (
line TEXT
);
""")
with open(filename_in) as fp:
line = fp.readline()
while line:
cursor.execute("INSERT INTO lines (line) VALUES (?);", (line))
line = fp.readline()
connection.commit()
with open(filename_out, "w") as fp:
for line in cursor.execute("""
SELECT line FROM lines ORDER BY random();
"""):
fp.write(line(0))
shuffle_sql(filename_in_big, filename_out_big, 1_000_000, debug=True)
Riesci a battere l’algoritmo ricorsivo di shuffle, rimanendo esclusivamente in Python? Se è così, mi piacerebbe sentirlo!
Ti interessa l’intelligenza artificiale, l’apprendimento automatico e la scienza dei dati? Considera un applauso e un seguito. Fammi sapere cosa ti interessa!
