Schnittmenge von mehreren Mengen ermitteln

[Amateurprofi]

Zitat von Horst_:

Hallo,

Was soll ich sagen, aber es zählt immer noch einen zuwenig, wenn gleiche Felder vorliegen .

Gruß Horst

Hallo Horst,
sorry, aber bei mir passiert das nicht.
Zumindest dann nicht, wenn ich tData=integer deklariere.
Wenn ich, wie du es gemacht hast tData=cardinal deklariere, dann wird nicht compiliert, anstatt kommt in der Prozedur FillArray bei der Zeile
d := delta * MAXDATCOUNT; eine Fehlermeldung :
[DCC Fehler] Intersect_Main.pas(318): E2099 Überlauf bei Konvertierung oder arithmetischer Operation
Die OH sagt hierzu:
Der Compiler hat in einem arithmetischen Ausdruck einen Überlauf entdeckt. Das Ergebnis des Ausdrucks kann wegen seiner Größe nicht in 32 Bits dargestellt werden. Überprüfen Sie die durchgeführten Berechnungen, und stellen Sie sicher, dass die Ergebnisse von der Hardware des Computers dargestellt werden können.

Und wenn ich mit der Maus auf die Konstante "delta" zeige dann kommt der Hinweis
delta = null - Erroneous Type

Wenn ich aber nun die Konstante delta explizit als cardinal deklariere, also
delta:cardinal= High(TData) div maxdatcount-1; dann wird compiliert und die Asm-Funktion liefert korrekte Ergebnisse.

Ich vermute, dass es daran liegt….

Delphi-Quellcode:

type
   TData=cardinal;

const
   maxdatcount=5000000;
//   delta=High(TData) div maxdatcount-1; // so wird nicht compiliert
     delta:cardinal=High(TData) div maxdatcount-1; // so funktioniert es

procedure FillArray(var A:TSampleArray);
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 TMain.Button1Click(Sender: TObject);
var intersect,data:TSampleArray; 
begin
   SetLength(data,maxdatcount);
   FillArray(data);
   intersect:=copy(data);
   SetLength(intersect,GetIntersect_5(intersect,data,Length(intersect)));
   meRes.Lines.Add(inttostr(Length(intersect)));
end;

[Horst_]

Hallo,

Ach Herr je,
da will man clever sein und fällt wieder auf die Nase
Weil bei mir PrepareSamples wegen random in freepascal so ewig dauerte, kam ich auf die Idee, für eine neue Runde Left aus Right zu kopieren und anschliessend nur PrepareSamples(Right) aufzurufen.
Dämlicherweise habe ich dies nicht ans Ende der repetitions-Schleife getan sondern noch in der Schleife für die Varianten.
Deshalb hatten die Nicht-Ersten Varianten immer gleiche Felder zu untersuchen, was rasend schnell ist.
Dies habe ich nun geändert.

@Amateurprofi:
Ich benutze seit der letzten Version für die Belegung der Testfelder die Version von Panthrax.
Ich weiß nicht, ob freepascal statt length, high abspeichert und deshalb das Programm das letzte Element des array nicht mehr testet

Delphi-Quellcode:

asm

...
mov edi,[eax] // @Intersect[0]
              // Zeiger in Intersect und Data hinter jeweils letzten Eintrag
              // stellen und Indizes auf jeweils ersten Eintrag ausrichten
lea edi,[edi+ecx*8] // @Intersect[Len] // Offset berechnen damit
neg ecx             // [edi+ecx*8] = Intersect[0]

..
mov esi,[edx] // @Data[0]
..
mov ebx,[esi-4] // Length(Data) oder High(Data)?
...
add ecx,1 // Nächster Intersect-Index
je @SetRes // Fertig
end;

Deshalb hab ich die Vorbelegung derart geändert, das im letzten Element im High(TData) steht.

Delphi-Quellcode:

procedure PrepareSamples(out Value: TSampleArray; const N: NativeInt = 10000000; const S: NativeInt = 5);
var
  I: NativeInt;
begin
  SetLength(Value, N);
  Value[0] := Random(S);
  for I := 1 to N - 2 do
    Value[I] := Value[I - 1] + Random(S) + 1;
  Value[N-1] := High(TData);
end;

Dann habe ich die Ausgabe wie im Kommentar von Panthrax gemacht, also die Ausgabe von Länge der Schnittmenge und Laufzeit,aber mit Komma getrennt ( csv )
Mit Freepascal ergibt sich:

Code:

  #39, Pascal  10000000
  #51, Pascal  10000000
  #61, Pascal  10000000
  #59, Assem    9999999

   Messung  #39, Pascal  #51, Pascal  #61, Pascal  #59, Assem
         1,3332223,125 ,3332223,116 ,3332223,111  ,3332222,76
         2,3333764,129 ,3333764,121 ,3333764,118  ,3333763,70
         3,3338301,123 ,3338301,117 ,3338301,112  ,3338300,69
         4,3334825,123 ,3334825,115 ,3334825,111  ,3334824,68
         5,3330696,123 ,3330696,115 ,3330696,112  ,3330695,68
         6,3333988,124 ,3333988,119 ,3333988,111  ,3333987,71
         7,3333174,123 ,3333174,117 ,3333174,111  ,3333173,76
         8,3333983,123 ,3333983,118 ,3333983,111  ,3333982,68
         9,3335054,125 ,3335054,117 ,3335054,112  ,3335053,74
        10,3333229,123 ,3333229,117 ,3333229,111  ,3333228,71
        11,3332975,123 ,3332975,115 ,3332975,111  ,3332974,70
Fertig.

Hier hat die Assembler Version immer ein Element zu wenig.

Gruß Horst

EDIT:
Der Test mit Freepascal ergab:

Delphi-Quellcode:

  L := @Left[0];
  R := @Right[0];
  DEC(R); writeln(R^);INC(R);
  DEC(L); writeln(L^);INC(L);
...
Ausgabe
9999999
9999999

Also speichert freepascal High(DynArray) statt Length(DynArray)

Böse Falle das!

[Panthrax]

{$DEFINE INT64DATA}
{$DEFINE LAPTOP}

Code:

 #39, Pascal  10000000
 #51, Pascal  10000000
 #61, Pascal  10000000
 #59, Assem   10000000

  Messung  #39, Pascal  #51, Pascal  #61, Pascal  #59, Assem
        1,3333535,239 ,3333535,238 ,3333535,217 ,3333535,138
        2,3332769,223 ,3332769,223 ,3332769,210 ,3332769,129
        3,3332354,223 ,3332354,218 ,3332354,202 ,3332354,124
        4,3335244,219 ,3335244,221 ,3335244,200 ,3335244,129
        5,3330107,222 ,3330107,220 ,3330107,204 ,3330107,128
        6,3333308,219 ,3333308,222 ,3333308,208 ,3333308,128
        7,3330565,226 ,3330565,220 ,3330565,202 ,3330565,128
        8,3331374,252 ,3331374,245 ,3331374,206 ,3331374,129
        9,3332415,220 ,3332415,221 ,3332415,206 ,3332415,141
       10,3333225,223 ,3333225,216 ,3333225,219 ,3333225,128
       11,3333172,221 ,3333172,221 ,3333172,217 ,3333172,127
Mittelwert
          226,091      224,091      208,273      129,909
Standardabweichung
           10,232        8,949        6,680        4,989

//{$DEFINE INT64DATA}
{$DEFINE LAPTOP}

Code:

 #39, Pascal  10000000
 #51, Pascal  10000000
 #61, Pascal  10000000
 #59, Assem   10000000

  Messung  #39, Pascal  #51, Pascal  #61, Pascal  #59, Assem
         1,3333535,206 ,3333535,193 ,3333535,176 ,3333535,116
         2,3332769,188 ,3332769,179 ,3332769,166 ,3332769,104
         3,3332354,194 ,3332354,181 ,3332354,165 ,3332354,108
         4,3335244,219 ,3335244,194 ,3335244,183 ,3335244,120
         5,3330107,201 ,3330107,181 ,3330107,166 ,3330107,100
         6,3333308,198 ,3333308,189 ,3333308,171 ,3333308,102
         7,3330565,195 ,3330565,179 ,3330565,165 ,3330565,106
         8,3331374,195 ,3331374,177 ,3331374,166 ,3331374,104
         9,3332415,199 ,3332415,180 ,3332415,163 ,3332415,105
        10,3333225,207 ,3333225,182 ,3333225,167 ,3333225,107
        11,3333172,220 ,3333172,179 ,3333172,163 ,3333172,102
Mittelwert
           202,000      183,091      168,273      106,727
Standardabweichung
            10,188        5,991        6,150        6,101

[Horst_]

Hallo,

dann liegt es wohl an Freepascal und deren Speicherung dynamischer Felder.
Was mich wundert, dass Panthrax mit Win64 das kompiliert bekommt.
Freepascal 2.7.1. für Linux64 meckert über jede Zeile.
Die Pascalversionen sind dann aber für Int64 (etwas mehr) und Int32 ( ein wenig) schneller, weil dann viel mehr Register benutzt werden können, aber kein Vergelich zu den Assemblerversionen.

Gruß Horst