Вперед, на поиски палиндромов

Не так давно на Хабре была статья про codebattle от hexlet.io. Ну и затянуло же нас с друзьми, это как наркотик! Вроде пытаешься на работу отвлечься, а руки прям сами тянутся зайти на сайт, и все мысли — об оптимизации решений.
И вот однажды попалась мне задачка, звучала она так: «The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». А если по-русски, то так: «десятичное число 585 в двоичном виде выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-ый подобный палиндром». Она совсем не сложная и решена была быстро.

function is_palindrome($num) {    return $num == strrev($num); } function solution($num) {    $count = $i = 0;    while($count<$num) {       $i++;       // Проверяем по порядку все числа, являются ли они палиндром в десятичном и двоичном виде       if (is_palindrome($i) && is_palindrome(decbin($i))){          $count++;       }    }    return $i; } 

Но вот незадача. Примерно в то время на сайт напал хабраэффект, и тесты ни в какую не хотели проходить, отваливались по timeout. В местном чате началось обсуждение по оптимизации решения, но никто дельного совета так и не дал. Потом сайт отпустило, все тесты прошли, но желание оптимизировать осталось…

Генерируем десятичные палиндромы

Для начала мне стало интересно сколько же я смогу найти палиндромов на своей машинке. Хоть в чате и не советовали искать больше 22-х, я спокойно нашел 27 всего за 5 секунд, а вот следующий пришел только через 4 с лишним минуты. Дальше я уж ждать не стал — долго что-то. Чтобы начать оптимизацию, я решил поподробнее узнать палиндромы. Сгенерировал себе несколько штук и начал рассматривать.

По сути числовой палиндром — это некое число, которое взяли, отзеркалили и прикрепили в конец этого же числа. Т.е. взяли число 235, отзеркалили, получили 532 и соединили — получился прекрасный палиндром — 235532. И было принято решение: зачем перебирать все числа в поисках десятичного палиндрома, если можно их просто генерировать. Сказано — сделано!

function solution($num) {    $count = $i = 0;    while($count<$num) {       $i++;       //Берем числа по порядку и соединяем с собой же в перевернутом виде       $palindrome = $i . strrev($i);       // И проверяем является ли наш десятичный палиндром таким же в двоичном виде.       if (is_palindrome(decbin($palindrome))) {          $count++;       }    }    return $palindrome; } 

Запустив я увидел, что пропущены однознаковые палиндромы и добавил простой цикл на первые девять чисел.

for ($i = 1; $i < 10; $i++) {    if (is_palindrome(decbin($i))) {       $count++;       if ($count == $num) return $i;    } } 

Запустив ещё раз, я увидел, что ошибка моя была гораздо сильнее. Я ведь совсем забыл про палиндромы с нечетным количеством знаков, таких как 313, 585 или 717! И вот тут мне пришлось крепко задуматься. Посмотрев на список полученных палиндромов, можно увидеть, что палиндромы с нечетным количеством знаков — это те же четные палиндромы, только с центровым знаком. Т.е. берем четный палиндром, вставляем в центр цифры 1-9 и вуаля — нечетные палиндромы готовы. Но! Если я буду вставлять их в этом цикле, я потеряю порядок чисел. Поэтому пришлось внести кардинальные изменения в код и отталкиваться от количества знаков.

function solution($num) {    $count = 0;    // Одноразрядные палиндромы.    for ($i = 1; $i < 10; $i++) {       if (is_palindrome(decbin($i))) {          $count++;          if ($count == $num) return $i;       }    }    $p_size = 1;    while (true) {       $min = 10**($p_size-1);       $max = (10**$p_size)-1;       // $min и max с каждым проходом цикла будут увеличиваться на один разряд       for ($i = $min; $i <= $max; $i++) {          // Генерируем палиндром с четным кол-вом знаков          $palindrome = $i . strrev($i);          //проверяем является ли он палиндромом в двоичном виде.          if (is_palindrome(decbin($palindrome))) {             $count++;             if ($count == $num) return $palindrome;          }       }       for ($i = $min; $i <= $max; $i++) {          for ($j = 0; $j < 10; $j++) {             // Генерируем палиндром с нечетным кол-вом знаков             $palindrome = $i . $j . strrev($i);             //проверяем является ли он палиндромом в двоичном виде.             if (is_palindrome(decbin($palindrome))) {                $count++;                if ($count == $num) return $palindrome;             }          }       }       $p_size++;    } } 

Собственно тут всё просто. Берем сначала одноразрядные числа 1-9. Создаем двухразрядные палиндромы. Следом трёхразрядные. Потом просто увеличиваем разряд и берем числа от 10-99. Получатся палиндромы 4-х и 5-тиразрядные. Ну и т.д.

Тестируем!

Для начала запустил посмотреть 28-ой палиндром. Оказалось что для улучшенной функции это абсолютно плёвая задача. 28-ой был получен за 0.15 секунды! А это значит, что скорость была увеличена больше чем в 1500 раз. Я был доволен. За 5 секунд я мог получить уже более 40-а полиндромов. 50-ый был получен за 2.5 минуты.

Обратив внимание на полученные палиндромы, я заметил, что все они нечетные. И ведь правда! Четные десятичные палиндромы в двоичном виде будут заканчиваться на 0, а так как они всегда начинаются с 1, то и палиндромом быть не могут. А это значит, что их даже проверять не нужно. А так как палиндромы мы генерируем, мы можем пропускать все числа с первой четной цифрой.

Простой continue по условию сразу отмёл. Нам даже не имеет смысла крутить на них цикл. Будем их пролистывать. Попробовав несколько вариантов:

if(!(substr($i,0,1))%2)) $i += $min; 

if(!((floor($i/$min))%2)) $i += $min; 

if (!$limit){    $limit = $min;    $i += $min; } $limit--; 

Я остановился на последнем, как на самом быстром и получил вот такой код.

function solution($num) {    $count = 0;    // Одноразрядные палиндромы.    for ($i = 1; $i < 10; $i++) {       if (is_palindrome(decbin($i))) {          $count++;          if ($count == $num) return $i;       }    }    $p_size = 1;    while (true) {       $min = 10**($p_size-1);       $max = (10**$p_size)-1;       // $min и max с каждым проходом цикла будут увеличиваться на один разряд       $limit = $min;       for ($i = $min; $i <= $max; $i++) {          // Условие чтобы перескочить числа с чётной первой цифрой          if (!$limit){             $limit = $min;             $i += $min;          }          $limit--;          // Генерируем палиндром с четным кол-вом знаков          $palindrome = $i . strrev($i);          //проверяем является ли он палиндромом в двоичном виде.          if (is_palindrome(decbin($palindrome))) {             $count++;             if ($count == $num) return $palindrome;          }       }       $limit = $min;       for ($i = $min; $i <= $max; $i++) {          if (!$limit){             $limit = $min;             $i += $min;          }          $limit--;          for ($j = 0; $j < 10; $j++) {             // Генерируем палиндром с нечетным кол-вом знаков             $palindrome = $i . $j . strrev($i);             //проверяем является ли он палиндромом в двоичном виде.             if (is_palindrome(decbin($palindrome))) {                $count++;                if ($count == $num) return $palindrome;             }          }       }       $p_size++;    } } 

Этим мы получили ускорение ещё примерно в два раза. 50-ый был получен за 88 секунд и, на мой взгляд, это был отличный результат!

Генерируем двоичные палиндромы

И вот я уже был готов остановиться и порадоваться, как мне пришла в голову мысль попробовать сформировать двоичные палиндромы. А что? Используемых цифр меньше, четных не сгенирируешь. Одни плюсы кругом!

Немного поразмыслив, я быстренько изменил код и получил:

function solution($num) {    if ($num==1) return 1;    $count = 1;    $p_size = 1;    while (true) {       $min = 2**($p_size-1);       $max = (2**$p_size)-1;       // $min и max с каждым проходом цикла будут увеличиваться на один разряд в двоичном виде       for ($i = $min; $i <= $max; $i++) {          $half_palindrome = decbin($i);          // Генерируем палиндром с четным кол-вом знаков в двоичном виде          $bin_palindrome = ($half_palindrome) . strrev($half_palindrome);          //проверяем является ли он палиндромом в десятичном виде.          $dec_palindrome = bindec($bin_palindrome);          if (is_palindrome($dec_palindrome)) {             $count++;             if ($count == $num) return $dec_palindrome;          }       }       for ($i = $min; $i <= $max; $i++) {          $half_palindrome = decbin($i);          for ($j = 0; $j < 2; $j++) {             // Генерируем палиндром с нечетным кол-вом знаков в двоичном виде             $bin_palindrome = $half_palindrome . $j . strrev($half_palindrome);             //проверяем является ли он палиндромом в десятичном виде.             $dec_palindrome = bindec($bin_palindrome);             if (is_palindrome($dec_palindrome)) {                $count++;                if ($count == $num) return $dec_palindrome;             }          }       }       $p_size++;    } } 

После тестов я понял, что всё сделал правильно. 28-ой был получен за 0.05 секунды. 50-ый за 48 секунд. Когда брался за эту задачу, такого результата я совсем не ожидал.

Тут я уже решил, что хватит: я и так превзошел все свои ожидания. Хотя вру, конечно. Потом ещё пытался придумать как можно увеличить скорость ещё больше, но уже ничего в голову не пришло. Устал уже, да и ночь на дворе.

Ну и на последок сводная таблица:

ссылка на оригинал статьи http://habrahabr.ru/post/270325/