Zwei Zahlenreihen miteinander vergleichen.

klezmor · Beiträge: 558 delphi 6 personal delphi 2005 personal

Ich habe folgendes Problem.
Ich möchte möglichst schnell feststellen ob zwei Zahlenreihen der Länge 10 in Form von eines eins zu eins übereinstimmen. Dieser Vergleich soll möglichst schnelle gehen, da er ein paar Millionen Mal von statten geht.
Es kommt aber nicht auf die Reihenfolge der Elemente innerhalb des Arrays an. 1 Array hat den Vorteil, dass es sortiert ist, das andere jedoch nicht.
Bsp: 1 2 3 4 5 6 8 9 10 = 7 4 6 5 3 2 9 1 10 8 aber 1 2 3 4 5 6 8 9 10 ungleich 1 2 3 4 5456 6 8 9 10. eine möglichkeit bestände ja darin das zweite Array mit bubblesort zu sortieren und dann solange auf gleichheit prüfen bis ungleichheit da ist oder auch nicht.
Aber ist das die effektivste Möglichkeit?

Gruß Klezmor.

_________________
"Beware of bugs in the above code; I have only proved it correct, not tried it." Donald Knuth

jaenicke · Verfasst: Do 18.09.08 04:18

Die Frage ist, wie groß die Zahlen sein können, wenn die Zahlen nicht allzu groß sind, könnte man mit Tabellen arbeiten, dies würde schnell sein, aber je mehr Speicher erfordern je größer die Zahlen sein können.
Und es geht nur, wenn es unterschiedliche 10 Zahlen sind.

Beispiel (mit festen 10 Zahlen in zwei Arrays zum Testen):

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:

procedure TForm77.btnStartClick(Sender: TObject);
var
  TestTable: array of Boolean;

  procedure InitTable(uMaxValue: Integer);
  var
    i: Integer;
  begin
    SetLength(TestTable, uMaxValue);
    for i := 0 to uMaxValue - 1 do
      TestTable[i] := False;
  end;

  function CompareArrays(uArray1, uArray2: TTestArray): Boolean;
  var
    j: Integer;
  begin
    Result := True;
    for j := 0 to High(uArray1) do
      TestTable[uArray1[j]] := True;
    for j := 0 to High(uArray2) do
      if not TestTable[uArray2[j]] then
      begin
        Result := False;
        Break;

      end;
    for j := 0 to High(uArray1) do
      TestTable[uArray1[j]] := False;
  end;

var
  test1: TTestArray;
  test2: TTestArray;
begin
  test1[0] := 1;
  test1[1] := 2;
  test1[2] := 3;
  test1[3] := 4;
  test1[4] := 5;
  test1[5] := 6;
  test1[6] := 7;
  test1[7] := 8;
  test1[8] := 9;
  test1[9] := 10;

  test2[0] := 1;
  test2[1] := 2;
  test2[2] := 3;
  test2[3] := 422;
  test2[4] := 5;
  test2[5] := 6;
  test2[6] := 7;
  test2[7] := 8;
  test2[8] := 9;
  test2[9] := 10;

  InitTable(1000);
  if CompareArrays(test1, test2) then
    ShowMessage('Gleich')
  else
    ShowMessage('Nicht gleich');
end;

alzaimar · Verfasst: Do 18.09.08 07:41

Ermittle zu beiden Zahlenkolonnen einen Hash-Wert, der auf die Position keine Rücksicht nimmt und vergleiche diese Werte. Wenn sie gleich sind, vergleiche Zahl für Zahl. Eine Möglichkeit wäre z.B.:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Function HashFromArray (Const anArray : TMyArray) : Cardinal;
Var
  i : Integer;

Begin
  Result := 0;
  For i:=Low (anArray) To High(anArray) Do
    If Odd (anArray[i]) Then 
      Result := (Result + 13*anArray[i]) mod maxint
   Else
      Result := (Result + 29*anArray[i]) mod maxint
End;

Du müsstest die beiden willkürlichen Konstanten 13 und 29 (Primzahlen sind gut, denke ich) vielleicht anpassen.

Bubblesort würde O(N*N) Zeit verbraten, vielleicht ist das hier schneller, das mit O(N log N) auskommt:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Function AreArraysEqual (Const aSorted, aUnsorted : TMyArray) : Boolean;
Var
  i : Integer;

Begin
  For i:=Low (aUnsorted) To High(aUnsorted) Do
    If Not Find_Using_BinarySearch(aSorted, aUnsorted[i]) Then Begin
      Result := False;
      Exit;
    End;
End;

Wenn in den Arrays nur relativ kleine Zahlen sind, dann könnte der Vorschlag von jaenike etwas bringen.

P.S.: Kleine Arrays sortiert man schneller mit 'Straight Insertion'. QuickSort ist -glaube ich- hier nicht gut genug.

Auch wäre etwas mehr Information angebracht. Du kennst doch die Performancefetischisten hier. Gib uns (Hechel!) ein paar Testarrays als Textdatei und lobe einen Performance-War aus. Du wirst dich wundern (wenn ein paar Freaks mitziehen)...

_________________
Na denn, dann. Bis dann, denn.

Gausi · Verfasst: Do 18.09.08 08:09

Das Suchen mit Binärsuche ist zwar eine tolle Sache, löst aber das Problem nur dann, wenn erstens die Zahlenfolgen die gleiche Länge haben (scheint der Fall zu sein) und zweitens jede Zahl höchstens einmal pro Folge auftritt (ist das auch so?).

_________________
We are, we were and will not be.

alzaimar · Verfasst: Do 18.09.08 08:15

Dat stimmt natürlich, aber dafür haben wir ja noch den Hash.

_________________
Na denn, dann. Bis dann, denn.

klezmor · Beiträge: 558 delphi 6 personal delphi 2005 personal

Also was ich eigentlich machen möchte, ist eine kleine Lottosimulation. Der Computer zieht eine zufällige Zahlenkombination, also praktisch 6 aus 49. Dies ist die Startkombination welche anschließend sortiert wird man zieht nun so lange, bis er genau diese 6 aus 49 wiedergezogen hat. Die Anzahl der Ziehungen konvergeriert, wie angenommen gegen 6 über 49 also 13mio... Da dies eine Reihe an Vergleichen sind, dauert es natürlich auch recht lange. Diesen Prozess des zufälligen Ziehens und dann schauen ob sich die Kombination mit der gegebenen deckt, möchte ich wie gesagt aus Zeitgründen optimieren. Mein bisheriger Ansatz ist folgender:
gezogene kombination sei z.b. 3, 22, 34, 36, 40, 48

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:

...
n=49, p=6
...
TZiehung = array [1..p] of byte;
...
function VergleichZiehung(const Ziehung:Tziehung):boolean;
var Lottozahlen: array [1..n] of byte;
    i,j,tmp,rnd,a,b:byte;
    sorted:boolean;
begin
 randomize;
 sorted:=false;
 for  i:=1 to n do
  Lottozahlen[i]:=i;
 for  i:=n downto n-p+1 do
 begin
   rnd:=random(i)+1;
   tmp:=Lottozahlen[rnd];
   Lottozahlen[rnd]:=Lottozahlen[i];
   Lottozahlen[i]:=tmp;
   if not check(tmp,ziehung,1,p) then
   begin
    result:=false;
    exit;
   end;
 end;
 result:=true;
end;

function check(tmp:integer;const Ziehung:Tziehung; l,r:byte):boolean;
var mid:byte;
begin
 result:=false;
 mid:=trunc((l+r)/2);
 while r-l>0 do
 begin
  if tmp>Ziehung[mid] then
   l:=mid+1
  else
   r:=mid;
  mid:=trunc((l+r)/2);
 end;
 if Ziehung[l]=tmp then
  result:=true;
end;
...
while not VergleichZiehung(Ziehung1) do
  begin
  inc(count);
  end;

was kann man daran verbessern?

_________________
"Beware of bugs in the above code; I have only proved it correct, not tried it." Donald Knuth

alzaimar · Verfasst: Do 18.09.08 12:33

Du kannst mit einer Menge arbeiten:

markieren

Delphi-Quelltext

1:
2:
3:

Type
  TLottozahlen = 1..49;
  TLottoziehung = Set Of TLottozahlen;

Zwei Ziehungen kannst Du direkt miteinander vergleichen

_________________
Na denn, dann. Bis dann, denn.

klezmor · Beiträge: 558 delphi 6 personal delphi 2005 personal

ist das dann also schneller, wie mein bisheriger ansatz oder?

_________________
"Beware of bugs in the above code; I have only proved it correct, not tried it." Donald Knuth

Horst_H · Verfasst: Do 18.09.08 12:43

Hallo,

wie wäre die Nutzung von Mengen?
Du nimmst einen mengentyp 1..49
Füllst eine Ausgangsmenge mit der ersten Ziehung.
Erzeugts jetzt ein Zufallsziehung trägst diese in die Menge ein und machst einen Vergleich auf Gleichheit der Mengen.
Der Vorteil von Mengen: "Sortiert" automatisch
Nachteil nur begrenzter Wertebereich 0..255 ( ausser TBits )

Gruß Horst
P.S
Da war alzaimar schneller ;-)

Mit Mengen lässt sich auch Bingo mit speziellen Mustern leicht testen
P.S.S
Sehr schnell

alzaimar · Verfasst: Do 18.09.08 12:43

klezmor hat folgendes geschrieben:

ist das dann also schneller, wie mein bisheriger ansatz oder?

Jupp. Kannst Du einen drauf ....

_________________
Na denn, dann. Bis dann, denn.

klezmor · Beiträge: 558 delphi 6 personal delphi 2005 personal

Horst_H hat folgendes geschrieben:

Hallo,

Füllst eine Ausgangsmenge mit der ersten Ziehung.
Erzeugts jetzt ein Zufallsziehung trägst diese in die Menge ein und machst einen Vergleich auf Gleichheit der Mengen.

Wie geht das ich hab noch nie mit Mengen gearbeitet.

---Moderiert von Narses: Beiträge zusammengefasst---

Meine jetzige Lösung:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:

//gibt die Lottozahlenmenge aus
function ausgabeMenge(Ziehung:TLottoziehung):string;
var i:byte;
begin
 for i:=1 to n do
  if i In Ziehung then
   result:=result+' '+inttostr(i);
end;
//erzeugt Zufallszahlen nach dem Prinzip von Fisher-Yates und fügf diese dann einer Menge hinzu
procedure ZufallsZiehung(var Ziehung:TLottoziehung);
var Lottozahlen: array [1..n] of byte;
    i,tmp,rnd:byte;
begin
 Ziehung:=[];
 randomize;
 for  i:=1 to n do
  Lottozahlen[i]:=i;
 for  i:=n downto n-p+1 do
 begin
   //Fisher-Yates mischeln
   rnd:=random(i)+1;
   tmp:=Lottozahlen[rnd];
   Lottozahlen[rnd]:=Lottozahlen[i];
   Lottozahlen[i]:=tmp;
   
   Ziehung:=Ziehung+[tmp];//was ist besser + oder include?
   //include(Ziehung,tmp);
 end;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
 Zufallsziehung(startziehung);
 Label1.Caption:=AusgabeMenge(startziehung);
end;

procedure TForm1.Button2Click(Sender: TObject);
var endziehung:TLottoziehung;
             i:byte;
          count:longint;
begin
 for i:=1 to 10 do
 begin
  count:=0;
  repeat
   ZufallsZiehung(endziehung);
   inc(count);
  until startziehung=endziehung;
  Listbox1.Items.Add(inttostr(count));
  application.ProcessMessages;
  application.ProcessMessages;
 end;
end;

der unterschied zur älteren Lösung ist minimal, es lässt sich natürlich auch nicht so leicht feststellen.
Gibt es keine Möglichkeit, das noch ein wenig schneller zu machen?
Danke im voraus.

Gruß Klezmor.

_________________
"Beware of bugs in the above code; I have only proved it correct, not tried it." Donald Knuth

Boldar · Verfasst: Do 18.09.08 14:36

Du kannst die Procedur Zufallsziehung als

markieren

Delphi-Quelltext

1:	procedure ZufallsZiehung(var Ziehung:TLottoziehung);inline;

deklarieren, das Spart wirklich zeit.
Ausserdem randomize immer ins oncreate der Form packen, dass Spart einiges und erst dass erzeugt dir wirklich zufällige Zahlen!

klezmor · Beiträge: 558 delphi 6 personal delphi 2005 personal

Ok der tip mti dem randomize war gut, das hat wirlich einiges an performance gebracht.
Aber noch ne frage ist eine Funktion mit rückgabewert ohne var parameter schneller, also mit var parameter?

_________________
"Beware of bugs in the above code; I have only proved it correct, not tried it." Donald Knuth

Boldar · Verfasst: Do 18.09.08 15:04

AM Schnellsten ist es Glaube ich mit Pointern. zeig doch mal, wie TLottoziehung deklariert ist!

Horst_H · Verfasst: Do 18.09.08 15:05

Hallo,

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

procedure ZufallsZiehung(var Ziehung:TLottoziehung); 
var Lottozahlen: array [1..n] of byte; 
    i,tmp,rnd:byte; 
begin 
 Ziehung:=[]; 
 randomize; 
 for  i:=1 to n do 
  Lottozahlen[i]:=i; 
 for  i:=n downto n-p+1 do 
 begin 
   //Fisher-Yates mischen 
   rnd:=random(i)+1; 
   tmp:=Lottozahlen[rnd]; 
   Lottozahlen[rnd]:=Lottozahlen[i]; 
   Lottozahlen[i]:=tmp; 
    
   Ziehung:=Ziehung+[tmp];//was ist besser + oder include? 
   //include(Ziehung,tmp); 
 end; 
end;
...
repeat 
   ZufallsZiehung(endziehung); 
   inc(count); 
  until startziehung=endziehung;

ist doch der casus cnactus.
Wenn Du direkt eine neue Ziehung startest, wenn die erste Zahl schon falsch ist, ist dies erheblich schneller.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:

const
  n = 49;
  p = 6;

type
  tBereich = 1..n;
  tlottoFeld = array[tBereich] of byte;
  tLottoZiehung = set of tBereich;
var
  LottoFeld : tLottoFeld;
procedure InitLottofeld;
//Einmal im Programm füllen, dann nur noch kopieren
//auch nur einmal randomize im Programm
var
   i : integer;
begin
  randomize;
 for  i:=1 to n do 
  Lottozahlen[i]:=i; 
end;

function ZufallsZiehung(var Ziehung:TLottoziehung):boolean; 
var Lottozahlen: tLottoFeld;
    i,tmp,rnd:byte; 
begin 
 result := false;
 Ziehung:=StartZiehung; 
 LottoZahlen := LottoFeld;

 for  i:=n downto n-p+1 do 
 begin 
   //Fisher-Yates mischen 
   rnd:=random(i)+1; 
   tmp:=Lottozahlen[rnd]; 
   Lottozahlen[rnd]:=Lottozahlen[i]; 
   Lottozahlen[i]:=tmp; 
   If Not(tmp in Ziehung) then 
      EXIT;//EDIT nicht break ich Narr...; 
 end; //for
 result := true;
end;

begin
 InitLottofeld;
 ErzeugeStartziehung;
 for i:=1 to 10 do 
 begin 
  count:=0; 
  while Not(ZufallsZiehung(Endziehung)) do 
    inc(count); 
  Listbox1.Items.Add(inttostr(count)); 
...
end.

Gruß Horst

EDIT 2

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Running "c:\fpc\2.2.2\bin\i386-win32\lotto.exe "
   35   42    6   45   27   17
     3913595 00:00:00.719
    13828990 00:00:01.171
     2272051 00:00:00.188
     1897814 00:00:00.156
    43655409 00:00:03.703
     5111971 00:00:00.438
    24644679 00:00:02.094
    28823683 00:00:02.437
      624677 00:00:00.063
     4135739 00:00:00.343

klezmor · Beiträge: 558 delphi 6 personal delphi 2005 personal

Boldar hat folgendes geschrieben:

AM Schnellsten ist es Glaube ich mit Pointern. zeig doch mal, wie TLottoziehung deklariert ist!

markieren

Delphi-Quelltext

1:
2:
3:

n=49;
TLottozahlen = 1..n;
TLottoziehung = set of TLottozahlen;

ich dachte var parameter werden intern wie zeiger gehandhabt?
Was ist eigentlich schneller, die Startziehung als var parameter Übergeben, oder direkt auf die globale Variable Startziehung zuzugreifen?

Horst_H hat folgendes geschrieben:

Hallo,
ist doch der casus cnactus.
Wenn Du direkt eine neue Ziehung startest, wenn die erste Zahl schon falsch ist, ist dies erheblich schneller.

Das dachte ich mir zuerst auch, aber ich weiß halt nicht, wie das delphi intern mit mengen regelt, denn das vorzeitige abbrechen der Ziehung hatte ich ja in meinem ersten Code realisiert, per binaerer Suche:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

function check(tmp:integer;const Ziehung:Tziehung; l,r:byte):boolean;
var mid:byte;
begin
 result:=false;
 mid:=trunc((l+r)/2);
 while r-l>0 do
 begin
  if tmp>Ziehung[mid] then
   l:=mid+1
  else
   r:=mid;
  mid:=trunc((l+r)/2);
 end;
 if Ziehung[l]=tmp then
  result:=true;
end;

, und da ich annahm, dass Delphi, um ein beliebiges Element in einer Menge zu suchen, auch nichts anderes macht.
Habe ich jetzt halt gleich die ganze Menge verglichen.

Gruß Klezmor.

_________________
"Beware of bugs in the above code; I have only proved it correct, not tried it." Donald Knuth

Hidden · Verfasst: Do 18.09.08 16:53

klezmor hat folgendes geschrieben:

mid := trunc((l + r) / 2);

Da aber eher: mid := (l + r) div 2;

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

klezmor · Beiträge: 558 delphi 6 personal delphi 2005 personal

jop zwischenzeitig hatte ich es eh in mid := (l + r) shr 1; umgewandelt.

_________________
"Beware of bugs in the above code; I have only proved it correct, not tried it." Donald Knuth

klezmor · Beiträge: 558 delphi 6 personal delphi 2005 personal

Hab versucht die Vergleichsroutine nach inlineAssembler zu portieren, aber da das meine ersten Schritte in Assembler sind, komme ich irgendwie net weiter, hoffe es kann mir jemand helfen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:

function VergleichZufallsZiehungAsm:boolean;//(startziehung:TLottoziehung):boolean;
var
    //Lottozahlen: array[1..n] of word;//lokal funktioniert es nicht, deshalb musste ich es global machen hängt vermutlich irgendwie mit er Adressierung zusammen, kenne //mich da aber nicht gut aus
    i,tmp,rnd: byte;
begin
 asm
  push edi;
  push eax;
  push ebx;  //zählervariable
  
  mov result, 0;
  //Array initialisieren
  mov edi, offset Lottozahlen;
  xor ebx,ebx;
  xor ecx,ecx;
  //funktioniert soweit ganz gut
  @1:
    inc ebx;
    mov [ebx + edi-1], bx;
  //  add ebx, 1;
    cmp ebx,n;
    jne @1;
  
  //Zufallszahlenziehen hier komme ihc nicht weiter
  xor eax, eax;
  @2:
   mov al, byte ptr [random(ebx)]; //das hier funktioniert nicht
   //jetzt kommt dieser Teil: 
   tmp:=Lottozahlen[rnd];
   Lottozahlen[rnd]:=Lottozahlen[i];
   Lottozahlen[i]:=tmp;
  tmp:=irgendein register;
  pop edi;
  pop eax;
  pop ebx;
 end;
 if not (tmp in startziehung) then
   exit;
end;

Lottozahlen musste ich global machen, was ich nicht verstehe, denn nur so kommt bei mov edi, offset Lottozahlen; keine fehlermeldung, geht es nicht dass Lottozahlen lokal bleiben.

_________________
"Beware of bugs in the above code; I have only proved it correct, not tried it." Donald Knuth

Horst_H · Verfasst: Fr 19.09.08 00:02

Hallo,

Delphi-Funktionen, wie random,abs,...kann nichr so einfach aus assembler heraus aufrufen.
Wie schnell ist den Dein Code bisher.
Der angefügte Code schafft ca. 54 Millionen Teil-Ziehungen in der Sekunde oder 8,3 Mio Komplett-Ziehungen (2,3 Ghz AMD64 X2 ).

Gru0 Horst

Einloggen, um Attachments anzusehen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme