ОШИБКА 1140 (42000) В агрегированном запросе без GROUP BY, выражение # 1

Ответ

broofa довольно гладкий, действительно - впечатляюще умный, действительно ... rfc4122 совместимый, несколько читаемый и компактный. Awesome!

Но если вы смотрите на это регулярное выражение, эти многие replace() обратные вызовы, toString() и Math.random() вызовы функций (где он использует только 4 бита результата и тратит впустую остальное), вы можете начать задаваться вопросом о производительности. Действительно, joelpt даже решил выбросить RFC для общей скорости GUID с помощью generateQuickGUID.

Но можем ли мы получить соответствие скорости и RFC? Я сказал да! Можем ли мы поддерживать читаемость? Ну ... Не совсем, но это легко, если вы будете следовать.

Но сначала мои результаты, по сравнению с broofa, 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.

Итак, на моей 6-й итерации оптимизаций я обыграл самый популярный ответ более чем на 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 обратных вызова, по одному для каждого совпадения и в каждом из

Первый шаг к производительности - это исключить RegEx и его функции обратного вызова и вместо этого использовать простой цикл. Это означает, что мы должны иметь дело с символами - и 4, тогда как broofa этого не делал. Также обратите внимание, что мы можем использовать индексирование 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 и использование в то время как цикл (вместо обратных вызовов 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, но это не так сложно. Затем мы должны сделать более крупную таблицу поиска (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 бит за раз, все еще используя 256-элементный LUT, и показал уменьшающуюся отдачу от оптимизации. Хотя у него было меньше итераций, внутренняя логика осложнялась увеличением обработки, и она выполнялась на рабочем столе одинаково, и только на 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.