Effiziente Verkettung von Bit-Arrays Java

9

Ich schreibe gerade ein Stück Code, bei dem ich festgestellt habe, dass die Verkettung meiner zwei Bit-Arrays der Engpass ist und darüber debattiert wird, wie man es effizienter macht.

Mein Bit-Array ist wie folgt modelliert:

%Vor%

wobei die Größe die Größe in Bits ist.

Die Herausforderung bei der effizienten Verkettung von zwei Bit-Arrays besteht in der Überlappung, die auftreten muss, wenn beispielsweise ein Bit-Array der Größe 7 mit einem der Größe 6 verkettet wird. So wie, Es ist nicht möglich, einfach zwei Array-Kopien zu erstellen.

Die Lösungen, die ich derzeit untersuche, sind folgende: Berechnen Sie die "Straddle-Region" (die letzten 3 Bits eines 5-Bit-Arrays zum Beispiel). Kopiere das erste Array mit system.array.copy setze die 3 "Spreizbits" manuell aus dem zweiten Array mit meiner setBit Funktion. verschiebe das zweite Array um 3 nach links Mach ein System.arraycopy()

Gegenwärtig stelle ich jedes einzelne Bit des zweiten Arrays wie unten gezeigt manuell ein.

Das Problem ist, dass bei Bit-Shifting die Operation ziemlich teuer ist, da sie für jedes Byte ausgeführt werden muss, dann muss das Straddling erneut auftreten.

Gedanken zur Verbesserung der oben beschriebenen Techniken?

Hier ist der aktuelle Code, der schlecht funktioniert:

%Vor%     
user1018513 03.10.2013, 08:58
quelle

2 Antworten

1

Ihr Code ist sehr verworren und schwer zu lesen. Allerdings ein paar Dinge, die Zeit brauchen:

  • Verwenden des % Operators
  • Aufruf von getSize() mehrmals in der Methode - warum verwenden Sie nicht die Eigenschaft size Ihrer Bit-Arrays?

Ich denke, die Verwendung einer verketteten Liste von Bytes / Longs zur Repräsentation von BitArray würde das Verketten viel, viel schneller machen, da Sie überhaupt nichts kopieren können, nur einen Zeiger aktualisieren.

Ist concatenate eine Operation, die Sie in den Arrays durchführen werden? Wenn ja, hätte ich eine verkettete Liste von Longs verwendet, um das Bit-Array darzustellen. Wie groß sind Ihre Bit-Arrays?

    
Erik A. Brandstadmoen 03.10.2013 09:29
quelle
0

Ich denke, Sie können ein neues Array erstellen, ohne Daten zu kopieren. Etwas wie das:

%Vor%     
Mikhail 03.10.2013 10:17
quelle

Tags und Links