在Perl中执行base36算法的最佳方法是什么？

Question

在Perl中执行base36算法的最佳方法是什么？

更具体地说,我需要能够做到以下几点:

• 在基数为36的正N位数字上运算(例如数字为0-9 AZ)

  N是有限的,比如说9

• 提供基本算术,至少以下3:

  • 加法(A + B)

  • 减法(AB)

  • 整个部门,例如楼层(A/B).

  • 严格来说,我真的不需要base10转换能力 - 数字将100%的时间在base36中.所以我很好,如果解决方案没有实现从base36转换回base10,反之亦然.

我不太关心解决方案是否是暴力"转换为基础10并返回"或转换为二进制,或者一些更优雅的方法"本地"执行baseN操作(如上所述,往返于base10转换不是需求).我唯一的三个注意事项是:

1. 它符合上述最低规格

2. 这是"标准".目前我们正在使用基于base10转换的老本土模块,这种模块是手动完成的,这种模块很糟糕,很糟糕.

   我宁愿用一些常用的CPAN解决方案取而代之,而不是从头开始重新编写自己的自行车,但如果不存在更好的标准可能性,我完全有能力构建它.

3. 它必须是快速的(虽然不是闪电般快).需要1秒才能总结2个9位数的base36数字的东西比我自己可以滚动的任何东西都差:)

PS只是提供一些上下文,以防人们决定解决我的XY问题,除了回答上面的技术问题:)

我们有一个相当大的树(作为一堆边存储在DB中),我们需要在该树的子集上叠加顺序.树的尺寸在深度和宽度方面都很大.树非常积极地更新(插入和删除以及分支移动).

目前这是通过具有3列的第二个表来完成的:parent_vertex, child_vertex, local_order其中local_order是由A-Z0-9构建的9个字符的字符串(例如,基数36的数字).

其他考虑因素

• 要求每个孩子的本地订单是唯一的(并且每个父母显然是唯一的),

• 父母的任何完整的重新排序都有些昂贵,因此实现是尝试为具有X个子节点的父节点分配在0到36**10-1之间有些均匀分布的顺序,因此几乎没有树插入导致完全重新排序.

Answer 1

什么数学:: Base36？

Answer 2

我假设Perl核心模块没问题？

如何使用本机(二进制)整数数学并使用POSIX :: strtol()从基数36结果转换

转换到基数36的不同方法的速度存在巨大的变化.例如,Strtol比Math :: Base36:decode_base36快80倍,我在列表中的转换次数比Math快2到4倍: :Base36.它们还支持任何最大为62的整数.(通过在nums数组中添加字符可以轻松扩展.)

这是一个快速的基准:

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