Entwickler-Ecke :: Thema anzeigen - Zwei Zahlenreihen miteinander vergleichen.

klezmor - Do 18.09.08 01:32
Titel: Zwei Zahlenreihen miteinander vergleichen.

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.

jaenicke - Do 18.09.08 05: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):

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 - Do 18.09.08 08: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.:

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:

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)...

klezmor - Do 18.09.08 12:55

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

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?

klezmor - Do 18.09.08 13:53

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:

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.

Horst_H - Do 18.09.08 16:05

Hallo,

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.

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

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 - Do 18.09.08 16:54

Boldar hat folgendes geschrieben:

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

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:

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.

klezmor - Do 18.09.08 21:23

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:

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.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!