Bitmuster in Speicherbereich suchen

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Bitmuster in Speicherbereich suchen

Beitrag von Dirty Oerti » Sa Okt 24, 2009 10:31 am

Tag zusammen :)

So, ich wollte euch mal vor eine Aufgabe stellen:
Ich muss eine bestimmte Bitfolge (bzw eine Folge von Bits, die alle den Wert 0 besitzen) in einem relativ großem Speicherbereich suchen.
Ich hab also sozusagen:

Code: Alles auswählen

int speicher[SIZE];
int *zeiger = speicher;
Nun möchte ich darin möglichst effizient (Das ist hierbei das wichtige) z.B. die Bitfolge 0000 suchen.
Wie mach ich das?
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Bitmuster in Speicherbereich suchen

Beitrag von Xin » Sa Okt 24, 2009 11:59 am

Dirty Oerti hat geschrieben:Nun möchte ich darin möglichst effizient (Das ist hierbei das wichtige) z.B. die Bitfolge 0000 suchen.
Wie mach ich das?
Pro Byte gibt es nur eine bestimmte Anzahl Muster, die Du prüfen musst:
- 10000000 post 1
- 11000000 post 2
- 11100000 post 3
- 11110000 match
- 01111000 match
- 00111100 match
- 00011110 match
- 00001111 match
- 00000111 pre 1
- 00000011 pre 2
- 00000001 pre 3

Die Einser erfordern Übereinstimmung, die 0er sind Dir egal. Also kannst Du & verwenden. Du musst hast also 5 Muster, die sofort einen Treffer signalisieren, Du hast 3 Muster, die ein Prefix darstellen, denen im nachfolgenden Byte ein Postfix folgen muss, damit es ein match ist. Hast Du zuvor kein Prefix gefunden, brauchst Du auf Postfixe schonmal nicht mehr zu achten. Hast Du prefix 3 gefunden, brauchst Du postfix 1 und 2 auch nicht mehr zu prüfen.
Heißt pro Byte maximal 11 Vergleiche, im Regelfall 8. Programmierst Du die 11 Möglichkeiten aus, so dass Du eine Statusmaschine erhälst, sollte das sehr schnell sein. If-Abfragen kosten hier richtig Zeit.

Möglichkeit 2:
Du nimmst ein Short, machst ein & auf 0xF000 und guckst, um es Dein Suchmuster ergibt. Du hast maximal 16 Möglichkeiten, also machst Du ein Array, wo Du den Ergebniswert von & als Index verwendest, der Dir sagt, ob Du 1, 2, 3 oder sogar vier Bits verschieben kannst. Nachdem Du acht Bit verschoben hast, lädst Du das nächste Byte ins Deine Short-Testvariable rein. Auch hier gilt - ifs vermeiden, so programmieren, dass hier einfach durchgerannt werden kann.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Bitmuster in Speicherbereich suchen

Beitrag von Dirty Oerti » So Okt 25, 2009 9:11 am

Hm...ich hab vergessen das wichtigste zu schreiben, glaube ich:

Diese Bitfolge darf (und wird) sich auch über Bytegrenzen ersrtecken.
Sprich so in etwa (Suche nach 0000) :

10110100|00100011|11111100|01000010|00011111

Und das natürlich über diesen kompletten Speicherbereich.
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Bitmuster in Speicherbereich suchen

Beitrag von Xin » So Okt 25, 2009 9:52 am

Dirty Oerti hat geschrieben:Diese Bitfolge darf (und wird) sich auch über Bytegrenzen ersrtecken.
Beide Möglichkeiten berücksichtigen das!?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Bitmuster in Speicherbereich suchen

Beitrag von Dirty Oerti » So Okt 25, 2009 11:44 pm

Ähm..ja, natürlich^^

Ok, jetzt bei genauerer Betrachtung habe ich verstanden, was du mit Möglichkeit eins bezwecken möchtest.
Möglichkeit 2 verstehe ich irgendwie nicht so ganz...kannst du das an einem Beispiel zeigen?

Hm..bei Möglichkeit 1 könnte ich nur das Problem haben, dass ich ja variable Bitmuster (manchmal 00, dann wieder 000000000) suchen muss...
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Bitmuster in Speicherbereich suchen

Beitrag von Xin » Mo Okt 26, 2009 9:29 am

Dirty Oerti hat geschrieben:Ähm..ja, natürlich^^

Ok, jetzt bei genauerer Betrachtung habe ich verstanden, was du mit Möglichkeit eins bezwecken möchtest.
Möglichkeit 2 verstehe ich irgendwie nicht so ganz...kannst du das an einem Beispiel zeigen?
Du nimmst ein Short. Da sind 0 Bits drin, solange weniger Bits als für Deinen Test notwendig sind, lädst Du nach.
repeat...
- Bytenachladen. 8 Bits sind belegt: reicht für einen Test
- Dein Bitmuster hat vier Bit, also prüfst Du Dein (Short >> 12) == Dein Bitmuster. Wenn ja => Treffer
- Wenn nein, dann ist (Short >> 12) eine Zahl zwischen 1 und 15. In einem Array verzeichnest Du, wie weit Du Dein Short nach links bewegen musst. Bei 1000???? läuft der nächste Test, 1 Bit weiter nach links. bei 1001???? kannst Du das Bitmuster um ganze 4 Bit verschieben.
until fertig.
Dirty Oerti hat geschrieben:Hm..bei Möglichkeit 1 könnte ich nur das Problem haben, dass ich ja variable Bitmuster (manchmal 00, dann wieder 000000000) suchen muss...
Könntest Du. Wenn Du allerdings mitten im Spiel die Spielregeln änderst, bekommst Du immer Probleme. :->
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten