Schnittmenge von mehreren Mengen ermitteln

[Panthrax]

Mein Algorithmus hatte einen Fehler. Er hatte einige Treffer überprungen, daher die kleinere Schnittmenge. Hier die Korrektur:

Delphi-Quellcode:

procedure Intersect47(var Left: TSampleArray; const Right: TSampleArray);
type
{$PointerMath On}
  PInt64 = ^Int64;
{$PointerMath Off}
var
  L, R, LeftEnd, RightEnd: PInt64;
  N: NativeInt;
begin
  N := 0;
  L := @Left[0];
  R := @Right[0];
  LeftEnd := @Left[Length(Left)];
  RightEnd := @Right[Length(Right)];

  if (L < LeftEnd) and (R < RightEnd) then
    repeat
      if L^ = R^ then
      begin
        Left[N] := L^;
        Inc(N);
      end;

      repeat
        Inc(L);
      until (L^ >= R^) or (L >= LeftEnd);

      if L >= LeftEnd then
        Break;
{+}
{+}   if L^ = R^ then
{+}   begin
{+}     Left[N] := L^;
{+}     Inc(N);
{+}   end;

      repeat
        Inc(R);
      until (L^ <= R^) or (R >= RightEnd);

      if R >= RightEnd then
        Break;
    until False;

  SetLength(Left, N);
end;

Code:

             Messung  #19, Pascal  #39, Pascal  #47, Pascal  #35, Assembler
                   1      251          236          200              66
                   2      267          227          199              63
                   3      277          227          200              64
                   4      268          228          199              64
                   5      257          226          198              66
                   6      264          222          199              65
                   7      253          227          200              64
                   8      253          247          202              63
                   9      253          222          197              66
                  10      250          232          197              63
                  11      247          230          200              65

          Mittelwert      258,182      229,455      199,182          64,455
  Standardabweichung        9,421        7,076        1,471           1,214

Die Zeit-Messwerte aus dem Testprogramm von Horst kann ich nicht zuverlässig ermitteln, wegen der Prozessortaktanpassung bei Hitzeentwicklung. Die Ergebnisse von #39 und #47 zeigen dort jetzt aber die gleiche Schnittmengengröße in der "Vorwärtsrichtung". In der "Rückwärtsrichtung" und für #47 stimmt die Schnittmengengröße beim ersten Mal, dann verkleinert sich die Schnittmengengröße um 1. Ich habe bei meinem ersten Blick nicht verstanden wie die Testdaten erzeugt werden und wie genau getestet wird, und was das für einen Einfluss das auf das "Vorwärts" und "Rückwärts" hat. Vielleicht habe ich auch immer noch Fehler in meinem Algorithmus?

[Horst_]

Hallo,

ich hatte bei #45 übersehen, dass setlength garnicht genutzt wird, dann stimmt die assembler Version für 32 Bit Datentypen.

Delphi-Quellcode:

procedure _Intersect35ASM(var Left: TSampleArray; const Right: TSampleArray);
var
  R: TSampleArray;
begin
  R := Right;
  setlength(Left,Intersect35ASM(Left, R, Length(Left)));
end;

Meine Funktionen, um ein Testfeld zu erzeugen und anschliessend immer mehr zu verfremden.

Delphi-Quellcode:

type
  tData = longint;
  TSampleArray = Array of tData;
  tVersuch = array[0..15] of TSampleArray;
const 
//  MAXDATCOUNT = 1000;
  MAXDATCOUNT = 10*1000*1000;
  delta  = High(tData) div MAXDATCOUNT-1; 

procedure FillArray(var A:TSampleArray);  
//Fuellt A mit Werten von 0 bis MAXDATCOUNT*Delta
// im Abstand delta also, 0,delta,2*delta,3*delta...
var
  i : integer;
  d : tData;
begin 
  i := High(A);
  d := delta * MAXDATCOUNT;
  For i := i downto 0 do
    begin
    d := d-delta;    
    A[i] := d;
    end;
end;

procedure RandomiseArray(out   A:TSampleArray;
                         const B:TSampleArray;
                         Step   :tData;// mittlerer Abstand
                         diff   :tData);// Aenderungswert  
// Veränderte zufällige Werte im durchschnittlichen Abstand Step
var
  cnt: longInt;
  i : longint;
begin 
  A := copy(B);
  i := High(A);
  cnt := 0;
  repeat
    inc(cnt);
    inc(A[i],diff);
    dec(i,random(2*Step-1)+1);
  until (i< 0);
end;
..Im Hauptprogramm
...
  setlength(TestFeld,MAXDATCOUNT);
  FillArray(TestFeld);
  Versuch[low(tVersuch)] := copy(TestFeld);
  //Zufaellige Werte verändern
  For i := low(tVersuch)+1 to High(tVersuch) do
    RandomiseArray(Versuch[i],Versuch[i-1],16,i);

[Panthrax]

Die Testdatenerstellung finde ich etwas umständlich. Das ist aber unwichtig, solange die erzeugten Daten gültig sind: Array[I] < Array[J] mit I < J und I, J: Low(Array)..High(Array). Als Mensch erschwert es mir aber die Testdaten bewerten zu können.

Ja, ich hatte für die Assemblerroutine einen separaten Aufruf geschrieben, weil der Typ von den anderen Routinen abwich.

So auf die Schnelle werde ich den Fehler bei mir wohl nicht finden... Vielleicht hat Furtbichler ja noch eine Idee?