AGB  ·  Datenschutz  ·  Impressum  







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

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
Panthrax

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

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 17. Mär 2012, 15: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
 
#2

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 17. Mär 2012, 15: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
 
#3

AW: Schnittmenge von mehreren Mengen ermitteln

  Alt 17. Mär 2012, 15: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
Antwort Antwort


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 10:54 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz