Простое доказательство, что GUID не уникален [закрытый]
Папка по умолчанию является на самом деле тем же как текущей рабочей папкой для буфера, т.е. это может отличаться для каждого файла, с которым Вы работаете. Скажите, что файл, с которым Вы работаете, расположен в C:\dir_a, тогда рабочий каталог для того буфера по умолчанию будет C:\dir_a. Можно изменить это с M-x cd и ввести в любом каталоге, требуется быть значением по умолчанию вместо этого (и по умолчанию я имею в виду тот, который обнаружится, когда Вы сделаете C-x C-f).
при запуске emacs, не открывая файл Вы закончите с *scratch* открытый буфер. При запуске emacs с ярлыка Windows рабочий каталог совпадет с, который определил в свойствах ярлыка. При запуске его с командной строки это будет каталог от того, где Вы запустили его. Можно все еще изменить этот каталог по умолчанию с M-x cd, также от эти *scratch* буфер.
Наконец, можно сделать, как Vadim предполагает и поместил
(cd "c:/dir_a/")
в Вашем .emacs файл, для создания того каталога значением по умолчанию, неважно, как Вы запускаете emacs.
22 ответа
Кай, я предоставил программу которые будут делать то, что вы хотите, используя потоки. Он лицензируется на следующих условиях: вы должны платить мне 0,0001 доллара в час за каждое ядро процессора, на котором он запущен. Сборы уплачиваются в конце каждого календарного месяца. Пожалуйста, свяжитесь со мной для получения информации о моей учетной записи PayPal при первой же возможности.
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: Я хотел опробовать библиотеку параллельных расширений. Это было легко.
И использование OutOfMemoryException в качестве потока управления кажется неправильным.
EDIT
Что ж, похоже, это все еще привлекает голоса. Итак, я исправил проблему с GC.KeepAlive (). И изменил его на работу с C # 4.
И чтобы уточнить условия моей поддержки: поддержка доступна только 28 февраля 2010 года. As always, the GC does a better job than I do at managing memory; any previous attempts at doing it myself were doomed to failure.
Вы пробовали begin = begin + new BigInteger ((long) 1) вместо begin ++?
for(begin; begin<end; begin)
Console.WriteLine(System.Guid.NewGuid().ToString());
Вы не увеличиваете begin , поэтому условие begin
Предположительно у вас есть основания полагать что алгоритм создания Guids не производит действительно случайных чисел, а фактически циклически повторяется с периодом << 2 ^ 128.
например, метод RFC4122, используемый для получения идентификаторов GUID, который фиксирует значения некоторых битов.
Доказательство цикличности будет зависеть от возможного размера периода.
Для малых периодов используется хеш-таблица хешей (GUID) -> GUID с заменой при столкновении если GUID не совпадают (прекратить, если они совпадают), может быть подход. Также подумайте о том, чтобы производить замену только в случайной части времени.
В конечном итоге, если максимальный период между столкновениями достаточно велик (и не известен заранее), любой метод даст только вероятность того, что столкновение будет обнаружено если бы он существовал.
Обратите внимание, что если метод создания Guids основан на часах (см. RFC), то может быть невозможно определить, существуют ли коллизии, потому что либо (а) вы не сможете ждать достаточно долго, пока часы или (b) вы не можете запросить достаточное количество Guid за один такт часов, чтобы вызвать коллизию.
В качестве альтернативы вы можете показать статистическую связь между битами в Guid или корреляцию битов между Guid . Такая взаимосвязь может сделать весьма вероятным, что алгоритм ошибочен, но при этом не обязательно обнаруживать реальную коллизию.
Конечно, если вы просто хотите доказать, что гиды могут сталкиваться, то ответом будет математическое доказательство, а не программа.
Вы все не упускаете одну важную вещь?
Я думал, что идентификаторы GUID были сгенерированы с использованием двух вещей, которые делают их глобальными уникальный довольно высокий. Во-первых, они заполняются MAC-адресом компьютера, на котором вы находитесь, а во-вторых, они используют время, которое они были сгенерированы, плюс случайное число.
Так что, если вы не запустите его на реальной машине и не запустите все, что вы предполагаете в пределах наименьшее количество времени, которое машина использует для представления времени в GUID, вы никогда не сгенерируете одно и то же число, независимо от того, сколько предположений вы сделаете с помощью системного вызова.
Counting to 2^128 - ambitious.
Lets imagine that we can count 2^32 IDs per second per machine - not that ambitious, since it's not even 4.3 billion per second. Lets dedicate 2^32 machines to that task. Furthermore, lets get 2^32 civilisations to each dedicate the same resources to the task.
So far, we can count 2^96 IDs per second, meaning we will be counting for 2^32 seconds (a little over 136 years).
Now, all we need is to get 4,294,967,296 civilisations to each dedicate 4,294,967,296 machines, each machine capable of counting 4,294,967,296 IDs per second, purely to this task for the next 136 years or so - I suggest we get started on this essential task right now ;-)
Here's a nifty little extension method that you can use if you want to check guid uniqueness in many places in your code.
internal static class GuidExt
{
public static bool IsUnique(this Guid guid)
{
while (guid != Guid.NewGuid())
{ }
return false;
}
}
To call it, simply call Guid.IsUnique whenever you generate a new guid...
Guid g = Guid.NewGuid();
if (!g.IsUnique())
{
throw new GuidIsNotUniqueException();
}
...heck, I'd even recommend calling it twice to make sure it got it right in the first round.
Любые два идентификатора GUID, скорее всего, уникальны (не равны).
См. эту запись SO и из Википедии
Хотя каждый сгенерированный GUID является не гарантированно уникальна, общая количество уникальных ключей (2 ^ 128 или 3,4 × 10 ^ 38) настолько велико, что вероятность того, что то же число сгенерировано дважды, очень мало. За Например, рассмотрим наблюдаемый Вселенная, которая содержит около 5 × 10 ^ 22 звезды; тогда каждая звезда могла бы иметь 6,8 × 10 ^ 15 универсально уникальных идентификаторов GUID.
Так что, вероятно, вам придется подождать еще много миллиардов лет и надеяться, что вы попадете в него раньше, чем Вселенная, как мы знаем, подходит к концу.
If you're worried about uniqueness you can always purchase new GUIDs so you can throw away your old ones. I'll put some up on eBay if you'd like.
Of course GUIDs can collide. Since GUIDs are 128-bits, just generate 2^128 + 1 of them and by the pigeonhole principle there must be a collision.
But when we say that a GUID is a unique, what we really mean is that the key space is so large that it is practically impossible to accidentally generate the same GUID twice (assuming that we are generating GUIDs randomly).
If you generate a sequence of n GUIDs randomly, then the probability of at least one collision is approximately p(n) = 1 - exp(-n^2 / 2 * 2^128) (this is the birthday problem with the number of possible birthdays being 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
To make these numbers concrete, 2^60 = 1.15e+18. So, if you generate one billion GUIDs per second, it will take you 36 years to generate 2^60 random GUIDs and even then the probability that you have a collision is still 1.95e-03. You're more likely to be murdered at some point in your life (4.76e-03) than you are to find a collision over the next 36 years. Good luck.
GUID теоретически не уникален. Вот ваше доказательство:
- GUID - это 128-битное число
- Вы не можете сгенерировать 2 ^ 128 + 1 или более GUID без повторного использования старых GUID
Однако, если вся выходная мощность солнца была направлена на выполнение Эта задача остыла бы задолго до ее завершения.
GUID могут быть сгенерированы с использованием ряда различных тактик, некоторые из которых требуют специальных мер, чтобы гарантировать, что данная машина не будет генерировать один и тот же GUID дважды. Обнаружение коллизий в конкретном алгоритме покажет, что ваш конкретный метод генерации GUID плох, но ничего не докажет о GUID в целом.
Это будет работать намного больше, чем часы. Предполагая, что он будет работать на частоте 1 ГГц (чего не будет - он будет намного медленнее), он проработает 10790283070806014188970 лет. Что примерно в 83 миллиарда раз больше возраста Вселенной.
Если предположить, что закон Мура соблюдается, было бы намного быстрее не запускать эту программу, подождать несколько сотен лет и запустить ее на компьютере это в миллиарды раз быстрее. Фактически, любая программа, выполнение которой занимает больше времени, чем требуется для удвоения скорости процессора (около 18 месяцев), завершится раньше, если вы дождетесь увеличения скорости процессора и купите новый процессор перед его запуском (если вы не напишете его так, чтобы он может быть приостановлено и возобновлено на новом оборудовании).
Вы можете хэшировать идентификаторы GUID. Таким образом, вы должны получить результат намного быстрее.
О, конечно, одновременное выполнение нескольких потоков также является хорошей идеей, так вы увеличите вероятность того, что условие гонки генерирует один и тот же GUID дважды на разные нити.
Вы можете показать это за время O (1) с помощью варианта квантового алгоритма богосорта .
Guid g1 = Guid.NewGuid();
Guid g2 = Guid.NewGuid();
if(g1 != g2) Universe.Current.Destroy();
[Обновление:] Как указано в комментариях ниже, более новые идентификаторы GUID MS V4 и не использовать MAC-адрес как часть генерации GUID (хотя я не видел никаких указаний на реализацию V5 от MS, поэтому, если у кого-то есть ссылка, подтверждающая это, дайте мне знать). Тем не менее, с V4 время все еще является фактором, и вероятность дублирования GUID остается настолько малой, что не имеет значения для любого практического использования. Вы, конечно, вряд ли когда-нибудь сгенерируете дублированный GUID из всего лишь одного системного теста, такого как OP, который пытался выполнить.
В большинстве этих ответов отсутствует один важный момент, касающийся реализации GUID Microsoft. Первая часть GUID основана на метке времени, а другая часть основана на MAC-адресе сетевой карты (или случайном числе, если сетевая карта не установлена).
Если я правильно понимаю, это означает, что единственный надежный способ дублировать GUID - это запускать одновременное создание GUID на нескольких машинах, где MAC-адреса были одинаковыми И где часы на обеих системах были в одно и то же точное время. когда произошла генерация (временная метка основана на миллисекундах, если я правильно понимаю) .... даже тогда в числе много других битов, которые являются случайными, так что шансы все еще исчезающе малы.
Для всех практические цели GUID универсально уникальны.
Существует довольно хорошее описание MS GUID на "The Old New Thing" блог
Я не понимаю, почему никто не упомянул об обновлении вашей видеокарты ... Конечно, если бы у вас была высокопроизводительная NVIDIA Quadro FX 4800 или что-то в этом роде (192 ядра CUDA), это было бы быстрее ...
Конечно, если бы вы могли позволить себе несколько NVIDIA Qadro Plex 2200 S4 (по 960 ядер CUDA каждый), этот расчет действительно кричал бы. Возможно, NVIDIA захочет одолжить вам несколько для «демонстрации технологий» в качестве пиар-трюка?
Конечно, они хотели бы участвовать в этом историческом вычислении ...
Если время работы в 83 миллиарда лет вас не пугает, подумайте, что вам также нужно будет где-то хранить сгенерированные GUID, чтобы проверить, нет ли у вас дубликата; хранение 2^128 16-байтовых чисел потребует от вас всего лишь 4951760157141521099596496896 терабайт оперативной памяти, так что представьте, что у вас есть компьютер, который может все это вместить, и что вы каким-то образом найдете место, где можно купить терабайтные модули DIMM по 10 грамм каждый, вместе они будут весить более 8 масс Земли, так что вы можете серьезно сдвинуть его с текущей орбиты, еще до того, как нажмете кнопку "Run". Подумайте дважды!
Программа, хотя и содержит ошибки, демонстрирует доказательство того, что GUID не уникален. Те, кто пытается доказать обратное, упускают из виду главное. Это утверждение просто доказывает слабую реализацию некоторых вариантов GUID.
GUID не обязательно должен быть уникальным по определению, он в высшей степени уникален по определению. Вы только что уточнили значение слова «высоко». В зависимости от версии, разработчика (MS или других), использования виртуальных машин и т. Д. Ваше определение сильно меняется. (см. ссылку в предыдущем посте)
Вы можете сократить свою 128-битную таблицу, чтобы доказать свою точку зрения. Лучшее решение - использовать хеш-формулу, чтобы сократить вашу таблицу дубликатами, а затем использовать полное значение после столкновения хеша и на основе этого повторно сгенерировать GUID. При запуске из разных мест вы должны хранить свои пары хэш / полные ключи в центральном месте.
Ps: Если цель состоит в том, чтобы просто сгенерировать x различных значений, создайте хеш-таблицу такой ширины и просто проверьте хеш-значение.
Если конфликты GUID вызывают беспокойство, я бы рекомендовал использовать вместо него ScottGuID .
Лично я думаю, что «Большой взрыв» был вызван столкновением двух идентификаторов GUID.
Вероятность ошибки в коде генерации GUID намного выше, чем вероятность того, что алгоритм генерирует коллизию. Вероятность ошибки в вашем коде для проверки GUID еще выше. Сдавайтесь.
Идентификаторы GUID имеют длину 124 бита, поскольку 4 бита содержат номер версии.