Den nächsten verwendeten Index vor einem angegebenen Index in einem Array finden (Fast)

Question

Diese Frage bezieht sich auf Array of pairs of 3 bit elements
Dieses Array hat 52 Paare (etwa 40 Bytes), und ich möchte das erste Paar vor dem angegebenen finden Es hat andere Werte als 0 (benutztes Paar). Die offensichtliche Lösung wäre, jedes Paar < als dieses zu überprüfen (Scan von rechts nach links), aber das scheint sehr ineffizient zu sein, wenn es viele unbenutzte Paare gibt (auf 0 gesetzt).

Dieses Bild kann die Situation besser erklären:

Paare 0, 1 und 51 verwendet werden.
Ich möchte das erste verwendete Paar vor 51 finden (das ist 1 hier).

habe ich versucht, Tricks wie

if(*((int *)&array[arrayPos]) == 0) { 
    arrayPos -= sizeof(int); 
    pairPos -= ??? 
} 

Das Problem hierbei ist, dass von pairPos Subtrahieren nicht so einfach ist, weil die 6 Bits/Paare, so dass ich endete mit einer Lookup-Tabelle basierend auf einige Beziehungen zwischen pairPos und arrayPos, und all dies machte die Lösung wie die triviale durchführen.

Gibt es eine Möglichkeit, diese Suche schneller zu machen? Ein weiteres Problem ist, dass es nur 1 unbenutztes Byte gibt ... vielleicht kann ich Platz für weitere 4 schaffen. Wenn es mindestens 7 gäbe, könnte ich eine Bitmap des Arrays verwenden und es wäre viel schneller unbenutzte Paare zu überspringen.

Answer 1

Die beste Lösung, die ich gefunden war:
1. Die Artikel 1 Byte (nicht mehr als 6 Bits als zuvor) machen - dank Skizz
2. Verwenden Sie ein Bitmap, um zu sehen, welches Element der nächste auf der linken Seite. Das war viel schneller als mit der von djna beschriebenen Technik.

Die Verbesserungen in der Geschwindigkeit sind beeindruckend:
in einem Testfall, von 13s ist es jetzt 6,5 s
in einer anderen, von 7.4s bis 3.6s
Die Leistung hat sich verdoppelt: D

Nochmals vielen Dank für deine Antworten!

Answer 2

Es gibt prozessorspezifische Anweisungen zum Suchen von Bit-Arrays. Diese können als intrinsische Funktionen des Compilers bereitgestellt werden. Viele Linux-Dateisysteme verwenden diese ausführlich.

__builtin_ffs() ist eine in GCC.

ffsll() kann POSIX sein, obwohl ich bis jetzt noch nichts davon gehört habe.

Answer 3

Können Sie etwas über die angrenzenden Bytewerte sagen, die ein leeres Paar darstellen?

Ich möchte vorschlagen, die Bytes anstelle der Bits zu betrachten.

Jedes gegebene Byte, wenn es der linksseitige Beitrag eines Paares leerer 6-Bit-Zeichen sein soll, muss zu einer bestimmten Bitmaske passen, deren Wert von seiner Position abhängt. ?? ?? 00 00 oder ?? 00 00 00 oder was auch immer. Sie können jedes Byte der Reihe nach für seine Kandidatur als das linke Byte betrachten. Eine einfache Nachschlagetabelle, welche Maske zu verwenden ist, ist möglich.

Daher müssen wir nicht wirklich die 6bit Zeichen herausziehen, bevor wir sie betrachten.

Können wir es besser machen, nachdem wir ein Byte als Kandidat verworfen haben, können wir jetzt den einen nach links überspringen?

In dem Fall, in dem unsere Maske 00 00 00 00 war, wenn das fehlschlägt, dann unser Nachbar links, ja, wenn das erste Bit gesetzt ist.

Macht das wirklich die Dinge schneller?

Answer 4

Verarbeiten Sie die 6-Bit-Werte in Gruppen.

Sie könnten Gruppen von 5 Werten in einem 32-Bit-Wort verwenden, das 2 Bits oder etwa 7% Speicherplatz verschwendet.Wenn alle Werte in einem Wort 0 sind, dann ist das Wort Null, daher ist es schnell, ein nichtleeres Wort zu finden und dann die 5 Werte im Wort zu prüfen.

Wenn Sie nicht mit wenig verschwendeten Speicherplatz leben können, verwenden Sie Gruppen von 96 Bits, wobei 96 das kleinste gemeinsame Vielfache von 6 und 32 ist. pack 16 Werte von 6 Bits in drei 32-Bit-Wörter.