Quelle est la meilleure façon de faire de l'arithmétique en base 36 en Perl ?

Question

Quelle est la meilleure façon de faire de l'arithmétique en base 36 en Perl ?

Pour être plus précis, je dois être capable de faire ce qui suit :

• Opérer sur des nombres positifs à N chiffres en base 36 (par exemple les chiffres sont 0-9 A-Z)

  N est fini, disons 9

• Fournir les bases de l'arithmétique, au moins les suivantes 3 :

  • Addition (A+B)

  • Soustraction (A-B)

  • Division entière, par exemple étage (A/B).

  • À proprement parler, je n'ai pas vraiment besoin d'une capacité de conversion en base 10 - les nombres seront 100 % du temps en base 36. Je ne vois donc pas d'inconvénient à ce que la solution ne permette PAS la conversion de la base 36 à la base 10 et vice versa.

Je ne me soucie guère de savoir si la solution consiste à effectuer une conversion brute en base 10 et inversement, à convertir en binaire ou à adopter une approche plus élégante permettant d'effectuer des opérations en base N de manière "native" (comme indiqué ci-dessus, la conversion en base 10 n'est pas une exigence). Mes trois seules considérations sont les suivantes :

1. Il répond aux spécifications minimales ci-dessus

2. C'est "standard". Actuellement, nous utilisons un vieux module maison basé sur une conversion en base 10 faite à la main, qui est bogué et qui craint.

   Je préférerais largement remplacer cela par une solution CPAN couramment utilisée plutôt que de réécrire mon propre vélo à partir de zéro, mais je suis parfaitement capable de le construire si aucune meilleure possibilité standard n'existe.

3. Il doit être rapide (mais pas aussi rapide que l'éclair). Quelque chose qui prend 1 seconde pour additionner 2 nombres à 9 chiffres en base 36 est pire que tout ce que je peux faire moi-même :)

P.S. Juste pour donner un peu de contexte au cas où les gens décideraient de résoudre mon problème XY pour moi en plus de répondre à la question technique ci-dessus :)

Nous avons un arbre assez grand (stocké dans la base de données comme un tas d'arêtes), et nous avons besoin de superposer l'ordre sur un sous-ensemble de cet arbre. Les dimensions de l'arbre sont importantes, tant en profondeur qu'en largeur. L'arbre est très activement mis à jour (insertions, suppressions et déplacements de branches).

Cela se fait actuellement en ayant un deuxième tableau avec 3 colonnes : parent_vertex, child_vertex, local_order donde local_order est une chaîne de 9 caractères composée de A-Z0-9 (par exemple, un nombre en base 36).

Considérations supplémentaires :

• Il est nécessaire que l'ordre local soit unique par enfant (et évidemment unique par parent),

• Tout réordonnancement complet d'un parent est quelque peu coûteux, et l'implémentation consiste donc à essayer d'assigner - pour un parent avec X enfants - les ordres qui sont distribués de manière assez égale entre 0 et 36**10-1, de sorte que presque aucune insertion d'arbre n'entraîne un réordonnancement complet.

Answer 1

Qu'en est-il Math::Base36 ?

Answer 2

Je suppose que les modules de base de Perl sont acceptés ?

Que diriez-vous d'utiliser le calcul natif (binaire) des nombres entiers et de convertir le résultat en base 36 en utilisant la méthode suivante POSIX::strtol()

Il y a ÉNORME la variabilité de la vitesse dans les différentes méthodes de conversion de/vers la base 36. Strtol est 80x plus rapide que Math::Base36:decode_base36 par exemple et les sous-convertisseurs que j'ai dans la liste sont 2 à 4X plus rapides que Math::Base36. Ils supportent également n'importe quelle base d'entiers jusqu'à 62 (facilement extensible en ajoutant des caractères au tableau nums).

Voici un repère rapide :

#!/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);}},
} );

Answer 3

Je parierais mon argent sur la conversion en base 10 et retour.

Si vous n'avez pas à le faire très souvent et que les chiffres ne sont pas très élevés, c'est la façon la plus simple (et donc la moins complexe => moins de bogues) de le faire.

Bien sûr, une autre façon de procéder consiste à enregistrer le nombre en base 10 uniquement à des fins de calcul, mais je ne suis pas sûr que cela soit possible ou que cela présente un avantage dans votre cas.