基本変換ループの最適化

Question

私の暗号化ライブラリでは、私が頻繁に使用するbase converterがあります。これは世界で最も効率的なものではありませんが、すべての入力範囲で非常にうまく機能します。

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

$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)となります。私はそれをデータの2キロバイトを養う場合は、別の例では、配列の各要素が$dstBaseでシングル「数字」である（array(1, 6, 7, 7, 7, 2, 1, 6)を与えることになるarray(1, 0, 0), 256, 10だろう。

私が今直面してる問題は、ある、それはほとんど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

はい、それは少し最適化することができます。

$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モジュールの作成/インストールを使って）いくつかの高速なCコードを使うべきだと思います。ヒップホップPHP、Zend Optimizedなどのコードオプティマイザ/コンパイラは、この場合パフォーマンスを大幅に向上させることができると私は思います。

Answer 2

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

Answer 3

私はわからないんだけど、

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

が少し速いかもしれない...