Help with sort

am 01.04.2010 02:36:40 von Barry Brevik

I'm having a problem sorting data items that are alpha-numeric strings.
I know how to do it if the string is all alpha or all numeric, but the
combo eludes me.

Take as example the following code. It is my desire that the machine
names be processed in the order that they have been loaded into the
hash. This is an example only- the machine names will not actually be
loaded in order. Also, there will not always be "dashes" separating the
alpha from the numbers:

use strict;
use warnings;

my %mdata =
(
'CALIBRATION1', 1,
'CALIBRATION02', 1,
'LABVIEW-1', 1,
'LABVIEW-2', 1,
'LABVIEW-4', 1,
'LABVIEW-11', 1,
'LABVIEW-12', 1,
'LABVIEW-114', 1,
'YESTECH-L3-RW1', 1,
'YESTECH-L03-RW2', 1,
'YESTECH-L4-RW125',1
);

foreach my $key (sort(keys(%mdata)))
{
print "$key\n";
}

The output of this code is as follows, and you can see that the sort
order is not what I wanted:

CALIBRATION02
CALIBRATION1
LABVIEW-1
LABVIEW-11
LABVIEW-114
LABVIEW-12
LABVIEW-2
LABVIEW-4
YESTECH-L03-RW2
YESTECH-L3-RW1
YESTECH-L4-RW125

Any ideas on how to get this to come out in the "right" order?

Barry Brevik
_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

Re: Help with sort

am 01.04.2010 03:33:32 von jwkenne

On Mar 31, 2010, at 8:36 PM, Barry Brevik wrote:

> I'm having a problem sorting data items that are alpha-numeric strings.
> I know how to do it if the string is all alpha or all numeric, but the
> combo eludes me.
>
> Take as example the following code. It is my desire that the machine
> names be processed in the order that they have been loaded into the
> hash. This is an example only- the machine names will not actually be
> loaded in order. Also, there will not always be "dashes" separating the
> alpha from the numbers:
>
> use strict;
> use warnings;
>
> my %mdata =
> (
> 'CALIBRATION1', 1,
> 'CALIBRATION02', 1,
> 'LABVIEW-1', 1,
> 'LABVIEW-2', 1,
> 'LABVIEW-4', 1,
> 'LABVIEW-11', 1,
> 'LABVIEW-12', 1,
> 'LABVIEW-114', 1,
> 'YESTECH-L3-RW1', 1,
> 'YESTECH-L03-RW2', 1,
> 'YESTECH-L4-RW125',1
> );
>
> foreach my $key (sort(keys(%mdata)))
> {
> print "$key\n";
> }
>
> The output of this code is as follows, and you can see that the sort
> order is not what I wanted:
>
> CALIBRATION02
> CALIBRATION1
> LABVIEW-1
> LABVIEW-11
> LABVIEW-114
> LABVIEW-12
> LABVIEW-2
> LABVIEW-4
> YESTECH-L03-RW2
> YESTECH-L3-RW1
> YESTECH-L4-RW125
>
> Any ideas on how to get this to come out in the "right" order?

It happens that I just had to solve that problem, but in C, not Perl. For what it's worth, it took 59 lines of C code, and still has one technical bug that I've decided to leave in because I can't think of an easy solution and it should only turn up in pathological circumstances (specifically, an aisle in a supermarket with an aisle number over 18 digits long).

You'll have to use the SUBNAME or BLOCK version of the sort function, and do your own left-to-right scan, comparing one character at a time, except that when you hit a digit on both sides, you scan to the end or the first non-digit on each side, convert both sequences of digits to integers (being careful that a leading 0 doesn't force you into octal) and then compare the two resulting numbers. As soon as you hit an inequality, or one key runs out before the other does, you can conclude that a>b or a
Alternatively, if your keys follow enough of a pattern, you can try creating a normalized form of the data and then sorting that instead. It will probably be faster that way, but you have to be certain that your normalized form and your normalization routine will work for all inputs, whereas the above algorithm will work for any arbitrary input, provided that there are no digit strings longer than will fit in an integer.

--
John W Kennedy
"...if you had to fall in love with someone who was evil, I can see why it was her."
-- "Alias"

_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

Re: Help with sort

am 01.04.2010 04:23:15 von Bill Luebkert

Barry Brevik wrote:
> I'm having a problem sorting data items that are alpha-numeric strings.
> I know how to do it if the string is all alpha or all numeric, but the
> combo eludes me.
>
> Take as example the following code. It is my desire that the machine
> names be processed in the order that they have been loaded into the
> hash. This is an example only- the machine names will not actually be
> loaded in order. Also, there will not always be "dashes" separating the
> alpha from the numbers:

This is a little brute force and specific to your data, but may do the
trick:

use strict;
use warnings;

my %mdata = (
'CALIBRATION1', 1,
'CALIBRATION02', 1,
'LABVIEW-1', 1,
'LABVIEW-2', 1,
'LABVIEW-4', 1,
'LABVIEW-11', 1,
'LABVIEW-12', 1,
'LABVIEW-114', 1,
'YESTECH-L3-RW1', 1,
'YESTECH-L03-RW2', 1,
'YESTECH-L4-RW125', 1,
);

sub mysort {

if ($a =~ /^([a-z-]+)(\d+)(.*)$/i) {

my $a1 = $1;
my $a2 = $2;
my $a3 = $3;

if ($b =~ /^([a-z-]+)(\d+)(.*)$/i) {

my $b1 = $1;
my $b2 = $2;
my $b3 = $3;

if ($a1 eq $b1) {
if ($a2 == $b2) {
return $a3 cmp $b3;
}
return $a2 <=> $b2;
}
}
}
$a cmp $b;

}

foreach my $key (sort mysort keys %mdata) { print "$key\n"; }

__END__
_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

Re: Help with sort

am 01.04.2010 06:00:00 von fzarabozo

Hi,

I wrote this sorting subroutine for those cases. It works very fine to me, I
hope it works for you. Include this subroutine in your code and then only
use lines like the following when sorting data:

for my $key (sort alphaANDnumeric keys %mdata) {
print "$key\n";
}

The subroutine I wrote is the following:

sub alphaANDnumeric {
my ($aa, $bb) = ($a, $b);
while (length($aa) and length($bb) and substr($aa, 0, 1) eq substr($bb, 0,
1)) {
$aa = substr($aa, 1);
$bb = substr($bb, 1);
}
return 0 unless (length($aa) or length($bb));
$aa =~ s/^(\d+|\D+).*?$/$1/;
$bb =~ s/^(\d+|\D+).*?$/$1/;
if (defined $aa and $aa =~ /\d/ and defined $bb and $bb =~ /\d/) {
return $aa <=> $bb;
} else {
return $a cmp $b;
}
}

HTH

Francisco Zarabozo

--------------------------------------------------
From: "Barry Brevik"
Sent: Wednesday, March 31, 2010 6:36 PM
To:
Subject: Help with sort

> I'm having a problem sorting data items that are alpha-numeric strings.
> I know how to do it if the string is all alpha or all numeric, but the
> combo eludes me.
>
> Take as example the following code. It is my desire that the machine
> names be processed in the order that they have been loaded into the
> hash. This is an example only- the machine names will not actually be
> loaded in order. Also, there will not always be "dashes" separating the
> alpha from the numbers:
>
> use strict;
> use warnings;
>
> my %mdata =
> (
> 'CALIBRATION1', 1,
> 'CALIBRATION02', 1,
> 'LABVIEW-1', 1,
> 'LABVIEW-2', 1,
> 'LABVIEW-4', 1,
> 'LABVIEW-11', 1,
> 'LABVIEW-12', 1,
> 'LABVIEW-114', 1,
> 'YESTECH-L3-RW1', 1,
> 'YESTECH-L03-RW2', 1,
> 'YESTECH-L4-RW125',1
> );
>
> foreach my $key (sort(keys(%mdata)))
> {
> print "$key\n";
> }
>
> The output of this code is as follows, and you can see that the sort
> order is not what I wanted:
>
> CALIBRATION02
> CALIBRATION1
> LABVIEW-1
> LABVIEW-11
> LABVIEW-114
> LABVIEW-12
> LABVIEW-2
> LABVIEW-4
> YESTECH-L03-RW2
> YESTECH-L3-RW1
> YESTECH-L4-RW125
>
> Any ideas on how to get this to come out in the "right" order?
>
> Barry Brevik
> _______________________________________________
> ActivePerl mailing list
> ActivePerl@listserv.ActiveState.com
> To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs
>
_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

RE: Help with sort

am 01.04.2010 13:03:22 von Brian Raven

Barry Brevik <> wrote:
> I'm having a problem sorting data items that are alpha-numeric
> strings.
> I know how to do it if the string is all alpha or all numeric, but
> the combo eludes me.
>
> Take as example the following code. It is my desire that the machine
> names be processed in the order that they have been loaded into the
> hash. This is an example only- the machine names will not actually be
> loaded in order. Also, there will not always be "dashes" separating
> the alpha from the numbers:
>
> use strict;
> use warnings;
>
> my %mdata =
> (
> 'CALIBRATION1', 1,
> 'CALIBRATION02', 1,
> 'LABVIEW-1', 1,
> 'LABVIEW-2', 1,
> 'LABVIEW-4', 1,
> 'LABVIEW-11', 1,
> 'LABVIEW-12', 1,
> 'LABVIEW-114', 1,
> 'YESTECH-L3-RW1', 1,
> 'YESTECH-L03-RW2', 1,
> 'YESTECH-L4-RW125',1
> );
>
> foreach my $key (sort(keys(%mdata)))
> {
> print "$key\n";
> }
>
> The output of this code is as follows, and you can see that the sort
> order is not what I wanted:
>
> CALIBRATION02
> CALIBRATION1
> LABVIEW-1
> LABVIEW-11
> LABVIEW-114
> LABVIEW-12
> LABVIEW-2
> LABVIEW-4
> YESTECH-L03-RW2
> YESTECH-L3-RW1
> YESTECH-L4-RW125
>
> Any ideas on how to get this to come out in the "right" order?

When you say "It is my desire that the machine names be processed in the
order that they have been loaded into the hash", it suggests that your
question is not about sorting at all. Indeed, it is a FAQ, see 'perldoc
-q "hash.*order"'.

If your question really is about sorting, then a more accurate
description of the keys and how to comare them is needed. However, the
following sort function, which splits the keys into strings of digits
and non-digits for comparison seems to work for the data provided.

use strict;
use warnings;
use List::Util qw{shuffle};

sub sortfun ($$) {
my ($v1, $v2) = @_;
my @v1 = split /(\d+)/, $v1;
my @v2 = split /(\d+)/, $v2;
while (@v1 and @v2) {
my $val1 = shift @v1;
my $val2 = shift @v2;
if ($val1 =~ /^\d+$/) {
if ($val1 != $val2) {
return $val1 <=> $val2;
}
}
elsif ($val1 ne $val2) {
return $val1 cmp $val2;
}
}
return @v1 <=> @v2;
}

my @data = ;
chomp @data;
my @result = sort sortfun @data;
print join("\n", @result), "\n\n";
print "Now after a shuffle\n";
@data = shuffle(@data);
print join("\n", @data), "\n\n";
print "Results in:\n";
@result = sort sortfun @data;
print join("\n", @result), "\n\n";

__DATA__
CALIBRATION1
CALIBRATION02
LABVIEW-1
LABVIEW-2
LABVIEW-4
LABVIEW-11
LABVIEW-12
LABVIEW-114
YESTECH-L3-RW1
YESTECH-L03-RW2
YESTECH-L4-RW125

HTH

--
Brian Raven

Please consider the environment before printing this email.

This e-mail may contain confidential and/or privileged information. If you are not the intended recipient or have received this e-mail in error, please advise the sender immediately by reply e-mail and delete this message and any attachments without retaining a copy.

Any unauthorised copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

RE: Help with sort

am 01.04.2010 13:14:13 von francois.bourgneuf

Hi,
You can solve this using a schwartzian transformation :

@x=3D map {
( @t =3D split /(\d+)/ );
if ( $#t > $max )
{
undef $sort;
$max =3D $#t;
foreach ( 0 .. $max )
{
$occ =3D $_ + 1;
$operator =3D $occ % 2 ? 'cmp' : '<=3D>';
$sort .=3D "\$a->[$occ] $operator \$b->[$occ]";
$sort .=3D '||' unless $_ == $#t;
}
}
[ $_, @t, $sort ]
}
keys %mdata;

$cmd=3Dqq!print foreach map { "\$_->[0]\n" } sort { $sort } \@x!;

eval qq!$cmd!;

---------------------------------------
CALIBRATION1
CALIBRATION02
LABVIEW-1
LABVIEW-2
LABVIEW-4
LABVIEW-11
LABVIEW-12
LABVIEW-114
YESTECH-L3-RW1
YESTECH-L03-RW2
YESTECH-L4-RW125

Bour9

-----Message d'origine-----
De : activeperl-bounces@listserv.ActiveState.com [mailto:activeperl-bounces=
@listserv.ActiveState.com] De la part de Francisco Zarabozo
Envoy=E9 : jeudi 1 avril 2010 06:00
=C0 : Barry Brevik; activeperl@listserv.ActiveState.com
Objet : Re: Help with sort

Hi,

I wrote this sorting subroutine for those cases. It works very fine to me, =
I hope it works for you. Include this subroutine in your code and then only=
use lines like the following when sorting data:

for my $key (sort alphaANDnumeric keys %mdata) {
print "$key\n";
}

The subroutine I wrote is the following:

sub alphaANDnumeric {
my ($aa, $bb) =3D ($a, $b);
while (length($aa) and length($bb) and substr($aa, 0, 1) eq substr($bb, 0,
1)) {
$aa =3D substr($aa, 1);
$bb =3D substr($bb, 1);
}
return 0 unless (length($aa) or length($bb));
$aa =3D~ s/^(\d+|\D+).*?$/$1/;
$bb =3D~ s/^(\d+|\D+).*?$/$1/;
if (defined $aa and $aa =3D~ /\d/ and defined $bb and $bb =3D~ /\d/) {
return $aa <=3D> $bb;
} else {
return $a cmp $b;
}
}

HTH

Francisco Zarabozo

--------------------------------------------------
From: "Barry Brevik"
Sent: Wednesday, March 31, 2010 6:36 PM
To:
Subject: Help with sort

> I'm having a problem sorting data items that are alpha-numeric strings.
> I know how to do it if the string is all alpha or all numeric, but the
> combo eludes me.
>
> Take as example the following code. It is my desire that the machine
> names be processed in the order that they have been loaded into the
> hash. This is an example only- the machine names will not actually be
> loaded in order. Also, there will not always be "dashes" separating the
> alpha from the numbers:
>
> use strict;
> use warnings;
>
> my %mdata =3D
> (
> 'CALIBRATION1', 1,
> 'CALIBRATION02', 1,
> 'LABVIEW-1', 1,
> 'LABVIEW-2', 1,
> 'LABVIEW-4', 1,
> 'LABVIEW-11', 1,
> 'LABVIEW-12', 1,
> 'LABVIEW-114', 1,
> 'YESTECH-L3-RW1', 1,
> 'YESTECH-L03-RW2', 1,
> 'YESTECH-L4-RW125',1
> );
>
> foreach my $key (sort(keys(%mdata)))
> {
> print "$key\n";
> }
>
> The output of this code is as follows, and you can see that the sort
> order is not what I wanted:
>
> CALIBRATION02
> CALIBRATION1
> LABVIEW-1
> LABVIEW-11
> LABVIEW-114
> LABVIEW-12
> LABVIEW-2
> LABVIEW-4
> YESTECH-L03-RW2
> YESTECH-L3-RW1
> YESTECH-L4-RW125
>
> Any ideas on how to get this to come out in the "right" order?
>
> Barry Brevik
> _______________________________________________
> ActivePerl mailing list
> ActivePerl@listserv.ActiveState.com
> To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs
> =

_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs
_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

Re: Help with sort

am 01.04.2010 21:27:04 von Williamawalters

--===============1385596929==
Content-Type: multipart/alternative;
boundary="--------MB_8CC9FE871AA5118_D3C_1E0B8_webmail-m072. sysops.aol.com"

----------MB_8CC9FE871AA5118_D3C_1E0B8_webmail-m072.sysops.a ol.com
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="us-ascii"

-----Original Message-----
From: Barry Brevik <BBrevik@StellarMicro.com>
To: activeperl@listserv.ActiveState.com
Sent: Wed, Mar 31, 2010 8:36 pm
Subject: Help with sort
> I'm having a problem sorting data items that are alpha-numeric string=
s. I know how to do it if the string is all alpha or all numeric, but the=
combo eludes me.?? Take as example the following code. It is my desire th=
at the machine names be processed in the order that they have been loaded=
into the hash. This is an example only- the machine names will not actual=
ly be loaded in order. Also, there will not always be "dashes" separating=
the alpha from the numbers:???? use strict;?? use warnings;???? my %mdata=
=3D?? (???? 'CALIBRATION1',??? 1,???? 'CALIBRATION02',?? 1,???? 'LABVIEW-=
1',?????? 1,???? 'LABVIEW-2',?????? 1,???? 'LABVIEW-4',?????? 1,???? 'LABV=
IEW-11',????? 1,???? 'LABVIEW-12',????? 1,???? 'LABVIEW-114',???? 1,????=
'YESTECH-L3-RW1',? 1,???? 'YESTECH-L03-RW2', 1,???? 'YESTECH-L4-RW125',1?=
? );???? foreach my $key (sort(keys(%mdata)))?? {???? print "$key
> ";=20
>?? }=20
>?=20
> The output of this code is as follows, and you can see that the sort=
=20
> order is not what I wanted:=20
>??=20
>?? CALIBRATION02=20
>?? CALIBRATION1=20
>?? LABVIEW-1=20
>?? LABVIEW-11=20
>?? LABVIEW-114=20
>?? LABVIEW-12=20
>?? LABVIEW-2=20
>?? LABVIEW-4=20
>?? YESTECH-L03-RW2=20
>?? YESTECH-L3-RW1=20
>?? YESTECH-L4-RW125=20
>??=20
> Any ideas on how to get this to come out in the "right" order?=20
>?=20
> Barry Brevik=20

here's a multi-key recursive approach that may fill the bill:
?
use warnings;
use strict;
?
use List::Util qw(shuffle);

MAIN: {? # begin main loop
?
# test words in desired sorted order
my @words =3D qw(
??? CALIBRATION1
??? CALIBRATION02
??? LABVIEW-1
??? LABVIEW-2
??? LABVIEW-4
??? LABVIEW-11
??? LABVIEW-12
??? LABVIEW-114
??? YESTECH-L3-RW1
??? YESTECH-L03-RW2
??? YESTECH-L4-RW125
??? );
?
my $ordered =3D join ' ', @words;? # words in desired order
?
my @sorted =3D sort multi_key shuffle @words;
?
print "$_ \n" for @sorted;
?
die "FAILED: not desired order" unless $ordered eq join ' ', @sorted;
?
print "desired order";
?
}? # end main loop
?
exit;

sub multi_key {
?
??? # assumes $a and $b are always defined.
??? return length($a) <=3D> length($b) unless length($a) and length(=
$b);
?
??? # at this point, neither $a nor $b are empty string.
??? my ($a_alpha, $a_numeric, $a_dashed) =3D split_key($a);
??? my ($b_alpha, $b_numeric, $b_dashed) =3D split_key($b);
?
??? return $a_alpha?? cmp $b_alpha
??????? || $a_numeric <=3D> $b_numeric
??????? || do { local ($a, $b) =3D ($a_dashed, $b_dashed);? multi_key();=
}
???????? ;
?
??? }
?
sub split_key {
??? $_[0] =3D~ m{ \A ([[:alpha:]]*) (\d*) (?<=3D .) (?: - (.+))? \z }xm=
s
??????? or die "malformed key: ``$_[0]''";
??? return $1, $2 ? 0+$2 : 0, defined($3) ? $3 : '';
??? }
?
Output:
?
>perl recursive_multikey_sort_1.pl
CALIBRATION1
CALIBRATION02
LABVIEW-1
LABVIEW-2
LABVIEW-4
LABVIEW-11
LABVIEW-12
LABVIEW-114
YESTECH-L3-RW1
YESTECH-L03-RW2
YESTECH-L4-RW125
desired order

?

----------MB_8CC9FE871AA5118_D3C_1E0B8_webmail-m072.sysops.a ol.com
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset="us-ascii"

or=3Dblack face=3Darial> ntEditable=3Dfalse>

-----Original Message-----

From: Barry Brevik <BBrevik@StellarMicro.com>

To: activeperl@listserv.ActiveState.com

Sent: Wed, Mar 31, 2010 8:36 pm

Subject: Help with sort

rdana, Arial, Sans-Serif; COLOR: #000; FONT-SIZE: 12px" id=3DAOLMsgPart_0_=
34624662-69f2-495f-8773-9cf6af3ea24e>

>=

; I'm having a problem sorting data items that are alpha-numeric strings.=

 I know how to do it if the string is all alpha or all numeric, but the co=

mbo eludes me.   Take as example the following code. It is my de=

sire that the machine names be processed in the order that they have been=

 loaded into the hash. This is an example only- the machine names will not=

 actually be loaded in order. Also, there will not always be "dashes" sepa=

rating the alpha from the numbers:     use strict;&nbs=

p;  use warnings;     my %mdata =3D  =

 (     'CALIBRATION1',    1,  =

;   'CALIBRATION02',   1,     'LAB=

VIEW-1',       1,     'L=

ABVIEW-2',       1,    =

 'LABVIEW-4',       1,   &nbs=

p; 'LABVIEW-11',      1,    =

 'LABVIEW-12',      1,     'L=

ABVIEW-114',     1,     'YESTECH-L=

3-RW1',  1,     'YESTECH-L03-RW2', 1,  =

   'YESTECH-L4-RW125',1   );    =

 foreach my $key (sort(keys(%mdata)))   {    =

; print "$key


> "; 


>   } 


>  


> The output of this code is as follows, and you can see that the sort=

 


> order is not what I wanted: 


>   


>   CALIBRATION02 


>   CALIBRATION1 


>   LABVIEW-1 


>   LABVIEW-11 


>   LABVIEW-114 


>   LABVIEW-12 


>   LABVIEW-2 


>   LABVIEW-4 


>   YESTECH-L03-RW2 


>   YESTECH-L3-RW1 


>   YESTECH-L4-RW125 


>   


> Any ideas on how to get this to come out in the "right" order? 


>  


> Barry Brevik

rdana, Arial, Sans-Serif; COLOR: #000; FONT-SIZE: 12px">here's a multi-key recursive approach that may fill the bill: