Обратиться к теме написания случайных генераторов букв навела мысль о том, что в JS существует нетипичная нативная функция преобразования строки в n-ичное число, где n = 2..36. 36 в стандарте языка придумано не случайно — это сумма количества цифр и малых английских букв, из которых предлагается писать такие числа. Это значит, что парой нативных функций уже можно построить полезный генератор небольших строк из буквоцифр.
Math.random().toString(36) //даст числа вида 0.816cwugw2ky, 0.opgqwav8w1m, 0.f0w4ejtq8wk, ...
Это значит, что для некоторых задач можно не писать относительно честные генераторы на основе унылых строк вида «abcdefghijklmno...».
Результаты можно использовать в любом языке программирования, в котором получим любым путём используемые функции, но будем говорить о джаваскрипте, поскольку длина и простота функций в виде текста в браузере имеет значение в различных практических задачах.
Узнав о ключевых словах, легко нагуглить достижения в строительстве случайных генераторов буквоцифр, которые предлагаются, в частности, на StackOverflow. Можно видеть забавную картину, что сначала пишут добросовестный многословный алгоритм с выбором символов из строки, его бешено плюсуют, как здесь, потом кто-то вспоминает, что есть такой очень краткий способ, который иногда очень хорошо ложится в решение задачи. Правда, не всегда доводят дело до конца, и решение нужно допиливать, самостоятельно оценивать скорость и наглядность решения.
Рассмотрим варианты решений под разные типичные задачи. Попробуем оценить быстродействие некоторых решений — иногда нужно генерировать случайные строки в больших объёмах. В результате получится рассказ о методах и их сравнение. Посмотрим, о чём обычно спрашивают в интернете, когда речь касается генерации случайных символов.
Не будем касаться вопросов качества случайных последовательностей — возьмём за основу генератор Math.random(). Его улучшения сильно зависят от потребностей и есть тема отдельного исследования. Не будем забывать о балансе вероятностей появления различных символов, чтобы наш алгоритм не ухудшал вероятности распределения чисел или символов. Рассмотрим и классические алгоритмы с последовательностью символов в качестве образца для генератора.
Задача в общем виде ставится так:
"Нужно получить последовательность случайных символов (цифр, букв, больших и малых букв, всего вместе, букв национального алфавита) так, чтобы вероятность появления любого символа была равной для всех символов."
Если вопрос касается небольшого количества цифр, то решение уже есть, надо лишь отрезать нужный их кусок от результата функции Math.random().
function randN(n){ // [ 1 ] random numbers
return (Math.random()+'').slice(2, 2 + Math.max(1, Math.min(n, 15)) );
}
Посмотрим сначала, с чем придётся иметь дело: сколько цифр после точки даёт функция Math.random().
Chrome30: 0.5439428824465722
Firefox24:0.8270932732750623
Opera 12: 0.1945655094774541
IE8: 0.48207786689050286
В двоичном представлении (javascript: Math.random().toString(2)):
Chrome30: 0.10010010010000001000110001001001
Firefox24:0.1000101010011110010101000000110000110010010101111001
Opera 12: 0.11000111010010011011101000110100000000100110000011111
IE8: 0.10000011001010000101111011000010000101001001110001
В 36-ричном (javascript: Math.random().toString(36)):
Chrome30: 0.acpi1knlm53tyb9
Firefox24:0.r9pe3mirhw
Opera 12: 0.kmzlo986rok
IE8: 0.33t3if0bsh6j
Как видим, надо быть осторожными и в ожидании количества цифр, и в точности, зависящей от системы счисления. За минимальный предел надо брать минимальное из показанного количества цифр и полностью не верить никому. Среди десятичных цифр показан минимум — 16, поэтому максимальным числом взяли 15, что и без того чересчур оптимистично, но и ценность нашей первой функции небольшая.
Результаты профилирования функции randN() без проверки пределов (300 тыс. циклов по 15 символов в каждом, значения в миллисекундах, усреднение по 20 измерениям — всего вычислено 300000*15*20 = 90 млн. символов):
Ch30: 240.2 ± 2.47%
Fx24: 770.8 ± 1.68%
Op12: 274.9 ± 3.89%
IE8 : 1020.4 ± 0.71%
<div class="resTest">
<table class=resTable>
<tr><td class=randN></td></tr>
</table>
<script src="jquery-1.9.1.js"></script>
<script type="text/javascript">
onload = function(){
var tSred = function(a){
var s =0;
for(var i =0, iL = a.length; i < iL; i++)
s += a[i];
return s / iL;
};
var tSigm = function(a){
var s = 0, f2 = 0;
for(var i =0, iL = a.length; i < iL; i++){
f2 += a[i] * a[i];
s += a[i];
}
s = s / iL;
return Math.sqrt(f2 / iL - s * s);
};
var randN = function(n){
return (Math.random()).toString().slice(2)
}
,testName ='randN'
,nIzmer =20
,timeS =[];
for(var j =0; j < nIzmer; j++){
var i =3e5
,time0 = +new Date();
while(i-- >0)
randN(15);
timeS.push(new Date() - time0);
}
var sred = tSred(timeS).toFixed(1)
,sigm = (tSigm(timeS) / sred *100 ).toFixed(2)
,nu = navigator.userAgent
,br = /MSIE/.test(nu) ?'IE8 : ': /Opera/.test(nu) ?'Op12: ': /Firefox/.test(nu) ?'Fx24: ':'Ch30: '
$('.resTest .resTable .'+ testName).html(br + sred +' ± '+ sigm +'% | '+ timeS.join(', '));
};</script></div>То же, но с проверкой пределов аргумента:
Ch30: 238.4 ± 4.16%
Fx24: 782.5 ± 1.84%
Op12: 303.1 ± 3.18%
IE8 : 1230.5 ± 0.56%
Первый поучительный вывод: хотя проверки кажутся быстрыми операциями, не везде они сделаны по-настоящему быстрыми.
Накладные расходы в этом профилировании занимают очень немного и находятся в пределах погрешностей: если поставить пустой цикл, его скорость прохода вычисляется как в 100-300 раз более быстрая (от 0.5 до 10 мс за те же 300 тыс. циклов). Сообщения о том, не пора ли остановить скрипты, для тестов в браузерах специально отключены. Таким образом, мы измеряем именно то, что хотим. Имеет смысл лишь сравнение показателей, сделанных на одном компьютере. Если захотим сделать сравнение с IE10, во всех остальных браузерах придётся повторить тесты — операционная система будет другая и скорости как браузеров, так и компьютерного «железа» — другие.
Уже интересно? А ведь это была всего лишь подготовка инструментов для настоящего исследования. Они будут работать для всех остальных измерений, отличаться будет основной цикл и общее заданное их число. Полученная функция [ 1 ] randN() даёт нам очень немного: всего лишь строчку до 15 случайных цифр. А впереди — буквы, цифры с буквами, русские и другие национальные. Самое интересное будет — сравнить, насколько отличается по скорости применение нативных функций вида .toString(36) по сравнению с более традиционным кросс-языковым алгоритмом.
Латинские буквоцифры
В этом есть небольшой национализм, поэтому в заголовок закралась политкорректная формулировка. Уже французы и испанцы останутся недовольны тем, что не все их буквы алфавита входят в предлагаемый набор. Но она будет полезна для генерации случайных имён, пусть лишь с одними маленькими латинскими буквами.
Предположим для начала, что нам не нужно будет очень много буквоцифр — максимум 10 вполне хватит, которые сможет выдавить из себя Firefox.
function randWD(n){ // [ 2 ] random words and digits
return Math.random().toString(36).slice(2, 2 + Math.max(1, Math.min(n, 10)) );
} //result is such as "46c17fkfpl"
Как изменились скорости (с проверкой пределов: мы же — серьёзные люди)?
Ch30: 195.4 ± 3.17%
Fx24: 1049.0 ± 1.26%
Op12: 421.6 ± 2.46%
IE8 : 1150.8 ± 0.66%
Кое-кто прошёл тест в 1.5 раза дольше, Хром вообще показал чудеса, выполнив преобразование в 36-ричное быстрее, чем в десятичное (а двоичное он просчитал за 350 мс), IE — немного быстрее себя, за пределами погрешностей.
Основной итог такой: ничего не потеряв, мы вычислили буквоцифры примерно так же быстро, как и случайные числа.
Сравним теперь скорости с унылым классическим алгоритмом, где нужно руками набирать весь алфавит и цифры впридачу. Не хотелось его писать, но наука требует жертв.
Буквоцифры из классики
randWDclassic = function(n){ // [ 3 ] random words and digits by the wocabulary
var s ='', abd ='abcdefghijklmnopqrstuvwxyz0123456789', aL = abd.length;
while(s.length < n)
s += abd[Math.random() * aL|0];
return s;
} //such as "46c17fkfpl"
Ch30: 226.4 ± 0.95%
Fx24: 1006.4 ± 0.93%
Op12: 917.3 ± 1.14%
IE8 : 1268.0 ± 0.45%
Он вычислил 15 символов в тесте вместо 10 в прежнем алгоритме, показал в среднем даже хорошие результаты, и у него нет проблем с масштабированием. Из минусов — надо много буковок писать. Но ведь и первый алгоритм не сказал своего последнего слова. Большой плюс алгоритма со строкой — возможность собрать строку из любых символов и даже предусмотреть в ней частотность символов, правда, кратную относительно минимальной частоты встречаемости единственного упомянутого символа.
Значит, в этом алгоритме решаются вообще все поставленные задачи и сверх того, вопросы частотности. Может ли нативная toString(36) противопоставить что-то и занять хотя бы часть ниши? Ведь у неё — малые латинские буквоцифры на выдаче или только цифры, а на stackoverflow хотят всё, что только можно себе представить: малые с большими, буквы без цифр, не за горами — национальные наборы.
Реванш toString(36)
Нужно решить 2 проблемы с этим подходом: обеспечить масштабируемость и хотя бы научиться выдавать только цифры. Тогда, если алгоритм будет быстр, он займёт свою нишу. Уже хотя бы потому, что он краток.
Воспользуемся тем, что сможем набирать строку из нескольких символов за 1 раз.
function randWDn(n){ // [ 4 ] random words and digits unlimited
var s ='';
while(s.length < n)
s += Math.random().toString(36).slice(2, 12);
return s.substr(0, n);
}
Ch30: 440.6 ± 0.49%
Fx24: 1760.2 ± 5.05%
Op12: 858.8 ± 1.36%
IE8 : 2495.3 ± 0.35%
Вычислялось 15 символов (фактически, не менее 20), функция масштабируема, может брать любой положительный аргумент. В целом сравнение выглядит довольно провально: алгоритм с toString(36) играет роль догоняющего, сравниваясь по скорости в районах 10, 20, 30, символов и проигрывая в промежутках. При этом поддерживает только 2 (пока что) набора символов: цифры и буквоцифры. Можно ли его распространить на буквы, не теряя в краткости? Да.
function randWn(n){ // [ 5 ] random words
var s ='';
while(s.length < n)
s += Math.random().toString(36).replace(/d|_/g,'').slice(2, 12);
return s.substr(0, n);
} //such as "amyozispiizmmrb"
Ch30: 785.6 ± 0.80%
Fx24: 3121.6 ± 4.58%
Op12: 1985.5 ± 0.62%
IE8 : 5967.2 ± 0.16%
Что тут сказать? Тестировали на получение 15 символов, фактически 20. 90-140 миллионов символов за весь тест. Получили чисто буквенные строки. В регекспах теперь можно писать и другие условия выкусывания ненужных элементов. Например, выключить часть букв. Регекспы проседают у всех. Ведут себя супер-провально в IE8 — получили не 90 миллионов случайных символов в секунду, как в Хроме, а каких-то 16, что тоже много, смотря с чем сравнивать. В сравнении с наборами символов проигрывают по всем статьям.
Выводы. Использование экзотической нативной функции .toString(36) — штука красивая. Её выгодно использовать не в составе функции, а для непосредственного взятия случайной строки до 10 символов в коде один раз. Тогда она выглядит коротко, хотя и не всем понятно. В остальном — по скорости и гибкости проигрывают наборам символов [ 3 ].
Случайная кириллица на регекспах
В варианте с кириллицей уже некуда применить toString(36). Пойдём другим путём. Получим любой символ из некоторого диапазона кодов и удалим ненужные. Что-то наподобие решета Эратосфена. Понятно, что каждое удаление вычисленного случайного символа записывается в пассив, поэтому, чем больший процент удалений, тем медленнее алгоритм и тем сильнее он будет проигрывать классике [ 3 ]. Оптимизировать — легко, если набор символов занимает ограниченный диапазон кодов юникодов. Но в коде тогда появляются проверки и магические числа.
Вот, для начала, пример такой сборки из латинницы. Получаем добавление больших и малых букв. Из-за «лени», оттого что выбрали диапазон 0...127, имеется много лишних вычислений случайных величин. Алгоритму это не мешает — он строку наберёт, если есть хотя бы 1 символ в диапазоне, но время страдает.
function randAa(n){ // [ 5 ] random big/small letters
var s ='';
while(s.length < n)
s += String.fromCharCode(Math.random() *127).replace(/W|d|_/g,'');
return s; //such as "AujlgLpHLVfDVpNEP"
}(Если хотим увидеть, сколько пропадает попыток, просто пишем ".length" в конце длинной строчки. Нули в ответной строке — пропавшие попытки, 1 — использованные. Примерно такая плотность: «0101000010000000010100010100101100». Это к тому, чтобы не удивляться, насколько медленнее будет алгоритм.)
Ch30: 2897.7 ± 0.23%
Fx24: 7720.0 ± 0.35%
Op12: 74651.3 ± 0.35%
IE8 : 49903.7 ± 0.21% - 50 секунд на 100 миллионов символов
Легко проверить, что тормозит здесь короткий, но сложно выполняемый регексп (несколько проверок на буквы и цифры). Самый простой способ оптимизации — исключить диапазон 0...47, написав внутри скобок Math.random() *80 +48.
Аналогично поступаем и для кириллицы. Берём диапазон где вся она есть, и удаляем не-кириллицу. Надо помнить, что такие циклы записываются красиво, но выполняются крайне медленно, в 1106/66 раз медленнее, чем могли бы быть при эффективном выборе диапазона, поэтому для вычисления нескольких тысяч символов использование их нормально, но для миллионов — не пойдёт. В то же время, алгоритм с набором символов в строке годится и для миллионов.
randAYa = function(n){ // [ 6 ] random big/small cyrillic letters
var s ='';
while(s.length < n)
s += String.fromCharCode(Math.random() *1106).replace(/[^а-яА-ЯёЁ]|_/g,'');
return s; //such as "хУэЛГЖХпЫРЙТЪд"
}Для тестов здесь было взято в 100 раз меньше проходов с набором 15 символов, но результаты увеличены в 100 раз для наглядного сравнения с другими.
Ch30: 21800.3 ± 1.77%
Fx24: 64100.6 ± 1.70%
Op12: 57000.0 ± 1.92%
IE8 : 341200.5 ± 4.20%
Время можно сократить в 16 раз, исходя из того, что код 1105 — максимальный юникод кириллицы, а 1040 — минимальный, записав Math.random() *(1106-1040) * 1040 в нужном месте. Но всё равно, секунды на 100 миллионов символов — это много для массовых вычислений по сравнению с функцией [ 3 ].
Автор: spmbt
