AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign FreePascal Schnittmenge von mehreren Mengen ermitteln

Schnittmenge von mehreren Mengen ermitteln

Offene Frage von "Horst_"
Ein Thema von Laser · begonnen am 11. Mär 2012 · letzter Beitrag vom 21. Mär 2012
Antwort Antwort
Seite 5 von 7   « Erste     345 67   
Furtbichler
(Gast)

n/a Beiträge
 
#41

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 15. Mär 2012, 18:55
Hi Panthrax, hättest Du ein Problem damit, deine Testroutine hier zur Verfügung zu stellen?
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#42

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 15. Mär 2012, 20:56
Also das in ASM umzusetzen halte ich nicht für sinnvoll. Da geht nur die Wartbarkeit flöten, und die Performance wird sich dadurch kein bisschen okay, kaum verbessern, da die Festplatte der Flaschenhals ist, nicht die CPU.
Hallo NamenLozer,
ich sehe das ganz anders.
Auch wenn mein Flug nach Neuseeland 36 Stunden dauert, laufe ich nicht zu Fuß zum Flughafen sondern versuche eine schnellere Lösung zu finden. Zudem ging es hier um den speziellen Fall, daß sich die Daten bereits im RAM befinden. Den Flaschenhals Festplatte gab es hier also nicht.
Ja, im Test gab es den nicht, da man sonst die Algorithmen unmöglich vergleichen könnte. In der Praxis wird es den Flaschenhals Festplatte aber dennoch geben. Ich will deinen Code auf keinen Fall schlechtreden, der eigentliche Vergleiche-Teil ist schon erheblich schneller . Die Frage ist nur, ob es sich lohnt, hier 200ms zu sparen, wenn das Laden an sich schon mehrere Sekunden dauert.
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#43

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 15. Mär 2012, 22:01
Die Frage ist nur, ob es sich lohnt...
Du musst das sportlich sehen.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#44

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 15. Mär 2012, 22:22
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.
  Mit Zitat antworten Zitat
Panthrax

Registriert seit: 18. Feb 2005
286 Beiträge
 
Delphi 2010 Enterprise
 
#45

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 16. Mär 2012, 21:50
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:
Angehängte Dateien
Dateityp: pas Thema167053.dpr.pas (5,8 KB, 10x aufgerufen)
"Es gibt keine schlimmere Lüge als die Wahrheit, die von denen, die sie hören, missverstanden wird."
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#46

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 17. Mär 2012, 05:53
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
Angehängte Dateien
Dateityp: pas Thema167053_2.dpr.pas (9,8 KB, 5x aufgerufen)
  Mit Zitat antworten Zitat
Panthrax

Registriert seit: 18. Feb 2005
286 Beiträge
 
Delphi 2010 Enterprise
 
#47

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 17. Mär 2012, 16:04
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?
"Es gibt keine schlimmere Lüge als die Wahrheit, die von denen, die sie hören, missverstanden wird."
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#48

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 17. Mär 2012, 16:17
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);
Angehängte Dateien
Dateityp: pas Thema167053_2.dpr.pas (10,2 KB, 3x aufgerufen)
  Mit Zitat antworten Zitat
Panthrax

Registriert seit: 18. Feb 2005
286 Beiträge
 
Delphi 2010 Enterprise
 
#49

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 17. Mär 2012, 16:42
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?
"Es gibt keine schlimmere Lüge als die Wahrheit, die von denen, die sie hören, missverstanden wird."
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
963 Beiträge
 
Delphi XE2 Professional
 
#50

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 17. Mär 2012, 17:45
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.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:55 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf