4

そのため、私の暗号化ライブラリには、頻繁に使用するベース コンバーターがあります。これは世界で最も効率的な方法ではありませんが、すべての範囲の入力に対して非常にうまく機能します。

作業の大部分は、コールバック ループによって行われます。

    $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)もう 1 つの例は、次のようarray(1, 0, 0), 256, 10になりますarray(1, 6, 7, 7, 7, 2, 1, 6)(配列の各要素は、$dstBase.

私が今直面している問題は、2kb のデータをフィードすると、実行に約 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 回の反復が必要です)。

何かご意見は？

4

3 に答える 3

2

このスクリプトの実行にかかる時間の 99.9% は、入力を反復処理する固有の必要性から生じています。foreach 内のコードは非常に基本的なものであるため、実行時間を短縮する唯一の方法は反復回数を減らすことです。それが不可能な場合は、この関数の最も効率的なバージョンがあります。

于 2011-08-11T13:19:07.307 に答える
1

はい、少し最適化できます。

$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;
}

メモリと CPU の使用量がいくらか削減され、はるかに楽しくなりますが、もちろん判読できません (:.

しかし、個人的にはあなたのやり方は間違っていると思います。この種のタスクには、高速なCコードを使用する必要があると思います（システムコールを使用するか、既存のPHPモジュールを作成/インストールすることにより）。そして、Hip-Hop PHP、Zend Optimized などのコード オプティマイザ/コンパイラは、この場合、パフォーマンスを劇的に向上させることができると思います。

于 2011-08-11T15:23:05.390 に答える
-1

よくわかりませんが、

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

もう少し速くなるかもしれません...

于 2011-08-11T13:41:21.527 に答える