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

StackOverflow https://stackoverflow.com/questions/2670869

  •  28-09-2019
  •  | 
  •  

Pregunta

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

Para ser más específico, tengo que ser capaz de hacer lo siguiente:

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

    N es finito, decir 9

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

    • adición (A + B)

    • Resta (A-B)

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

    • En sentido estricto, yo realmente no necesita una capacidad de conversión base10 - los números del 100% del tiempo de estar en base36. Así que estoy bastante bien si la solución no implementa la conversión de volver a base36 base10 y viceversa.

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

  1. Se adapta a las especificaciones mínimas anteriores

  2. Se trata de "estándar". Actualmente estamos utilizando y el módulo de cosecha propia de edad basado en la conversión base10 hecho a mano que está libre de errores y chupa.

    mucho preferiría que lo sustituya con un poco de solución de CPAN comúnmente usado en lugar de volver a escribir mi propia bicicleta a partir de cero, pero soy perfectamente capaz de construirlo si no existe ninguna posibilidad de un mejor estándar.

  3. Debe ser rápido-ish (aunque no la velocidad del rayo). 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. Sólo para proporcionar algún contexto en el caso de personas deciden resolver mi problema XY para mí, además de responder a la pregunta técnica anterior:)

Tenemos un árbol bastante grande (almacenados en el PP como un grupo de bordes), y tenemos que superponer fin en un subconjunto de ese árbol. Las Dimensiones de los árboles son grandes tanto profundidad- y lo ancho sabia. El árbol es muy realizan actualizaciones (inserciones y eliminaciones y la rama se mueve).

Esto se realiza actualmente por tener 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 base 36 número).

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 aplicación es tratar de asignar - para un padre con hijos X - las órdenes que son algo distribuidos uniformemente entre 0 y 36 ** 10 1, por lo que casi no hay inserciones de árboles como resultado una reordenación completa.

¿Fue útil?

Solución

¿Qué hay de Matemáticas :: Base36 ?

Otros consejos

Estoy asumiendo que los módulos básicos de Perl están bien?

¿Y si uso nativo (binario) operaciones aritméticas con enteros y convertir el resultado de la base 36 usando POSIX: : strtol ()

No 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 Matemáticas :: Base36: decode_base36 por ejemplo, y la conversión de los submarinos que tienen en la lista son de 2 a 4 veces más rápido que el de Matemáticas :: Base36. También apoyan cualquier base número entero de hasta 62. (extender fácilmente mediante la adición de caracteres a la matriz nums.)

Aquí es una 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);}},
} );

Yo apostaría mi dinero en convertir a base10 y la espalda.

Si usted no tiene que hacer esto muy a menudo y los números no son muy grandes, que es el más fácil (y por lo tanto menos compleja => menor número de errores) manera 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

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top