Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive sorting in Perl

I have a hash that contains keys that correspond to database subscripts, but the database can have multidimensional records so the key could be a single subscript, or a list of subscripts.

I need to find a way to sort these records so I can print them in a logical order.

Example:

my $data = {
    '1,1,1' => 'data1',
    '1,2'   => 'data2',
    '1,1,3' => 'stuff',
    '2,1,1' => 'data3',
    '2,1,2' => 'data4',
    '2,1,3' => 'data blah',
    '2,2,2' => 'datawk2n',
    '3,1,2' => 'more',
};

# Should print the keys in the properly sorted order
print join "\n", sort some_function keys %$data;

sub some_function {
    # Do some sorting magikz
}

I want it to sort by the leftmost subscript first. If the leftmost value is identical I want to move to the next value and compare those. If those are identical I want to continue to the next one ... and so on ... until all possibilities are exhausted.

This will most likely involve some recursion, but I can't figure out how to make recursion work with those fancy $a and $b variables.

What can I put in some_function to get the following output?

1,1,1
1,1,3
1,2
2,1,1
2,1,2
2,1,3
2,2,2
3,1,2
like image 427
tjwrona1992 Avatar asked May 09 '16 21:05

tjwrona1992


People also ask

How do I sort in ascending order in Perl?

Perl has two operators that behave this way: <=> for sorting numbers in ascending numeric order, and cmp for sorting strings in ascending alphabetic order. By default, sort uses cmp -style comparisons.

How do I sort a list in Perl?

sort() function in Perl is used to sort a list with or without the use of method of sorting. This method can be specified by the user in the form of subroutines or blocks. If a subroutine or block is not specified then it will follow the default method of sorting.

How do I sort an array of numbers in Perl?

Perl has a built-in function called sort that can, unsurprisingly, sort an array. In its most simple form, you just give it an array, and it returns the elements of that array in a sorted order. @sorted = sort @original.


1 Answers

The following is the fastest solution (by far!):

my @sorted_keys =
   map { join ',', unpack 'N*', $_ }
   sort
   map { pack 'N*', split /,/, $_ }
   keys(%$data);

If you want something simpler, and still quite fast, you could use a "natural sort".

  • Sort::Key::Natural

    use Sort::Key::Natural qw( natsort );
    
    my @sorted_keys = natsort(keys(%$data));
    
  • Sort::Naturally

    use Sort::Naturally qw( nsort );
    
    my @sorted_keys = nsort(keys(%$data));
    

Benchmarks:

       Rate   SN  SKN  grt
SN   3769/s   -- -40% -88%
SKN  6300/s  67%   -- -79%
grt 30362/s 705% 382%   --

Benchmark code:

use strict;
use warnings;

use Benchmark          qw( cmpthese );
use List::Util         qw( shuffle );
use Sort::Key::Natural qw( );
use Sort::Naturally    qw( );

my @keys =
   shuffle
      split ' ',
         '1 1,0 1,1 1,1,1 1,1,3 1,2 2,1,1 2,1,2 2,1,3 2,2,2 3,1,2 10,1,1';

sub grt {
   my @sorted_keys =
      map { join ',', unpack 'N*', $_ }
      sort
      map { pack 'N*', split /,/, $_ }
      @keys;
}

sub SKN { my @sorted_keys = Sort::Key::Natural::natsort(@keys); }

sub SN { my @sorted_keys = Sort::Naturally::nsort(@keys); }

cmpthese(-3, {
   grt => \&grt,
   SKN => \&SKN,
   SN  => \&SN,
});
like image 177
ikegami Avatar answered Sep 22 '22 08:09

ikegami