Я пытаюсь создать глобально уникальные идентификаторы в JavaScript. Я не уверен, какие подпрограммы доступны во всех браузерах, насколько «случайным» и затравленным является встроенный генератор случайных чисел и т. Д.
GUID / UUID должен быть не менее 32 символов и должен оставаться в диапазоне ASCII, чтобы избежать проблем при их передаче.
UUID (универсальный уникальный идентификатор), также известный как GUID (глобальный уникальный идентификатор), в соответствии с RFC 4122, являются идентификаторами с определенной гарантией уникальности.
Лучший способ их генерирования — следовать инструкциям по реализации в указанном RFC, использовать одну из многих проверенных реализаций с открытым исходным кодом или использовать встроенную реализацию для языков, в которых она есть.
Некоторые примеры инструментов с открытым исходным кодом для работы с UUID, для некоторых популярных языков программирования перечислены здесь.
JavaScript
PHP
Идти
Рубин
питон
Обратите внимание, что просто случайная генерация идентификаторов побайтово или посимвольно не даст вам таких же гарантий, как соответствующая реализация. Кроме того, очень важно, что системы, работающие с совместимыми UUID, могут не принимать случайно сгенерированные, и многие валидаторы с открытым исходным кодом фактически проверяют правильность структуры.
UUID должен иметь этот формат:
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
Где M а также N позиции могут иметь только определенные значения. В настоящее время единственными допустимыми значениями для M являются 1, 2, 3, 4 и 5, поэтому случайная генерация этой позиции сделает большинство результатов неприемлемыми.
Для RFC4122 решение, совместимое с версией 4, это однострочное (ish) решение — самое компактное, которое я мог придумать:
function uuidv4() {
return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
var r = Math.random() * 16 | 0, v = c == 'x' ? r : (r & 0x3 | 0x8);
return v.toString(16);
});
}
console.log(uuidv4())
Обновление, 2015-06-02Имейте в виду, что уникальность UUID в значительной степени зависит от базового генератора случайных чисел (RNG). Решение выше использует Math.random()
для краткости, однако Math.random()
является не гарантированно будет качественный ГСЧ. Смотрите Адама Хайленда отличная рецензия на Math.random () для деталей. Для более надежного решения рассмотрим что-то вроде модуль uuid[Отказ от ответственности: я автор], который использует API RNG более высокого качества, где это возможно.
Обновление, 2015-08-26: Как примечание, это суть описывает, как определить, сколько идентификаторов может быть сгенерировано до достижения определенной вероятности столкновения. Например, с 3.26×1015 версия 4 RFC4122 UUID у вас есть шанс столкновения 1 на миллион.
Обновление, 2017-06-28: A хорошая статья от разработчиков Chrome обсуждение состояния Math.random PRNG в Chrome, Firefox и Safari. tl; dr — По состоянию на конец 2015 года это «довольно хорошо», но не криптографическое качество. Чтобы решить эту проблему, вот обновленная версия вышеупомянутого решения, которое использует ES6, crypto
API и немного волшебства JS, я не могу взять кредит на:
function uuidv4() {
return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c =>
(c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16)
)
}
console.log(uuidv4());
Мне очень нравится как чисто Бруфа ответ есть, но, к сожалению, плохие реализации Math.random
оставь шанс на столкновение.
Вот похожий RFC4122 совместимое с версией 4 решение, которое решает эту проблему путем смещения первых 13 шестнадцатеричных чисел на шестнадцатеричную часть метки времени. Таким образом, даже если Math.random
на одном и том же начальном этапе оба клиента должны будут сгенерировать UUID в одну и ту же миллисекунду (или более 10 000 лет спустя), чтобы получить тот же UUID:
function generateUUID() { // Public Domain/MIT
var d = new Date().getTime();
if (typeof performance !== 'undefined' && typeof performance.now === 'function'){
d += performance.now(); //use high-precision timer if available
}
return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function (c) {
var r = (d + Math.random() * 16) % 16 | 0;
d = Math.floor(d / 16);
return (c === 'x' ? r : (r & 0x3 | 0x8)).toString(16);
});
}
Ответ broofa довольно приятный, действительно — впечатляюще умный, действительно … rfc4122-совместимый, несколько читабельный и компактный. Потрясающие!
Но если вы посмотрите на это регулярное выражение, те многие replace()
обратные вызовы, toString()
и Math.random()
вызовы функций (когда он использует только 4 бита результата и тратит впустую все остальное), вы можете начать задумываться о производительности. Действительно, joelpt даже решил отказаться от RFC для общей скорости GUID с generateQuickGUID
,
Но мы можем получить скорость а также Соответствие RFC? Я говорю да! Можем ли мы сохранить читабельность? Ну … Не совсем, но это легко, если вы будете следовать.
Но сначала мои результаты, по сравнению с бройфой, guid
(принятый ответ) и не соответствующий RFC generateQuickGuid
:
Desktop Android
broofa: 1617ms 12869ms
e1: 636ms 5778ms
e2: 606ms 4754ms
e3: 364ms 3003ms
e4: 329ms 2015ms
e5: 147ms 1156ms
e6: 146ms 1035ms
e7: 105ms 726ms
guid: 962ms 10762ms
generateQuickGuid: 292ms 2961ms
- Note: 500k iterations, results will vary by browser/cpu.
Таким образом, благодаря шестой итерации оптимизаций, я опередил самый популярный ответ 12X, принятый ответ более 9X, и быстрый несоответствующий ответ 2-3x. И я все еще совместим с rfc4122.
Заинтересованы в том, как? Я поставил полный источник на http://jsfiddle.net/jcward/7hyaC/3/ и на http://jsperf.com/uuid-generator-opt/4
Для объяснения давайте начнем с кода брофы:
'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
return v.toString(16);
});
Так он заменяет x
с любой случайной шестнадцатеричной цифрой, y
со случайными данными (кроме форсирования 2 верхних битов 10
согласно спецификации RFC), и регулярное выражение не соответствует -
или же 4
персонажи, поэтому он не должен иметь с ними дело. Очень, очень гладко.
Первое, что нужно знать, это то, что вызовы функций являются дорогими, как и регулярные выражения (хотя он использует только 1, он имеет 32 обратных вызова, по одному на каждое совпадение, и в каждом из 32 обратных вызовов он вызывает Math.random () и v. ToString (16)).
Первым шагом к производительности является устранение RegEx и его функций обратного вызова и использование вместо этого простого цикла. Это означает, что мы должны иметь дело с -
а также 4
символов, тогда как брофа нет. Кроме того, обратите внимание, что мы можем использовать индексирование String Array, чтобы сохранить его простую архитектуру шаблона String:
function e1() {
var u='',i=0;
while(i++<36) {
var c='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'[i-1],r=Math.random()*16|0,v=c=='x'?r:(r&0x3|0x8);
u+=(c=='-'||c=='4')?c:v.toString(16)
}
return u;
}
По сути, та же самая внутренняя логика, за исключением того, что мы проверяем -
или же 4
и используя цикл while (вместо replace()
обратные вызовы) дает нам почти 3х улучшение!
Следующим шагом будет небольшой шаг на рабочем столе, но он будет иметь большое значение для мобильных устройств. Давайте сделаем меньше вызовов Math.random () и используем все эти случайные биты вместо того, чтобы выбрасывать 87% из них со случайным буфером, который смещается при каждой итерации. Давайте также уберем это определение шаблона из цикла, на случай, если это поможет:
function e2() {
var u='',m='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx',i=0,rb=Math.random()*0xffffffff|0;
while(i++<36) {
var c=m[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8);
u+=(c=='-'||c=='4')?c:v.toString(16);rb=i%8==0?Math.random()*0xffffffff|0:rb>>4
}
return u
}
Это экономит нам 10-30% в зависимости от платформы. Неплохо. Но следующий большой шаг избавляет от вызовов функции toString вместе с классикой оптимизации — справочной таблицей. Простая 16-элементная таблица поиска выполнит работу toString (16) за гораздо меньшее время:
function e3() {
var h='0123456789abcdef';
var k='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx';
/* same as e4() below */
}
function e4() {
var h=['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'];
var k=['x','x','x','x','x','x','x','x','-','x','x','x','x','-','4','x','x','x','-','y','x','x','x','-','x','x','x','x','x','x','x','x','x','x','x','x'];
var u='',i=0,rb=Math.random()*0xffffffff|0;
while(i++<36) {
var c=k[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8);
u+=(c=='-'||c=='4')?c:h[v];rb=i%8==0?Math.random()*0xffffffff|0:rb>>4
}
return u
}
Следующая оптимизация — еще одна классика. Поскольку в каждой итерации цикла мы обрабатываем только 4-битные выходные данные, давайте сократим количество циклов пополам и обработаем 8-битные в каждой итерации. Это сложно, так как нам все еще приходится обрабатывать битовые позиции, соответствующие RFC, но это не слишком сложно. Затем нам нужно создать таблицу поиска большего размера (16×16 или 256) для хранения 0x00 — 0xff, и мы создадим ее только один раз, вне функции e5 ().
var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); }
function e5() {
var k=['x','x','x','x','-','x','x','-','4','x','-','y','x','-','x','x','x','x','x','x'];
var u='',i=0,rb=Math.random()*0xffffffff|0;
while(i++<20) {
var c=k[i-1],r=rb&0xff,v=c=='x'?r:(c=='y'?(r&0x3f|0x80):(r&0xf|0x40));
u+=(c=='-')?c:lut[v];rb=i%4==0?Math.random()*0xffffffff|0:rb>>8
}
return u
}
Я попробовал e6 (), который обрабатывает 16 бит одновременно, используя LUT из 256 элементов, и он показал убывающую отдачу от оптимизации. Несмотря на меньшее количество итераций, внутренняя логика усложнялась из-за увеличения обработки, и она выполняла то же самое на настольном компьютере и только на ~ 10% быстрее на мобильном устройстве.
Последняя применяемая техника оптимизации — разверните цикл. Поскольку мы зацикливаемся фиксированное количество раз, технически мы можем выписать все это вручную. Я попробовал это однажды с одной случайной переменной r, которую я продолжал перераспределять, и производительность снижалась. Но с четырьмя переменными, которым заранее назначены случайные данные, затем с помощью таблицы поиска и применения правильных битов RFC, эта версия выкуривает их все:
var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); }
function e7()
{
var d0 = Math.random()*0xffffffff|0;
var d1 = Math.random()*0xffffffff|0;
var d2 = Math.random()*0xffffffff|0;
var d3 = Math.random()*0xffffffff|0;
return lut[d0&0xff]+lut[d0>>8&0xff]+lut[d0>>16&0xff]+lut[d0>>24&0xff]+'-'+
lut[d1&0xff]+lut[d1>>8&0xff]+'-'+lut[d1>>16&0x0f|0x40]+lut[d1>>24&0xff]+'-'+
lut[d2&0x3f|0x80]+lut[d2>>8&0xff]+'-'+lut[d2>>16&0xff]+lut[d2>>24&0xff]+
lut[d3&0xff]+lut[d3>>8&0xff]+lut[d3>>16&0xff]+lut[d3>>24&0xff];
}
Modualized: http://jcward.com/UUID.js — UUID.generate()
Самое смешное, что генерация 16 байтов случайных данных — самая простая часть. Весь трюк состоит в том, чтобы выразить его в формате String с соблюдением требований RFC, и он наиболее тщательно выполнен с 16 байтами случайных данных, развернутым циклом и таблицей поиска.
Я надеюсь, что моя логика верна — очень легко ошибиться в этом утомительном занятии. Но результаты выглядят хорошо для меня. Надеюсь, вам понравилась эта безумная поездка благодаря оптимизации кода!
Имейте в виду: моей главной целью было показать и научить потенциальных стратегий оптимизации. Другие ответы охватывают важные темы, такие как столкновения и действительно случайные числа, которые важны для создания хороших UUID.
Вот код, основанный на RFC 4122, раздел 4.4 (Алгоритмы для создания UUID из действительно случайного или псевдослучайного числа).
function createUUID() {
// http://www.ietf.org/rfc/rfc4122.txt
var s = [];
var hexDigits = "0123456789abcdef";
for (var i = 0; i < 36; i++) {
s[i] = hexDigits.substr(Math.floor(Math.random() * 0x10), 1);
}
s[14] = "4"; // bits 12-15 of the time_hi_and_version field to 0010
s[19] = hexDigits.substr((s[19] & 0x3) | 0x8, 1); // bits 6-7 of the clock_seq_hi_and_reserved to 01
s[8] = s[13] = s[18] = s[23] = "-";
var uuid = s.join("");
return uuid;
}
Самый быстрый GUID, как метод строкового генератора в формате XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX
, Это не генерирует стандартный GUID.
Десять миллионов выполнений этой реализации занимают всего 32,5 секунды, что является самым быстрым, что я когда-либо видел в браузере (единственное решение без циклов / итераций).
Функция так же проста, как:
/**
* Generates a GUID string.
* @returns {String} The generated GUID.
* @example af8a8416-6e18-a307-bd9c-f2c947bbb3aa
* @author Slavik Meltser ([email protected]).
* @link http://slavik.meltser.info/?p=142
*/
function guid() {
function _p8(s) {
var p = (Math.random().toString(16)+"000000000").substr(2,8);
return s ? "-" + p.substr(0,4) + "-" + p.substr(4,4) : p ;
}
return _p8() + _p8(true) + _p8(true) + _p8();
}
Чтобы проверить производительность, вы можете запустить этот код:
console.time('t');
for (var i = 0; i < 10000000; i++) {
guid();
};
console.timeEnd('t');
Я уверен, что большинство из вас поймет, что я там делал, но, возможно, есть хотя бы один человек, которому понадобится объяснение:
Алгоритм:
Math.random()
функция возвращает десятичное число от 0 до 1 с 16 цифрами после запятой (для0.4363923368509859
).0.6fb7687f
).Math.random().toString(16)
,0.
префикс (0.6fb7687f
=>6fb7687f
) и получить строку с восемью шестнадцатеричными(Math.random().toString(16).substr(2,8)
,Math.random()
функция вернется0.4363
), из-за нулей в конце (из примера выше, на самом деле число 0.4363000000000000
). Вот почему я добавляю в эту строку "000000000"
(строка с девятью нулями), а затем отрезать его substr()
функция, чтобы сделать его ровно девятью символами (заполняя нули справа).Math.random()
функция вернет ровно 0 или 1 (вероятность 1/10 ^ 16 для каждого из них). Вот почему нам нужно было добавить девять нулей ("0"+"000000000"
или же "1"+"000000000"
), а затем обрезать его из второго индекса (3-й символ) длиной восемь символов. В остальных случаях добавление нулей не повредит результату, так как он все равно обрезает его.Math.random().toString(16)+"000000000").substr(2,8)
,Ассамблея:
XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX
,XXXXXXXX
а также -XXXX-XXXX
,XXXXXXXX
-XXXX-XXXX
-XXXX-XXXX
XXXXXXXX
,_p8(s)
, s
Параметр сообщает функции, следует ли добавлять тире или нет._p8() + _p8(true) + _p8(true) + _p8()
и вернуть его.Ссылка на этот пост в моем блоге
Наслаждайтесь! 🙂
var uniqueId = Math.random().toString(36).substring(2)
+ (new Date()).getTime().toString(36);
document.getElementById("unique").innerHTML =
Math.random().toString(36).substring(2) + (new Date()).getTime().toString(36);
<div id="unique">
</div>
Вот комбинация Топ проголосовал ответ, с обходным путем для Столкновения Chrome:
generateGUID = (typeof(window.crypto) != 'undefined' &&
typeof(window.crypto.getRandomValues) != 'undefined') ?
function() {
// If we have a cryptographically secure PRNG, use that
// https://stackoverflow.com/questions/6906916/collisions-when-generating-uuids-in-javascript
var buf = new Uint16Array(8);
window.crypto.getRandomValues(buf);
var S4 = function(num) {
var ret = num.toString(16);
while(ret.length < 4){
ret = "0"+ret;
}
return ret;
};
return (S4(buf[0])+S4(buf[1])+"-"+S4(buf[2])+"-"+S4(buf[3])+"-"+S4(buf[4])+"-"+S4(buf[5])+S4(buf[6])+S4(buf[7]));
}
:
function() {
// Otherwise, just use Math.random
// https://stackoverflow.com/questions/105034/how-to-create-a-guid-uuid-in-javascript/2117523#2117523
return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
return v.toString(16);
});
};
На jsbin если вы хотите проверить это.