323 votos

Prueba simple que GUID no es la única

Me gustaría demostrar que un GUID no es único en un programa de prueba simple. Esperaba el siguiente código a correr durante horas, pero no está funcionando. ¿Cómo puedo hacer que funcione?

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());

Estoy usando C#.

407voto

ligos Puntos 3149

Kai, me han proporcionado un programa que hace lo que usted desea el uso de hilos. Está licenciada bajo las siguientes condiciones: usted debe pagar me 0,0001 usd por hora por cada núcleo de la CPU ejecuta. Las cuotas se pagan al final de cada mes calendario. Por favor, póngase en contacto conmigo por mi cuenta de paypal detalles a la brevedad posible.

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: yo quería probar el Paralelo de las extensiones de la biblioteca. Eso fue fácil.

Y el uso de OutOfMemoryException como control de flujo sólo se siente mal.

EDITAR

Bien, parece que esto todavía atrae votos. Así que lo he corregido el GC.KeepAlive() problema. Y cambió a ejecutar con C# 4.

Y para aclarar mi apoyo términos: soporte técnico está disponible sólo en el 28/Feb/2010. Por favor use una máquina del tiempo para hacer las solicitudes de soporte en que sólo día.

EDICIÓN 2 Como siempre, la GC hace un trabajo mejor que yo en el manejo de la memoria de anteriores intentos de hacerlo yo misma estaban condenadas al fracaso.

226voto

rjmunro Puntos 10522

Esto va para mucho más que las horas. Suponiendo que se repite a 1 GHz (que no será mucho más lento que eso), se llevará a cabo 10790283070806014188970 años. Que es de alrededor de 83 mil millones de veces más que la edad del universo.

Suponiendo Moores de la ley se mantiene, sería mucho más rápido para que no se ejecute este programa, esperar varios cientos de años y ejecutar en un equipo que está a miles de millones de veces más rápido. De hecho, cualquier programa que toma más tiempo para ejecutar lo que se lleva velocidades de CPU el doble (18 meses) se completa antes si usted espera hasta que las velocidades de CPU han aumentado y comprar una nueva CPU antes de ejecutarlo (a menos que se escribe por lo que puede ser suspendido y reanudado en el nuevo hardware).

170voto

tylerl Puntos 14541

Un GUID es teóricamente no único. Aquí está la prueba:

  • GUID es un número de bits 128
  • No se puede generar 2^128 + 1 o más Guid sin volver a usar los Guid

Sin embargo, si la totalidad de la potencia de salida del sol fue dirigido a la realización de esta tarea, que pasaría frío, mucho antes de que se termine.

Guid puede ser generado a partir de un número de diferentes tácticas, algunas de las cuales tomar medidas especiales para garantizar que una determinada máquina no va a generar el mismo GUID dos veces. Encontrar colisiones en un determinado algoritmo de demostrar que su método en particular para la generación de Guid es malo, pero no prueba nada acerca de Guid en general.

137voto

Jason Puntos 125291

Por supuesto Guid puede chocar. Desde Guid son de 128 bits, solo generan 2^128 + 1 de ellos y por el principio del palomar debe haber una colisión.

Pero cuando decimos que un GUID es un ser único, lo que significa realmente es que la tecla de espacio es tan grande que es prácticamente imposible accidentalmente generar el mismo GUID dos veces (suponiendo que estamos generando Guid al azar).

Si se genera una secuencia de n Guid aleatoriamente, la probabilidad de que al menos uno de colisión es de aproximadamente p(n) = 1 - exp(-n^2 / 2 * 2^128) (este es el problema del cumpleaños con el número de cumpleaños posibles de ser 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

Para hacer estos números concretos, 2^60 = 1.15e+18. Así que, si eres capaz de generar mil millones de Guid por segundo, que tendrá 36 años a generar 2^60 Guid aleatorio y, aún así, la probabilidad de que un accidente es todavía 1.95e-03. Usted tiene más probabilidades de ser asesinado en algún momento de su vida (4.76e-03) que los que se van a encontrar una colisión durante los próximos 36 años. Buena suerte.

61voto

ctacke Puntos 53946

Si estás preocupado por singularidad siempre puedes comprar nuevo GUID entonces puedes tirar tus viejos. Pondré algunas en eBay si quieres.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by: