Какой лучший способ сделать арифметику base36 в Perl? - PullRequest
6 голосов
/ 20 апреля 2010

Как лучше всего выполнять арифметику base36 в Perl?

Чтобы быть более конкретным, я должен быть в состоянии сделать следующее:

  • Работа с положительными N-значными числами в базе 36 (например, цифры 0-9 A-Z)

    N конечно, скажем, 9

  • Укажите основную арифметику, по крайней мере, следующие 3:

    • Сложение (A + B)

    • Вычитание (A-B)

    • Целое подразделение, например этаж (A / B).

    • Строго говоря, мне действительно не нужна конверсионная способность base10 - числа будут в 100% времени находиться в base36. Так что я вполне в порядке, если решение НЕ реализует преобразование из base36 обратно в base10 и наоборот.

Меня не очень волнует, является ли решение "грубым принуждением" "преобразование в базу 10 и обратно" или преобразование в двоичный файл, или какой-то более элегантный подход "нативно", выполняющий операции baseN (как указано выше, в / из преобразования base10) не является обязательным требованием). Мои только 3 соображения:

  1. Соответствует минимальным спецификациям, указанным выше

  2. Это "стандарт". В настоящее время мы используем и старый доморощенный модуль, основанный на конвертации в base10, сделанный вручную, с ошибками и отстой.

    Я бы скорее заменил это на какое-нибудь обычно используемое решение CPAN вместо того, чтобы переписывать свой собственный велосипед с нуля, но я вполне способен построить его, если не существует лучшей стандартной возможности.

  3. Должно быть быстрым (но не молниеносным). То, что для суммирования 2-х 9-значных чисел base36 занимает 1 секунду, хуже всего, что я могу сделать самостоятельно:)

P.S. Просто предоставим некоторый контекст на случай, если люди решат мою проблему с XY в дополнение к ответу на технический вопрос выше:)

У нас довольно большое дерево (хранится в БД в виде группы ребер), и нам нужно наложить порядок на подмножество этого дерева. Размеры дерева велики как по глубине, так и по ширине. Дерево ОЧЕНЬ активно обновляется (вставляет, удаляет и перемещает ветви).

В настоящее время это выполняется с помощью второй таблицы с 3 столбцами: parent_vertex, child_vertex, local_order, где local_order - это 9-символьная строка, построенная из A-Z0-9 (например, номер 36).

Дополнительные соображения:

  • Требуется, чтобы местный порядок был уникальным для каждого ребенка (и, очевидно, уникальным для каждого родителя),

  • Любое полное переупорядочение родителя несколько дорого, и, следовательно, реализация состоит в том, чтобы попытаться назначить - для родителя с X потомками - порядки, которые несколько равномерно распределены между 0 и 36 ** 10- 1, так что почти никакие вставки деревьев не приводят к полному переупорядочению.

Ответы [ 3 ]

12 голосов
/ 20 апреля 2010

А как насчет Math :: Base36 ?

9 голосов
/ 20 апреля 2010

Я предполагаю, что модули ядра Perl в порядке?

Как насчет использования собственной (двоичной) целочисленной математики и преобразования из результата base 36 с использованием POSIX :: strtol ()

Существует ОГРОМНАЯ изменчивость скорости в различных методах преобразования в / из базы 36. Strtol в 80 раз быстрее, чем, например, Math :: Base36: decode_base36 и сабвуферы преобразования, которые есть в список в 2-4 раза быстрее, чем Math :: 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);}},
} );
1 голос
/ 20 апреля 2010

Я бы поставил свои деньги на конвертацию в base10 и обратно.

Если вам не нужно делать это очень часто и числа не очень велики, это самый простой (и, следовательно, наименее сложный => наименьшее количество ошибок) способ сделать это.

Конечно, еще один способ сделать это - сохранить число base10 только для вычислительных целей, однако я не уверен, возможно ли это или имеет какое-либо преимущество в вашем случае

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...