Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

So I need to handle sorting some strings that contain numbers. Instead of rolling my own, I did a super search to see what others have done and found this example by tye. Just a few lines of code and does exactly what I need. Just could not understand what the heck it was doing at first glance. So I decided to deconstruct it and ask you all if I got it right.

Lets analyze the code:

my @list = <DATA>;

Read in the data to the unsorted list. Ok, this part is easy. :)

my @sorted = @list[ map { unpack "N", substr($_,-4) } sort map { my $key = $list[$_]; $key =~ s[(\d+)][ pack "N", $1 ]ge; $key . pack "N", $_ } 0..$#list ];

Ok this is not as simple to follow.. Lets break it down.

my @sorted = @list[ ... ];

Ok, we are assigning an array slice to the @sorted array. So if the code between the brackets returned "1,5,2,3" then we the sorted array would be assigned $list[1], $list[5], $list[2], $list[3] in that order. The code inside the brackets returns the order which is assigned using an array slice.

map { my $key = $list[$_]; $key =~ s[(\d+)][ pack "N", $1 ]ge; $key . pack "N", $_ } 0..$#list

What the??? Ok.. lets see.. First lets look at what the map is doing:

map { ... } 0..$#list

Ok, The map is just itterating over the number 0 .. to the subscript of the last element in the array @list. So if there are 5 elements of in the array map will be getting 0 .. 4. So why are we not just doing for $a = ( 0 .. $#list)? That is because we want map to return a modified list to be sorted.

my $key = $list[$_] $key =~ s[(\d+)][ pack "N", $1 ]ge;

Now what is going on inside the map? Here we are setting $key to a value from the @list. We then use a greedy regex to globaly replace all numbers with the number packed as a 32 bit Big Endian Number. So the string "Happy4" would be converted to "Happy" . chr(00) . chr(00). chr(00) . chr(04). The modifier to the regex "e" evaluates the right side of the substitution as perl code.

$key . pack "N", $_

Now we are taking the converted string and adding that elements position in the unsorted array as a packed 32 bit Big Endian Number and returning this value from the map.

This results in a list of the unsorted array with all number converted to 32 bit Big Endian Format and the position tacked on to the last 4 bytes. This list is returned to the builtin sort function which can then sort the resulting array asciibetically. This sorts how we think it should.

Given the strings "apple1", "apple2", "apple3","apple20". A normal sort would return the results in the order:

  1. apple1
  2. apple2
  3. apple20
  4. apple3

With the conversion from this routine, the strings are converted to:

  1. "apple" . chr(00) . chr(00) . chr(00) . chr(1)
  2. "apple" . chr(00) . chr(00) . chr(00) . chr(2)
  3. "apple" . chr(00) . chr(00) . chr(00) . chr(3)
  4. "apple" . chr(00) . chr(00) . chr(00) . chr(20)

Because of this conversion, the strings sort properly.

Ok now for the last bit of code.

map { unpack "N", substr($_,-4) }

What this does is takes the last 4 chars of each string which is the the position in the unsorted array packed in Big Endian Format and unpacks it and returns it to be used as an array slice.

So given the following

@list = ( 'apple01', 'apple10', 'apple20', 'apple3', 'apple4');

all the following sorts and maps result in a statement that would simplify as

 my @sorted = @list[ 0, 3, 4, 1, 2];

Pretty cool. ++tye!!

So only limitations I can see, would it could only sort a list up to 4,294,967,295 strings.. Not to bad.

Anything you think Im missing.. Or any reason not to use this for sorting these types of strings? Performance issues? Bugs? etc.. You still using it tye?? :)

Also found this module: Sort::Naturally. Which looking at the source is quite a bit of code.


In reply to [ Natural Sort ]: Sorting a string with numbers by zzspectrez

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others imbibing at the Monastery: (6)
    As of 2021-05-11 01:26 GMT
    Find Nodes?
      Voting Booth?
      Perl 7 will be out ...

      Results (111 votes). Check out past polls.