Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
perl.perl6.language
+ new post
About this group
Subscribe to this group
This is a Usenet group - learn more
Message from discussion The Sort Problem
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Rod Adams  
View profile  
 More options Feb 16 2004, 2:48 pm
Newsgroups: perl.perl6.language
From: r...@rodadams.net (Rod Adams)
Date: Mon, 16 Feb 2004 13:46:24 -0600
Local: Mon, Feb 16 2004 2:46 pm
Subject: Re: The Sort Problem
Print | View thread | Show original | Report this message | Find messages by this author

Damian Conway wrote:
> Uri persisted:
> > but int is needed otherwise? int is more commonly a sort key than
> float.
> > it just feels asymetrical with one having a symbol and the other a
> named
> > operator.

> Sorry, but that's the way the language works. The more general and usual
> conversion (to number, not to integer) has the shorter name.

For the record, I do a lot of statistical work. On the sorts where I
care about speed, I'm using floats far more often than ints. Uri's usage
obviously varies from mine. Let's not hack up the language to make sort
more efficient for some arguable benefit.

I would entertain, however, C<float> and C<string> comparators (and
functions in core) that pretty much (if not precisely) alias C<+> and
C<~>, forcing said type.

> >   DC> If you don't explicitly cast either way, C<sort> just DWIMs by
> >   DC> looking at the actual type of the keys returned by the extractor.
> >   DC> If any of them isn't a number, it defaults to C<cmp>.

> > that doesn't work for me. the GRT can't scan all keys before it decides
> > on what comparison operator is needed. the GRT needs to merge keys as
> > they are extracted and it needs to do the correct conversion to a byte
> > string then and not later. you can't DWIM this away if you want the
> > optimization.

> EXACTLY!!! So, if you want the GRT to kick in, you have to make sure the
> return type of your block is appropriate. If you don't give the
> compiler that
> hint, you don't get the optimized sorting.

When fed a number that it doesn't trust to be an int or a float,
couldn't the GRT store the number with C<pack 'Nd', $_, $_>? (ok,
there's some prepping for sign and endian, but you get the point) Seems
like a not-terrible way to handle the issue.

> Here's another example (all praise be to Rod!):

>     @teams = sort [
>                   # 1 parameter so it's a key extractor...
>                   {+ $^team->{WinPct} },
>                   # 2 parameters so it's a comparator...
>                   { ($^a->{Conference} eq $^b->{Conference}
>                         ? ($^b->{ConfWinPct} <=> $^a->{ConfWinPct} ||
>                            $^b->{ConfWon}    <=> $^a->{ConfWon}    ||
>                            $^a->{ConfLost}   <=> $^b->{ConfLost})
>                     : ($^a->{Division} eq $^b->{Division}
>                         ? ($^b->{DivWinPct} <=> $^a->{DivWinPct} ||
>                            $^b->{DivWon}    <=> $^a->{DivWon}    ||
>                            $^a->{DivLost}   <=> $^b->{DivLost})
>                     : 0
>                     )
>                   },
>                   # 1 parameter each so all three are key extractors...
>                   {+ $^team->{Won}  } is descending,
>                   {+ $^team->{Lost} },
>                   {+ $^team->{GamesPlayed} } is descending,
>               ] @teams;

Now that's just spiffy. Except in moving from my P5 version to your P6
version, you have to s/?/??/ and s/:/::/, IIRC.

> >   DC> But you *can't* apply C<is descending> to a Code reference.
> > then how did you apply 'is insensitive'?

> I applied it to the *block* (i.e. a closure definition).
> That's not the same thing as a Code reference.

> > what i am saying is i think that you need to go back to the drawing
> > board to find a clean syntax to mark those flags.

> No, I think we have it...just put the appropriate trait on the extractor
> *block* when you define it.

I really don't see the problem with

@out = sort {lc $_}, @in;

It's short, simple, unambiguous, IMO very clean. But if people want to
take a tool that we're creating anyways elsewhere in the language
(traits) to provide another way to do it, that's fine too.

> > i just don't like the reverse args concept at all. it is not
> > semantically useful to sorting. sorts care about ascending and
> > descending, not a vs b in args.

> The problem is that sometimes comparator logic is suffiently complex that
> a single comparator needs to have a "bit each way", as in Rod's
> football team comparator above.

What my football example was meant to show is that no matter how much we
abuse poor C<sort> in the name of progress, we need to have a way to
drop it all and go back to how we did it in P5, for those truly
pathological cases where nothing else works. If people don't trust this,
I'll come up with something worse.

As a side note, the reason I couldn't find the original sort in question
is that I later scraped it in favor of a more robust 100 line sub to
figure out who ranked where.

But in more common case, how much it break things to have

   type Comparator   ::= Code(Any, Any) returns Int;

become

   type Comparator   ::= Code(Any, Any) returns Int
                                     | '!' Code(Any, Any) returns Int;

where the '!' sets the reverse/descending trait?

So we could get things like:

 @out = sort {!~ $_} @in;
 @out = sort {!+ -M} @in;
 @out = sort {! &complex} @in;

Overall, Damian's proposal looks very good.
Yeah Damian!

-- Rod Adams

PS -- Only pure and utter insanity would lead someone to not make string
the default sort comparator, and I don't think I've heard anyone here
mention they are in favor of doing anything else.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2013 Google