Schleife solange bis freie ID gefunden wurde

**PHP-Desaster** · 06.12.2008, 12:49

Genau so. Wenn du erst mit einem SELECT nachsehen würdest und anschließend deine generierte ID einfügst, könnte es sein, dass die ID inzwischen vergeben ist, das müsstest du dann zusätzlich abfangen. Da kannst du besser einen UNIQUE-Constraint auf die Spalte setzen (hast du ja wahrscheinlich eh schon) und dann nach der Query entsprechend kontrollieren, ob dieser Constraint verletzt wurde und mit einer neuen ID erneut versuchen.

**Truncate** · 06.12.2008, 17:53

Hm also so müßte es doch eigentlich funktionieren oder nicht?

Hängt bei mir aber irgendwie...

PHP-Code:


while($ergebnis="1")

                    

{

                        

$dateiname=randompass("3");

mysql_query("INSERT INTO ... VALUES ...");



if(mysql_affected_rows()==1)

{$ergebnis="1";}

                        

}

Was ich auch nicht genau verstehe:

Sie weist PHP an, einen in ihr eingebetteten Befehl so lange zu wiederholen, wie die while-Bedingung als TRUE ausgewertet wird.

vs.

Falls die while-Bedingung bereits beim ersten Mal FALSE ist, werden die Anweisungen der while-Schleife nicht ein einziges Mal durchlaufen.

**ghostgambler** · 06.12.2008, 17:57

Dann lies es halt noch drei Mal. Ist jetzt nicht soo schwer, vllt. etwas unglücklich formuliert, dann musst es halt mal genauer lesen.

Was du scheinbar auch nicht verstanden hast:
$ergebnis = 1 vs. $ergebnis == 1

**Truncate** · 06.12.2008, 18:00

PHP-Code:


while($ergebnis<>"1")

                    

{

                        

$dateiname=randompass("3");

mysql_query("INSERT INTO ... VALUES ...");



if(mysql_affected_rows()==1)

{$ergebnis="1";}

                        

}

**onemorenerd** · 06.12.2008, 21:09

Dieses Vorgehen ist ... nicht sehr clever. Du kannst nämlich nicht vorhersagen, wie lange die Schleife rattert bis endlich mal eine freie ID gefunden wurde. Letztlich ist es von randompass("3") abhängig und wenn diese Funktion das tut, was der Name andeutet, hängt sie vom Zufall ab. Du solltest aber unbedingt sicherstellen, dass nur eine maximale Zahl von Zufallsversuchen notwendig ist, bis es klappt. Sonst terminiert das im Worst Case niemals.

Muss die ID denn wirklich zufällig sein? Kannst du nicht den MD5 von time() nehmen oder sowas? Oder einfach hochzählen?

**Truncate** · 07.12.2008, 16:35

Muss die ID denn wirklich zufällig sein? Kannst du nicht den MD5 von time() nehmen oder sowas? Oder einfach hochzählen?

Hallo,

ja die ID muss zufällig sein. Hochzählen geht also nicht. Und MD5 von time() nehmen und auf 3 Stellen kürzen wäre ja genauso ein "Geratter" dann...

Die Frage ist ja auch wie oft es überhaupt vorkommen wird das generierte IDs schon vorhanden sind (ich geh jetzt mal davon aus das permanent immer nur 5000 IDs in der DB vorhanden sind).

**phpguru42** · 07.12.2008, 17:13

Original geschrieben von Truncate
Die Frage ist ja auch wie oft es überhaupt vorkommen wird das generierte IDs schon vorhanden sind (ich geh jetzt mal davon aus das permanent immer nur 5000 IDs in der DB vorhanden sind).

Bei einer 32-stelligen ID in hexadezimal (wie bei MD5), kannst Du 2^128 verschiedene IDs generieren.
Ich würde denken, dass es nahezu ausgeschlossen ist, dass sich eine ID doppelt, wenn sie hinreichend zufällig generiert wird.

Wobei die kürzliche entdeckte DNS-Sicherheitslücke, mathematisch auf dem Geburtstagsparadoxon beruht. Von daher bin ich mir jetzt doch nicht mehr so sicher

- vielleicht kann das mal ein Mathematiker unter den Forenmitgliedern genauer analysieren? Wäre sicherlich ganz interessant.

**Truncate** · 07.12.2008, 17:50

Original geschrieben von phpguru42
Bei einer 32-stelligen ID in hexadezimal (wie bei MD5), kannst Du 2^128 verschiedene IDs generieren.
Ich würde denken, dass es nahezu ausgeschlossen ist, dass sich eine ID doppelt, wenn sie hinreichend zufällig generiert wird.

Ja es sollte aber eine extrem kurze ID sein (wird für Dateinamen genutzt).

MD5 nutzt ja nichtmal alle möglichen Zeichen von a-z weswegen das noch mehr einschränken würde.

**phpguru42** · 07.12.2008, 18:30

Original geschrieben von Truncate
Ja es sollte aber eine extrem kurze ID sein (wird für Dateinamen genutzt).

Na je kürzer die ID desto höher die Kollisionen, ist klar.

Die Kombinationen kannst Du mit "Anzahl der verschiedenen Zeichen" hoch "Länge der ID" ermitteln, das heißt z.B. mit a-z A-Z 0-9 und drei Stellen erhältst du 238328 verschiedene Kombinationen:

238328 / 5000 = 47,6656

Im Schnitt gibt es also nach ca. jedem 47. Versuch eine Kollision.

Oder wie war jetzt Deine Frage?

EDIT:
Achso, und wenn es ganz dumm läuft, terminiert der Algo nie

**Truncate** · 07.12.2008, 18:36

Original geschrieben von phpguru42
Na je kürzer die ID desto höher die Kollisionen, ist klar.

Ja und deswegen gibt's ja extra eine Schleife

Ziel ist ja eine kurze ID und nicht die Vermeidung von ev. Kollisionen.

Original geschrieben von phpguru42
Die Kombinationen kannst Du mit "Anzahl der verschiedenen Zeichen" hoch "Länge der ID" ermitteln, das heißt z.B. mit a-z A-Z 0-9 und drei Stellen erhältst du 238328 verschiedene Kombinationen:

Wie kommst Du auf 238.328? Bei mir macht das 195.112 (58^3).

**phpguru42** · 07.12.2008, 18:43

a-z A-Z 0-9 = 26 + 26 + 10 = 62
Und wie kommst Du auf 58?

**onemorenerd** · 07.12.2008, 23:08

Original geschrieben von Truncate
MD5 von time() nehmen und auf 3 Stellen kürzen wäre ja genauso ein "Geratter" dann...

Die Frage ist ja auch wie oft es überhaupt vorkommen wird das generierte IDs schon vorhanden sind (ich geh jetzt mal davon aus das permanent immer nur 5000 IDs in der DB vorhanden sind).

Man kann keine 5.000 Werte mit nur 3 Stellen darstellen!

Wenn du weißt, wie viele IDs du maximal (!) haben wirst, kannst du das Problem auch von dieser Seite angehen. Bleiben wir mal bei 5.000, also maximal 5.000. Dann tritt der Worst Case ein, wenn du bereits 4.999 vergeben hast. Wie lange braucht ein Zufallsgenerator, um die 1 freie von 5000 IDs zu erraten? Bestenfalls nur einen Versuch, klar. Aber schlimmstenfalls rät er niemals richtig. Und was ist nun der Average Case von 1 und unendlich?

Du mußt also unbedingt etwas tun, um sicherzustellen, dass überhaupt mal eine freie ID gefunden wird und wenn du schon an den Parametern drehst, dann mach es doch gleich so, dass sie auch in "akzeptabler Zeit" gefunden wird.
Du könntest zum Beispiel den Wertebereich vergrößern. Du weißt zwar, dass du maximal 5.000 Werte brauchst, aber indem du den Wertebereich auf 100.000 ausdehnst, sind garantiert stets 95% aller IDs frei. Die Chance erhöht sich von 1/5.000 auf 95.000/100.000 oder 9,5/10.

Aber lass dich nicht täuschen. Das Verfahren ist immernoch schlecht. Du hast zwar die Chance erhöht, eine freie ID zu finden, aber es kann immernoch unendlich lange dauern (wenn der Generator permament in den belegten 5% des Wertebereichs tippt).

Begründe doch mal, warum die ID zufällig sein soll und wofür du sie brauchst!

**phpguru42** · 07.12.2008, 23:24

Original geschrieben von onemorenerd
Man kann keine 5.000 Werte mit nur 3 Stellen darstellen!

Warum nicht

**Truncate** · 07.12.2008, 23:27

Original geschrieben von onemorenerd
Man kann keine 5.000 Werte mit nur 3 Stellen darstellen!

Doch. Oder bist Du nur von Zahlen ausgegangen?

Original geschrieben von onemorenerd
Begründe doch mal, warum die ID zufällig sein soll und wofür du sie brauchst!

Für einen Dateinamen. Natürlich kann ich die fortlaufend nummerieren aber dann kann ja jeder rumschnüffeln und man kann sofort sehen wievieles Uploads schon erfolgt sind usw.

Als Alternative fallen mir jetzt eben nur längere IDs ein.

Schleife solange bis freie ID gefunden wurde