Ответ
брофы довольно приятный, действительно - впечатляюще умный, действительно ... 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() обратных вызовов) дает нам почти трехкратное улучшение!
Следующим шагом является небольшой шаг на рабочем столе, но он имеет существенное значение для мобильных устройств. Давайте сделаем меньше вызовов 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, но это не так уж сложно. Затем нам нужно создать таблицу просмотра большего размера (16x16 или 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];
}
Модулированный: http://jcward.com/UUID.js - UUID.generate()
Самое смешное, генерировать 16 байтов случайных данных - это самая простая часть. Весь трюк состоит в том, чтобы выразить его в формате String с соблюдением требований RFC, и это наиболее точно достигается с помощью 16 байтов случайных данных, развернутого цикла и таблицы поиска.
Я надеюсь, что моя логика верна - очень легко ошибиться в этом утомительном занятии. Но результаты выглядят хорошо для меня. Надеюсь, вам понравилась эта безумная поездка благодаря оптимизации кода!
Имейте в виду: Моя основная цель состояла в том, чтобы показать и обучить потенциальным стратегиям оптимизации. Другие ответы охватывают важные темы, такие как столкновения и действительно случайные числа, которые важны для создания хороших UUID.