기본 변환 루프 최적화

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)이됩니다. I가 데이터 2KB의 공급을 다른 예 array(1, 6, 7, 7, 7, 2, 1, 6) 줄 것이라고 array(1, 0, 0), 256, 10 것 (상기 어레이의 각각의 요소는 $dstBase 단일 "디지트"이다.

지금 대향있어 문제이며, 이는 거의 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는 읽을 수 없다 (:.

하지만 개인적으로 나는 당신이 잘못하고 있다고 생각합니다. 나는 당신이 시스템 콜을 사용하거나 쓰기/기존 PHP 모듈을 설치하여 태스크의 이런 종류의 빠른 C 코드를 사용해야한다고 생각한다. 그리고 나는 코드 최적화/컴파일러 (Hip-Hop PHP, Zend Optimized 등)가이 경우 성능을 크게 향상시킬 수 있다고 생각합니다.

Answer 2

이 스크립트를 실행하는 데 걸린 시간의 99.9 %는 입력을 통해 반복해야하는 고유 한 필요성에서 기인합니다. foreach 내부의 코드는 매우 기본이기 때문에 실행 시간을 줄이는 유일한 방법은 반복 횟수를 줄이는 것입니다. 그렇게 할 수 없다면이 함수의 가장 효율적인 버전을 얻게됩니다.

Answer 3

잘 모르겠어요

하지만

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

조금 빠를 수 ...