Rechnen mit Sparse Vectoren

[abrosda]

Ich habe eine Klasse zum arbeiten mit Sparse Vectoren geschrieben.
Gespeichert wird ein Vector, bei dem jedem Index ein Double zugeordnet ist.

Die Null-Werte werden nicht gespeichert....
Es gibt ein Bitarray in dem durch eine 1 angezeigt wird, daß ein Wert vorhanden ist, eine 0 zeigt an das kein Wert, also eine 0 vorhanden ist.

Delphi-Quellcode:

  TSparseVector = class
  private
    // Actual Capacity of the BitMatrix:
    fBitCapacity: Integer;
    // An Array holding the bits for the sparse Vector
    fBitMatrix: PBitArray;
    // Maximum Count
    fCount: Integer;
    // The Values (not containing Zero's)
    fValues: PDoubleArray;
    fValuesCapacity: Integer;

Ich suche nach einer performanten Methode zwei Vectoren zu addieren. Bis jetzt sieht die Methode so aus:

Delphi-Quellcode:

procedure TSparseVector.AddVector(const aSparseVector: TSparseVector);
var
  a_Item: Double;
  a_LowestIndex: Integer;
  a_Index: Integer;
  a_OwnIndex: Integer;
  a_NewCount: integer;
  a_MaxNonZero: Integer;
  i: Integer;
  a_DoubleArray: PDoubleArray;
  a_SparseVector: TSparseVector;
begin
  // Als erstes feststellen, ob der eigene Vektor leer ist, wenn ja wird einfach eine Speicher-kopie des anderen Vektors gemacht
  if IsNullVector then
  begin
    if not (aSparseVector.IsNullVector) then
      InnerCopyWholeVector(aSparseVector)
  end
  else
    if not (aSparseVector.IsNullVector) then
    begin
      Assert(Count = aSparseVector.Count);
      GetMem(a_DoubleArray, fCount * 8);
        //:= getDenseVector; // own Vector as Dense Vector
      a_SparseVector := GetImplementingObject(aSparseVector) as TSparseVector;
      //    a_LowestIndex := a_SparseVector.getLowestIndex;
      a_Index := 0;
      a_OwnIndex := 0;
      a_NewCount := 0;
      a_MaxNonZero := 0;
      for i := 0 to fCount - 1 do
      begin
        if GetBitValue(i) then
        begin
          a_Item := fValues^[a_OwnIndex];
          inc(a_OwnIndex);
          if a_SparseVector.GetBitValue(i) then
          begin
            a_DoubleArray^[i] := a_Item + a_SparseVector.fValues^[a_Index];
            inc(a_Index);
            inc(a_NewCount);
            a_MaxNonZero := i;
          end
          else
          begin
            a_DoubleArray^[i] := a_Item;
            inc(a_NewCount);
            a_MaxNonZero := i;
          end;
        end
        else // First Vector not set:
        begin
          if a_SparseVector.GetBitValue(i) then
          begin
            a_DoubleArray^[i] := a_SparseVector.fValues^[a_Index];
            inc(a_Index);
            inc(a_NewCount);
            a_MaxNonZero := i;
          end
          else
            a_DoubleArray^[i] := 0;
        end;
      end; // for
      System.ReallocMem(fValues, a_NewCount * 8);
      fValuesCapacity := a_NewCount;

      SetCapacityBitMatrix((fCount and $FFFFFFC0) + 64);
      FillChar(fBitMatrix^, fBitCapacity div 8, 0);

      try
        a_LowestIndex := GetLowestNonZeroIndexForDoubleArray(a_DoubleArray);
        a_Index := 0;
        for i := a_LowestIndex to a_MaxNonZero do
        begin
          if a_DoubleArray^[i] <> 0 then
          begin
            fValues^[a_Index] := a_DoubleArray^[i];
            inc(a_Index);
            SetBit(i);
          end;
        end; // for
        fValuesCount := a_Index;
      finally
        FreeMem(a_DoubleArray);
      end;
    end;
end;

Eine Idee war, den Vektor auf den addiert werden soll in einen "Dense" Vektor zu verwandeln, also einen kompletten Vektor inklusive der Nullen zu haben. Das war mir jedoch zu langsam.

Die jetztige Lösung ist immer noch 'suboptimal', ich versuche mal die Idee zu beschreiben:

Delphi-Quellcode:

     for i := 0 to fCount - 1 do
      begin
// Wenn ein Wert gesetzt ist
        if GetBitValue(i) then
        begin
          a_Item := fValues^[a_OwnIndex];
          inc(a_OwnIndex);
// Schaue nach ob anderer Wert gesetzt ist
          if a_SparseVector.GetBitValue(i) then
          begin
// Addiere beide Werte und speicher im DoubleArray
            a_DoubleArray^[i] := a_Item + a_SparseVector.fValues^[a_Index];
            inc(a_Index);
            inc(a_NewCount);
            a_MaxNonZero := i;
          end
          else
          begin
// ansonsten: nimm ursprünglichen Wert
            a_DoubleArray^[i] := a_Item;
            inc(a_NewCount);
            a_MaxNonZero := i;
          end;
        end
        else // First Vector not set:
        begin
/7 Erster Wert nicht gesetzt, also evtl zweiten Wert nehmen
          if a_SparseVector.GetBitValue(i) then
          begin
            a_DoubleArray^[i] := a_SparseVector.fValues^[a_Index];
            inc(a_Index);
            inc(a_NewCount);
            a_MaxNonZero := i;
          end
          else
// kein Wert gesetzt - Neuer Wert ist 0
            a_DoubleArray^[i] := 0;
        end;

Nach der For Schleife wird ein neuer Sparsevector aus dem DoubleArray gebaut, der neue Vektor enthält anschließend keine Nullen mehr.


Ich hatte ursprünglich überlegt, die Bitmatrixen driekt zu verknüpfen und anschließend die Double's zu addieren, mir erschien das nur zu kompliziert.