Уже наверное больше года хочу написать про GRT(Guttman-Rosler Transform) и наконец-то дошли руки. Вернее, наткнулся на Sort::External::Cookbook, который и взял за основу своего поста. Повествование решил разбить на две части. Первая с описанием, вторая с результатами тестирования.
Собственно сабж.
Думаю многие знакомы с преобразованием Шварца, которое позволяет повысить эфективность сортировки за счет предварительной подготовки сортируемых данных. Преобразование Гутмана-Рослера это еще один способ повышения эфективности сортировки.
Perl имеет очень удобную в использовании функцию sort. Когда мы хотим нестандартный порядок сортировки, то мы использует колбек, который передаем в функцию sort.
Например, sort {$b <=> $a } @array;
Идея GRT заключается в том, чтобы преобразовать входные данные так, чтобы мы могли сортировать без использования дополнительного колбека( "sort @transformed_array;" )
Тогда вся сортировка будет происходить на уровне C, что даст нам выигрышь в скорости.
Собственно сабж.
Думаю многие знакомы с преобразованием Шварца, которое позволяет повысить эфективность сортировки за счет предварительной подготовки сортируемых данных. Преобразование Гутмана-Рослера это еще один способ повышения эфективности сортировки.
Perl имеет очень удобную в использовании функцию sort. Когда мы хотим нестандартный порядок сортировки, то мы использует колбек, который передаем в функцию sort.
Например, sort {$b <=> $a } @array;
Идея GRT заключается в том, чтобы преобразовать входные данные так, чтобы мы могли сортировать без использования дополнительного колбека( "sort @transformed_array;" )
Тогда вся сортировка будет происходить на уровне C, что даст нам выигрышь в скорости.
