[gelöst]Gibt es in FPC eine IntegerList?

Rund um die LCL und andere Komponenten
Socke
Lazarusforum e. V.
Beiträge: 2736
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Gibt es in FPC eine IntegerList?

Beitrag von Socke »

hubblec4 hat geschrieben:Da hast du recht Socke. Deine Lösung gefällt mir auch besser und ich finde, dass diese art der Abfrage für Integer also auch für Floats funktioniert.

Für eine genrische Standardimplementierung wäre die in der Tat nutzbar, sofern die Vergleichsoperatoren < und > definiert sind (was aber bei z.B. Pointern nicht der Fall ist!).
Bei Integer ist eine einzige Subtraktion aber immer schneller als zwei Vergleiche mit Sprunganweisung.


hubblec4 hat geschrieben:Schade eigentlich das diese

Code: Alles auswählen

Compare: TFPSListCompareFunc

zwei Integer als Parameter erwartet in der Function erwartet. Wär es nicht besser das wären gleich Floats? Denn ein Integer ist ja auch ein Float, oder?

Da hast du dich in der Klasse geirrt. TFPSListCompareFunc wird in TFPSList verwendet, nicht in TFPGList. Außerdem werden hier Pointer verarbeitet.

hubblec4 hat geschrieben:EDIT: eine kleine Bemerkung zu den Floats habe ich da noch.

wenn man mit

Code: Alles auswählen

 if item1 = item2 then

die beiden Floats vergleicht ist bei mir folgendes aufgetreten.

item1 = 0
item2 wurde durch ein paar berechnungen in meinem Programm ermittelt und sollte auch 0 ergeben, was ja eigentlich auch der Fall ist.
Nur wird für item2 die 0 so dargestellt 0.0+10E-1 oder so, weis jetzt gerade nicht ganz genau.
Auf jedenfall sind beide Items NICHT gleich was dann dazu führte das falsche weitere prozeduren ausgelöst wurden, daher habe ich dann alles soweit auf int64 umgestellt.

Du kannst Fließkommazahlen nicht auf exakte Gleichheit prüfen, da sie per Definition ungenau sind. Der Wikipediaartikel Maschinengenauigkeit beschreibt das ganz gut. Beim Prüfen auf Gleichheit muss man also den systembedingen Rechenfehler einbeziehen.
Für das Sortieren der Größe nach spielt das aber keine Rolle, da die Werte - auch wenn sie im Rahmen der Genauigkeit als gleich verarbeitet werden können - immernoch unterschiedlich sind.
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

Frank Ranis
Beiträge: 157
Registriert: Do 24. Jan 2013, 21:22
OS, Lazarus, FPC: Winux (L 0.9.xy FPC 2.2.z)
CPU-Target: xxBit

Re: Gibt es in FPC eine IntegerList?

Beitrag von Frank Ranis »

Hallo ,


Code: Alles auswählen

Beitragvon Socke » 11. Sep 2018, 15:32 Re: Gibt es in FPC eine IntegerList?
Um Rundungsfehler zu vermeiden muss der Nachkommateil ebenfalls beachtet werden.
Ich würde die Zahlen hier einfach vergleichen:
 
Code:
 
    if Item1 < Item2 then
      Result := -1
    else if Item1 > Item2 then
      Result := 1
    else // Item 1 = Item2
      Result := 0;
 


Danke , Super , Einfach , Universell.

Habe alles noch mal überarbeitet.

Für die beiden Vergleichsoperationen nach Auf- und Absteigend sortieren habe ich zwei Funktionen mit Varianten-Input gebaut.
Ob das nachher Nachteile in Sachen Geschwindigkeit beim Sortieren gibt weis ich jetzt nicht , dafür sind hier im Beispiel zu wenige Listen-Einträge vorhanden.

Code: Alles auswählen

unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
 Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls,
 fgl;
 
type
 
 { TForm1 }
 
 TForm1 = class(TForm)
  Button1: TButton;
  Button2: TButton;
  Memo1: TMemo;
  RadioButton1: TRadioButton;
  RadioButton2: TRadioButton;
  procedure Button1Click(Sender: TObject);
  procedure Button2Click(Sender: TObject);
 private
 
 public
 
 end;
 
 T_Int64List = specialize TFPGList<int64>;
 T_ExtendedList = specialize TFPGList<extended>;
 
var
 Form1: TForm1;
 i64_list:T_Int64List;
 extended_list:T_ExtendedList;
 
 // Up Down int64-Sortier-Funktionen
 function SortMyList_int64_up(const Item1, Item2: int64):longint;
 function SortMyList_int64_down(const Item1, Item2: int64):longint;
 // Up Down extended-Sortier-Funktionen
 function SortMyList_extended_up(const Item1, Item2: extended):longint;
 function SortMyList_extended_down(const Item1, Item2: extended):longint;
 
 // Vergleich per Variant , spart Code , universeller , Geschwindigkeit ??
 function _up(const Item1, Item2:variant):shortint;
 function _down(const Item1, Item2:variant):shortint;
 
implementation
 
{$R *.lfm}
 
{ TForm1 }
 
// Up Down - Test
function _up(const Item1, Item2:variant):shortint;
begin
 if Item1 < Item2
  then Result := -1
  else if Item1 > Item2
   then Result := 1
   else Result := 0; // Item 1 = Item2
end;
 
function _down(const Item1, Item2:variant):shortint;
begin
 if Item1 > Item2
  then Result := -1
  else if Item1 < Item2
   then Result := 1
   else Result := 0; // Item 1 = Item2
end;
 
 
// Int64 Sort-Funktionen
function SortMyList_int64_up(const Item1, Item2: int64):longint;
begin
 result:=_up(item1,item2); // Test per Variant-Übergabe
end;
 
function SortMyList_int64_down(const Item1, Item2: int64):longint;
begin
 result:=_down(item1,item2); // Test per Variant-Übergabe
end;
 
// Extended Sort-Funktionen
function SortMyList_extended_up(const Item1, Item2: extended):longint;
begin
 result:=_up(item1,item2); // Test per Variant-Übergabe
end;
 
function SortMyList_extended_down(const Item1, Item2: extended):longint;
begin
 result:=_down(item1,item2); // Test per Variant-Übergabe
end;
 
 
 
// Int64 - Beispiel
procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
    iz:int64;
begin
 i64_list:=T_Int64List.Create;
 i64_list.Clear;
 i64_list.Add(5);
 i64_list.Add(82898797);
 i64_list.Add(995);
 i64_list.Add(115);
 i64_list.Add(445);
 i64_list.Add(577777);
 i64_list.Add(55555);
 Memo1.Clear;
 
 memo1.lines.add('Orginal Eingabedaten');
 for i:=0 to i64_list.Count-1 do
  begin
   iz:=i64_list[i];
   memo1.lines.add(floattostr(iz));
  end;
 
 if radiobutton1.Checked
  then i64_list.Sort(@SortMyList_int64_up);
 if radiobutton2.Checked
  then i64_list.Sort(@SortMyList_int64_down);
 
 memo1.lines.add('');
 memo1.lines.add('Sortiert');
 for i:=0 to i64_list.Count-1 do
  begin
   iz:=i64_list[i];
   memo1.lines.add(floattostr(iz));
  end;
 i64_list.free;
end;
 
// Extended - Beispiel
procedure TForm1.Button2Click(Sender: TObject);
var i:integer;
    ez:extended;
begin
 extended_list:=T_ExtendedList.Create;
 extended_list.Clear;
 extended_list.Add(5.33);
 extended_list.Add(82898797.01);
 extended_list.Add(995.99000);
 extended_list.Add(995.98999);
 extended_list.Add(445.45);
 extended_list.Add(577777.001);
 extended_list.Add(55555.999);
 Memo1.Clear;
 
 memo1.lines.add('Orginal Eingabedaten');
 for i:=0 to extended_list.Count-1 do
  begin
   ez:=extended_list[i];
   memo1.lines.add(floattostr(ez));
  end;
 
 if radiobutton1.Checked
  then extended_list.Sort(@SortMyList_extended_up);
 if radiobutton2.Checked
  then extended_list.Sort(@SortMyList_extended_down);
 
 memo1.lines.add('');
 memo1.lines.add('Sortiert');
 for i:=0 to extended_list.Count-1 do
  begin
   ez:=extended_list[i];
   memo1.lines.add(floattostr(ez));
  end;
 extended_list.free;
end;
 
end.
 


Gruß

Frank
Dateianhänge
LAZ_specialize_TFPGList_Version_2.zip
(127.28 KiB) 25-mal heruntergeladen
www.flz-vortex.de

wp_xyz
Beiträge: 3252
Registriert: Fr 8. Apr 2011, 09:01

Re: Gibt es in FPC eine IntegerList?

Beitrag von wp_xyz »

Also ich weiß nicht: Bei einer Funktion, die vielleicht Millionenfach aufgerufen wird, mit Varianten herumzuhantieren, erscheint mir sehr ungeschickt, weil Varianten i.A. als sehr langsam gelten. Nimm doch CompareValue aus der Unit math, wenn dir das Schreiben einer mehrfachen IF-Anweisung zu umständlich ist. CompareValue gibt es als Overloads für alle möglichen Zahlentypen:

Code: Alles auswählen

uses
  Math;
function SortMyList_extended_up(const Item1, Item2: extended):longint;
begin
 result:=CompareValue(item1,item2);
end;

Socke
Lazarusforum e. V.
Beiträge: 2736
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Gibt es in FPC eine IntegerList?

Beitrag von Socke »

Socke hat geschrieben:
hubblec4 hat geschrieben:Da hast du recht Socke. Deine Lösung gefällt mir auch besser und ich finde, dass diese art der Abfrage für Integer also auch für Floats funktioniert.

Für eine genrische Standardimplementierung wäre die in der Tat nutzbar, sofern die Vergleichsoperatoren < und > definiert sind (was aber bei z.B. Pointern nicht der Fall ist!).
Bei Integer ist eine einzige Subtraktion aber immer schneller als zwei Vergleiche mit Sprunganweisung.

Ich muss meine Einschätzung relativieren: Eine Subtraktion ist nicht zwangsläufig schneller.
Bei einem Test maximaler Listengröße ergibt: die Subtraktion ist ca. 1-2% langsamer als der direkte Vergleich mit < und >. Getestet habe ich mit zwei identischen Listen von Zufallszahlen (64 Bit unter x86_64).

Code: Alles auswählen

{$Codepage UTF8}
program Project1;
 
uses
  sysutils, fgl, math;
 
type
  // als Listenelement wird der für Prozessor native Integer verwendet
  TMyIntList = specialize TFPGList<NativeInt>;
 
  function Compare_If(const Item1, Item2: NativeInt): integer;
  begin
    if Item1 < Item2 then
      Result := -1
    else if Item1 > Item2 then
      Result := 1
    else
      Result := 0; // Item 1 = Item2
  end;
  function Compare_Calc(const Item1, Item2: NativeInt): integer;
  begin
    Result := Item2 - Item1;
  end;
 
const
  MS_PER_DAY = 24*60*60*1000;
  MAX_ITEMS = MaxListSize; // Anzahl zu sortierender Elemente
var
  i, t: NativeInt;
  l1, l2: TMyIntList;
  t1, t2: TDateTime;
begin
  Randomize;
  l1 := TMyIntList.Create;
  l2 := TMyIntList.Create;
  try
    Write('Fülle Listen mit ', MAX_ITEMS,' Einträgen ... ');
    // Speicherbedarf der Listen vorab reservieren
    l1.Capacity := MAX_ITEMS;
    l2.Capacity := MAX_ITEMS;
    for i := 0 to MAX_ITEMS - 1 do
    begin
      t := Random(high(t));
      l1.Add(t);
      l2.Add(t);
    end;
    WriteLn('Fertig!');
 
    WriteLn('Sortiere mit IF...');
    t1 := now();
    l1.Sort(@Compare_If);
    t2 := now();
    WriteLn('Dauer: ', trunc((t2-t1)*MS_PER_DAY),'ms');
 
    WriteLn('Sortiere mit Subtraktion...');
    t1 := now();
    l2.Sort(@Compare_Calc);
    t2 := now()
    WriteLn('Dauer: ', trunc((t2-t1)*MS_PER_DAY),'ms');
 
  finally
    l1.Destroy;
    l2.Destroy;
  end;
  readln;
end.

Ausgabe:

Code: Alles auswählen

Fülle Listen mit 134217727 Einträgen ... Fertig!
Sortiere mit IF...
Dauer: 67594ms
Sortiere mit Subtraktion...
Dauer: 68624ms

.. und ja: das Verhältnis bewegt sich über mehrere Ausführungen im gleichen Rahmen (1-2%). Das heißt aber auch, dass der Sortieralgorithmus bei großen Datenmengenen einen wesentlich größeren Einfluss hat als eine einfache Vergleichsfunktion.
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

mschnell
Beiträge: 3410
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: Gibt es in FPC eine IntegerList?

Beitrag von mschnell »

./.

Horst_h
Beiträge: 71
Registriert: Mi 20. Mär 2013, 08:57

Re: Gibt es in FPC eine IntegerList?

Beitrag von Horst_h »

Hallo,

ich habe einen Ryzen 5 1600 Rechner und das Programm mal für 64-Bit unter Linux mit FPC 3.0.4 compiliert.
Bei mir bleibt Subtraktion schneller.
Original:

Code: Alles auswählen

 
{$Codepage UTF8}
{$mode objfpc}{$H+}
{$CODEALIGN proc=32,loop=8}
program Project1;
und fpc so aufgerufen:
fpc -O3  -Xs -al "NameDesProgrammes"
 


Ergebnis 1 mit IF

Code: Alles auswählen

 
F�lle Listen mit 134217727 Eintr�gen ... Fertig!
Sortiere mit IF...
Dauer: 46807ms
Sortiere mit Subtraktion...
Dauer: 41781ms

Es regibt sich ein Unterschied von ~10%

Ergebnis 2 mit ORD

Code: Alles auswählen

  function Compare_If(const Item1, Item2: NativeInt): integer;
  begin
    result := Ord(Item1 >= Item2)-Ord(Item1 <= Item2);
  end;

Sortiere mit Ord...

Code: Alles auswählen

F�lle Listen mit 134217727 Eintr�gen ... Fertig!
Sortiere mit Ord...
Dauer: 43127ms
Sortiere mit Subtraktion...
Dauer: 41945ms


Es bleibt ein Unterschied von ~ 3%

Gruß Horst

hubblec4
Beiträge: 245
Registriert: Sa 25. Jan 2014, 17:50

Re: Gibt es in FPC eine IntegerList?

Beitrag von hubblec4 »

Erstmal ein Dankeschön an alle die hier gepostet haben. Es waren wieder viele nützliche Infos für mich dabei.

Für mein Programm habe ich nun meine uLists mit der entsprechenden Int64Liste und alles funktioniert wie gewünscht.

Es geht dabei nicht soooo sehr um Geschwindigkeit da es vielleicht um die 50 (max 150) Einträge gibt.
Wichtig und schön ist nun das ich auch zwei Sortiert Varianten habe (ASC und DESC), denn das gibst bei einer normalen StringList nicht.

ich würde das Thema mal als gelöst markieren. Aber bitte ruhig weiter posten wenn es noch etwas schönes gibt was man einbauen könnte.


@Socke
Du schreibst man müsste für Floats einen "systembedingden Rechenfehler" einbeziehen wenn man zwei Werte vergleicht.
Was ist dieser Systembedingte Fehler, wie und wo ermitteln man diesen?

Socke
Lazarusforum e. V.
Beiträge: 2736
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Gibt es in FPC eine IntegerList?

Beitrag von Socke »

hubblec4 hat geschrieben:@Socke
Du schreibst man müsste für Floats einen "systembedingden Rechenfehler" einbeziehen wenn man zwei Werte vergleicht.
Was ist dieser Systembedingte Fehler, wie und wo ermitteln man diesen?

Ließ dir als erstes den Wikipedia Artikel zum Thema Maschinengenauigkeit durch. Als weiterführende Literatur gibt es mit Sicherheit div. Bücher zu IEEE754 Fließkommazahlen; auch hier im Forum gibt es Leute, die das besser erklären können als ich.
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

Warf
Beiträge: 1426
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: [gelöst]Gibt es in FPC eine IntegerList?

Beitrag von Warf »

Zum Thema maschinengrnauigkeit, du kannst dir das so vorstellen, es gibt zahlen die lassen sich nur mit extrem vielen nachkommastrllen darstellen, 1/3 im 10er system benötigt unendlich viele (0,333...)
Ein float hat aber nur begrenzte Größe (Single 32bit, Double 64 Bit, extnded 80 Bit) daher gibt es zählen die man nicht unterscheiden kann. Z.b. Im 10er System mit 3 nachkommastellen könntest du 0,3335 und 1/3 nicht unterscheiden

Frank Ranis
Beiträge: 157
Registriert: Do 24. Jan 2013, 21:22
OS, Lazarus, FPC: Winux (L 0.9.xy FPC 2.2.z)
CPU-Target: xxBit

Re: [gelöst]Gibt es in FPC eine IntegerList?

Beitrag von Frank Ranis »

Hallo ,

gibt es eine Möglichkeit die TFPG-Listen auch für Records oder Object zu nutzen ?

So etwa

Code: Alles auswählen

type
 
 TPunkt3d=record
   x,y,z:double;
 end;
 
 TDreieck=record
   a,b,c:TPunkt3d;
 end;
 
 T_Dreiecklist = specialize TFPGList<TDreieck>;
 
var
 Dreieckliste:T_Dreiecklist;
 


Leider spuckt mir LAZ dafür folgende Fehlermeldung aus .

Code: Alles auswählen

Error: Operator is not overloaded: "TDreieck" = "TDreieck" 


Gruß

Frank
www.flz-vortex.de

Warf
Beiträge: 1426
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: [gelöst]Gibt es in FPC eine IntegerList?

Beitrag von Warf »

Für Records ist das ein bisschen doof, du musst für die Records den = Operator im delphi mode überladen (also in einer Unit mit Mode Delphi) frag mich nicht warum.

Da empfehle ich dir lieber Klassen mithilfe der TFPGObjectList, wenn man der beim constructor true übergibt kümmert die sich selbständig darum die Objekte zu freed wenn sie aus der Liste gelöscht werden (also beim delete, clear oder free der Liste selbst) somit musst du dich nicht darum kümmern den Speicher aufzuräumen

Frank Ranis
Beiträge: 157
Registriert: Do 24. Jan 2013, 21:22
OS, Lazarus, FPC: Winux (L 0.9.xy FPC 2.2.z)
CPU-Target: xxBit

Re: [gelöst]Gibt es in FPC eine IntegerList?

Beitrag von Frank Ranis »

Hallo ,

Warf hat geschrieben:Für Records ist das ein bisschen doof, du musst für die Records den = Operator im delphi mode überladen (also in einer Unit mit Mode Delphi) frag mich nicht warum.

Da empfehle ich dir lieber Klassen mithilfe der TFPGObjectList, wenn man der beim constructor true übergibt kümmert die sich selbständig darum die Objekte zu freed wenn sie aus der Liste gelöscht werden (also beim delete, clear oder free der Liste selbst) somit musst du dich nicht darum kümmern den Speicher aufzuräumen


Danke dir .

Gruß

Frank
www.flz-vortex.de

hubblec4
Beiträge: 245
Registriert: Sa 25. Jan 2014, 17:50

Re: [gelöst]Gibt es in FPC eine IntegerList?

Beitrag von hubblec4 »

@Frank
Für Objecte nutzte ich immer die TObjectList, aus der units contnrs.

Benutzeravatar
m.fuchs
Lazarusforum e. V.
Beiträge: 2256
Registriert: Fr 22. Sep 2006, 19:32
OS, Lazarus, FPC: Winux (Lazarus 2.0.8, FPC 3.0.4)
CPU-Target: x86, x64, arm
Wohnort: Berlin
Kontaktdaten:

Re: [gelöst]Gibt es in FPC eine IntegerList?

Beitrag von m.fuchs »

hubblec4 hat geschrieben:Für Objecte nutzte ich immer die TObjectList, aus der units contnrs.

Hat aber den Nachteil, dass man beim Nutzen der Objekte in der Liste immer noch einen Typecast machen muss. Das erspart man sich bei einer generischen Liste.
Software, Bibliotheken, Vorträge und mehr: https://www.ypa-software.de

hubblec4
Beiträge: 245
Registriert: Sa 25. Jan 2014, 17:50

Re: [gelöst]Gibt es in FPC eine IntegerList?

Beitrag von hubblec4 »

m.fuchs
Stimmt da hast du recht. Ich schreibe mir dann dazu eine kleine Hilfe function als GETTER und habe dann eine Property über die ich gecastete Objecte erhalte.

Allerdings sind generishce Listen dann auf einen Type beschränkt. In eine TObjectList kann ich erstmal jedes Object reinpacken.

Antworten