優化基礎轉換循環

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)。另一個例子是array(1, 0, 0), 256, 10這將使array(1, 6, 7, 7, 7, 2, 1, 6)（該數組的每個元素是一個單一的「數字」在$dstBase。

我現在所面臨的問題，如果是我給它的數據的2KB，它需要差不多10 。

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

我現在面臨的問題是：秒跑所以我已經開始着手優化它到目前爲止，我通過更換這個遞歸循環整體結構有它下降到約4秒如何進一步優化它（如果甚至可能的話）我認爲問題是大輸入所需的迭代的剪切次數（對於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使用的減少，它更加有趣，但是cource不可讀（：。

但是我個人認爲你做錯了。我認爲你應該爲這類任務使用一些快速的C代碼（通過使用系統調用或編寫/安裝現有的PHP模塊）。我認爲像Hip-Hop PHP，Zend Optimized等代碼優化器/編譯器可以在這種情況下顯着提高性能。

Answer 2

99.9％的執行此腳本所需的時間源於迭代輸入的固有需求。由於foreach中的代碼非常基本，減少執行時間的唯一方法是減少迭代次數。如果這是不可能的，那麼你有這個功能的最有效的版本。

Answer 3

我不知道，但

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

可能是一個有點快......