Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Sorting an array containing version numbers

by appu_rajiv (Novice)
on Dec 22, 2009 at 18:14 UTC ( #813943=perlquestion: print w/ replies, xml ) Need Help??
appu_rajiv has asked for the wisdom of the Perl Monks concerning the following question:

I want to sort an array whose elements are release versions in a.b.c format.
e.g. my @versions = (2.4.74, 3.2.5, 1.14.56, 1.45.2, 3.14.75)
There are many ways to achieve it but I need a very optimized way.

Comment on Sorting an array containing version numbers
Re: Sorting an array containing version numbers
by Corion (Pope) on Dec 22, 2009 at 18:21 UTC

    So, maybe you want to tell us which ways of the many you've already tried, and what results you got with each? This will make it much easier for us to gauge in what direction you want to go.

    For a small number of versions as you've shown, likely a direct sort with a custom comparator subroutine is the quickest. For more items, you might get better performance by packing the version numbers into strings and then let Perl sort them with the native string sort.

Re: Sorting an array containing version numbers
by kennethk (Monsignor) on Dec 22, 2009 at 18:21 UTC
    What have you tried? What makes you think you need heavy optimization? Have you done benchmarking? This sounds like premature optimization to me.

    Using the native Perl sort function with a customized comparison function should do what you need, assuming Perl is fast enough for your needs. sort explains the basics, and combining a split with /\./ and piecewise comparison of the resulting arrays with the numeric comparison operator <=> will handle the rest. If this is not fast enough, you can write it all in C and use XS (perlxs, perlxstut).

Re: Sorting an array containing version numbers
by sweetblood (Parson) on Dec 22, 2009 at 18:22 UTC
    Optimized in what way? If you only have 5 values then any "optimization" is irrelavent. Depending on how many items you have in your list would determine the best sort method, but if it is only 5 then it won't matter.

    Sweetblood

Re: Sorting an array containing version numbers
by salva (Monsignor) on Dec 22, 2009 at 20:12 UTC
    Try Sort::Key::Multi:
    use Sort::Key::Multi 'u3_keysort'; # u3 => 3 unsigned integer keys my @sorted = u3_keysort { /^(\d+)\.(\d+)\.(\d+)$/ } @versions;
    Or you can also use Sort::Key::OID:
    use Sort::Key::OID qw(oidsort); my @sorted = oidsort @versions;
Re: Sorting an array containing version numbers
by talexb (Canon) on Dec 22, 2009 at 21:51 UTC
      I want to sort an array whose elements are release versions in a.b.c format. e.g. my @versions = (2.4.74, 3.2.5, 1.14.56, 1.45.2, 3.14.75)

    I have put together the following solution ..

    #!/usr/bin/perl -w # # Sort version numbers use strict; use warnings; { my @versions = qw/2.4.74 3.2.5 1.14.56 1.45.2 3.14.75/; print "Original version string:\n" . join( "\n", @versions ) . "\n +"; print "Sorted version strings:\n" . join( "\n", sort compareVersionStrings @versions ) . "\n"; } # Compare two version strings. # # Among other assumptions, this code assumes that the version strings + have the # same number of elements in them. Thus, comparing 3 against 2 will w +ork; as # will 3.1 against 2.7 and 3.1.4 against 2.7.18. Comparing 2.0 agains +t 4 will # fail, as will 2.0 against 4.5.6. sub compareVersionStrings { my ( @a, @b ); my @left = split( /\./, $a ); my @right = split( /\./, $b ); return ( $left[0] <=> $right[0] || $left[1] <=> $right[1] || $left[2] <=> $right[2] ); }
    It seems to work, although there are some limitations, as I've explained in the comment.

    However, as others have already pointed out, this sounds like premature optimization.

      There are many ways to achieve it but I need a very optimized way.

    You haven't explained why an optimized method is required. Are you expecting to have to do this thousands of times a second?

    If you're sincere in your request to speed it up, you'll need to hash the version numbers into something that's very easily sorted -- a trivial solution would be to multiply major by 1,000,000, minor by 1,000 and add the three values together, giving you a single number that should sort correctly.

    Alex / talexb / Toronto

    Team website: Forex Chart Monkey, Forex Technical Analysis and Pickpocket Prevention

    "Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

Re: Sorting an array containing version numbers
by Cristoforo (Deacon) on Dec 23, 2009 at 00:47 UTC
    Two handrolled ways using the Schwartzian Transform and the GRT transform.
    #!/usr/bin/perl use strict; use warnings; use Benchmark qw( cmpthese ); my @versions = qw(2.4.74 3.2.5 1.14.56 1.45.2 3.14.75); my @sorted = map {$_->[0]} sort {$a->[1] cmp $b->[1]} map {[$_, pack "C*", split /\./]} @versions; print join("\n", @sorted), "\n"; @sorted = map {join ".", unpack "C*", $_} sort map {pack "C*", split /\./} @versions; print join("\n", @sorted), "\n";

    Chris

Re: Sorting an array containing version numbers
by ikegami (Pope) on Dec 23, 2009 at 01:04 UTC
    Ignoring the "very optimised way" request, here's a "nice a proper way"
    use version; print "$_\n" for sort map version->declare($_), 2.4.74, 3.2.5, 1.14.56, 1.45.2, 3.14.75, 1.12.0, 1.2.0, 1.20.0;

      To put those values in an array in sorted order using this technique, I had to do this:

      for (sort (map {version->declare($_)} @unsorted_versions)) { push @versions, (sprintf "%s", $_); }

      I also added () and {} to help my amateur mind see precedence and the for/sort/map boundaries easier.

        You just had to change print "$_\n" for to @versions = .
Re: Sorting an array containing version numbers
by tomfahle (Priest) on Dec 23, 2009 at 11:32 UTC

    Have a look at Sort::Versions - a perl 5 module for sorting of revision-like numbers, too.

    #!/usr/bin/perl use strict; use warnings; use Sort::Versions; # exports versions and versioncmp my @version_numbers = qw( 1.1 1.1.1 1.2.1 1.2 1.4 1.6.1 1.6 0.9 1.1.a 1.1.b 1.3 1.5.1 1.5 2.3.5-0022 2.3.5-0041 2.1.4.0046 ); my @sorted = sort versioncmp @version_numbers; print join("\n", @sorted), "\n";

    Running above code yields

    0.9 1.1 1.1.1 1.1.a 1.1.b 1.2 1.2.1 1.3 1.4 1.5 1.5.1 1.6 1.6.1 2.1.4.0046 2.3.5-0022 2.3.5-0041

    HTH, Thomas

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://813943]
Approved by kennethk
Front-paged by biohisham
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (9)
As of 2014-08-27 19:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (250 votes), past polls