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

Rund um die LCL und andere Komponenten

Re: Gibt es in FPC eine IntegerList?

Beitragvon Socke » 11. Sep 2018, 21:31 Re: Gibt es in FPC eine IntegerList?

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
Socke
 
Beiträge: 2552
Registriert: 22. Jul 2008, 18:27
Wohnort: Köln
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 8.1/Debian GNU/Linux/Raspbian/openSUSE | 
CPU-Target: 32bit x86 armhf
Nach oben

Beitragvon Frank Ranis » 12. Sep 2018, 06:53 Re: Gibt es in FPC eine IntegerList?

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
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
www.flz-vortex.de
Frank Ranis
 
Beiträge: 112
Registriert: 24. Jan 2013, 21:22
OS, Lazarus, FPC: Winux (L 0.9.xy FPC 2.2.z) | 
CPU-Target: xxBit
Nach oben

Beitragvon wp_xyz » 12. Sep 2018, 08:43 Re: Gibt es in FPC eine IntegerList?

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;
wp_xyz
 
Beiträge: 2672
Registriert: 8. Apr 2011, 08:01

Beitragvon Socke » 12. Sep 2018, 09:23 Re: Gibt es in FPC eine IntegerList?

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
Socke
 
Beiträge: 2552
Registriert: 22. Jul 2008, 18:27
Wohnort: Köln
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 8.1/Debian GNU/Linux/Raspbian/openSUSE | 
CPU-Target: 32bit x86 armhf
Nach oben

Beitragvon mschnell » 12. Sep 2018, 12:09 Re: Gibt es in FPC eine IntegerList?

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

Beitragvon Horst_h » 12. Sep 2018, 12:24 Re: Gibt es in FPC eine IntegerList?

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
Horst_h
 
Beiträge: 69
Registriert: 20. Mär 2013, 08:57

Beitragvon hubblec4 » 12. Sep 2018, 14:11 Re: Gibt es in FPC eine IntegerList?

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?
hubblec4
 
Beiträge: 204
Registriert: 25. Jan 2014, 17:50

Beitragvon Socke » 12. Sep 2018, 15:03 Re: Gibt es in FPC eine IntegerList?

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
Socke
 
Beiträge: 2552
Registriert: 22. Jul 2008, 18:27
Wohnort: Köln
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 8.1/Debian GNU/Linux/Raspbian/openSUSE | 
CPU-Target: 32bit x86 armhf
Nach oben

Beitragvon Warf » 12. Sep 2018, 15:28 Re: [gelöst]Gibt es in FPC eine IntegerList?

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
Warf
 
Beiträge: 985
Registriert: 23. Sep 2014, 16:46
Wohnort: Aachen
OS, Lazarus, FPC: Mac OSX 10.11 | Win 10 | FPC 3.0.0 | L trunk | 
CPU-Target: x86_64, i368, ARM
Nach oben

Beitragvon Frank Ranis » 13. Sep 2018, 06:15 Re: [gelöst]Gibt es in FPC eine IntegerList?

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
Frank Ranis
 
Beiträge: 112
Registriert: 24. Jan 2013, 21:22
OS, Lazarus, FPC: Winux (L 0.9.xy FPC 2.2.z) | 
CPU-Target: xxBit
Nach oben

Beitragvon Warf » 13. Sep 2018, 09:37 Re: [gelöst]Gibt es in FPC eine IntegerList?

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
Warf
 
Beiträge: 985
Registriert: 23. Sep 2014, 16:46
Wohnort: Aachen
OS, Lazarus, FPC: Mac OSX 10.11 | Win 10 | FPC 3.0.0 | L trunk | 
CPU-Target: x86_64, i368, ARM
Nach oben

Beitragvon Frank Ranis » 13. Sep 2018, 12:20 Re: [gelöst]Gibt es in FPC eine IntegerList?

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
Frank Ranis
 
Beiträge: 112
Registriert: 24. Jan 2013, 21:22
OS, Lazarus, FPC: Winux (L 0.9.xy FPC 2.2.z) | 
CPU-Target: xxBit
Nach oben

Beitragvon hubblec4 » 13. Sep 2018, 17:37 Re: [gelöst]Gibt es in FPC eine IntegerList?

@Frank
Für Objecte nutzte ich immer die TObjectList, aus der units contnrs.
hubblec4
 
Beiträge: 204
Registriert: 25. Jan 2014, 17:50

Beitragvon m.fuchs » 18. Sep 2018, 10:08 Re: [gelöst]Gibt es in FPC eine IntegerList?

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
m.fuchs
 
Beiträge: 1971
Registriert: 22. Sep 2006, 18:32
Wohnort: Berlin
OS, Lazarus, FPC: Winux (L 1.8.4, FPC 3.0.4) | 
CPU-Target: x86, x64, arm
Nach oben

Beitragvon hubblec4 » 18. Sep 2018, 10:43 Re: [gelöst]Gibt es in FPC eine IntegerList?

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.
hubblec4
 
Beiträge: 204
Registriert: 25. Jan 2014, 17:50

• Themenende •
Vorherige

Zurück zu Komponenten und Packages



Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 4 Gäste

cron
porpoises-institution
accuracy-worried