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.
Re: Sorting an array containing version numbers
by Corion (Patriarch) 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.
| [reply] |
Re: Sorting an array containing version numbers
by kennethk (Abbot) 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). | [reply] [d/l] [select] |
Re: Sorting an array containing version numbers
by salva (Canon) on Dec 22, 2009 at 20:12 UTC
|
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;
| [reply] [d/l] [select] |
Re: Sorting an array containing version numbers
by sweetblood (Prior) 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.
| [reply] |
Re: Sorting an array containing version numbers
by ikegami (Patriarch) 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;
| [reply] [d/l] |
|
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. | [reply] [d/l] |
|
You just had to change print "$_\n" for to @versions =.
| [reply] [d/l] [select] |
Re: Sorting an array containing version numbers
by talexb (Chancellor) on Dec 22, 2009 at 21:51 UTC
|
#!/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.
| [reply] [d/l] |
Re: Sorting an array containing version numbers
by tomfahle (Priest) on Dec 23, 2009 at 11:32 UTC
|
#!/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
| [reply] [d/l] [select] |
Re: Sorting an array containing version numbers
by Cristoforo (Curate) 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 | [reply] [d/l] |
|
|