Perl Guru Forums: Perl Programming Help: Intermediate: sorting problem

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	LOG IN

Home: Perl Programming Help: Intermediate:
sorting problem

perlkid
stranger

Jul 28, 2000, 2:14 PM

Post #1 of 11 (816 views)

sorting problem	Can't Post

I'm using somone elses script to do data base editing, adding, and removing. It has a sort function and to sort from a-z it uses

@sorted_rows = sort (@new_rows);

It will sort lines by individual fields also.

I needed it to sort by field 5 which contains the number of the line. it counts in order from 1 - 500 or whatever the last line is because I used $count++; to number the lines when I wrote them to a data base. After I add them to a data base I open the data base unsing the data base manager and add lines. But when I add them for the number I'll use decimals so I can get them between numbers.

i.e. I add a line to the bottom of the data base and for the number I put 1.01. I expect this to go to the top of the data base when I sort it by the number field.

So I sort the data base by that field and the data base looks like this in the number field.

1.01
100
101
102
103
104

so on and so on.

I wanted

1.01
1
2
3
4

What can I use to get the numbers to sort properly?

Thanks A lot,

perlkid

Kanji
User

Jul 28, 2000, 3:19 PM

Post #2 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

Your 'wanted' results don't make sense given the dataset, but it sounds like you want to do a numeric sort ...

<BLOCKQUOTE>code:<HR>

sort { $a <=> $b } @new_rows</pre><HR></BLOCKQUOTE>

perlkid
stranger

Jul 28, 2000, 3:36 PM

Post #3 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

Well Said,

I had tough time explaining that. I'm glad you can read minds.

Anyway it worked just great. Thanks a lot Kanji. Smile

perlkid

Kanji
User

Jul 28, 2000, 7:27 PM

Post #4 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

No problem.

As a side, it is possible to get the results you asked for from the dataset you supplied; it just didn't make any sense.

If you're curious (and you're probably not), here's how using the mucho groovy Schwartzian Transform ...

<BLOCKQUOTE>code:<HR>

@sorted_rows =
map { $_->[0] }
sort { $a->[1] <=> $b->[1]
| | $b->[2] <=> $a->[2] }
map { my($no,$dec) = /^\d+$/
? ( $_ - 100, sprintf("%.2f", $_ - 100 ) )
: ( $_, $_ );
$dec =~ s/^(\d+)//;
my $whole = $1;

$no ? [ $no, $whole, $dec ] : ();
} @new_rows;</pre><HR></BLOCKQUOTE>

Yes, thats one major mind ****, although I'm sure there are 'cleaner' ways.

rGeoffrey
User / Moderator

Jul 28, 2000, 9:24 PM

Post #5 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

Here is a 'cleaner' Schwartzian Transform...

<BLOCKQUOTE>code:<HR>

my @newarray =
map { (split /<->/)[1] }
sort
map { /(\d*\.?\d*)$/; join ('<->', sprintf ("%12.5f", $1), $_)}
@array;
</pre><HR></BLOCKQUOTE>

I am a big fan of Schwartzian Transforms, but they can be expensive if used in the wrong places.

Perl's built in sort that works on strings is qsort, and runs in n log n time for arbitrary data. It turns out that n log n is the best that can every be hoped for on arbitrary data.

If you give sort your own action like...

<BLOCKQUOTE>code:<HR>

sort { $a->[1] <=> $b->[1] }
</pre><HR></BLOCKQUOTE>

you then run the risk that your sort will take longer, like running in n squared time.

So the purpose of a Schwartzian Transform is to move the expensive stuff out of the sort and into the two maps. And in the best case, you are left with boring strings and use the built in sort which is the best sort for arbitrary data. This can be a big win because the maps are each done once, while the sort is done enough to get everything in order.

But you can still lose with this strategy. If the array is sufficently short, then the overhead of the maps is larger than the speed up in the sort.

Kanji
User

Jul 28, 2000, 9:56 PM

Post #6 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

Your example looks more like the Guttman-Rosler Transform, which I really haven't played with much but have heard about because of the reported speed increases over the Schwartzian method.

Anyhoo, I think you misread why I threw that ST out there: while yours is indeed cleaner, it's also returns...<UL TYPE=SQUARE><LI>1.01 100 101 102 103 104</UL>...instead of...<UL TYPE=SQUARE><LI>1.01 1 2 3 4</UL>

On a side note, any ideas how much faster the GRT is over the simpler sort { $a <=> $b }?

I know, I know: use Benchmark;, but I'm feeling lazy. :-)

Anyhoo, I suspect for most small(ish) applications, the difference is going to make a neglible contribution in overall speed of the program, with the sort EXPR winning out for simplicity unless you love to micro-optimize. :-)

perlkid
stranger

Jul 29, 2000, 12:08 AM

Post #7 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

Talk About Gurus At Work!

Thanks For All the Input. I'm always intrested in more information. Smile

About the "Schwartzian Transform" and the "Guttman-Rosler Transform". Where do you get that kind of stuff?

I never have to sort more than 2 thousand lines of data but I love to know how to write speedy scripts.

But anyway thanks a lot you guys. With out this forum I don't know what I would do. I'd Probably be banging my head against the wall out of frustration. Smile

perlkid

Kanji
User

Jul 29, 2000, 11:08 AM

Post #8 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

A good place to start is
What are the Schwartzian and Guttman-Rosler Transforms?, although I think I first came across both in news:comp.lang.perl.misc , but I've seen both mentioned in other places (print, etc.)

perlkid
stranger

Jul 30, 2000, 1:46 AM

Post #9 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

Cool, I'll check it out.

Thanks Again For All The Help.

perlkid Smile

rGeoffrey
User / Moderator

Jul 31, 2000, 8:27 AM

Post #10 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

I think my sort is doing what I want and putting things in order.

I tested with...

my @array = ('103', 82, "104.6", 0.23, '101.2', '.762', 105, '102', "1.", 6, "2", "3.01", "3");

and got the order I expected.

But even if it is not quite right, the only part that needs to change is the lower map (between the input array and the sort). By using a long string from sprintf we can make sure that any input number will fit into one string, and don't need multiple fields for the sort.

As to where I learned about such things, I was at last year's The Perl Conference 3.0 when they first presented the paper and won $1000 for best paper. Howerver, I did not know until Kanji pointed it out, that we now have a new name for these things. I thought they were still just Schwartzian Transforms.

If you read the actual paper from the link at the bottom of the Perlfaq link to http://www.hpl.hp.com/personal/Larry_Rosler/sort/sorting.html you will find benchmarks in Appendix A. They seem to get twice the speed using the built in sort over more complicated sorts for arrays longer than 1000 lines.

Kanji
User

Jul 31, 2000, 9:18 AM

Post #11 of 11 (816 views)

Re: sorting problem [In reply to]	Can't Post

Right, that's what was wanted (and why I spat out the simpler sort {$a<=>$b}), but not what was asked for (which is where the ST came into the picture).

I'm sure my ST could be changed into a GRT, though. Prolly along the lines of the following with more sanity checking ...

<BLOCKQUOTE>code:<HR>

@newarray =
map { (split /<->/)[1] }
sort
map {
my $no = my $dec = $_;

if ( /^\d+$/ ) {
$no -= 100;
$dec = "$no.999";
}

$no ? join ('<->', sprintf ("%12.5f", $dec ), $no )
: ( );
} @array;</pre><HR></BLOCKQUOTE>

Search for (options)

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives