Autor Beitrag
Gagga
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 95

Win 11
Delphi 12 Athen Pro
BeitragVerfasst: Di 22.03.22 22:27 
Hallo!

Ich muss/will zwei Mengen aus einem großen Mengen-Array vergleichen. Wenn die Schnittmenge größer x ist, wird eine gelöscht.
Ich mache das wie folgt:
ausblenden Delphi-Quelltext
1:
2:
m:= m1[a] * m2[b];
if CountMenge(@m, sizeof(m)) > x then DeleteArrayElement(m2[b]);

Vom Tempo her ist das suboptimal. Wie geht es schneller?

Gruß
Gagga
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 4764
Erhaltene Danke: 1052

Win10
C#, C++ (VS 2017/19/22)
BeitragVerfasst: Mi 23.03.22 10:27 
Hallo,

das ist zu wenig Kontext.
Wie hast du denn die beiden Funktionen definiert?
Ich weiß, daß es keine einfache Funktion zum Ermitteln der Anzahl in einem Set gibt, aber vllt. eine effizientere. Wie viele Elemente hat denn dein Set?
Und beim Löschen eines Array Elements: warum nicht anhand des Index b?
Gagga Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 95

Win 11
Delphi 12 Athen Pro
BeitragVerfasst: Mi 23.03.22 12:10 
user profile iconTh69 hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,

das ist zu wenig Kontext.
Wie hast du denn die beiden Funktionen definiert?
Ich weiß, daß es keine einfache Funktion zum Ermitteln der Anzahl in einem Set gibt, aber vllt. eine effizientere. Wie viele Elemente hat denn dein Set?
Und beim Löschen eines Array Elements: warum nicht anhand des Index b?


Zur Ermittlung der Mengengröße:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
function CountMenge(P: Pointer; Count: Cardinal): Cardinal;  //CountMenge(@m, sizeof(m))
const
  lu : packed array[0..15of Byte = (0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
var
  b: Byte;
begin
  Result := 0;
  while Count > 0 do
  begin
    b := PByte(P)^;
    // lower Nibble
    Inc(Result, lu[b and $0F]);
    // upper Nibble
    Inc(Result, lu[b shr 4]);

    Dec(Count);
    Inc(PByte(P));
  end;
end;


Das Array ist dynamisch, daher muss nach dem Löschen des Elementes `was passieren.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
procedure DeleteArrayElement(var AArray: TIntArray; const AIndex: Integer);
begin
  Move(AArray[AIndex + 1], AArray[AIndex], SizeOf(AArray[0]) * (Length(AArray) - AIndex - 1)); //Dahinterliegende Daten aufrücken
  SetLength(AArray, Length(AArray) - 1); // Länge kürzen
end;
Sinspin
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1321
Erhaltene Danke: 117

Win 10
RIO, CE, Lazarus
BeitragVerfasst: Mi 23.03.22 13:14 
Hey, ich sehe da keine Möglichkeit wirklich was zu verbessern. Wie oft wird das denn ausgeführt?
Eventuell solltest du parallel arbeiten falls das öfter gebraucht wird.

Was ginge, wäre auf SetLength zu verzichten indem Du die maximale Länge merkst und die aktuell verwendete Länge.
Generell kann SetLength sehr langsam werden wenn man das Array vergrößert. Daher besser gleich um 1000 verlängern und erst wieder wenn kein Platz mehr da ist.

_________________
Wir zerstören die Natur und Wälder der Erde. Wir töten wilde Tiere für Trophäen. Wir produzieren Lebewesen als Massenware um sie nach wenigen Monaten zu töten. Warum sollte unser aller Mutter, die Natur, nicht die gleichen Rechte haben?
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 4764
Erhaltene Danke: 1052

Win10
C#, C++ (VS 2017/19/22)
BeitragVerfasst: Mi 23.03.22 13:49 
Also rufst du die Funktion doch (mit explizitem Index) auf:
ausblenden Delphi-Quelltext
1:
DeleteArrayElement(m2, b);					
?
Da du schon in CountMenge das vordefinierte Array benutzt, sehe ich dort auch kein Verbesserungspotential mehr.

Wie oft wird denn diese Funktion aufgerufen und ist dann der Schwellwert öfters erreicht?
Gagga Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 95

Win 11
Delphi 12 Athen Pro
BeitragVerfasst: Mi 23.03.22 15:32 
Es geht darum Tippreihen für die Auswahlwette [1..45] zu filtern. Ich sehe die Möglichkeit vor, beliebige Vollsystemreihen nach verschiedenen Kriterien zu filtern. Eines ist, Reihen zu eliminieren, die mit einer anderen in n Elementen übereinstimmen, wobei n zwischen 2 und 4 wählbar ist.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
if cbKongru.Checked then begin                                                     //b2
n := RGKongru.ItemIndex+2;
for a := 0 to high(ungef)-1 do begin                                              //b3
for b := high(ungef) downto a +1 do  begin                                        //b4
     m:= ungef[a].m * ungef[b].m;
    if CountMenge(@m, sizeof(m)) > n then DeleteArrayElement(ungef,b);
  end;                                                                            //e4
  end;                                                                            //e3

Im schlimmsten Fall ist die Menge ungef 8.145.060 Elemente groß. Da kommen schon ein paar Milliarden Vergleiche zusammen.
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 4764
Erhaltene Danke: 1052

Win10
C#, C++ (VS 2017/19/22)
BeitragVerfasst: Mi 23.03.22 16:32 
Dann solltest du wohl besser eine eigene Datenstruktur, anstatt Set, benutzen.
Und für das Array wohl besser auch (wie Sinspin schon vorgeschlagen hat).
Sinspin
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1321
Erhaltene Danke: 117

Win 10
RIO, CE, Lazarus
BeitragVerfasst: Mi 23.03.22 17:13 
So sachte kommen wir näher. Deine Sets finde ich Ok. Das ist nicht das Problem.

CountMenge :
packed array, weg. Verwende normales array, packed kann den Zugriff langsam machen.

Ein Problem ist, für CountMenge ist es besser mit einem Array zu arbeiten. Für DeleteArrayElement wäre eine verkettete Liste besser. Allerdings ist der Aufwand dafür höher.

Um weiter bei Arrays zu bleiben, auf keinen Fall irgendwas mit packed, das macht den Zugriff langsam.
Bei der Masse an Tests macht es Sinn das ganze in Threads zu packen. (Gruppiert nach der äußeren Schleife, immer Max(a) / CPU cores Stück in einem Thread)
Ich würde die Elemente im Array nicht löschen. Sondern auf "Gelöscht" setzen und im weiteren Verlauf einfach überspringen. Spart massig Zeit/Arbeit.

_________________
Wir zerstören die Natur und Wälder der Erde. Wir töten wilde Tiere für Trophäen. Wir produzieren Lebewesen als Massenware um sie nach wenigen Monaten zu töten. Warum sollte unser aller Mutter, die Natur, nicht die gleichen Rechte haben?
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 4764
Erhaltene Danke: 1052

Win10
C#, C++ (VS 2017/19/22)
BeitragVerfasst: Mi 23.03.22 18:50 
Ich meine besonders: wenn dauernd die Anzahl im Set (aus der Vereinigung zweier Sets) ermittelt werden muß, wäre es besser, wenn diese gleich mitgespeichert werden würde (daher eine entsprechend angepaßte Datenstruktur).
Gagga Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 95

Win 11
Delphi 12 Athen Pro
BeitragVerfasst: Mi 23.03.22 20:07 
user profile iconSinspin hat folgendes geschrieben Zum zitierten Posting springen:
So sachte kommen wir näher. Deine Sets finde ich Ok. Das ist nicht das Problem.

CountMenge :
packed array, weg. Verwende normales array, packed kann den Zugriff langsam machen.
...

Das lokale packed Array in der Funktion bringt gegenüber dem normalen Array eine Zeitersparnis von ca. 5 %.

user profile iconSinspin hat folgendes geschrieben Zum zitierten Posting springen:
...

Ich würde die Elemente im Array nicht löschen. Sondern auf "Gelöscht" setzen und im weiteren Verlauf einfach überspringen. Spart massig Zeit/Arbeit.

Das bringt eine Zeitersparnis von 38 % - danke!

Gruß
Gagga
Sinspin
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1321
Erhaltene Danke: 117

Win 10
RIO, CE, Lazarus
BeitragVerfasst: Do 24.03.22 10:12 
user profile iconGagga hat folgendes geschrieben Zum zitierten Posting springen:
Das bringt eine Zeitersparnis von 38 %

:zustimm:
Wenn Du damit deine Chancen beim tippen / wetten erhöhen willst... Zufall funktioniert anders.
Aber wenn es klappt, ich bin mit 1% zufrieden. 38% müssen garnicht sein ;-)

_________________
Wir zerstören die Natur und Wälder der Erde. Wir töten wilde Tiere für Trophäen. Wir produzieren Lebewesen als Massenware um sie nach wenigen Monaten zu töten. Warum sollte unser aller Mutter, die Natur, nicht die gleichen Rechte haben?
Gagga Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 95

Win 11
Delphi 12 Athen Pro
BeitragVerfasst: Fr 25.03.22 11:55 
user profile iconSinspin hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconGagga hat folgendes geschrieben Zum zitierten Posting springen:
Das bringt eine Zeitersparnis von 38 %

:zustimm:
Wenn Du damit deine Chancen beim tippen / wetten erhöhen willst... Zufall funktioniert anders.
...


Wer redet denn vom Zufall bei der Auswahlwette? Letztes Wochenende u.a. 5 Richtige gehabt, knapp den JP von 2 Mio. verpasst.