Guttman-Rosler Transform. Часть 1: Описание преобразования.

Уже наверное больше года хочу написать про GRT(Guttman-Rosler Transform) и наконец-то дошли руки. Вернее, наткнулся на Sort::External::Cookbook, который и взял за основу своего поста. Повествование решил разбить на две части. Первая с описанием, вторая с результатами тестирования.

Собственно сабж.
Думаю многие знакомы с преобразованием Шварца, которое позволяет повысить эфективность сортировки за счет предварительной подготовки сортируемых данных. Преобразование Гутмана-Рослера это еще один способ повышения эфективности сортировки.

Perl имеет очень удобную в использовании функцию sort. Когда мы хотим нестандартный порядок сортировки, то мы использует колбек, который передаем в функцию sort.
Например, sort {$b <=> $a } @array;

Идея GRT заключается в том, чтобы преобразовать входные данные так, чтобы мы могли сортировать без использования дополнительного колбека( "sort @transformed_array;" )

Тогда вся сортировка будет происходить на уровне C, что даст нам выигрышь в скорости.

Кодирование, сортировка, раскодирование

Стадартный способ сортировки ключей хеша по значению:

my %colors = (
    "Granny Smith"     => "green",
    "Golden Delicious" => "yellow",
    "Pink Lady"        => "pink",
);
my @sorted_by_color = sort { $colors{$a} cmp $colors{$b} } keys %colors;

# Result:
# @sorted_by_color = ( "Granny Smith", "Pink Lady", "Golden Delicious" );

Для реализации этого же с использованием GRT, мы должны сделать 3 шага:

# 1. Закодировать
my @sortkeys;
while ( my ( $variety, $color ) = each %colors ) {
    push @sortkeys, sprintf( "%-6s%-16s", $color, $variety );
}

# @sortkeys = (
#     "green Granny Smith    ",
#     "yellowGolden Delicious",
#     "pink  Pink Lady       ",
# );

# 2. Отсортировать
my @sorted_by_color = sort @sortkeys;    # no sortsub!

# 3. Раскодировать
@sorted_by_color = map { substr( $_, 6 ) } @sorted_by_color;

Способы закодировать данные

sprintf()

Использование функции sprintf для кодирование ключей - это наиболее простой и гибкий способ. Кроме подготовки текстовых данных, мы можем исползовать sprintf  для препобразования числовых данных в строку.

my %prices = (
    "Granny Smith"     => 1.69,
    "Pink Lady"        => 1.99,
    "Golden Delicious" => .79,    # on sale!
);
my @sortkeys;
while ( my ( $variety, $price ) = each %prices ) {
    push @sortkeys, sprintf( "%1.2f%-16s", $price, $variety );
}

# @sortkeys = (
#     "1.69Granny Smith    ",
#     "0.79Golden Delicious",
#     "1.99Pink Lady       ",
# );

Но есть две потенциальные проблемы при использовании sprintf:

1. Вы должны знать заранее максимальную длину сортируемого поля. Если не знаете, то придется пройти по всем данным лишь для того, чтобы это выяснить.
2. Если максимальная длина значительно больше средней длины, то ключи сгенерированные при помощи sprintf займут много лишнего места.

Использование нулевого байта

Вместо использования sprintf для создания строк фиксированной длины, мы можем отделять данные нулевым байтом.

while ( my ( $variety, $color ) = each %colors ) {
    push @sortkeys, "$color\0$variety";
}
my @sorted = sort @sortkeys;
s/.*?\0// for @sorted;

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

pack

pack() может служить менее гибкой альтернативой sprintf() для создания строк фиксированной длины. Однако он более полезен для кодирования положительных целых чисел в компактную сортируемую форму. Следующие форматы корректно сортируются:

# c => signed char                    максимальное значение 127
# C => unsigned char                  максимальное значение 255
# n => 16-bit network short           максимальное значение 65_535
# N => 32-bit network unsigned long   максимальное значение 4_294_967_295

my %first_introduced = (
    "Granny Smith"     => 1868,
    "Pink Lady"        => 1970,
    "Golden Delicious" => 1890,
);
while ( my ( $variety, $year ) = each %first_introduced ) {
    push @sortkeys, ( pack( 'n', $year ) . $variety );
}
my @sorted = map { substr( $_, 2 ) } sort @sortkeys;

Если необходимо отсортировать много больших целых чисел, то pack() будет значительно быстрее и экономичнее по памяти чем sprintf.

Комбинирование разных видов кодирования.

Зачастую комбинирование разных походов является наиболее эффективным.
Вот небольшой пример.

my %apple_stats = (
    "Granny Smith" => {
        color => "green",
        price => 1.69,
        year  => 1868,
    },
    "Pink Lady" => {
        color => "pink",
        price => 1.99,
        year  => 1970,
    },
    "Golden Delicious" => {
        color => "yellow",
        price => .79,
        year  => 1890,
    },
);
my @sortkeys;
while ( my ( $variety, $stats ) = each %apple_stats ) {
    push @sortkeys, (
            $stats->{color} . "\0\0"
          . sprintf( "%1.2f", $stats->{price} )
          . pack( 'n', $stats->{year} ) . "\0\0"
          . $variety 
    );
}
my @sorted = sort @sortkeys;
my @sorted_varieties = map { s/.*\0\0//; $_ } @sorted;

в этом случае sprintf() будет лучшим выбором, при помощи unpack() легче востановить все поля :

while ( my ( $variety, $stats ) = each %apple_stats ) {
    push @sortkeys,
      sprintf( "%-6s%1.2f%04d%-16s",
        @{$stats}{ 'color', 'price', 'year' }, $variety );
}
my @sorted = sort @sortkeys;
for (@sorted) {
    my ( %result, $variety );
    ( @result{ 'color', 'price', 'year' }, $variety ) =
      unpack( 'a6 a4 a4 a16', $_ );
    $_ = { $variety => \%result };
}

Более сложные варианты сортировки

Сортировка по убыванию с использованием оператора побитового отрицания("bitwise not")

Вы можете изменить порядок сортировки на обратный обратив все биты в сортируемых ключах.

while ( my ( $variety, $color ) = each %colors ) {
    push @sortkeys, sprintf( "%-6s%-16s", $color, $variety );
}
@sortkeys = map { ~$_ } @sortkeys;
my @sorted = sort @sortkeys;
@sorted = map { ~$_ } @sorted;
@sorted = map { substr( $_, 5 ) } @sorted;

Сортировка по нескольким полям с разным порядком

Сортировка по нескольким полям с использованем GRT заключается в простой конкатенации полей при помощи sprintf или нулевого байта. Однако, если Вам необходимо использовать разный порядок сортировки для разных полей, то использование нулевого байта не подходит поскольку перевернутые строки могут содержать нулевые байты.

# sort by:
#     color по убыванию,
#     price по возрастанию,
#     year  по убыванию

while (my $variety, $stats) = each %apple_stats) {
    push @sortkeys, (
        (~ sprintf( "%-6s",  stats->{color}  ) ) .
           sprintf( "%1.2f", $stats->{price} )   .
        (~ sprintf( "%04d",  stats->{year}   ) ) .
           sprintf( "%-16s", $variety        )
    );
}
my @sorted = sort @sortkeys;

Сортировка нечувствительная к регистру

Единственный способ сделать сортировку независимой от регистра, не используя при этом  колбек, - это двойное кодирование:

while ( my ( $variety, $color ) = each %colors ) {
    push @sortkeys, ( lc($variety) . "\0\0" . $variety );
    push @sortkeys, ( lc($color) . "\0\0" . $color );
}
my @sorted = sort @sortkeys;
@sorted = map { s/.*?\0\0//; $_ } @sorted;

# @sorted = (
#     "Golden Delicious",
#     "Granny Smith",
#     "green",
#     "pink",
#     "Pink Lady",
#     "yellow",
# );

Дополнительные материалы

1. Есть на CPAN модуль, который облегчает жизнь - Sort::Maker
2. Более детальную информацию можно найти в работе Гутмана и Рослера

PS: Часть 2 будет содержать результаты тестирования.