Das deutsche Python-Forum

Hi zusammen,

ich bastle gerade einen eigenen Binär-Search.
D.h. ich habe ein Such-Pattern was ich mit meinem Buffer vergleichen will.
Alle Werte sind "eigentlich" (aber was ist schon eigentlich ...) Bytes und keine Char's, aber wie mache ich hier eine Byte-weise XOR Operation ?

Code: Alles auswählen

...
seek_pointer = 0
bin_search_pattern = b'\x00\x00\x00\x01\x42'
	
with open(inputfile, "br") as fi:
	while True:
		read_buffer = fi.read(5)
		test = read_buffer ^ bin_search_pattern
		if test:
			print(seek_pointer)
	
		seek_pointer += 1
		fi.seek(seek_pointer)

Code: Alles auswählen

    test = read_buffer ^ bin_search_pattern
TypeError: unsupported operand type(s) for ^: 'bytes' and 'bytes'

@may24x: Was soll denn ``if test:`` hier bedeuten? Jedes `bytes`-Objekt mit einer Länge von mindestens 1 ist ”wahr”, die Bedingung ist also etwas komisch.

oops, stimmt ... das stammt noch von vorherigem Code ... da war/sollte test ein Bool sein ...
Aber egal erst mal, das hier geht schon nicht

Code: Alles auswählen

bin_search_pattern = b'\x00\x00\x00\x01\x42'
seek_pointer = 0
	
with open(inputfile, "br") as fi:
	while True:
		read_buffer = fi.read(5)
		test = read_buffer ^ bin_search_pattern
		print(test)

PS: Warum funktioniert der Codeblocks Tag eigentlich nicht ?

@may24x: Ja aber was sollte `test` als `bool` an der Stelle aussagen? Was möchtest Du denn da machen? Was sollte bei ``read_buffer ^ bin_search_pattern`` heraus kommen und auf was soll dieses Ergebnis dann getestet werden? (Ich will hier sicherstellen das Du nicht einfach nur einen simplen Vergleich viel zu kompliziert ausdrücken willst.)

Nun, ich habe zwei Array's mit Bytes. Eines was mein Search-Pattern ausdrückt und einen Ausschnitt welches ich binär aus einer Datei lese.
Um zu prüfen ob der Ausschnitt mit meiner Suche übereinstimmt, benutze ich eine EXOR Verknüpfung.
D.h. sind beide gleich - binär gesehen - müsste "test" -> \xff \xff \xff \xff \xff -> True sein

Die "if" Abfrage gibt mir dann die Position aus wenn die zwei Byte-folgen überein stimmen

@may24x: Genau so etwas hatte ich befürchtet. *WARUM*‽ Mach einfach einen Vergleich und gut ist. Zudem ist das Ergebnis lauter 0-Bits wenn die beiden Bytefolgen gleich sind.

Du willst also ``test = read_buffer == bin_search_pattern``. Und *eigentlich* willst Du in grösseren Blöcken lesen und die `index()`-Methode zum Suchen verwenden, kein `seek()` verwenden, und vielleicht sogar einfach das `mmap`-Modul benutzen.

Tja ... das mit dem XOR war zu kompliziert gedacht

ein einfaches "==" funktioniert wunderbar.

Nein, das mit den größeren Blöcken ist so 'ne Sache. Da die Files die ich parse zwischen 500MB und 2 GB groß sind, müsste ich das Ganze erst mal in den Speicher schieben, dann indexieren und durchsuchen ...
Da ist meine Vorgehensweise doch etwas schlanker ... wenn auch nicht so performant ... behaupte ich mal

@may24x: Es ist halt (abgesehen von komischen Sachen wie XOR

) die langsamste Art das zu machen, und das dann auch noch wenn die Datenmengen grösser sind. Du solltest ja nicht alles auf einmal in den Speicher laden, aber mindestens mal grössere Blöcke verarbeiten. Oder eben `mmap` anschauen.

Hm ... ok ... Ich hab 'n ARM7 Prozessor mit 512 MB Speicher ... insgesamt.
D.h. für OS + App's ... ist kein Handy sondern ein SAP (Stand Alone Player).

Über'n Daumen schätze ich mal das ich ca. 100 MB für das Script kurzzeitig mir unter'n Nagel reißen könnte.
Was meinst du ... index() oder mmap ... ?
Und wenn der schon eine Binärsuche macht ... wie macht er das ? Schiebt Python das Pattern immer nur ein Byte weiter und testet ... oder mehrere ... ganz anders ?

@may24x: Hm, beim ARM wüsste ich jetzt gerade nicht ob der trotzdem einen grossen, virtuellen Adressraum zur Verfügung stellen kann, deshalb könnte `mmap` für wirklich grosse Dateien nicht funktionieren.

100 MiB würde ich wohl auch nicht gleich nehmen, eher etwas zwischen 16 Kilobyte und einem Megabyte. Auf jeden Fall würde ich Daten nicht in len(pattern)-Häppchen und dann auch noch len(pattern) mal lesen was Du ja effektiv machst.

Nun das mit dem index() scheint gar keine so gute Idee zu sein, da nur das erste Element ausgegeben wird.
Kommt aber die Search-Pattern mehrfach vor, werden alle folgenden ignoriert ....

may24x hat geschrieben:Nun das mit dem index() scheint gar keine so gute Idee zu sein, da nur das erste Element ausgegeben wird.
Kommt aber die Search-Pattern mehrfach vor, werden alle folgenden ignoriert ....

Man kann festlegen, dass index() bei einer Position > 0 mit der Suche beginnt. Wenn man das so implementiert, dass auch abgeschnittene Treffer (also zwischen zwei Chunks) erkannt werden, dann wird es schon etwas komplexer, ist aber machbar:

Code: Alles auswählen

def get_chunks(f, size=1024):
    while True:
        chunk = f.read(size)
        if not chunk:
            break
        yield chunk

def find_indices(chunk, needle, index=0):
    while True:
        try:
            index = chunk.index(needle, index)
        except ValueError:
            break
        yield index
        index += len(needle)

def find_all(filename, needle, is_binary=False):
    mode = 'rb' if is_binary else 'r'
    with open(filename, mode) as infile:
        buf = ''
        for chunk in get_chunks(infile):
            for index in find_indices(buf + chunk, needle):
                yield index
            if not chunk.endswith(needle):
                # Might be part of truncated needle
                buf = chunk[-(len(needle) - 1):]

@snafu: buf ist falsch, wenn Chunk 17 nicht mit needle ended, Chunk 18 aber schon; die Frage ist ja auch, ob es überlappende needels geben könnte. Der Index berücksichtigt nicht, dass schon mehrere Chunks gelesen wurde und liefert nur relative Werte. Für len(needle)==1 funktioniert das Slicing nicht.

Code: Alles auswählen

def find_all(filename, needle, mode = 'rb'):
    start = 0
    with open(filename, mode) as infile:
        buf = ''
        while True:
            data = infile.read(1024)
            if not data:
                break
            start += len(buf)
            if len(needle)>1:
                buf = buf[-(len(needle)-1):]
            start -= len(buf)
            buf += data
            index = 0
            while True:
                try:
                    index = chunk.index(needle, index)
                except ValueError:
                    break
                yield start + index
                index += len(needle)

oder mit mmap

Code: Alles auswählen

import mmap

def find_all(filename, needle):
    with open(filename, 'rb') as infile:
        data = mmap(infile.fileno(), 0, access=mmap.ACCESS_READ)
        index = 0
        while True:
            index = data.find(needle, index)
            if index < 0:
                break
            yield index
            index += len(needle)

Die Indexberechnung über mehrere Chunks war vermurkst. Ist nun korrigiert:

Code: Alles auswählen

CHUNK_SIZE = 1024 * 1024

def get_chunks(f, size=CHUNK_SIZE):
    while True:
        chunk = f.read(size)
        if not chunk:
            break
        yield chunk

def find_indices(chunk, needle, index=0):
    while True:
        try:
            index = chunk.index(needle, index)
        except ValueError:
            break
        yield index
        index += len(needle)

def find_all(filename, needle, is_binary=False):
    mode = 'rb' if is_binary else 'r'
    with open(filename, mode) as infile:
        buf = ''
        index_total = 0
        for chunk in get_chunks(infile):
            for index in find_indices(buf + chunk, needle):
                yield index_total + index
            if chunk.endswith(needle) or len(needle) <= 1:
                buf = ''
            else:
                # Might be part of truncated needle
                buf = chunk[-(len(needle) - 1):]
            index_total += len(chunk) - len(buf)

@Sirius3:
Danke für deine Anmerkungen.

Ob mmap genutzt werden kann, ist hier ja nicht sicher.

Das Beachten von überlappenden Needles kommt in deinem Code aber auch nicht vor, oder übersehe ich was?
Zumal das deutlich aufwändiger und womöglich unnötig wäre.

Mein Test mit mmap auf einem Rechner mit 32GB und einer Datei mit 100GB hat gezeigt, dass das Programm nur 10GB für sich verwendet hat. Sollte so auf einen ARMv7 mit 512MB RAM übertragbar sein.

@Sirius3: Was zum Problem werden könnte ist der Adressraum, denn die Datei wird ja in den Adressraum des Prozesses abgebildet, und wenn der beispielsweise bei einem 32-Bit-System nur 2GiB gross ist, dann bekommt man da zusätzlich zu Programm und Daten keine 2GiB grosse Datei mehr abgebildet.

Der ARM im Raspi 3 ist beispielsweise ein 64-Bit-Prozessor, aber Rasbian ist trotzdem nur ein 32-Bit-System. Die haben abgewogen zwischen Geschwindigkeitsgewinn (war wohl nicht so doll) und dem verhältnismässig kleinen Speicher (1 GiB RAM), für den 32-Bit zum adressieren ausreichen, und dem zusätzlichen Speicherverbrauch von 64-Bit grossen Zeigern.

Das deutsche Python-Forum

Byte-weise XOR

Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR

Re: Byte-weise XOR