Мы вынашиваем амбициозные планы по изданию вот такой книги:
Как вы понимаете, эта книга требует не только литературного перевода, но и классной полиграфии, хорошей бумаги, широкого формата и т.п. Поэтому предлагаем ознакомиться с замечательной публикацией об этой книге, появившейся в блоге автора Ангуса Кролла спустя несколько месяцев после публикации оригинала.
Приятного чтения, и поучаствуйте пожалуйста в опросе!
Я написал книгу If Hemingway Wrote JavaScript. В ней я фантазирую, как 25 знаменитых прозаиков, поэтов и драматургов могли бы решать простые задачи на JavaScript. Это дань уважения моим любимым писателям и признание в любви языку JavaScript – ведь я не знаю, какой еще язык наделял бы программиста такой свободой, позволял раскрыть творческий потенциал, а также был бы настолько своеобразен, чтобы привлечь внимание великих литераторов.
В этом посте – оригинальный материал, которого нет в книге (считайте его «бонусом»). Это первый глубокий технический разбор решений, приписываемых каждому автору. Некоторые решения требуют более подробных объяснений, нежели другие.
Приятного чтения!
Часть 1: Простые числа
Задание: напишите функцию, возвращающую все простые числа вплоть до значения заданного аргумента.
1. Хорхе Луис Борхес
// Они повествуют (я знаю) о пинаклях, флеронах и балюстрадах,
// о потаенных интервольтах и чудищах, вечно идущих вверх размашистым шагом
var monstersAscendingAStaircase = function(numberOfSteps) {
var stairs = []; stepsUntrodden = [];
var largestGait = Math.sqrt(numberOfSteps);
// Череда тварей карабкается по ступенькам;
// шаг каждой следующей химеры шире, чем у предыдущей
for (var i = 2; i <= largestGait; i++) {
if (!stairs[i]) {
for (var j = i * i; j <= numberOfSteps; j += i) {
stairs[j] = "stomp";
}
}
// Длиннолапые чудища не попадают по ступенькам, номера которых – простые числа
for (var i = 2; i <= numberOfSteps; i++) {
if(!stairs[i]) {
stepsUntrodden.push(i);
}
}
// Вот и наш ответ
return stepsUntrodden;
};
Решение Борхеса – вариант алгоритма «Решето Эратосфена», в котором кратные каждого известного простого числа помечаются как составные (непростые) числа. В таком случае, у Борхеса длиннолапые чудовища занимают места делителей. Каждое чудище делает шаг на одну ступеньку шире, чем шедшее за ним: 2, 3, 4, 5… вплоть до квадратного корня из числа, соответствующего наивысшей ступеньке. (почему-то Борхес позволяет карабкаться по лестнице и чудищам с неровным шагом). Те ступеньки, на которые никто не встанет – и есть простые числа.
Обратите внимание на строку 12: каждый монстр начинает восхождение с квадрата своего множителя:
for (var j = i * i; j <= numberOfSteps; j += i) {
Дело в том, что составные числа между n и n² уже будут пройдены чудищами с более мелким шагом.
2. Льюис Кэрролл
function downTheRabbitHole(growThisBig) {
var theFullDeck = Array(growThisBig);
var theHatter = Function('return this/4').call(2*2);
var theMarchHare = Boolean('The frumious Bandersnatch!');
var theVerdict = 'the white rabbit'.split(/the march hare/).slice(theHatter);
// в море слез…
eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {\
theMarchHare = 1;\
theVerdict.push(theHatter);\
' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
);
return theVerdict;
}
Как и творчество Кэрролла, его код — смесь загадки и нонсенса. Давайте построчно в нем разберемся, начиная с объявления переменных.
В принципе, строка 2 вполне традиционна (если закрыть глаза на использование конструктора Array). Кэрролл создает пустой массив, длина которого совпадает с сообщенным аргументом. Он называется theFullDeck , поскольку в решении воображается колода карт, причем в итоге рубашкой вниз будут лежать лишь те из них, что соответствуют простым числам.
В строке 3 создается функция (с применением малоиспользуемого конструктора Function), а затем эта функция вызывается при помощи call, при этом 2 * 2 (т.е. 4) передается как аргумент this. Следовательно, theHatter инициализируется со значением 1.
В строке 4 theMarchHare устанавливается в true . Когда конструктор Boolean вызывается как функция, его аргумент преобразуется в true или false . В таком случае непустая строка ‘The frumious Bandersnatch!’ преобразуется в true . (Кстати, такое присваивание не очень-то здесь нужно, поскольку в строке 10 theMarchHare присваивается новое значение).
Наконец – вероятно, это верх абсурда – в строке 6 Кэрролл присваивает theVerdict пустой массив, и делает это максимально иносказательно:
var theVerdict = 'the white rabbit'.split(/the march hare/).slice(theHatter);
Здесь не так много бросается в глаза. Аргумент для split – это регулярное выражение, не совпадающее с ‘the white rabbit’, поэтому при вызове split получаем массив, в котором содержится лишь ‘the white rabbit’. Последующая операция slice заносит в копию массива все элементы исходного массива, начиная с заданного индекса. Поскольку в нашем одноэлементном массиве нет индекса 1 (таково значение theHatter ), никакие члены из него не копируются, и у нас получается пустой массив.
Проще говоря, можно переписать объявления переменных вот так:
function downTheRabbitHole(growThisBig) {
var theFullDeck = Array(growThisBig);
var theHatter = 1;
var theMarchHare = true;
var theVerdict = [];
А теперь полный угар:
// в море слез…
eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {\
theMarchHare = 1;\
theVerdict.push(theHatter);\
' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
);
Прежде, чем перейти к пресловутой функции eval , давайте поговорим о вложенных инструкциях join . Функция join превращает массив в строку, при этом ее аргумент служит клеем между элементами массива. Если вызвать join применительно к пустому массиву, получится строка, состоящая из сплошного клея (повторенная n – 1 раз, где n – длина массива):
Array(4).join('hi'); //'hihihi'
Если вложить друг в друга два join, то вкладывается и соответствующий клей:
Array(4).join('A' + Array(4).join('a')); //'AaaaAaaaAaaa'
Когда же мы включаем в клей переменные, начинаем понимать, что к чему:
var arr = [], count = 0;
Array(4).join('arr.push(' + Array(4).join('count++,') + '-1);');
//"arr.push(count++,count++,count++,-1);arr.push(count++,count++,count++,-1);arr.push(count++,count++,count++,-1)"
Теперь, растолковав JavaScript, как генерировать JavaScript, остается только придумать, как все это запустить. Заходим в гнусную
eval …
var arr = [], count = 0;
eval(Array(4).join('arr.push(' + Array(4).join('count++,') + '-1);'));
arr; //[0, 1, 2, -1, 3, 4, 5, -1, 6, 7, 8, -1]
…так вот каким образом Кэрролл автоматически генерирует программу для работы с простыми числами. Давайте еще раз взглянем на этот код:
// в море слез...
eval(theFullDeck.join('if (!theFullDeck[++theHatter]) {\
theMarchHare = 1;\
theVerdict.push(theHatter);\
' + theFullDeck.join('theFullDeck[++theMarchHare * theHatter]=true;') + '}')
);
Аргумент к eval (после форматирования) принимает вид:
if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
}
if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
}
if (!theFullDeck[++theHatter]) {
theMarchHare = 1;
theVerdict.push(theHatter);
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
theFullDeck[++theMarchHare * theHatter] = true;
}
// etc...
…и т.д. (Сгенерированный таким образом код может получиться очень длинным. Запросив все простые числа вплоть до 100, получим более 10 000 строк кода – можете себе представить, как это скажется на производительности – но для Страны Чудес, полагаю, сойдет)
Итак, постепенно все проясняется. Оказывается, Кэрролл использовал вариант того самого решета Эратосфена, которое мы видели у Борхеса. theFullDeck – это массив со всеми числами, которые необходимо проверить, theHatter и theMarchHare – вложенные счетчики, умножаемые при каждом инкременте, чтобы сгенерировать все возможные составные числа. Все карты, чьи индексы – составные числа, переворачиваются (поскольку theFullDeck с таким индексом равен true ). Открытыми остаются лишь те карты, которым соответствуют простые числа.
3. Дуглас Адамс
// Вот я, мозг размером с планету, и они просят меня написать на JavaScript...
function kevinTheNumberMentioner(_){
l=[]
/* почти безвредно --> */ with(l) {
// извините за все это, у моей вавилонской рыбки сегодня мигрень...
for (ll=!+[]+!![];ll<_+(+!![]);ll++) {
lll=+!![];
while(ll%++lll);
// У меня в правом полушарии все болит от этих чертовых точек с запятой
(ll==lll)&&push(ll);
}
forEach(alert);
}
// ну так вы же точно делать не будете...
return [!+[]+!+[]+!+[]+!+[]]+[!+[]+!+[]];
}
Читать код Адамса в целом сложно, так как он многое заимствует из jsfuck – хитроумного, но убийственно лаконичного языка, в котором используется всего 6 символов. Тем не менее, это настоящий JavaScript — если вы запустите его в консоли, все сработает. Давайте переведем простой фрагмент:
for (ll=!+[]+!![];ll<_+(+!![]);ll++) {
Здесь видим цикл for , а ll и _ — имена переменных. Все остальное – литерал и форменный вынос мозга.
В первом условии этой инструкции ll получает значение !+[]+!![] . Разобрав это выражение, видим в нем два пустых литерала массива. Перед первым стоит +, из-за которого массив принудительно приводится к числу 0. Прямо перед ним стоит!, принудительно приводящий 0 к его булевской противоположности, то есть, к true . Итак, !+[] результирует в true .
Теперь рассмотрим второй литерал массива. Ему предшествуют два !! , что попросту принудительно приведет его к булеану. Поскольку массивы – всегда объекты, булеан массива всегда равен true . Итак, !![] всегда дает true .
Сложив два этих выражения, !+[]+!![] , фактически, имеем true + true . Здесь + принудительно приводит оба операнда к числу 1, поэтому окончательный результат всего выражения равен 2.
Два остальных условия цикла for теперь понятны без труда. Опять же, имеем !![] , на сей раз перед ним идет +, принудительно приводящий true к 1. Итак, ll<_+(+!![]) дает ll < _ + 1 .
Последнее условие – это обычный постфикс JavaScript, поэтому весь цикл for дает:
for (ll = 2; ll < _ + 1; ll++) {
А вот все решение, переведенное на обычный мирской JavaScript (переменным я также дал более осмысленные имена)
// Вот я, мозг размером с планету, и они просят меня написать на JavaScript…
function kevinTheNumberMentioner(max){
var result = [];
/* почти безвредно --> */ with(result) {
// извините за все это, у моей вавилонской рыбки сегодня мигрень...
for (candidate = 2; candidate < max + 1; candidate++) {
var factor = 1;
while (candidate % ++factor);
// У меня в правом полушарии все болит от этих чертовых точек с запятой
(candidate == factor) && push(candidate);
}
forEach(alert);
}
// ну так вы же точно делать не будете...
return '42';
}
Славно, теперь перед нами, по крайней мере, узнаваемый JavaScript, но в нем по-прежнему таятся кое-какие странности.
Инструкция with относится к наиболее предосудительным с точки зрения «блюстителей чистоты JavaScript», но все-таки в строке 3 – именно она. JavaScript попытается заключить все свойства, на которые не указывают ссылки, в блоке with заданного объекта. Следовательно, неприкаянные методы массива push and forEach окажутся в области видимости result .
Еще одна любопытная инструкция — цикл while в девятой строке. У этого цикла нет тела, поэтому factor просто продолжает увеличиваться на единицу, пока не станет нацело делиться, давая candidate в качестве частного. В следующей строке проверяется, равны ли теперь значения candidate и factor . В таком случае, у числа нет меньших делителей, следовательно, оно простое и добавляется к result .
В строке 13 перебираем результаты и во всеуслышание объявляем каждое простое число в виде alert . Наконец, программа возвращает 42.
4. Чарльз Диккенс
function MrsPrimmerwicksProgeny(MaxwellNumberby) {
Number.prototype.isAPrimmerwick = function() {
for (var AddableChopper = 2; AddableChopper <= this; AddableChopper++) {
var BittyRemnant = this % AddableChopper;
if (BittyRemnant == 0 && this != AddableChopper) {
return console.log(
'It is a composite. The dear, gentle, patient, noble', +this, 'is a composite'),
false;
}
}
return console.log(
'Oh', +this, +this, +this, 'what a happy day this is for you and me!'),
true;
}
var VenerableHeap = [];
for (var AveryNumberby = 2; AveryNumberby <= MaxwellNumberby; AveryNumberby++) {
if (AveryNumberby.isAPrimmerwick()) {
VenerableHeap.push(AveryNumberby);
}
}
return VenerableHeap;
}
Что, если бы вы могли спросить у числа, простое ли оно:
6..isPrime(); // ложь
7..isPrime(); // истина
Что бы сделал Чарльз Диккенс? Расширил бы Number.prototype . Его собственное расширение называется isAPrimmerwick (на самом деле, у всех объектов здесь причудливые диккенсовские имена) и определяется в строках 2-14. В строках 17-21 мы просто спрашиваем каждое число, простое ли оно, и добавляем простые числа в массив с результатами, который называется VenerableHeap .
Логика метода isAPrimmerwick в основном проста. Делим имеющееся число на все возможные делители. Если то или иное число делится без остатка, то является составным, в противном случае — простым.
В каждой инструкции возврата (строки 6 и 11) есть пара любопытных моментов. Во-первых, поскольку число вызывает метод в его же прототипе, на него можно сослаться при помощи this (но с префиксом +, чтобы принудительно привести его от числового объекта к примитиву). Во-вторых, Диккенс использует оператор-запятую, чтобы одновременно вызвать console.log и вернуть булевское значение.
5. Дэвид Фостер Уоллес
var yearOfTheLighteningQuickAtkinSieve = function(tops) {
//B.P. #40 07-14
//ELEPHANT BUTTE, NM
var NSRS/*[1]*/ = [0,0,2,3];
/* два конкурентных цикла мобилизуются так, что переменные i и j (каждая с
исходным значением 1) увеличиваются на 1 при каждом инкременте
(правда, во вложенном виде). */
for(var i = 1; i < Math.sqrt(tops); i++){
for(var j = 1; j < Math.sqrt(tops); j++){
if (i*i + j*j >= tops) {
break;
}
/* Две переменные (т.e. i и j) подставляются в первую квадратичную функцию quadratic,
и результат ее присваивается дополнительной переменной (n). */
var n = 4*i*i + j*j;
/* Если дополнительная переменная (т.e. n) деленная на 12, даст в остатке
1 или 5, то у значения с этим индексом (т.e. у n) меняется знак [2]. */
if(n <= tops && (n%12 == 1 || n%12 == 5)){
NSRS[n] = NSRS[n] ? 0 : n;
}
/* Теперь мы (т.e. JavaScript) подходим ко второй квадратичной функции, and again the result
и результат вновь присваивается (существующей) переменной n. */
n = 3*i*i + j*j;
/* Хотя переменная (т.e. n) вновь делится на 12, на сей раз остаток
сравнивается с 7 для определения того, должен ли у значения с данным
индексом(т.e. у n)
меняться знак */
if(n <= tops && (n % 12 == 7)){
NSRS[n] = NSRS[n] ? 0 : n;
}
/* Теперь вы (т.e. читатель), испытываете чувство нерешительности и раскаяния,
тем не менее, мы (т.e. JavaScript) еще не закончили. Как и следовало ожидать, теперь в ход
идет третья квадратичная функция и(не менее предсказуемо) ее значение присваивается (уже
уже поистрепавшейся) переменной n. */
n = 3*i*i - j*j;
/* Единственный интересный момент в третьей операции деления (однако и самый
удручающий) заключается в том, что она происходит лишь тогда, когда первая переменная
в цикле (i) оказывается больше
т.e. не меньше (или равна) второй переменной цикла (j) [3]. */
if (i>j) {
if((n <= tops) && (n % 12 == 11)){
NSRS[n] = NSRS[n] ? 0 : n;
}
}
}
}
/* В полуобморочном состоянии (но не доверяя фильтру кольцевой факторизации) мы
(т.e. JavaScript) теперь предварительно определяем как составные
все без исключения простые множители, без учета их актуального статуса: простые ли они
(т.е не составные) или составные (т.е. не простые)
*/
for(i = 5; i < Math.sqrt(tops); i++){
if(NSRS[i] == 1){
for(j = i*i; j < tops; j += i*i){
NSRS[j] = 0;
}
}
}
return NSRS.filter(Number); // [4]
}
/*
[1] Числовая система хранения и поиска информации.
[2] То есть значения, соответствующие текущему индексу [a] устанавливаются в 0, а значения 0 устанавливаются в текущие индексы.
[3] В противном случае каждый релевантный индекс [a] менял бы знак дважды.
[4] `Array.prototype.filter` будучи функцией высшего порядка, определяется в стандарте EcmaScript-262 (5-я
версия) [b]. Поскольку `Number` - это встроенная в язык функция, преобразующая любое значение в число. а Array.prototype.filter
отклоняет ложные (т.e. неистинные) значения, значения 0, будучи ложными (т.e. неистинными) не
будут включаться в массив, возвращаемый `Array.prototype.filter`.
[a] т.e. индекс, на котором рассматриваемая квадратичная функция результирует в true.
[b] http://ift.tt/MfTCBL
*/
Благодаря пространным комментариям, которыми так известен Уоллес, рассказывать особенно нечего — надо только отметить, что в основе его решения лежит сильно оптимизированное (и слишком сложное, чтобы вдаваться здесь в объяснения) решето Эткина.
Код особенно интересен изысканной логикой и уоллесовским точным, но непринужденным стилем. Однако в строке 54 есть и интересный оборот JavaScript:
return NSRS.filter(Number); // [4]
Результат — NSRS . Здесь это разрежённый массив, содержащий все простые числа, которые, однако, перемежаются с неопределенными значениями (спереди он заполнен нулями):
[0, 0, 2, 3, undefined, 5, undefined, 7/*, etc.. */]
Функция Array.prototype.filter создает новый массив, в котором содержатся лишь те элементы исходного массива, для которых заданная функция возвращает значение true . Здесь речь идет о Number , встроенной в язык функции, которая пытается принудительно привести свой аргумент к числу. Number принудительно приводит undefined к NaN , оставляя все настоящие числа нетронутыми. Поскольку оба значения: NaN и 0 означают «ложь», вновом массиве будут содержаться только простые числа:
[0, 0, 2, 3, undefined, 5, undefined, 7].filter(Number); //[2, 3, 5, 7]
Заключение
Вот и все. Надеюсь, вам понравилось.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий