Preuve simple que le GUID n'est pas unique

Question

J'aimerais prouver qu'un GUID n'est pas unique dans un simple programme de test. Je m'attendais à ce que le code suivant fonctionne pendant des heures, mais il ne fonctionne pas. Comment puis-je le faire fonctionner ?

BigInteger begin = new BigInteger((long)0);
BigInteger end = new BigInteger("340282366920938463463374607431768211456",10);  //2^128
for(begin; begin<end; begin++)
  Console.WriteLine(System.Guid.NewGuid().ToString());

J'utilise C#.

Answer 1

Kai, j'ai fourni un programme qui fera ce que vous voulez en utilisant des fils. Sa licence est soumise aux conditions suivantes : vous devez me payer 0,0001 $ par heure et par cœur de CPU sur lequel vous l'exécutez. Les frais sont payables à la fin de chaque mois civil. Veuillez me contacter pour obtenir les détails de mon compte Paypal dès que possible.

using System;
using System.Collections.Generic;
using System.Linq;

namespace GuidCollisionDetector
{
    class Program
    {
        static void Main(string[] args)
        {
            //var reserveSomeRam = new byte[1024 * 1024 * 100];     // This indeed has no effect.

            Console.WriteLine("{0:u} - Building a bigHeapOGuids.", DateTime.Now);
            // Fill up memory with guids.
            var bigHeapOGuids = new HashSet<Guid>();
            try
            {
                do
                {
                    bigHeapOGuids.Add(Guid.NewGuid());
                } while (true);
            }
            catch (OutOfMemoryException)
            {
                // Release the ram we allocated up front.
                // Actually, these are pointless too.
                //GC.KeepAlive(reserveSomeRam);
                //GC.Collect();
            }
            Console.WriteLine("{0:u} - Built bigHeapOGuids, contains {1} of them.", DateTime.Now, bigHeapOGuids.LongCount());

            // Spool up some threads to keep checking if there's a match.
            // Keep running until the heat death of the universe.
            for (long k = 0; k < Int64.MaxValue; k++)
            {
                for (long j = 0; j < Int64.MaxValue; j++)
                {
                    Console.WriteLine("{0:u} - Looking for collisions with {1} thread(s)....", DateTime.Now, Environment.ProcessorCount);
                    System.Threading.Tasks.Parallel.For(0, Int32.MaxValue, (i) =>
                    {
                        if (bigHeapOGuids.Contains(Guid.NewGuid()))
                            throw new ApplicationException("Guids collided! Oh my gosh!");
                    }
                    );
                    Console.WriteLine("{0:u} - That was another {1} attempts without a collision.", DateTime.Now, ((long)Int32.MaxValue) * Environment.ProcessorCount);
                }
            }
            Console.WriteLine("Umm... why hasn't the universe ended yet?");
        }
    }
}

PS : Je voulais essayer la bibliothèque Parallel extensions. C'était facile.

Et l'utilisation de OutOfMemoryException comme flux de contrôle ne semble pas correcte.

EDIT

Eh bien, il semble que cela attire toujours les votes. J'ai donc corrigé le problème de GC.KeepAlive(). Et je l'ai modifié pour qu'il fonctionne avec C# 4.

Et pour clarifier mes conditions de support : le support n'est disponible que le 28 février 2010. Veuillez utiliser une machine à remonter le temps pour faire des demandes de support ce jour-là uniquement.

EDIT 2 Comme toujours, le GC fait un meilleur travail que moi pour gérer la mémoire ; toutes les tentatives précédentes de le faire moi-même étaient vouées à l'échec.

Answer 2

Cela durera bien plus que quelques heures. En supposant qu'il tourne en boucle à 1 GHz (ce qui n'est pas le cas - il sera beaucoup plus lent que cela), il fonctionnera pendant 10790283070806014188970 ans. Ce qui est environ 83 milliards de fois plus long que l'âge de l'univers.

En supposant que Loi Moores tient, il serait beaucoup plus rapide de ne pas exécuter ce programme, d'attendre plusieurs centaines d'années et de l'exécuter sur un ordinateur qui est des milliards de fois plus rapide. En fait, tout programme dont l'exécution prend plus de temps que le doublement de la vitesse des processeurs (environ 18 mois) sera achevé plus rapidement si vous attendez que la vitesse des processeurs ait augmenté et si vous achetez un nouveau processeur avant de l'exécuter (à moins que vous ne l'écriviez de manière à pouvoir le suspendre et le reprendre sur un nouveau matériel).

Answer 3

Un GUID est théoriquement non unique. Voici votre preuve :

• Le GUID est un nombre de 128 bits
• Vous ne pouvez pas générer 2^128 + 1 ou plus de GUIDs sans réutiliser les anciens GUIDs.

Cependant, si toute la puissance du soleil était utilisée pour accomplir cette tâche, elle se refroidirait bien avant d'être terminée.

Les GUID peuvent être générés en utilisant un certain nombre de tactiques différentes, dont certaines prennent des mesures spéciales pour garantir qu'une machine donnée ne générera pas deux fois le même GUID. Trouver des collisions dans un algorithme particulier montrerait que votre méthode particulière de génération de GUIDs est mauvaise, mais ne prouverait rien sur les GUIDs en général.

Answer 4

Bien sûr, les GUIDs peuvent entrer en collision. Puisque les GUIDs sont de 128 bits, il suffit de générer 2^128 + 1 d'eux et par le principe du pigeonnier il doit y avoir une collision.

Mais lorsque nous disons qu'un GUID est unique, ce que nous voulons vraiment dire, c'est que l'espace des clés est si grand qu'il est pratiquement impossible de générer accidentellement deux fois le même GUID (en supposant que nous générons des GUID de manière aléatoire).

Si vous générez une séquence de n GUID de façon aléatoire, alors la probabilité d'au moins une collision est d'environ p(n) = 1 - exp(-n^2 / 2 * 2^128) (c'est le problème d'anniversaire le nombre d'anniversaires possibles étant 2^128 ).

   n     p(n)
2^30 1.69e-21
2^40 1.77e-15
2^50 1.86e-10
2^60 1.95e-03

Pour rendre ces chiffres concrets, 2^60 = 1.15e+18 . Donc, si vous générez un milliard de GUIDs par seconde, il vous faudra 36 ans pour générer 2^60 des GUIDs aléatoires et même dans ce cas, la probabilité d'avoir une collision est toujours 1.95e-03 . Vous avez plus de chances d'être assassiné à un moment donné de votre vie ( 4.76e-03 ) que de trouver une collision au cours des 36 prochaines années. Bonne chance.

Answer 5

Si vous êtes préoccupé par l'unicité, vous pouvez toujours acheter de nouveaux GUID afin de pouvoir jeter les anciens. Je peux en mettre sur eBay si vous le souhaitez.