PHP Radix Sort Algorithm - преобразование типа ok?

Question

Это функция, которую я написал для Radix Sort в PHP. Это работает для всех случаев, когда массив заполняются номера больше 0.

function radix_sort($arr) { 

    // Find the number of passes needed to complete the sort 
    $passes = strlen((string)max($arr)); 
    $buckets = []; 

    // Start the passes 
    for($i = 1; $i <= $passes; $i++) { 
     // Create - reinitialize some buckets 
     for ($b = 0; $b <= 9; $b++) { 
      $buckets[$b] = []; 
     } 

     for ($j = 0; $j < count($arr); $j++) { 
      // Drop into the proper bucket based on the significant digit 
      $numStr = (string)$arr[$j]; 
      if (strlen($numStr) < $i) { 
       $bucketsIndex = 0; 
      } else { 
       $bucketsIndex = $numStr[strlen($numStr) - $i]; 
      } 
      array_push($buckets[$bucketsIndex], $arr[$j]); 
     } 

     // Repopulate our array by pulling out of our buckets 
     $k = 0; 
     foreach ($buckets as $bucket) { 
      foreach ($bucket as $value) { 
       $arr[$k] = $value; 
       $k++; 
      } 
     } 
    } 
    return $arr; 
} 

Я чувствую, что есть слишком много типа преобразования происходит. Это нормально? Если бы я хотел вывести N-й разряд из большого числа, есть ли лучший способ в PHP?

Answer 1

Вы можете преобразовать все значения в string перед функцией, а затем вернуться к int в конце:

function radix_sort($arr) { 

    $arr = array_map ('strval', $arr) ; 
    $passes = strlen(max($arr)) ; // Should still work since all values are numeric 

    /* Do your stuff... */ 

    return array_map ('intval', $arr) ; 
} 

Тогда в вашем внутреннем цикле можно хранить длину (я не знаю, сложность strlen в PHP, но я предположил, что это не O(1)):

for ($j = 0; $j < count($arr); $j++) { 
    // Drop into the proper bucket based on the significant digit 
    $numStr = $arr[$j]; 
    $numLen = strlen($numStr) ; 
    if ($numLen < $i) { 
     $bucketsIndex = 0; 
    } else { 
     $bucketsIndex = $numStr[$numLen - $i]; 
    } 
    array_push($buckets[$bucketsIndex], $arr[$j]); 
} 

Или вы могли бы даже (если у вас есть достаточно памяти) использовать массив для предвычисления длина:

$lengths = array_map ('strlen', $arr) ;