Python Programmatisch große (pseudo)zufällig gefüllte Datei erzeugen

[Sukrim]

Interessanterweise habe ich zu dem Thema irgendwie nicht wirklich was ergooglen können...

Folgendes Problem:
Für einen Deduplizierungsalgorithmus möchte ich für Tests eine möglichst große (so ein paar Dutzend MB sollten schon drinnen sein) Datei zur Laufzeit erzeugen, die mit (pseudo-)zufälligen Daten gefüllt ist. Da ich danach auch Hashes testen möchte, sollten dann aber bei mehreren Durchläufen jeweils die gleichen Daten erzeugt werden.

Bisher erzeuge ich mit fixiertem Seed + dem "random" Befehl eher schlecht als recht einige ASCII chars - was mir einerseits nicht zufällig genug ist, andererseits dauert das Ganze auch noch ~30 Sekunden für 10 MB!
Ein bisschen Code dazu (zur Verwendung mit py.test, daher nicht reines Python):

import random

[...]
    tempfile = tmpdir.join("hugefile.txt")
    random.seed(0)
    randomdata = bytearray()
    for x in range(0,10000000): #<-- WTF 30 seconds!?
        randomdata.append(random.randint(128,255))
    with tempfile.open(mode="wb") as bigfile:
        bigfile.write(randomdata)
    #make sure the file has been created properly + the hash value is ok
    assert tempfile.read() == randomdata
    assert tempfile.computehash() == "cd23618e51385346e9cd2923f0ff8d22"

Wie kann ich nun also (ohne eine __ MB große statische Datei aus /dev/random ins Repository zu laden) rein in Python in ~1 Sekunde eine große Datei erzeugen, die so zufällig wie möglich ist (Benchmark: gezippt immer noch >85% so groß wie ungezippt)?

An Betriebssystemen verwende ich sowohl Windows als auch Linux, und es soll auch auf beiden Plattformen testbar sein, also bitte nichts Plattformspezifisches.

 

[zatarc]

Ich würde dir zu numpy raten. Die random-Implementierung ist da wesentlich effektiver.

import time
import random
import numpy

def benchmark(test):
    start = time.time()
    test()
    print time.time() - start

def test1():
    random.seed(0)
    randomdata = bytearray()
    for x in range(0,10000000):
        randomdata.append(random.randint(128,255))

def test2():
    numpy.random.seed(0)
    randomdata = bytearray()
    for x in range(0,10000000):
        randomdata.append(numpy.random.randint(128,255))

>>> benchmark(test1)
24.8860001564
>>> benchmark(test2)
4.01699995995

Vielleicht könnte man noch durch psyco noch ein wenig herauskitzeln, vorausgesetzt du verwendest Python <= 2.6 und x86.

// edit: mit pp kann man es nochmal beschleunigen, in dem man die Generierung parallelisiert.

import time
import numpy
import pp

def generateRandomData(amount): 
    numpy.random.seed(0)
    randomdata = bytearray()
    for x in range(0, amount): 
        randomdata.append(numpy.random.randint(128,255))
    return randomdata

def test3():
    job_server = pp.Server(4, ppservers=()) #  4 Threads
    randomdata = bytearray()
    inputs = (2500000, 2500000, 2500000, 2500000) # in 4 Teile á 2,5 MB splitten
    jobs = [(input, job_server.submit(generateRandomData,(input,), (), ("numpy",))) for input in inputs]
    for input in jobs:
        randomdata += job()

>>> benchmark(test3)
1.97300004959

 

[Sukrim]

Klingt schon mal super!

Zwar finde ich es ein bisschen arg nur für ein paar Tests gleich noch eine Abhängigkeit hinzuzufügen, aber im Endeffekt braucht man die dann ja auch nur bei den Tests selbst, Anwender kämen dann auch ohne aus...

pp könnte ich mir dann eh mal genauer anschauen, gerade für SSDs wäre es nämlich vielleicht ohnehin interessant mehrere Dateien zugleich zu öffnen und zu deduplizieren.

Ich bin mir nur generell nicht sicher, ob dieser Ansatz der Richtige ist oder ob man sowas nicht eigentlich komplett anders löst. Diesmal habe ich mir aber eben vorgenommen, von Anfang an erst Tests und dann Code zu schreiben und Tests haben bei mir auch eher nicht auf diesem Level stattgefunden... daher muss ich ehrlich zugeben, dass ich mich mit dem Thema auch nicht so gut auskenne.

 

[zatarc]

Egal wie man es umsetzt, die Generierung von Zufallszahlen ist immer der Flaschenhals und solange du keinen physischen Zufallsgenerator auf deinem Mainboard verbaut hast (haben wohl nur die teuren Servermainboards), wird hier immer der Knackpunkt liegen. Man muss also eine schnelle Implementierung von "random" finden. Wie man darauf dann zugreift, ist dann wurst...

/dev/random wäre wohl die schnellste Implementierung und mit cygwin (ich weiß, wieder ne Abhängigkeit) auch plattformübergreifend.

> dd if=/dev/random of=/cygdrive/x/test.random bs=1024 count=10000

10000+0 records in
10000+0 records out
10240000 bytes (10 MB) copied, [B][U]0.558282 s[/U][/B], 18.3 MB/s

Und das war mit cygwin!

Achja, wenn du den parallelen Ansatz verfolgen willst, musst du nicht unbedingt pp nehmen. Es gibt auch Möglichkeiten die in python in der Standard Library sind (threading, multiprocessing). Ich verwende pp immer wegen Bequemlichkeit

 

[r0b0t]

Warum so kompliziert? Du kannst doch einfach ein bestehendes Verzeichnis nehmen und dies mit allen Unterordnern unter einem anderen Namen irgendwohin kopieren. Die Dateinamen können ja gleich bleiben. Die Dateien darin können ja auch beliebig groß (Videos) sein. Dann hast du eine genau definierte Menge von Dateien, die dein Deduplizierer finden muss.

 

[Sukrim]

Naja, irgendwann will ich den Code (inklusive Tests) auch veröffentlichen, daher fallen /dev/random oder lokale Daten wie gesagt schon raus, da da ja nicht deterministische Zahlenfolgen rauskommen und jeder die Tests anpassen müsste...

 

[asdfman]

Es gibt doch Spezifikationen für PRNGs. Implementiere eine. Zum Beispiel:
http://www.schneier.com/yarrow.html

 

[Sukrim]

Ähm, nur um einen Unittest durchführen zu können einen PRNG selbst implementieren + optimieren? Naja...

Danke für den Link, aber ich werde es dann doch wohl eher erstmal Multithreaded versuchen, falls keine anderen Lösungsansätze als mein eigener kommen... Übrigens befürchte ich da, dass dann ja erst 4* die genau gleiche Zahlenfolge hintereinander steht und dadurch von mir dedupliziert werden könnte, oder?!