Еженедельное испытание III

Еженедельное испытание III

Хотя я провел годы, возясь с крошечными фрагментами JavaScript и PHP во времена моего партнерского маркетинга, мой первый настоящий опыт программирования был около 3 лет назад, когда кто-то, с кем я встречался, познакомил меня с Project Euler.

Project Euler — это большой список задач, для решения которых требуется как программирование, так и математика. Первая проблема, и, безусловно, самая простая, это FizzBuzz.

Я быстро пристрастился к этим вызовам; время между как, черт возьми, это вообще возможно? до ура! Я решил это! удивительно коротко. Я проглотил учебник Python, решая такие задачи, как оценка суммы всех дружественных чисел до 10000.

Я очень взволнован тем, что возвращаюсь к своим корням. На этой неделе я буду решать Задачу 92, связанную с счастливыми числами.

Примечание к этому сообщению: это глубокое погружение в математику. Если вам не нравится математика, вам, вероятно, лучше пропустить это. Однако, если вы действительно увлекаетесь математикой, я бы посоветовал вам решить эту задачу самостоятельно, а не просто прочитать мое решение!

Счастливое число — это число, цифры которого при возведении в квадрат и суммировании в конечном итоге достигают «1». Вот как это работает:

Проблема Эйлера требует от меня найти, сколько несчастливых чисел меньше 10 миллионов.

Рубин!

За последние 6 месяцев, как лично, так и профессионально, почти весь мой код был на Javascript. Я чувствовал себя как в отпуске. Ruby — удивительно лаконичный язык с красивым синтаксисом.

Попытка №1 — грубая сила

В Project Euler есть много проблем, у которых нет очевидной отправной точки. Это не такая уж проблема.

Подход грубой силы вполне очевиден: перебрать от 1 до 10 000 000, проверяя каждое число по пути на «счастье».

Вот это решение с множеством комментариев:

Хорошая новость: это работает! Он находит правильный ответ (8 581 146 — большинство чисел несчастливые 😞).

Плохая новость: для запуска требуется 278,4 секунды. Это более 4 минут.

Эмпирическое правило Project Euler заключается в том, что ваши решения не должны запускаться более 60 секунд на домашнем ПК средней мощности. Учитывая, что Project Euler существует уже более 10 лет, а средний домашний ПК сильно изменился за это время, я бы хотел, чтобы мое решение выполнялось за ‹20 секунд.

Другими словами, у меня много работы.

Попытка № 2: поиск хэша

Самая большая проблема — по крайней мере, так я думал в то время — заключалась в том, что я проходил через полный цикл для каждого отдельного числа от 1 до 10 миллионов. Что, если бы раньше существовал способ определить, является ли число счастливым или несчастливым?

Я заметил интересную закономерность. Чем больше число начинается с, тем быстрее оно уменьшается с каждой итерацией.

Самая большая цифра от 0 до 9 — это, очевидно, 9. 9² — это всего лишь 81. Это означает, что число «999» разрешается в 81*3, или 243. Число «99999», которое на несколько порядков больше, разрешается в 81*5 или просто 405.

Самое большое число, которое нас интересует, — 9 999 999. Это разрешается до 567, и оттуда становится только меньше. Это означает, что всего после одной итерации самое большое число, о котором нам когда-либо приходилось беспокоиться, равно 567.

Что, если мы начнем с итерации от 1 до 567 и сохраним, является ли число счастливым или нет, в хеше? Затем, при итерации до 10 миллионов, мы можем выполнить 1 итерацию вычисления, а затем посмотреть его в хэше, чтобы увидеть, счастлив он или нет?

Вот как выглядит это решение:

Итак, это определенно лучше, но решение все еще занимает слишком много времени: 67,0 секунды.

Затем я начал думать, что, может быть, массивы будут быстрее, чем хэши? Недавно я узнал, что хеш-алгоритмы удивительно сложны — может быть, использование массивных индексов было бы более эффективным?

Новый синтаксис будет просто массивом логических значений: [false, true, true] вместо {1: false, 2: true, 3: true}. Я не буду размещать код здесь, так как он очень и очень похож на версию 2, но любопытные глаза могут увидеть его на GitHub.

Конечный результат был маргинален. 63 секунды вместо 67. Оказывается, алгоритмы хеширования довольно эффективны!

Окончательная версия: Джош, ты идиот!

Мне стыдно признаться, что я провел здесь довольно много времени, разглядывая слова и пытаясь найти способ оптимизировать поиск хеша. Огромное узкое место все время было прямо передо мной, и я игнорировал его.

Чтобы выполнить одну итерацию моего метода квадратов и сумм, я:

• Преобразовать целое число в строку,
• Преобразуйте эту строку в массив ее символов,
• Выполните итерацию по этому массиву, чтобы: — преобразовать каждый символ назад в целое число, — возвести его в квадрат,
• И пройдите снова по этому массиву, просуммировав его значения.

Это слишком много конверсий. И это совершенно ненужно. Та красивая лаконичная линия Руби, которой я был так доволен? Это меласса.

Используя чудесную силу по модулю, это можно сделать без какого-либо преобразования типов. Представляю окончательное решение:

Если вы никогда раньше не имели дело с модулем, приношу извинения за то, что загнал вас в тупик; это определенно умопомрачительно. Однако стоит поэкспериментировать с ним самостоятельно, потому что это потрясающий инструмент.

Например, он может превратить любой массив в круговой массив.

Это окончательное решение выполняется на моем компьютере всего за 6 секунд. Это сокращение более чем на 90%.

В этом упражнении я извлек ценный урок; Я вкладывал свою энергию не в то место. Я был настолько уверен в своей цепочке конверсий, что даже не рассматривал ее как нечто, что можно было бы реорганизовать.

При рефакторинге подвергайте сомнению все. Если вы не можете понять, в чем ваше узкое место, протестируйте все.

Как всегда, все 4 решения можно найти на GitHub.

Если вы дошли до этого места, большое спасибо за чтение =) Есть ли у вас какие-либо предложения по проблеме, которую я должен решить на следующей неделе? Я хотел бы услышать от вас!

-Джош