Тестване на палиндроми — част 4

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

Днес ще видим как може да улесним и нашата работа, а и на самия компютър, така че да достигнем до по-кратък и изчистен код и по-добро бързодействие.

Кодът, който имаме до момента е:

$test = 'If I Had a Hi-Fi';

$simplified = preg_replace('/\W/', '', $test);
$simplified = strtolower($simplified);

$is_palindrome = true;

$repetition = strlen($simplified);
$repetition = $repetition / 2; # достатъчно е да проверим до средата, тъй като се очаква да е огледално

for ($i = 0; $i < $repetition; $i++) {
    $a = substr($simplified, $i, 1);
    $b = substr($simplified, -($i+1), 1);

    if ($a !== $b) { # стриктната проверка работи маааалко по-бързо
        $is_palindrome = false;
        break; # няма нужда да правим повече проверки -- вече е ясно, че не е палиндром
    }
}

var_dump($is_palindrome);

Функции независещи от главни и малки букви

Едно от нещата, което можем да направим е да премахнем функцията strtolower(). Вместо това по-нататък в кода можем да използваме функции, които не зависят от главни и малки букви (case insensitive).

Най-съществената част по оптимизирането може да стане когато използваме съчетанието от две функции, които са вградени в PHP.

strrev() и strcasecmp()

Първо чрез strrev() можем да обърнем целия string, а след това със strcasecmp() можем да направим case insensitive проверка между оригиналния текст и версията му в обратен ред.

Така че опростеният код би бил:

$test = 'If I Had a Hi-Fi';
$simplified = preg_replace('/\W/', '', $test);
$rev = strrev($simplified);
$is_palindrome = (strcasecmp($simplified, $rev) === 0);

var_dump($is_palindrome);

Не се бъркайте от синтаксиса (strcasecmp($simplified, $rev) === 0). Най-външните скоби са, за да се уверим, че променливата $is_palindrome получава стойност резултата от проверката с ===.

Лявата част на тази проверка е резултатът от функцията strcasecmp(). Тя приема като аргументи 2 string-а. Ако първият string е “по-малък” от втория, резултатът ще е по-малък от 0. Ако са равни (еднакви), то резултатът ще е 0. Ако първият е “по-голям” от втория — резултатът ще е по-голям от 0.

В документацията не пише точно как се определя големина на string-ове, но в нашия случай е достатъчно да знаем, че търсим резултат 0. Затова и тази проверка при присвояването на резултат към променливата $is_palindrome.

Резултат от оптимизацията

Направих няколко теста и се оказа, че този нов вариант е повече от 2 пъти по-бърз (при тестове конкретно с “If I Had a Hi-Fi”). Основното забавяне в кода идва даже от регулярния израз:

$simplified = preg_replace('/\W/', '', $test);

Това означава само едно — за бързодействие е важно да се познават вградените функции в PHP. Вместо да пишем всичко самички трябва да ползваме тях.

Такива вградени функции са писани на друго ниво и са част от самия PHP парсър. Така винаги ще имаме по-добро бързодействие, отколкото ако седнем да пишем custom функция.

Винаги, когато имате да правите нещо стандартно — проверете дали вече няма някаква готова функция за него. В най-лошия случай — ще има 2-3 функции, които комбинирани да вършат търсеното.

Ако преди сте се чудели за какво ви е бил урокът Първи стъпки в PHP — функции за текст — сега вече се надявам, че е по-ясно.

И ако искаме да го направим под формата на функция получаваме:

function test_palindrome($test) {
    $simplified = preg_replace('/\W/', '', $test);
    $rev = strrev($simplified);

    $comparison = strcasecmp($simplified, $rev);

    return ($comparison === 0);
}

$is_palindrome = test_palindrome('If I Had a Hi-Fi');

var_dump($is_palindrome);