Schnittmenge von mehreren Mengen ermitteln

[Namenloser]

Zitat von Furtbichler:

Zitat von NamenLozer:

Die Frage ist nur, ob es sich lohnt...

Du musst das sportlich sehen.

Klar, für einen „Wettbewerb“ kann man das schon mal machen . Aber im Produktivsystem würde ich die Pascal-Variante trotzdem vorziehen.

[Panthrax]

Code:

11 Messungen:
function Intersect(var Left: TSampleArray; const Right: TSampleArray);
* mit Length(Left) = Length(Right) = N = 10000000 // 10 Mio.
* mit denselben Daten für jede Routine
* mit zufällig generierten Daten für jede Messung
* in Millisekunden

             Messung  #19, Pascal  #39, Pascal  #45, Pascal  #35, Assembler
                   1      242          224          160              64
                   2      246          221          161              62
                   3      244          224          159              63
                   4      248          221          161              67
                   5      247          246          174              64
                   6      252          221          172              61
                   7      249          222          168              62
                   8      251          227          161              60
                   9      261          231          160              61
                  10      263          236          160              62
                  11      255          221          157              61

          Mittelwert      250,727      226,727      163,000          62,455
  Standardabweichung        6,665        8,026        5,639           1,968

Anmerkungen:

• Testsystem: Intel i7, Windows 7
• Den Mittelwert und die Standardabweichung füge ich mit Excel hinzu.
• Verglichene Implementierungen:
  #19 (Pascal, Furtbichler) ist der erste Vorschlag;
  #39 (Pascal, Furtbichler) ist eine korrigierte und verbesserte Variante von #19;
  #45 (Pascal, Panthrax) ist eine verbesserte Variante von #37;
  #35 (Assembler, Amateurprofi).

[Horst_]

Hallo,

ich habe mal das Programm geändert und einfach ein Testfeld mit Zahlen gleichen Abstandes gefüllt habe ( sehr großer Abstand) und anschließend in diesem diese Feld zufällige Werte um 1 oder mehr vergrößert habe.
Dies mehrfach hintereinander.
Versuch[i]= verändertere(Versuch[i-1])

Es war mir nicht geheuer, immer nur die gleiche Datei mit sich selbst zu vergleichen, da werden keine Daten bewegt.

Hier mal die Messungen mit 16 Feldern mit 1e7 = 10 Mio Werten.
Temp ist das Ausgangs und Intersectfeld
Einmal Intersect(Temp,versuch[i]) mit i von 0..15
und einmal rückwärts
Intersect(Temp,versuch[i]) mit i von 15..0
type
tData = int64;
Als Ergbenis:

Code:

   Messung
  #19, Pascal
   9999999   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244659   4916458   4608947   4321049   4050708   3796820

   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820
   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820

Zeit in ms :     4606
  #39, Pascal
  10000000   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244659   4916458   4608947   4321049   4050708   3796820

   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820
   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820

Zeit in ms :         3829
  #45, Pascal
  10000000   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244658   4916456   4608944   4321045   4050703   3796814

   3796820   3796819   3796818   3796817   3796816   3796815   3796814   3796813
   3796812   3796811   3796810   3796809   3796808   3796807   3796806   3796805

Zeit in ms :         2971
  #35, Assembler
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000

  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000

Zeit in ms :             993

Fertig.

Version #19 verzählt an der höchsten Stelle
Version #39 funktioniert
Version #45 verkleinert scheinbar das intersect um 1 zuviel ( aber nicht immer, besonders auffällig bei rueckwaerts.
Mit tdata = longint, war es richtig )
Version #35 funktioniert überhaupt nicht ( kann eigentlich nur bei tData= 32bit funktionieren, oder? Aber vielleicht übergibt freepascal die Register anders)

Version #45 War in der ursprünglichen Verson mit tdata = longint schneller als die Assembler Version 70 / 80 ms

Gruß Horst

[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?

[Amateurprofi]

Zitat von Horst_:

Version #35 funktioniert überhaupt nicht ( kann eigentlich nur bei tData= 32bit funktionieren, oder? Aber vielleicht übergibt freepascal die Register anders)

Hallo Horst,
das ist 'ne 32 Bit - Version.
Mir war schon klar, dass in #1 über 64 Bit Daten gesprochen wurde.
Aber ich hatte ja gegen #19 geschrieben aus der leider nicht hervorging ob TSampleArray 32 oder 64 Bit ist.
Aus #28

Zitat:

Ich weiss nur, das das Einlesen einer Zahl genauso lange dauert, wie 2000 (Systempage = 8k, 4Byte=eine Zahl) Also wieso sollte ich einzelne Zahlen einlesen und wie soll das gehen? Ich will ja nicht eine Zahl finden, sondern die Schnittmenge über alle Zahlen. Also muss ich auch alle einlesen (nun ja, bis MAX(Bisherige-Schnittmenge))

hatte ich dann geschlossen, dass #19 mit 32 Bit arbeitet.
Dummerweise habe dann aber auch ich die Definition von TSampleArray nicht explizit angegeben.

[Horst_]

Hallo,

@Amateruprofi,

kann es sein, dass die Assemblerversion in http://www.delphipraxis.net/1156992-post45.html bei gleichen Feldern ein Feld zu wenig zählt.

@panthrax
Ich habe habe Deine Version #45 zu #51 mit while-Schleifen umgebaut, die zählt scheinbar richtig.
Anbei ein Testprogramm.
Bei -1 wird Testfeld gegen Testfeld getestet und die Schnittmenge sollte die gleiche Länge besitzen, was Pascal #19 und Assembler nicht tuen.
Bei 0 werden 12 Felder die jeweile eine Modifikation vom Testfeld sind miteinander "geschnitten"
Bei 1 werden 12 Felder die jeweile eine Modifikation vom VorgängerFeld sind miteinander "geschnitten"
Die Ausgabe in µsec bei meinem Rechner, aber es geht ja nur um relative Beziehung als Assembler ist ~doppelt so schnell wie Pascal #19.

Code:

Pascal #19:Pascal #39:Pascal #39p:Pascal #45:Pascal #51:Assem  #35:
-1      -1:    470313:     388363:    475693:    371294:        -1:
 0  593633:    492619:     441995:    456582:    420622:    267954:
 1  638382:    521710:     459289:    462909:    451294:    296262:
 0  594878:    493216:     445630:    456969:    425607:    240649:
 1  638515:    520117:     461448:    457467:    447657:    302612:
 0  594142:    494672:     442169:    460931:    424432:    241258:
 1  641827:    519991:     459252:        -1:    449344:    298184:
 0  594625:    492036:     441968:        -1:    421176:    241215:
 1  640879:    519695:     459175:    462514:    452662:    296423:
 0  596518:    492056:     445751:    456175:    426792:    238062:
 1  636715:    519495:     458919:        -1:    452807:    301079:
 0  597456:    494035:     442330:    456586:    420898:    236698:
 1  643358:    520896:     462224:    458345:    449333:    294667:
Fertig.

Gruß Horst

[Amateurprofi]

Zitat von Horst_:

Hallo,

@Amateruprofi,

kann es sein, dass die Assemblerversion in http://www.delphipraxis.net/1156992-post45.html bei gleichen Feldern ein Feld zu wenig zählt.

Gruß Horst

Eigentlich kann das gar nicht angehen….
Aber vom Brand von Hamburg hatten auch alle gedacht, er könne nicht angehen.
Und dann ist er doch angegangen – und wie!
Das war am 5. Mai 1842, und die haben damals ziemlich dumm geguckt.

So wie ich eben!

Die Funktion ist für Arrays ausgelegt, die keine Zahlen mehrfach enthalten und aufsteigend sortiert sind. Eine weitere Einschränkung ist, dass die als Intersect bezeichnete Menge nicht mehr Elemente enthält, als die als Data bezeichnete.

Wenn wir 2 Arrays haben mit den Zahlen
1 4 4 4 4 7 und
4 4 4
Wie sollte dann die Schnittmenge aussehen?
4 4 4 (weil das die ursprüngliche Anzahl der 4en in der kleineren Menge ist)
oder
4 4 4 4 (weil ja auch die vierte 4 der größeren Menge in der kleineren gefunden wird)
oder
4 4 4 4 4 4 4 4 4 4 4 4 (weil jede 4 der kleineren Menge 4 Mal in der größeren Menge gefunden wird)
oder
4 (weil in Mengen keine Elemente doppelt vorkommen sollten)

Wenn ich in Delphi mit Mengen arbeite, dann kenne ich das so, dass Elemente in Mengen vorkommen oder auch nicht. Es kann aber nicht ein Element mehrfach vorkommen.
Also tendiere ich zur letztgenannten Lösung.

Vielleicht sollte mal jemand ein paar Testdaten (mit nicht mehr als 10 Zahlen in einem Array) zusammenstellen und es sollte auch festgesetzt werden, ob Elemente mehrfach vorkommen dürfen, und wie dann zu verfahren ist.
Und wenn dann mehrere Routinen korrekte Ergebnisse liefern kann man mit großen Mengen die Performance testen.
So wie es jetzt ist, macht das einfach keinen Sinn.

[Laser]

Moin,

Zitat von Amateurprofi:

Wenn wir 2 Arrays haben mit den Zahlen
1 4 4 4 4 7 und
4 4 4
Wie sollte dann die Schnittmenge aussehen?
4 4 4 (weil das die ursprüngliche Anzahl der 4en in der kleineren Menge ist)
oder
4 4 4 4 (weil ja auch die vierte 4 der größeren Menge in der kleineren gefunden wird)
oder
4 4 4 4 4 4 4 4 4 4 4 4 (weil jede 4 der kleineren Menge 4 Mal in der größeren Menge gefunden wird)
oder
4 (weil in Mengen keine Elemente doppelt vorkommen sollten)

Wenn ich in Delphi mit Mengen arbeite, dann kenne ich das so, dass Elemente in Mengen vorkommen oder auch nicht. Es kann aber nicht ein Element mehrfach vorkommen.
Also tendiere ich zur letztgenannten Lösung.

Vielleicht sollte mal jemand ein paar Testdaten (mit nicht mehr als 10 Zahlen in einem Array) zusammenstellen und es sollte auch festgesetzt werden, ob Elemente mehrfach vorkommen dürfen, und wie dann zu verfahren ist.
Und wenn dann mehrere Routinen korrekte Ergebnisse liefern kann man mit großen Mengen die Performance testen.
So wie es jetzt ist, macht das einfach keinen Sinn.

innerhalb der jeweiligen Menge kommen einzelne Elemente 0 bis 1 mal vor aber nicht mehrfach.

Für das Verständnis sollten diese Testdaten reichen:

Code:

Testdaten:
N1: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
N2: 02 06 08 12 14 16 18 20 22 24 26 28 30 32
N3: 03 06 09 15 18 24

Schnittmenge:
N0: 06 18

Der Festplattenzugriff ist für die Performance entscheidend. Daher habe ich mich noch nicht ganz vom "Rumgehüpfe" verabschiedet. Der Ansatz ist jetzt:

Code:

UntereSchwelle = größtes erstes Element aus Datei N1.. N3 = 03
ObereSchwelle = kleinstes letztes Element aus Datei N1..N3 = 20
vorzeitig beenden, falls  sich leere Schnittmenge ergibt
jeweils Anzahl Elemente in N1..N3 feststellen
Mit kleinster Datei starten für alle Dateien
  kleine Dateien komplett lesen (Grenze z.B. 4 KB)
  große Dateien nach UntererSchwelle und ObereSchwelle binär durchsuchen
  große Datei von UntererSchwelle bis ObereSchwelle komplett lesen
  Schnittmenge von 2 Dateien erzeugen
  vorzeitig beenden, falls  sich leere Schnittmenge ergibt

Angesichts der goßen Datenmengen, die von der Platte (nicht aus dem Puffer) gelesen werden müssen, wird dieser mit wenig Aufwand eingegrenzt und dann nur noch ein Teil der Daten von HDD gelesen.

Unter Linux kann man den Festplattenpuffer so löschen:

Code:

echo 3 | sudo tee /proc/sys/vm/drop_caches

Quelle: http://www.linuxatemyram.com/play.html

Weiß jemand, wie das unter Windows XP und 7 geht? Notfalls muss man rebooten.