¿Cuál es la mejor manera de hacer aritmética base36 en Perl?

Question

¿Cuál es la mejor manera de hacer base36 aritmética en Perl?

Para ser más específicos, que deben ser capaces de hacer lo siguiente:

• Operar en números positivos N-dígitos en base 36 (por ejemplo, dígitos son 0-9 AZ)

  N es finito, dicen 9

• Proporcionar aritmética básica, al menos la siguiente 3:

  • de adición (A + B)

  • Resta (A-B)

  • división entera, por ejemplo, piso (A/B).

  • Estrictamente hablando, realmente no necesito una habilidad de conversión de base10 - los números serán el 100% del tiempo en base36. Así que estoy bastante bien si la solución NO implementa la conversión de base36 a base10 y viceversa.

No me importa mucho si la solución es de fuerza bruta "convertir a la base 10 y de vuelta" o convertir a binario, o algún enfoque más elegante "nativa" realizar operaciones Basen (como se indica arriba, hacia/desde la conversión de base10 no es un requisito). Mis únicas 3 consideraciones son:

1. Se adapta a las especificaciones mínimas por encima de

2. Es "estándar". Actualmente estamos usando un viejo módulo basado en la conversión de base10 hecho a mano que tiene errores y es una mierda.

   Prefiero reemplazarlo con alguna solución de CPAN de uso común en lugar de volver a escribir mi propia bicicleta desde cero, pero soy perfectamente capaz de construirla si no existe una posibilidad estándar mejor.

3. Debe ser rápido (aunque no muy rápido). Algo que toma 1 segundo para resumir 2 números base36 de 9 dígitos es peor que cualquier cosa que pueda rodar por mi cuenta :)

P.S. Solo para proporcionar un contexto en caso de que las personas decidan resolver mi problema XY además de responder a la pregunta técnica anterior :)

Tenemos un árbol bastante grande (almacenado en DB como un grupo de bordes), y necesitamos para superponer el orden en un subconjunto de ese árbol. Las dimensiones de los árboles son grandes tanto en profundidad como en anchura. El árbol está MUY activamente actualizado (inserta y elimina y mueve ramas).

Esto se hace actualmente teniendo una segunda tabla con 3 columnas: parent_vertex, child_vertex, local_order, donde local_order es una cadena de 9 caracteres construida de A-Z0-9 (por ejemplo, número base 36).

consideraciones adicionales:

• se requiere que el orden local es única por niño (y, obviamente, único para cada padre),

• Cualquier completa reordenación de un padre es algo caro, y por lo tanto la implementación es intentar y asignar - para un padre con hijos X - los pedidos que están distribuidos de manera uniforme entre 0 y 36 ** 10-1, de modo que casi ningún inserto de árbol resulte en un reordenamiento completo.

Answer 1

¿Qué hay de Math::Base36?

Answer 2

Apostaría mi dinero en la conversión a base10 y viceversa.

Si no tiene que hacer esto muy a menudo y los números no son muy grandes, esa es la forma más fácil (y por lo menos menos compleja => menor cantidad de errores) de hacerlo.

Por supuesto, otra manera de hacerlo es también guardar el número base10 para fines de cálculo solamente, sin embargo, no estoy seguro de si esto es posible o tiene alguna ventaja en su caso

Answer 3

Supongo que los módulos de núcleo Perl están bien?

Cómo sobre el uso de matemáticas nativa (binario) número entero y convertir el resultado de la base 36 utilizando POSIX::strtol()

Hay enorme variabilidad en la velocidad en los diferentes métodos para convertir a/de base 36. strtol es 80x más rápido que un Math :: Base36: decode_base36 por ejemplo y los subs de conversión que tengo en el listado son de 2 a 4 veces más rápidos que Math :: Base36. También apoyan cualquier base número entero de hasta 62. (ampliarse fácilmente añadiendo caracteres a la matriz nums.)

Aquí es un punto de referencia rápida:

#!/usr/bin/perl 
use POSIX; 
use Math::BaseCnv; 
use Math::Base36 ':all'; 
use Benchmark; 

{ 
    my @nums = (0..9,'a'..'z','A'..'Z'); 
    $chr=join('',@nums); 
    my %nums = map { $nums[$_] => $_ } 0..$#nums; 

    sub to_base 
    { 
     my ($base, $n) = @_; 
     return $nums[0] if $n == 0; 
     return $nums[0] if $base > $#nums; 
     my $str = ''; 
     while($n > 0) 
     { 
      $str = $nums[$n % $base] . $str; 
      $n = int($n/$base); 
     } 
     return $str; 
    } 

    sub fr_base 
    { 
     my ($base,$str) = @_; 
     my $n = 0; 

     return 0 if $str=~/[^$chr]/; 

     foreach ($str =~ /[$chr]/g) 
     { 
      $n *= $base; 
      $n += $nums{$_}; 
     } 
     return $n; 
    } 
} 

$base=36; 
$term=fr_base($base,"zzz"); 

for(0..$term) { push @numlist, to_base($base,$_); } 

timethese(-10, { 
     'to_base' => sub { for(0..$#numlist){ to_base($base,$_); } }, 
     'encode_base36' => sub { for(0..$#numlist){ encode_base36($_); } }, 
     'cnv->to 36' => sub { for(0..$#numlist){ cnv($_); } }, 
     'decode_base36' => sub { foreach(@numlist){ decode_base36($_); } }, 
     'fr_base' => sub { foreach(@numlist){ fr_base($base,$_); } }, 
     'cnv->to decimal' => sub { foreach(@numlist){ cnv($_,$base,10); } }, 
     'POSIX' => sub { foreach(@numlist){ POSIX::strtol($_,$base);}}, 
});