Einzelnen Beitrag anzeigen

Michael II

Registriert seit: 1. Dez 2012
Ort: CH BE Eriswil
739 Beiträge
 
Delphi 11 Alexandria
 
#36

AW: TGUID - einzigartige ID auf andere Computer Systeme ?

  Alt 30. Okt 2023, 16:17
Die erzeugten Werte sollten GLOBAL (GUID) möglichst kollisionsfrei sein. CreateGUID(NewGUID); guid := GUIDToString(NewGUID); schneidet wohl in den meisten Anwendungsfällen besser ab als eine "Lösung" via TDateTime oder GetTickCount. Ich nenne mal deinen Vorschlag LUID (L für lokal) und den üblichen 128 Bit Wert GUID.

TDateTime. TDateTime ist ein double. 8 Byte. Wenn du deine Funktion zwischen Jahr 1 und Jahr 9999 anbieten willst, dann speicherst du für Zeitspempel1 9999*365.25*24*60*60*1000 voneinander verschiedene Werte ab, dazu benötigst du eigentlich nur 48.5 Bits (und nicht 64). Da dein zweiter Zeitstempel z2 zeitlich nach dem ersten liegt, ist der Informationsgehalt von z2 noch tiefer. Nehmen wir mal an, z2 liege maximal 100 Jahre nach z1; dann sind das weitere 41.5 Bit Infos. Zusammen mit deinem 2 Byte Zähler, speicherst du 92 Bit Infos in deinen 144Bits, verschwendest also 52 Bits.

Eine GUID, wie du sie dir einfach via Delphi unter Windows abholen kannst nutzt global (über alle Geräte) 128 Bits.

LUID ist also 128-92=36 Bit schwächer; erzeugt 2^36 Mal weniger Werte als GUID.

Das wirkt sich natürlich sehr schlecht auf die Kollisionswahrscheinlichkeit aus.
Wie viele LUIDs kannst du ausgeben, bis die Wahrscheinlichkeit mindestens einer Kollision auf >50% steigt?
Wären deine LUIDs gleichverteilt (wäre optimal; sie sind es nicht, da du zum Beispiel im Jahr 2023 kein Zeitstempel1 2045 ausgegeben wird), dann wären es k=1/2+sqrt(1/4+2*N*ln(2))*, wobei N=2^92 die Anzahl möglicher LUIDs. Für GUIDs gilt N=2^128.

92 Bit-Werte kollidieren gemäss * bezogen auf den Fall "mind. 1 Kollision" 2^18 mal schneller als die 128 Bit GUIDs. Effektiv tun es deine LUIDs noch viel rascher, weil deine LUIDs "aufsteigend" und damit weniger "zufällig/gleichverteilt" als die GUIDs ausgegeben werden.

Rollo63 hat Infos zum Thema Kollisionen verlinkt. Es gibt dort ein Beispiel, in welchem die Ausgabe von 1 Milliarde GUIDs/sec erst nach rund 86 Jahren mit p=0.5 zu mindestens einer Kollision führt. Selbst bei optimalen 92 Bit Werten dauerte es bei gleicher Ausgabegeschwindigkeit (1 Mio 92 Bit Werte/Millisekunde(!)) nur ungefähr 3 Stunden bis es in 50% aller Fälle zu mindestens einer Kollision kommt.

Der GetTickCount Vorschlag schneidet auch nicht gut ab; da verwendest du insgesamt 4+4+4 Bytes=96 Bits.(Nebenbei: Es gibt auch GetTickCount64). GetTickCount/64 hat laut microsoft immer noch eine Auflösung von nur 10 bis 16ms (wirkt sich negativ auf die Kollisionswahrscheinlichkeit p=1-N^k/((N-k)!*N^k) aus). Bei 16ms Auflösung verlierst du zum Beispiel 2*4=8 Bits an Infos, hast also noch 88 Bytes Informationsgehalt.

Sinspin erwähnte hochauflösende Timer. Diese hätten immerhin eine bessere Auflösung als TDateTime, gettickcount, gettickcount64.

Die GUID, welche du in Delphi via CreateGUID(NewGUID); abrufen kannst sind wohl in den meisten Anwendungsfällen genügend kollisionsfrei.

Wenn du kollisionsfreie IDs benötigst, dann musst du Eigenschaften der Geräte nutzen, welche jedes Gerät eindeutig identifizieren oder aber du verwendest wie weiter oben erwähnt wurde eine zentrale Vergabestelle (da würde dann auch ein einfacher Zähler genügen).
Michael Gasser

Geändert von Michael II (31. Okt 2023 um 07:54 Uhr)
  Mit Zitat antworten Zitat