Did the sort do anything?

[Lew]

The usual problem with heapsort-based algorithms, besides having O(n
lg n) as a lower bound, is that they have lousy locality of reference.
In traditional heapsort, once the heap is built, you proceed by taking
the leftmost element in the array (the root of the heap) and swapping
it with the last element of the heap part of the array. If the heap
size is not trivial, you're doing a load from one cache line and a
store into another.

Smoothsort appears to fix this problem, because it keeps the largest
elements at the right end of the forest of heaps, so the move from the
forest of heaps to the sorted part of the array is local. It also
avoids having to re-heapify large heaps, since it always operates on
the smallest heap left in the forest, and it splits large heaps as it
dequeues from them. In fact, while I've never tried implementing
smoothsort, much less analyzed its behavior, it looks like it has
quite good locality of reference.

But Timsort has great locality of reference, because it deals in runs
(including reversed-order runs), and when it doesn't have a decent run
at the current position, it sorts a small fragment of the array to
create one.

On the other hand, when sorts are used in most modern applications,
they're comparing keys that are located elsewhere in memory and
probably invoking a user-supplied comparison function, so locality of
reference may not have much effect on performance.

Proving once again that theory can lead you to town, but it can't find you the
concierge at the hotel. For that you need measurement under realistic
conditions. Evidence will tell you if the difference between Timsort,
Quicksort, Smoothsort, Bubble sort or Stupidsort even matters, much less which
one wins.

--
Lew
Stupidsort: scan the array looking for the largest element. Copy it to one
end of temporary array. Repeat with next element, placing in next position,
repeat until whole array is copied. Quicksort the result. Copy it back to
the original array. Cache the results.

 

[Lew]

You wag!

My dear boy, I am jolly pleased by all the attention, what? But I fear the
guess is incorrect. I am, in fact, not British, nor do I recognize any
monarch as having authority over me, save the butterfly.

And Patricia is right - I was calling the respondent "Laramie" because I find
his antics offensive. But because I honor and respect Patricia, not because
of any bonhomie I might feel towards Lawrence who ill deserves it because he's
a schmuck, I will not call him other names than "Lawrence".

To be fair, Lawrence's posts are improving. He's much more consistently on
topic, and he's actually started citing evidence and facts to back up his
conclusions. So his value to this group has improved.

 

[Heike Svensson]

On 5/18/2011 10:07 AM, Lew wrote:
...

Why "Laramie" in particular?

...

Thank you. The smooth functioning of this newsgroup is important to me,
and courtesy is the grease in the wheels of the relationships between
people, especially when communication is over a limited channel.

Alas, this advice is probably wasted on many of this newsgroup's regulars.

 

[Robert Klemme]

I'm English, and lived in England for the first 25 years of my life.

I might agree with you if Lew applied nicknames when agreeing as often
as he does when disagreeing with an article. As it is, it seems more
like a way of trying to put someone down than friendly humor.

Right you are.

My dear boy, I am jolly pleased by all the attention, what? But I fear
the guess is incorrect. I am, in fact, not British, nor do I recognize
any monarch as having authority over me, save the butterfly.

So I completely mixed / messed things up. Darn! Hopefully neither you
nor Patricia are feeling insulted by that wrong attribution of mine. I
am sorry for all the noise.

To be fair, Lawrence's posts are improving. He's much more consistently
on topic, and he's actually started citing evidence and facts to back up
his conclusions. So his value to this group has improved.

I am still waiting for some substance for the "SQL lacking
orthogonality" argument. Did I miss something?

Kind regards

robert

 

[Lew]

I am still waiting for some substance for the "SQL lacking orthogonality"
argument. Did I miss something?

"more" is a relative term. And I still don't fully respect his posts, yet.
He loves to make grand-sounding pronouncements without any logic, evidence,
reason or, sometimes, relevance. But improvement is good and should be
encouraged, even when still incomplete.

So, Lawrence, in the spirit of participation, why not address Robert's point?

 

[Lawrence D'Oliveiro]

The way I interpret it, and the way it works in practice, is that
System.identityHashCode(x) returns the value that would be returned by
x.hashCode() if the object referenced by x had inherited the Object
implementation of hashCode, regardless of whether x in fact uses an
overridden hash code.

Ah. Fair enough.

 

[Lawrence D'Oliveiro]

Now that we have clarified the fact that System.identityHashCode(x) is
not merely a synonym for x.hashCode(), have you changed your mind about
the need, or otherwise, for stability when sorting Java objects based on
the entire value of the object's fields?

What do you think I said about “the need, or otherwise, for stability�

 

[Lawrence D'Oliveiro]

On the other hand, when sorts are used in most modern applications,
they're comparing keys that are located elsewhere in memory and
probably invoking a user-supplied comparison function ...

Which is why Python, for example, has dropped the idea of a user comparison,
and emphasized a user key function instead.

 

[Robert Klemme]

Which is why Python, for example, has dropped the idea of a user comparison,
and emphasized a user key function instead.

Ruby solves this quite elegantly, you have all the choices:

# default ordering based on class
# implemented operator <=> (similar
# to compareTo() in Java)
sorted = array.sort

# user provided comparison function
sorted = array.sort {|x,y| x.name <=> y.name}

# key function
sorted = array.sort_by {|x| x.name}
# even shorter
sorted = array.sort_by &:name
# or if you like brackets
sorted = array.sort_by(&:name)

Cheers

robert

 

[Lawrence D'Oliveiro]

In message <6fe88262-
(e-mail address removed)>, Robert Klemme
wrote:

Ruby solves this quite elegantly, you have all the choices:

So did Python, until it turned out some of them weren’t worth using.

 

[Lew]

In message<6fe88262-
(e-mail address removed)>, Robert Klemme
wrote:


So did Python, until it turned out some of them weren’t worth using.

Language Wars! Language Wars!

Java rule! Python drools! Python sucks! Who needs it? Python is simply a
TERRible language! Java was given to us by the GODS! Anyone who feels
different is a pathetic loser!

Language Wars!

 

[Lew]

Ah. Fair enough.

That was only pointed out about five times, O Lawrence.

 

[Lew]

What do you think I said about “the need, or otherwise, for stability�

Please be polite to Patricia. She even stood up for you! For shame!

 

[RedGrittyBrick]

I am, in fact, not British, nor do I recognize
any monarch as having authority over me, save the butterfly.

Bless. Next you'll be suggesting it is possible to be "from the US" and
not recognise the authority of the pope.

 

[Lew]

^^^^^^^
Bless. Next you'll be suggesting it is possible to be "from the US" and not
recognise the authority of the pope.

Sure, why not? It's spelled "Pope", he has no authority over me, either, and
I am from the U.S.

Oh, my God! You predicted that I'd say that! You must be psychic!

I assume you were joking, of course, as it's obvious that one can be from the
U.S. and not recognize the Pope as having authority over oneself. I also
don't recognize Muammar Qaddafi as having authority over me, nor any other
head of state or government of a nation where I do not reside or am not visiting.

Duh.

 

[RedGrittyBrick]

Sure, why not? It's spelled "Pope", he has no authority over me, either,
and I am from the U.S.

Oh, my God! You predicted that I'd say that! You must be psychic!

I assume you were joking, of course, as it's obvious that one can be
from the U.S. and not recognize the Pope as having authority over
oneself. I also don't recognize Muammar Qaddafi as having authority over
me, nor any other head of state or government of a nation where I do not
reside or am not visiting.

I was pointing out your non-sequiteur. Being "from the UK" implies
nothing about what authorities you recognise. So the part about monarchs
was a bit weird. My hat is a dodo.

 

[RedGrittyBrick]

No. I'll suggest that. I'm Jewish-American. I have friends and family
members that are Mormon and Baptist. None of us view the Pope as an
authority figure, at least not one we answer to.

To recap:

RK: Lew is from UK.
Lew: I am not from UK, nor am I a zylophone.
RGB: That's silly! Here's an equally silly example. See?
SS: Did you seriously mean that silly thing?

 

[Robert Klemme]

To recap:

RK: Lew is from UK.
Lew: I am not from UK, nor am I a zylophone.
RGB: That's silly! Here's an equally silly example. See?
SS: Did you seriously mean that silly thing?

LOL

Now that I read this sub thread I am really glad I misplaced Lew. )

Cheers

robert

 

[Lew]

Sure, why not? It's spelled "Pope", he has no authority over me, either,
and I am from the U.S.

Oh, my God! You predicted that I'd say that! You must be psychic!

I assume you were joking, of course, as it's obvious that one can be
from the U.S. and not recognize the Pope as having authority over
oneself. I also don't recognize Muammar Qaddafi as having authority over
me, nor any other head of state or government of a nation where I do not
reside or am not visiting.

I was pointing out your non-sequiteur [sic]. Being "from the UK" implies nothing
about what authorities you recognise. So the part about monarchs was a bit
weird. My hat is a dodo.

What? That's crazy talk. Of course whether I'm from the U.K. affects who I
recognize as an authority over me. Duh. In what way does any monarch have
any authority over me, given that I live in the U.S.? How is it not relevant
that I am not a citizen of any nation that recognizes a monarchy as its
government? Perhaps if you explain that you will go some distance toward
explaining how it's a non sequitur.

 

[Lew]

To recap:

RK: Lew is from UK.
Lew: I am not from UK, nor am I a zylophone.
Xylophone.

RGB: That's silly! Here's an equally silly example. See?
SS: Did you seriously mean that silly thing?

It is an essential part of American culture that we do not recognize a
monarchy. It speaks to how much I am not from the U.K. Your analogy is
utterly flawed, as well as misspelled. "I am not from the U.K., nor do I
evince any characteristic that is quintessentially British, such as
recognizing a monarch as having authority over me. On the contrary, I am so
not from the U.K., that by way of demonstrating that fact let me point out
that I do not even recognize any monarch, let alone Queen Elizabeth II, as
having dominion over me. That's how utterly and trenchantly wrong you are."