Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

comment on

( [id://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?? :)

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

zzSPECTREz

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

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



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others exploiting the Monastery: (8)
As of 2024-04-25 11:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found