Question Preuve simple que GUID n'est pas unique [fermé]


Je voudrais prouver qu'un GUID n'est pas unique dans un programme de test simple. 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 #.


323


origine


Réponses:


Kai, j'ai fourni un programme qui fera ce que vous voulez en utilisant des threads. Il est autorisé sous les conditions suivantes: vous devez me payer 0,0001 $ par heure par cœur de processeur que vous utilisez. Les frais sont payables à la fin de chaque mois civil. S'il vous plaît contactez-moi pour les détails de mon compte paypal à votre meilleure convenance.

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 d'extensions Parallel. C'était facile.

Et utiliser OutOfMemoryException comme flux de contrôle ne semble pas correct.

MODIFIER

Eh bien, il semble que cela attire toujours des votes. J'ai donc résolu le problème GC.KeepAlive (). Et changé pour fonctionner avec C # 4.

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

EDIT 2 Comme toujours, le GC fait un meilleur travail que moi pour gérer la mémoire; toute tentative précédente de le faire moi-même était vouée à l'échec.


407



Cela va durer beaucoup plus que des heures. En supposant qu'il boucle à 1 GHz (ce qui ne sera 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 La loi de Moore En effet, il serait beaucoup plus rapide de ne pas exécuter ce programme, d'attendre plusieurs centaines d'années et de le faire fonctionner sur un ordinateur qui est des milliards de fois plus rapide. En fait, tout programme qui prend plus de temps que la vitesse du processeur à doubler (environ 18 mois) se terminera plus tôt si vous attendez que la vitesse du processeur augmente et que vous achetiez un nouveau processeur avant de l'exécuter (sauf si vous l'écrivez peut être suspendu et repris sur le nouveau matériel).


226



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

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

Cependant, si toute la puissance du soleil était dirigée vers l'accomplissement de cette tâche, elle se refroidirait longtemps avant qu'elle ne finisse.

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 le même GUID deux fois. Trouver des collisions dans un algorithme particulier montrerait que votre méthode particulière pour générer des GUID est mauvaise, mais ne prouvera rien sur les GUID en général.


170



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

Mais quand nous disons qu'un GUID est unique, ce que nous voulons vraiment dire c'est que l'espace clé est si grand qu'il est pratiquement impossible de générer accidentellement le même GUID deux fois (en supposant que nous générions des GUID au hasard).

Si vous générez une séquence de n GUID au hasard, alors la probabilité d'au moins une collision est approximativement p(n) = 1 - exp(-n^2 / 2 * 2^128)(c'est le problème d'anniversaire avec 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 GUID par seconde, cela vous prendra 36 ans pour générer 2^60 GUID au hasard et même alors la probabilité que vous avez une collision est encore 1.95e-03. Vous êtes plus susceptible d'être assassiné à un moment donné dans votre vie (4.76e-03) que vous êtes de trouver une collision au cours des 36 prochaines années. Bonne chance.


137



Si vous êtes préoccupé par l'unicité, vous pouvez toujours acheter de nouveaux GUID pour pouvoir jeter vos anciens. J'en mettrai sur eBay si vous le souhaitez.


61



Personnellement, je pense que le "Big Bang" a été causé lorsque deux GUID sont entrés en collision.


47



Vous pouvez le montrer en O (1) avec une variante du bogosort quantique algorithme.

Guid g1 = Guid.NewGuid();
Guid g2 = Guid.NewGuid();
if(g1 != g2) Universe.Current.Destroy();

42



Deux GUID sont très probablement uniques (non égaux).

Voir cette entrée SO, et de Wikipédia

Bien que chaque GUID généré ne soit pas   garanti être unique, le total   nombre de clés uniques (2 ^ 128 ou   3,4 × 10 ^ 38) est si grand que la probabilité d'un même nombre   généré deux fois est très petit. Pour   Par exemple, considérons l'observable   univers, qui contient environ 5 × 10 ^ 22   étoiles; chaque étoile pourrait alors avoir   6,8 × 10 ^ 15 GUID universellement uniques.

Il faut donc probablement attendre encore des milliards d’années et espérer que vous en toucherez un avant que l’univers prenne fin.


28



[Mettre à jour:]  Comme le soulignent les commentaires ci-dessous, les nouveaux GUID MS sont V4 et n'utilisent pas l'adresse MAC dans la génération GUID (je n'ai pas vu d'indication d'une implémentation V5 de MS, donc si quelqu'un a un lien confirmant que moi savoir). Cependant, avec la version V4, le temps reste un facteur, et les probabilités de duplication des GUID restent si faibles qu'elles sont sans importance pour toute utilisation pratique. Vous ne pourriez certainement pas générer un GUID dupliqué à partir d'un seul test système tel que celui que l'OP essayait de faire. 

La plupart de ces réponses manquent un point essentiel à propos de la mise en œuvre du GUID de Microsoft. La première partie du GUID est basée sur un horodatage et une autre partie est basée sur l'adresse MAC de la carte réseau (ou un nombre aléatoire si aucune carte réseau n'est installée).

Si je comprends bien, cela signifie que la seule façon fiable de dupliquer un GUID serait d'exécuter des générations GUID simultanées sur plusieurs machines où les adresses MAC étaient les mêmes ET où les horloges des deux systèmes étaient au même moment lorsque la génération s'est produite (l'horodatage est basé sur millisecondes si je le comprends bien) .... même alors, il y a beaucoup d'autres bits dans le nombre qui sont aléatoires, de sorte que les chances sont encore minimes.

À toutes fins utiles, les GUID sont universellement uniques.

Il y a une très bonne description de la MS GUID à "The Old New Thing" blog


27



Voici une petite méthode d’extension astucieuse que vous pouvez utiliser si vous voulez vérifier l’unicité des guides dans de nombreux endroits de votre code.

internal static class GuidExt
{
    public static bool IsUnique(this Guid guid)
    {
        while (guid != Guid.NewGuid())
        { }
        return false;
    }
}

Pour l'appeler, il suffit d'appeler Guid.IsUnique chaque fois que vous générez un nouveau guid ...

Guid g = Guid.NewGuid();
if (!g.IsUnique())
{
    throw new GuidIsNotUniqueException();
}

... diable, je recommanderais même de l'appeler deux fois pour être sûr qu'il a bien fonctionné au premier tour.


23



Compter à 2 ^ 128 - ambitieux.

Imaginons que nous puissions compter 2 ^ 32 ID par seconde par machine - pas cette ambitieux, puisque ce n'est même pas 4,3 milliards par seconde. Permet de consacrer 2 ^ 32 machines à cette tâche. De plus, permet d'obtenir 2 ^ 32 civilisations pour chacune dédier les mêmes ressources à la tâche.

Jusqu'à présent, nous pouvons compter 2 ^ 96 ID par seconde, ce qui signifie que nous compterons pendant 2 ^ 32 secondes (un peu plus de 136 ans).

Maintenant, tout ce dont nous avons besoin est d'obtenir 4 294 967 296 civilisations pour chacune des 4 294 967 296 machines, chacune capable de compter 4 294 967 296 ID par seconde, purement pour les quelques 136 prochaines années. -)


19