Did the sort do anything?

[Tom Anderson]

He was right about gotos being harmful, but I’m still not sure I
understand his remark that “computer science is no more about computers
than astronomy is about telescopesâ€.

He was a European.

tom

 

[Lawrence D'Oliveiro]

System.identityHashCode(x) does not necessarily return the same as
x.hashCode() ...

It says it does
<http://developer.android.com/reference/java/lang/System.html#identityHashCode(java.lang.Object)>:

The hash code returned is the same one that would be returned by the
method java.lang.Object.hashCode(), whether or not the object's class
has overridden hashCode().

It means "not the same object".

It means “can be distinguishedâ€. That is the literal meaning of “distinctâ€.

For example, equality for Integer is based only on the numeric value of
the integer the object represents.

Which brings us back to the point I made before, about whether the sort key
is computed from the entire value or not.

 

[Lawrence D'Oliveiro]

First, that applies to equals and hashCode and to == and
identityHashCode, but not to equals and identityHashCode.

Which of those has to do with the concepts of “distinct†and “equal†as
ordinarily understood?

 

[Lawrence D'Oliveiro]

He was a European.

Is that supposed to mean something?

 

[markspace]

Ah, the old imitate Maxwell Smart in a meaningless attempt to sound sage
trick.

He missed it by *that much*, too....

 

[Lew]

Is that supposed to mean something?

It means that he was from Europe.

 

[Lew]

Your attributions are messed up. You quote two people, but only attribute one.

Which of those has to do with the concepts of “distinct†and “equal†as
ordinarily understood?

First answer how these terms are "ordinarily understood", according to you.

"Distinct" does not mean "not equal". "Distinct" means "not identical".
"Equal" means "have the same value". Things can be distinct and equal, as
Patricia has pointed out several times now.

Java embodies this distinction by having both the operator == and the method
'equals()'. Distinct objects can be equal. For two references 'a' and 'b',
both 'a != b' and 'a.equals( b )' can be true at once.

So to answer your question, Laramie, 'equals()' applies to the concept of
"equal" as ordinarily understood; '==' applies to "distinct" as ordinarily
understood; 'hashCode()' applies to both "equal" and "distinct" as ordinarily
understood; and 'System.identityHashCode()' has to do with "distinct" as
ordinarily understood.

Capisce?

 

[thoolen]

On 16/05/2011 5:32 PM, Lew wrote:
1> Newsgroups: comp.lang.java.programmer

1> Your attributions are messed up. You quote two people, but only
1> attribute one.

What do D'Oliveiro's attributions have to do with Java, Lew?

1> So to answer your question, Laramie, 'equals()' applies to the concept
1> of "equal" as ordinarily understood; '==' applies to "distinct" as
1> ordinarily understood; 'hashCode()' applies to both "equal" and
1> "distinct" as ordinarily understood; and 'System.identityHashCode()' has
1> to do with "distinct" as ordinarily understood.

Who is "Laramie", Lew? There is nobody in this newsgroup using that alias.

 

[Lew]

That says a different thing, that it returns the same as *Object* hashCode(),
not x.hashCode().

 

[Gheerax IV]

It says it does
<http://developer.android.com/reference/java/lang/ System.html#identityHashCode%28java.lang.Object%29>:

The hash code returned is the same one that would be returned by the
method java.lang.Object.hashCode(), whether or not the object's
class has overridden hashCode().


It means “can be distinguishedâ€. That is the literal meaning of
“distinctâ€.


Which brings us back to the point I made before, about whether the sort
key is computed from the entire value or not.

Are you Twisted?

 

[Lawrence D'Oliveiro]

My sample program output showed both x.hashCode() and
System.identityHashCode(x) for x referencing an Integer. The values were
different, because Integer overrides hashCode.

How odd, because the above documentation says otherwise.

 

[Unitary Matrix]

Are you Twisted?

Who is "Twisted", Gheerax IV? There is nobody in this newsgroup using
that alias.

 

[Lew]

How odd, because the above documentation says otherwise.

No, it does npt. It says that 'System.identityHashCode()' returns the same
value as *Object* 'hashCode()', not as the 'x' type's override. I mentioned
this before.

 

[Lew]

The way I interpret it, and the way it works in practice,

and the way it's documented

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.

In other words, Laramie, 'x.hashCode()' can be different from
'Object#hashCode()'. It's called a "method override", and the point of
'System.identityHashCode()' is to ignore any possible override of
'Object#hashCode()' and just use the base version.

 

[Tom Anderson]

Is that supposed to mean something?

He thought so!

http://www.cs.utexas.edu/users/EWD/transcriptions/EWD12xx/EWD1284.html

And elsewhere. There is a thread of disdain for the American approach to
CS running through a number of Dijkstra's notes, which i think is a bit
bleeding rich coming from someone who banked a paycheque from the
University of Texas every month for sixteen years, but there you go.

tom

 

[markspace]

It says it does
<http://developer.android.com/reference/java/lang/System.html#identityHashCode(java.lang.Object)>:

The hash code returned is the same one that would be returned by
the method java.lang.Object.hashCode(), whether or not the object's
class has overridden hashCode().

Ouch, no. Newbie maneuver.

Lots of info on this, but if you override equals(), you must override
hashCode() because Object#hashCode() will not have the right semantics.
Basically, in this case Object#hashCode() will return different hash
codes for objects that compare equals() == true, and that breaks the
contract.

Which brings us back to the point I made before, about whether the
sort key is computed from the entire value or not.

Depends on the Comparator you are using.

 

[Robert Klemme]

On 5/17/2011 4:19 AM, Lew wrote:
...


I am in complete technical agreement with you. I find this a little
embarrassing, because I think making up your own nicknames for people is
very poor style. It would be much politer and more respectful to use
the name from the "From" header or signature.

Patricia

Dear Patricia,

I highly respect your contribution to our community! But I disagree
with you on this one: even if you are correct, a bit of politically
incorrect humor once in a while must be allowed. AFAIK Lew is from UK
- please also keep in mind that the British are well renowned for
their particular kind of humor. By asking him to stop this, you might
actually hurt his cultural identity. ;-)

Warm regards

robert


PS: I am in now way authoritative for questions of humor since I am
from Germany, so please apply the appropriate amount of salt.

 

[RedGrittyBrick]

AFAIK Lew is from UK

You wag!

 

[Boojum]

In other words, Laramie, 'x.hashCode()' can be different from
'Object#hashCode()'.

Who is "Laramie", Lew? There is nobody in this newsgroup using that alias.

 

[Michael Wojcik]

What would shut me up would be a performance comparison of two
comparable-quality implementations of the algorithms, showing that
Timsort wipes the floor with Smoothsort. Is anyone aware of one?

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.