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

ça va durer plus que des heures. En supposant qu'il boucle à 1 GHz (ce qu'il ne sera pas - il sera beaucoup plus lent que cela), il fonctionnera pour 10790283070806014188970 années. Qui est d'environ 83 milliards de fois plus longue que l'âge de l'univers.

en supposant Moores law tient, il serait beaucoup plus rapide de ne pas exécuter ce programme, attendre plusieurs centaines d'années et l'exécuter sur un ordinateur qui est des milliards de fois plus rapide. En fait, tout programme qui prend plus de temps à courir qu'il ne faut CPU vitesses de doubler (environ 18 mois) se terminera plus tôt si vous attendez jusqu'à ce que les vitesses CPU ont augmenté et acheter un nouveau CPU avant de l'exécuter (à moins que vous l'écrivez de sorte qu'il peut être suspendu et repris sur le nouveau matériel).

un guide est théoriquement non-unique. Voici votre preuve:

• GUID est une 128 bits
• Vous ne pouvez pas générer des 2^128 + 1 ou plus Guid sans l'aide d'une vieille Guid

cependant, si toute la puissance produite par le soleil était dirigée vers l'exécution de cette tâche, il se refroidirait longtemps avant qu'elle ne soit terminée.

GUIDs peuvent être générés en utilisant un certain nombre de tactiques différentes, dont prendre 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 GUIDs est mauvaise, mais ne prouverait rien au sujet des GUIDs en général.

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

mais quand nous disons qu'un GUID est un unique, ce que nous voulons vraiment dire est que l'espace de 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érons des GUID au hasard).

si vous générez une séquence de n GUIDs aléatoirement, 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 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 GUIDs par seconde, il vous faudra 36 ans pour générer 2^60 GUIDs aléatoires et même alors la probabilité que vous avez une collision est toujours 1.95e-03 . Vous êtes plus susceptible d'être assassiné à un moment de votre vie ( 4.76e-03 ) que vous êtes de trouver une collision au cours des 36 prochaines années. Bonne chance.

si vous êtes inquiet au sujet de l'unicité, vous pouvez toujours acheter de nouvelles GUIDs de sorte que vous pouvez jeter vos vieilles. J'en mettrai sur eBay si vous voulez.

personnellement, je pense que le "Big Bang" a été causé par la collision de deux GUIDs.

vous pouvez montrer que dans le temps O(1) avec une variante de bogosort quantique algorithme.

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

N'importe quelles deux guides sont très probablement uniques (pas égales).

voir cette entrée SO , et de Wikipedia

alors que chaque GUID généré n'est pas garantie d'être unique, le total nombre de touches uniques (2^128 ou 3.4×10^38) est si grande que la probabilité d'un même nombre généré deux fois est très petit. Pour exemple, considérons le observables l'univers, qui contient environ 5×10^22 les étoiles; chaque étoile pourrait alors avoir 6.8×10^15 GUIDs universellement uniques.

Donc, vous avez probablement attendre beaucoup plus de milliards d'années, et nous espérons que vous le frappez avant que l'univers tel que nous le connaissons.

[Update:] comme le font remarquer les commentaires ci-dessous, les nouvelles GUIDs MS sont V4 et N'utilisent pas L'adresse MAC comme partie de la génération de GUID (Je n'ai pas vu d'indication d'une implémentation V5 DE MS cependant, donc si quelqu'un a un lien confirmant que faites le moi savoir). Avec V4 cependant, le temps est encore un facteur, et les chances contre la duplication des GUIDs restent si faibles qu'elles ne sont pas pertinentes pour n'importe quel usage pratique. Vous ne seriez certainement pas susceptible de jamais générer une Version dupliquée D'un seul test de système comme L'OP essayait de le faire.

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

si je comprends bien cela, 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 sur les deux systèmes étaient à la même heure exacte quand la génération a eu lieu (l'horodatage est basé sur des millisecondes si je le comprends correctement).... même alors, il ya beaucoup d'autres bits du nombre qui sont aléatoires, de sorte que les chances sont toujours extrêmement petite.

pour toutes les utilisations pratiques les GUIDs sont universellement uniques.

Il ya une assez bonne description de la MS GUID à "la Vieille Nouvelle chose "blog

Voici une petite méthode d'extension astucieuse que vous pouvez utiliser si vous voulez vérifier l'unicité de l'interface graphique 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();
}

...je recommanderais même de l'appeler deux fois pour être sûr qu'il a eu raison au premier tour.

compte à 2^128-ambitieux.

laisse imaginer que nous pouvons compter 2^32 IDs par seconde par machine - pas que ambitieux, puisque ce n'est même pas 4,3 milliards par seconde. Consacrons 2^32 machines à cette tâche. En outre, 2 ^ 32 civilisations consacrent chacune les mêmes ressources à la tâche.

jusqu'à présent, nous pouvons compter 2^96 IDs par seconde, ce qui signifie que nous compterons pour 2^32 secondes (un peu plus de 136 an.)

Maintenant, tous nous avons besoin est d'obtenir 4,294,967,296 civilisations à chaque consacrer 4,294,967,296 machines, chaque machine capable de comptage 4,294,967,296 Id par seconde, purement à cette tâche pour la prochaine 136 ans - je vous suggère de commencer cette tâche essentielle en ce moment ;-)

bien si la durée de fonctionnement de 83 milliards d'années ne vous effraie pas, pensez que vous aurez également besoin de stocker les GUIDs générés quelque part pour vérifier si vous avez un duplicata; stocker 2^128 numéros 16 octets ne vous exigerait d'allouer 4951760157141521099596496896 terabytes de RAM à l'avance, donc imaginant que vous avez un ordinateur qui pourrait s'adapter à tout cela et que vous trouvez d'une manière ou d'une autre un endroit pour acheter DIMMs terabytes à 10 grammes chacun, combinés ils pèseront plus de 8 masses de terre, de sorte que vous pouvez virez-le sérieusement de l'orbite actuelle, avant même d'appuyer sur "Run". Réfléchir à deux fois!

for(begin; begin<end; begin)
    Console.WriteLine(System.Guid.NewGuid().ToString());

vous n'incrémentez pas begin donc la condition begin < end est toujours vraie.

si les collisions par GUID sont un problème, je recommande d'utiliser le ScottGuID à la place.

probablement vous avez des raisons d'être croire que l'algorithme pour produire des Guids ne produit pas des nombres vraiment aléatoires, mais est en fait le cycle avec une période << 2^128.

p.ex. méthode RFC4122 utilisée pour dériver des GUIDs qui fixe les valeurs de certains bits.

Preuve de cyclisme va dépendre de la taille de la période.

pour de petites périodes, table de hachage de hachage (GUID) - > GUID avec remplacement en cas de collision si Les GUIDs ne correspondent pas (se terminent s'ils le font) pourrait être une approche. Envisagez également de faire le remplacement seulement une fraction aléatoire du temps.

finalement si la période maximale entre les collisions est assez grande (et n'est pas connue à l'avance) n'importe quelle méthode va seulement produire une probabilité que la collision serait trouvée si elle existait.

notez que si la méthode de génération des Guids est basée sur l'horloge( voir la RFC), alors il peut ne pas être possible de déterminez s'il y a des collisions parce que (a) vous ne pourrez pas attendre assez longtemps pour que l'horloge tourne, ou (B) vous ne pouvez pas demander assez de repères à l'intérieur d'un tic-tac pour forcer une collision.

alternativement, vous pourriez être en mesure de montrer une relation statistique entre les bits dans le Guid, ou une corrélation de bits entre les Gids. Une telle relation pourrait rendre très probable que l'algorithme est défectueux sans nécessairement être en mesure de trouver une collision réelle.

bien sûr, si vous voulez juste prouver que les Guids peuvent entrer en collision, alors une preuve mathématique, pas un programme, est la réponse.

mais devez-vous être sûr vous avez un duplicata, ou ne vous souciez que si il peut être un duplicata. Pour être sûr que vous avez deux personnes avec le même anniversaire, vous avez besoin de 366 personnes (sans compter l'année bissextile). Pour qu'il y ait plus de 50% de chance d'avoir deux personnes avec le même anniversaire, vous n'avez besoin que de 23 personnes. C'est le problème d'anniversaire .

si vous avez 32 bits, vous besoin de 77 163 valeurs pour avoir une chance de plus de 50% d'un duplicata. Essayez:

Random baseRandom = new Random(0);

int DuplicateIntegerTest(int interations)
{
    Random r = new Random(baseRandom.Next());
    int[] ints = new int[interations];
    for (int i = 0; i < ints.Length; i++)
    {
        ints[i] = r.Next();
    }
    Array.Sort(ints);
    for (int i = 1; i < ints.Length; i++)
    {
        if (ints[i] == ints[i - 1])
            return 1;
    }
    return 0;
}

void DoTest()
{
    baseRandom = new Random(0);
    int count = 0;
    int duplicates = 0;
    for (int i = 0; i < 1000; i++)
    {
        count++;
        duplicates += DuplicateIntegerTest(77163);
    }
    Console.WriteLine("{0} iterations had {1} with duplicates", count, duplicates);
}

1000 iterations had 737 with duplicates

maintenant 128 bits est beaucoup, donc vous parlez encore un grand nombre d'éléments qui vous donnent encore une faible chance de collision. Vous auriez besoin du nombre suivant d'enregistrements pour les cotes données en utilisant une approximation:

• de 0,8 milliard de milliard de dollars pour le 1/1000 de chance de collision
• 21,7 milliards de milliards pour 50% risque de collision 1519150920"
• de 39,6 milliards de milliards pour 90% de chance de collision

il y a environ 1E14 e-mails envoyés par an donc il faudrait environ 400.000 ans à ce niveau avant que vous n'ayez 90% de chance d'en avoir deux avec le même GUID, mais c'est très différent de dire que vous devez exécuter un ordinateur 83 milliards de fois l'âge de l'univers ou que le soleil se refroidirait avant de trouver un duplicata.

Je ne comprends pas pourquoi personne n'a mentionné la mise à niveau de votre carte graphique... Sûrement si vous avez un haut-de-gamme NVIDIA Quadro FX 4800 ou quelque chose (192 noyaux CUDA) cela irait plus vite...

bien sûr si vous pouviez vous permettre quelques NVIDIA Qadro Plex 2200 S4s (à 960 Cuda Core chacun), ce calcul serait vraiment CRI. Peut-être NVIDIA serait-elle disposée à vous en prêter quelques-unes pour une "démonstration technologique" en tant que PR cascadeur?

sûrement qu'ils voudraient faire partie de ce calcul historique ...

ne manquez-vous pas un point important?

j'ai pensé que les GUIDs ont été générés en utilisant deux choses qui rendent les chances D'eux étant globalement unique assez élevé. Un est qu'ils sont ensemencés avec L'adresse MAC de la machine sur laquelle vous êtes et deux ils utilisent le temps qu'ils ont été générés plus un nombre aléatoire.

donc à moins que vous ne l'exécutiez sur la machine actuelle et que vous ne l'exécutiez avec toutes vos suppositions dans le plus petit laps de temps que la machine utilise pour représenter un temps dans le GUID, vous ne générerez jamais le même nombre peu importe le nombre de conjectures que vous prenez en utilisant l'appel système.

je suppose que si vous savez la façon dont un guide est fait serait effectivement raccourcir le temps de deviner assez substantiellement.

Tony

vous pourriez hachez les GUIDs. De cette façon, vous devriez obtenir un résultat beaucoup plus rapide.

Oh, bien sûr, exécuter plusieurs threads en même temps est également une bonne idée, de cette façon vous augmenterez la chance d'une condition de course générant le même guidon deux fois sur des threads différents.

1. allez au labo de cryogénie à New York.
2. se congeler pour (environ) 1990 années.
3. trouve un boulot à Planet Express.
4. acheter un CPU tout neuf. Construisez un ordinateur, lancez le programme, et placez-le en lieu sûr avec une pseudo machine à mouvement perpétuel comme la machine doomsday.
5. attendre que la machine à remonter le temps soit inventée.
6. saut vers le futur en utilisant le time machine. Si vous avez acheté 1YHz 128bit CPU, passez à 3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps après quand vous avez commencé à exécuter le programme.
7. ...?
8. PROFIT!!!

... Il faut au moins 10,783,127 années, même si vous aviez 1YHZ CPU qui est 1,000,000,000,000,000 (ou 1,125,899,906,842,624 si vous préférez utiliser le préfixe binaire) fois plus rapide que 1GHz CPU.

donc plutôt que d'attendre que le calcul soit terminé, il vaudrait mieux nourrir pigeons qui ont perdu leur maison parce que d'autres n pigeons ont pris leur maison. : (

ou, vous pouvez attendre jusqu'à ce que l'ordinateur quantique de 128 bits est inventé. Alors vous pouvez prouver que GUID n'est pas unique, en utilisant votre programme dans un délai raisonnable(peut-être).

Guid de 124 bits car 4 bits maintenez le numéro de version.

avez-vous essayé begin = begin + new BigInteger((long)1) au lieu de begin++?

si le nombre D'UUID généré suit la loi de Moore, l'impression de ne jamais manquer de GUID dans un avenir prévisible est fausse.

avec 2 ^ 128 UUIDs, cela ne prendra que 18 mois * Log2(2^128) ~= 192 ans, avant que nous soyons à court de tous les UUIDs.

et je crois (sans preuve statistique quoi-ainsi-jamais) que ces dernières années depuis l'adoption de masse de UUID, la vitesse que nous générons UUID augmente beaucoup plus vite que la loi de Moore dicter. En d'autres termes, nous avons probablement moins de 192 ans avant de devoir faire face à la crise UUID, c'est beaucoup plus tôt que la fin de l'univers.

mais comme nous ne les éliminerons pas d'ici la fin de 2012, nous laisserons aux autres espèces le soin de s'inquiéter du problème.

les chances d'un bug dans le code générateur de GUID sont beaucoup plus élevées que les chances de l'algorithme générant une collision. La probabilité d'un bug dans votre code pour tester les GUIDs est encore plus grande. Abandonner.

pas pour p**s sur le feu de joie ici, mais il se produit effectivement, et oui, je comprends la plaisanterie que vous avez donné à ce gars, mais le GUID est unique seulement en principe, je me suis cogné dans ce fil parce qu'il y a un bug dans L'émulateur WP7 qui signifie Chaque fois qu'il bottes il donne le même GUID la première fois qu'il est appelé! Donc, où en théorie vous ne pouvez pas avoir un conflit, s'il y a un problème générant ladite GUI, alors vous pouvez obtenir des doublons

http://forums.create.msdn.com/forums/p/92086/597310.aspx#597310

le programme, bien que ses erreurs, montre la preuve qu'un guide n'est pas unique. Ceux qui tentent de prouver le contraire n'en tiennent pas compte. Cette déclaration prouve juste la faible mise en œuvre de certaines des variations de guide.

un guide N'est pas nécessaire unique par définition, il est très unique par définition. Vous venez d'affiner le sens de highly. En fonction de la version, de l'implémentation (MS ou autres), de l'utilisation des VM, etc., votre définition change fortement. (voir lien dans le précédent post)

vous pouvez raccourcir votre table de 128 bits pour prouver votre point. La meilleure solution est d'utiliser une formule de hachage pour raccourcir votre table avec des doublons, puis d'utiliser la pleine valeur une fois que le hachage se heurte et sur la base de ce re-générer une GUID. Si vous exécutez à partir de différents emplacements, vous stockerez vos paires de clés hash/full dans un emplacement central.

Ps: si le but est juste de générer x nombre de valeurs différentes, créer une table de hachage de cette largeur et il suffit de vérifier la valeur de hachage.

Puisqu'une partie de la génération de Guid est basée sur le temps de la machine actuelle, ma théorie pour obtenir un Guid en double est:

1. effectuer une installation propre de fenêtres
2. créer un script de démarrage qui réinitialise le temps à 2010-01-01 12:00:00 Juste Comme Windows démarre.
3. juste après le script de démarrage, il déclenche votre application pour générer un Guid.
4. Cloner cette installation Windows, de sorte que vous écartez toute différence subtile qui pourrait se produire dans les amorces subséquentes.
5. re-image le disque dur avec cette image et démarrer la machine quelques fois.

pour moi.. le temps qu'il faut à un seul noyau pour générer un UUIDv1 garantit qu'il sera unique. Même dans une situation multi-core si le générateur UUID ne permet qu'à un UUID d'être généré à la fois pour votre ressource spécifique (gardez à l'esprit que plusieurs ressources peuvent utiliser Totalement les mêmes UUIDs mais peu probable puisque la ressource fait partie intégrante de l'adresse), alors vous aurez plus qu'assez d'UUIDs pour vous durer jusqu'à ce que l'horodatage brûle. À quel point je doute vraiment que vous en prendrait soin.

Voici une solution, aussi:

int main()
{
  QUuid uuid;
  while ( (uuid = QUuid::createUuid()) != QUuid::createUuid() ) { }
  std::cout << "Aha! I've found one! " << qPrintable( uuid.toString() ) << std::endl;
}

Remarque: nécessite Qt, mais je vous garantis que si vous le laissez courir assez longtemps, il peut en trouver un.

(Note: en fait, maintenant que je le regarde, il y a peut-être quelque chose dans l'algorithme de génération qui empêche deux uuids générés par la suite qui entrent en collision--mais j'en doute un peu).

la seule solution pour prouver que les GUIDs ne sont pas uniques serait d'avoir un Pool mondial de GUID. Chaque fois qu'un indicateur est généré quelque part, il doit être enregistré auprès de l'organisation. Ou diable, nous pourrions inclure une standardisation que tous les générateurs de GUID doit enregistrer automatiquement et pour cela il a besoin d'une connexion Internet active!