Оптимизация базового цикла преобразования

Question

Итак, для моей библиотеки криптографии у меня есть базовый конвертер , который я использую довольно часто. Это не самая эффективная вещь в мире, но она работает довольно хорошо для всех диапазонов ввода.

Большая часть работы выполняется циклом обратного вызова:

    $callback = function($source, $src, $dst) {
        $div       = array();
        $remainder = 0;
        foreach ($source as $n) {
            $e         = floor(($n + $remainder * $src) / $dst);
            $remainder = ($n + $remainder * $src) % $dst;
            if ($div || $e) {
                $div[] = $e;
            }
        }
        return array(
            $div,
            $remainder
        );
    };
    while ($source) {
        list ($source, $remainder) = $callback($source, $srcBase, $dstBase);
        $result[]                  = $remainder;
    }

По сути, он принимает массив чисел в $srcBase и преобразует их в массив чисел в $dstBase. Таким образом, пример ввода будет array(1, 1), 2, 10, что даст array(3) в результате. Другим примером будет array(1, 0, 0), 256, 10, который даст array(1, 6, 7, 7, 7, 2, 1, 6) (каждый элемент массива представляет собой одну «цифру» в $dstBase.

Проблема, с которой я сейчас сталкиваюсь, заключается в том, что, если я передаю 2 КБ данных, для ее запуска требуется почти 10 секунд. Поэтому я решил оптимизировать его. До сих пор у меня осталось около 4 секунд, заменив всю эту структуру рекурсивным циклом:

    while ($source) {
        $div       = array();
        $remainder = 0;
        foreach ($source as $n) {
            $dividend  = $n + $remainder * $srcBase;
            $res       = (int) ($dividend / $dstBase);
            $remainder = $dividend % $dstBase;
            if ($div || $res) {
                $div[] = $res;
            }
        }
        $result[] = $remainder;
        $source   = $div;
    }

Проблема, с которой я сталкиваюсь, заключается в том, как оптимизировать ее (если это вообще возможно). Я думаю, что проблема заключается в количестве итераций, которое требуется для большого ввода (для массива 2000 элементов, от базового 256 до базового 10, всего требуется 4 815 076 итераций).

Есть мысли?

Answer 1

99,9% времени, необходимого для выполнения этого скрипта, обусловлено внутренней необходимостью перебора входных данных. Поскольку код внутри foreach является очень базовым, единственный способ уменьшить время выполнения - уменьшить количество итераций. Если это невозможно, то у вас есть самая эффективная версия этой функции.

Answer 2

Да, это можно немного оптимизировать:

$source_count = count($source);
while ($source) {
    $remainder = $i = 0;
    foreach ($source AS &$n) {
        $dividend = $n + $remainder * $srcBase;
        $remainder = $dividend % $dstBase;
        $res = ($dividend - $remainder) / $dstBase;
        if ($i || $res)
            $source[$i++] = $res;
    }
    for ($j=$i; $j < $source_count; $j++)
        unset($source[$i]);
    $source_count=$i;
    $result[] = $remainder;
}

или даже быстрее, но более неясный:

$source_count = count($source);
while ($source) {
    $remainder = $i = 0;
    foreach ($source AS &$n) {
        if (($res = ($dividend - ($remainder = ($dividend = $n + $remainder * $srcBase) % $dstBase)) / $dstBase) || $i)
            $source[$i++] = $res;
    }
    for ($j=$i; $j < $source_count; $j++)
        unset($source[$i]);
    $source_count=$i;
    $result[] = $remainder;
}

Вы получите некоторое уменьшение использования памяти и ЦП, и это будет гораздо веселее, но, конечно, нечитаемо (:.

Но лично я думаю, что вы делаете это неправильно. Я думаю, что вы должны использовать некоторый быстрый C-код для такого рода задач (с помощью системного вызова или написания / установки существующего модуля PHP). И я думаю, что оптимизаторы / компиляторы кода, такие как Hip-Hop PHP, Zend Optimized и т. Д., Могут значительно повысить производительность в этом случае.

Answer 3

Я не уверен, но

$dividend  = $remainder * $srcBase + $n;

может быть немного быстрее ...