example - remarks c#

Prueba simple de que GUID no es único (30)

Me gustaría probar que un GUID no es único en un programa de prueba simple. Esperaba que el siguiente código se ejecutara durante horas, pero no funciona. ¿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 #.

Ve al laboratorio de criogenia en la ciudad de Nueva York.
Congelarte por (aproximadamente) 1990 años.
Consigue un trabajo en Planet Express.
Compra una nueva CPU. Construya una computadora, ejecute el programa y colóquela en un lugar seguro con una máquina de movimiento pseudo-perpetua como la máquina del día del juicio final.
Espera hasta que se invente la máquina del tiempo.
Salta al futuro usando la máquina del tiempo. Si compró una CPU de 1 YHz a 128 bits, vaya a 3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps después de cuando comenzó a ejecutar el programa.
...?
¡¡¡LUCRO!!!

... Tarda al menos 10,783,127 años incluso si tiene una CPU de 1 YHz que es 1,000,000,000,000,000 (o 1,125,899,906,842,624 si prefiere usar el prefijo binario) veces más rápido que la CPU de 1 GHz.

Entonces, en lugar de esperar a que finalice el proceso, sería mejor alimentar a las palomas que perdieron su hogar porque otras n palomas se llevaron su hogar. :(

O bien, puede esperar hasta que se invente la computadora cuántica de 128 bits. Entonces puede probar que GUID no es único, al usar su programa en un tiempo razonable (tal vez).

¿Has probado begin = begin + new BigInteger((long)1) en lugar de begin ++?

Aquí hay un ingenioso método de extensión que puede usar si desea verificar la singularidad de GUID en muchos lugares de su código.

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

Para llamarlo, simplemente llame a Guid.IsUnique cada vez que genere un nuevo guid ...

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

... diablos, incluso recomendaría llamarlo dos veces para asegurarme de que lo consiguió en la primera ronda.

Bueno, si el tiempo de ejecución de 83 mil millones de años no lo asusta, piense que también necesitará almacenar los GUID generados en algún lugar para verificar si tiene un duplicado; almacenar 2 ^ 128 números de 16 bytes solo requeriría que asignes 4951760157141521099596496896 terabytes de RAM por adelantado, por lo que imagina que tienes una computadora que puede ajustarse a todo eso y que de alguna manera encuentras un lugar para comprar DIMM de terabyte a 10 gramos cada uno, combinados pese más de 8 masas terrestres, de modo que pueda desplazarlo seriamente de la órbita actual, incluso antes de presionar "Ejecutar". ¡Pensar dos veces!

Contando hasta 2 ^ 128 - ambicioso.

Imaginemos que podemos contar 2 ^ 32 ID por segundo por máquina, no tan ambiciosos, ya que no son ni 4.300 millones por segundo. Vamos a dedicar 2 ^ 32 máquinas a esa tarea. Además, obtengamos 2 ^ 32 civilizaciones para que cada uno dedique los mismos recursos a la tarea.

Hasta ahora, podemos contar 2 ^ 96 ID por segundo, lo que significa que contaremos durante 2 ^ 32 segundos (un poco más de 136 años).

Ahora, todo lo que necesitamos es obtener 4,294,967,296 civilizaciones por cada 4,294,967,296 máquinas, cada máquina capaz de contar 4,294,967,296 ID por segundo, puramente para esta tarea durante los próximos 136 años más o menos; sugiero que comencemos con esta tarea esencial ahora mismo; -)

Cualquiera de los dos GUID son muy probablemente únicos (no iguales).

Vea esta entrada de SO , y de Wikipedia

Si bien no se garantiza que cada GUID generado sea único, el número total de claves únicas (2 ^ 128 o 3.4 × 10 ^ 38) es tan grande que la probabilidad de que se genere el mismo número dos veces es muy pequeña. Por ejemplo, considere el universo observable, que contiene aproximadamente 5 × 10 ^ 22 estrellas; cada estrella podría tener 6,8 × 10 ^ 15 GUID universalmente únicos.

Así que probablemente tengas que esperar muchos más miles de millones de años, y esperar que llegues a uno antes del universo, tal como lo conocemos, llega a su fin.

Es de suponer que tiene motivos para creer que el algoritmo para producir Guids no está produciendo números verdaderamente aleatorios, sino que, de hecho, tiene ciclos con un período << 2 ^ 128.

por ejemplo, el método RFC4122 utilizado para derivar GUID que corrige los valores de algunos bits.

La prueba de ciclismo dependerá del posible tamaño del período.

Para periodos pequeños, la tabla hash de hash (GUID) -> GUID con reemplazo en caso de colisión si los GUID no coinciden (terminan si lo hacen) podría ser un enfoque. Considera también hacer solo el reemplazo una fracción aleatoria del tiempo.

En última instancia, si el período máximo entre colisiones es lo suficientemente grande (y no se conoce de antemano), cualquier método solo dará una probabilidad de que se encontraría la colisión si existiera.

Tenga en cuenta que si el método de generación de Guids se basa en el reloj (consulte la RFC), es posible que no sea posible determinar si existen colisiones porque (a) no podrá esperar el tiempo suficiente para que el reloj se cierre. o (b) no puede solicitar suficientes Guids dentro de una marca de reloj para forzar una colisión.

Alternativamente, puede mostrar una relación estadística entre los bits en el Guid o una correlación de bits entre los Guids. Una relación de este tipo podría hacer que sea muy probable que el algoritmo sea defectuoso sin que necesariamente pueda encontrar una colisión real.

Por supuesto, si solo quieres probar que los Guids pueden colisionar, entonces una prueba matemática, no un programa, es la respuesta.

Esto se ejecutará durante mucho más de horas. Suponiendo que se mueva a 1 GHz (que no lo hará, será mucho más lento que eso), funcionará durante 10790283070806014188970 años. Que es aproximadamente 83 mil millones de veces más largo que la edad del universo.

Suponiendo que se cumpla la ley de Moores , sería mucho más rápido no ejecutar este programa, esperar varios cientos de años y ejecutarlo en una computadora que es miles de millones de veces más rápida. De hecho, cualquier programa que demore más en ejecutarse que la velocidad de la CPU se duplique (aproximadamente 18 meses) se completará antes si espera hasta que la velocidad de la CPU haya aumentado y compre una nueva CPU antes de ejecutarla (a menos que la escriba para que funcione). puede ser suspendido y reanudado en nuevo hardware).

Kai, he proporcionado un programa que hará lo que quieras usando hilos. Se licencia bajo los siguientes términos: debe pagarme $ 0.0001 por hora por núcleo de CPU en el que lo ejecute. Las tarifas se pagan al final de cada mes calendario. Por favor, póngase en contacto conmigo para los detalles de mi cuenta de PayPal a la mayor 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?"); } } }

PD: quería probar la librería de extensiones paralelas. Eso fue fácil.

Y usar OutOfMemoryException como flujo de control simplemente se siente mal.

EDITAR

Bueno, parece que esto todavía atrae votos. Así que he arreglado el problema GC.KeepAlive (). Y lo cambié para correr con C # 4.

Y para aclarar mis términos de soporte: el soporte solo está disponible el 28 / febrero / 2010. Utilice una máquina del tiempo para realizar solicitudes de asistencia solo ese día.

EDIT 2 Como siempre, el GC hace un mejor trabajo que yo en la gestión de la memoria; cualquier intento anterior de hacerlo yo mismo estaba condenado al fracaso.

Las probabilidades de un error en el código de generación de GUID son mucho mayores que las probabilidades de que el algoritmo genere una colisión. Las probabilidades de un error en su código para probar los GUID son aún mayores. Rendirse.

Los GUID son 124 bits porque 4 bits contienen el número de versión.

No entiendo por qué nadie ha mencionado la actualización de su tarjeta gráfica ... Seguramente, si tiene un NVIDIA Quadro FX 4800 de alta gama o algo (192 núcleos CUDA), esto iría más rápido ...

Por supuesto, si pudiera pagar unos cuantos NVIDIA Qadro Plex 2200 S4s (con 960 núcleos CUDA cada uno), este cálculo realmente gritaría. ¿Quizás NVIDIA estaría dispuesto a prestarte unos cuantos para una "Demostración de tecnología" como truco de relaciones públicas?

Seguramente ellos querrían ser parte de este cálculo histórico ...

Pero, ¿tiene que estar seguro de tener un duplicado, o solo le importa si puede haber un duplicado? Para asegurarse de que tiene dos personas con el mismo cumpleaños, necesita 366 personas (sin contar el año bisiesto). Para que haya una probabilidad mayor al 50% de tener dos personas con el mismo cumpleaños, solo se necesitan 23 personas. Ese es el problema del cumpleaños .

Si tiene 32 bits, solo necesita 77,163 valores para tener una probabilidad de duplicado superior al 50%. Pruébalo:

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

Ahora 128 bits es mucho, por lo que aún está hablando de un gran número de elementos que aún le dan una baja probabilidad de colisión. Necesitaría el siguiente número de registros para las probabilidades dadas utilizando una aproximación:

0.8 mil millones para una probabilidad de 1/1000 de que ocurra una colisión
21.7 mil millones de dólares para un 50% de probabilidad de que ocurra una colisión
39.6 mil millones para el 90% de probabilidad de que ocurra una colisión

Hay aproximadamente 1E14 correos electrónicos enviados por año, por lo que serían unos 400,000 años a este nivel antes de que tuvieras un 90% de probabilidades de tener dos con el mismo GUID, pero eso es muy diferente a decir que necesitas una computadora 83 mil millones veces la edad del universo o que el sol se enfríe antes de encontrar un duplicado.

Personalmente, creo que el "Big Bang" fue causado cuando dos GUIDs chocaron.

Podrías hash los GUIDs. De esa manera, debería obtener un resultado mucho más rápido.

Oh, por supuesto, ejecutar varios subprocesos al mismo tiempo también es una buena idea, de esa manera aumentará la posibilidad de que una condición de carrera genere el mismo GUID dos veces en diferentes subprocesos.

Por supuesto que los GUID pueden chocar. Dado que los GUID son de 128 bits, solo se generan 2^128 + 1 de ellos y, según el principio del casillero, debe haber una colisión.

Pero cuando decimos que un GUID es único, lo que realmente queremos decir es que el espacio clave es tan grande que es prácticamente imposible generar accidentalmente el mismo GUID dos veces (suponiendo que estamos generando GUID al azar).

Si genera una secuencia de n GUIDs al azar, entonces la probabilidad de que al menos una colisión sea aproximadamente p(n) = 1 - exp(-n^2 / 2 * 2^128) (este es el problema de cumpleaños con el número de cumpleaños posibles siendo 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 . Entonces, si genera mil millones de GUID por segundo, le llevará 36 años generar 2^60 GUID aleatorios, e incluso entonces la probabilidad de que tenga una colisión sigue siendo 1.95e-03 . Es más probable que te asesinen en algún momento de tu vida ( 4.76e-03 ) que si te encontraras con una colisión en los próximos 36 años. Buena suerte.

Puede mostrar eso en tiempo O (1) con una variante del algoritmo de bogosort cuántico .

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

Si está preocupado por la singularidad, siempre puede comprar nuevos GUID para poder deshacerse de los antiguos. Pondré un poco en eBay si quieres.

Si la cantidad de UUID que se genera sigue la ley de Moore, la impresión de no quedarse sin GUID en el futuro previsible es falsa.

Con 2 ^ 128 UUID, solo tomará 18 meses * Log2 (2 ^ 128) ~ = 192 años, antes de que nos agotemos todos los UUID.

Y creo que (sin ninguna prueba estadística) en los últimos años desde la adopción masiva de UUID, la velocidad que estamos generando UUID está aumentando mucho más rápido de lo que dicta la ley de Moore. En otras palabras, probablemente tengamos menos de 192 años hasta que tengamos que lidiar con la crisis UUID, eso es mucho antes que el final del universo.

Pero como definitivamente no los estaremos agotando para fines de 2012, dejaremos que otras especies se preocupen por el problema.

Si las colisiones de GUID son una preocupación, recomendaría usar el ScottGuID en ScottGuID lugar.

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

GUID es un número de 128 bits
No puede generar 2 ^ 128 + 1 o más GUID sin reutilizar los GUID antiguos

Sin embargo, si toda la potencia de salida del sol se dirigiera a realizar esta tarea, se enfriaría mucho antes de que terminara.

Los GUID se pueden generar mediante una serie de tácticas diferentes, algunas de las cuales toman medidas especiales para garantizar que una máquina determinada no genere el mismo GUID dos veces. Encontrar colisiones en un algoritmo particular mostraría que su método particular para generar GUID es malo, pero no probaría nada sobre los GUID en general.

¿No están todos perdiendo un punto importante?

Pensé que los GUID se generaron usando dos cosas que hacen que las posibilidades de que sean únicos a nivel mundial sean bastante altas. Uno de ellos es que están sembrados con la dirección MAC de la máquina en la que se encuentra y dos usan el tiempo que se generaron más un número aleatorio.

Por lo tanto, a menos que lo ejecute en la máquina real y haga todas las conjeturas en el menor tiempo que la máquina utilice para representar un tiempo en el GUID, nunca generará el mismo número, sin importar cuántas conjeturas tome con la llamada del sistema.

Supongo que si sabes la forma real en que se hace un GUID realmente acortaría el tiempo para adivinar bastante.

Tony

[Actualización:] Como señalan los comentarios a continuación, los GUID de MS más nuevos son V4 y no usan la dirección MAC como parte de la generación de GUID (no he visto ninguna indicación de una implementación V5 de MS, así que si alguien tiene una enlace confirmando que me avisas). Sin embargo, con V4, el tiempo sigue siendo un factor, y las probabilidades en contra de la duplicación de GUID siguen siendo tan pequeñas que son irrelevantes para cualquier uso práctico. Ciertamente, no es probable que alguna vez genere un GUID duplicado a partir de una sola prueba del sistema como la que el OP estaba tratando de hacer.

A la mayoría de estas respuestas les falta un punto vital sobre la implementación de GUID de Microsoft. La primera parte del GUID se basa en una marca de tiempo y otra parte se basa en la dirección MAC de la tarjeta de red (o un número aleatorio si no hay una NIC instalada).

Si entiendo esto correctamente, significa que la única forma confiable de duplicar un GUID sería ejecutar generaciones de GUID simultáneas en múltiples máquinas donde las direcciones MAC eran iguales Y donde los relojes de ambos sistemas estaban exactamente en el mismo momento en que la generación Ocurrió (la marca de tiempo se basa en milisegundos si lo comprendo correctamente) .... incluso entonces hay muchos otros bits en el número que son aleatorios, por lo que las probabilidades aún son muy pequeñas.

Para todos los propósitos prácticos, los GUID son universalmente únicos.

Hay una buena descripción de MS GUID en el blog "The Old New Thing"

Aquí también hay una solución:

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

Nota: requiere Qt, pero te garantizo que si lo dejas correr el tiempo suficiente, podría encontrar uno.

(Nota: en realidad, ahora que lo estoy viendo, puede haber algo sobre el algoritmo de generación que impide que dos uuids generados posteriormente colisionen, pero lo dudo).

Como parte de la generación de Guid se basa en el tiempo de la máquina actual, mi teoría para obtener un Guid duplicado es:

Realizar una instalación limpia de Windows.
Cree una secuencia de comandos de inicio que restablezca el tiempo a 2010-01-01 12:00:00 al igual que Windows se inicia.
Justo después del script de inicio, activa tu aplicación para generar un Guid.
Clone esta instalación de Windows, de modo que descarte cualquier diferencia sutil que pueda ocurrir en los siguientes arranques.
Vuelva a crear la imagen del disco duro con esta imagen y arranque la máquina varias veces.

El programa, a pesar de sus errores, muestra la prueba de que un GUID no es único. Aquellos que intentan probar lo contrario están perdiendo el punto. Esta declaración solo demuestra la débil implementación de algunas de las variaciones de GUID.

Un GUID no es necesariamente único por definición, es altamente único por definición. Acabas de refinar el significado de altamente. Dependiendo de la versión, el implementador (MS u otros), el uso de máquinas virtuales, etc., su definición de cambios altamente. (ver enlace en post anterior)

Puedes acortar tu tabla de 128 bits para probar tu punto. La mejor solución es usar una fórmula de hash para acortar la tabla con duplicados y luego usar el valor completo una vez que el hash colisione y, de acuerdo con eso, volver a generar un GUID. Si ejecuta desde diferentes ubicaciones, estaría almacenando sus hash / pares de claves completos en una ubicación central.

Ps: Si el objetivo es generar x número de valores diferentes, cree una tabla hash de este ancho y simplemente verifique el valor hash.

La única solución para probar que los GUID no son únicos sería tener un Grupo Mundial de GUID. Cada vez que se genera un GUID en algún lugar, debe registrarse en la organización. O diablos, podríamos incluir una estandarización de que todos los generadores GUID necesitan registrarlo automáticamente y para eso necesita una conexión activa a Internet.

No estoy en la hoguera aquí, pero en realidad sucede, y sí, entiendo las bromas que le has estado dando a este tipo, pero el GUID es único solo en principio, me topé con este hilo porque hay un error en el emulador WP7, lo que significa que cada vez que se inicia, se entrega el mismo GUID la primera vez que se llama. Entonces, donde en teoría no puede tener un conflicto, si hay un problema que genera dicha GUI, entonces puede obtener duplicados

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

Para mí ... el tiempo que lleva un solo núcleo para generar un UUIDv1 garantiza que será único. Incluso en una situación de varios núcleos, si el generador de UUID solo permite que se genere un UUID a la vez para su recurso específico (tenga en cuenta que múltiples recursos pueden utilizar totalmente los mismos UUID, aunque es poco probable que el recurso sea parte de la dirección). tendrá más que suficientes UUID para que te duren hasta que la marca de tiempo se agote. En ese punto realmente dudo que te importe.

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

No se está incrementando el begin por lo que la condición begin < end siempre es verdadera.