Did the sort do anything?
Roedy Green
I am interested in simple algorithms to detect whether the sort
actually did anything.
Some suggestions:
1. do a pairwise compare of the times before the sort, and if all is
in order, bypass the sort.
2. back a copy of the unsorted list of items. After the sort, do a
pairwise compare for identity. If all are identical, the sort did not
do anything.
3. write your own sort that has a boolean function you can ask if it
moved anything.
4. do some sort of checksum before and after.
--
Roedy Green Canadian Mind Products
http://mindprod.com
How long did it take after the car was invented before owners understood
cars would not work unless you regularly changed the oil and the tires?
We have gone 33 years and still it is rare to uncover a user who
understands computers don't work without regular backups.
markspace
> Often you sort things when they are already sorted.
>
> I am interested in simple algorithms to detect whether the sort
> actually did anything.
>
> Some suggestions:
>
> 1. do a pairwise compare of the times before the sort, and if all is
> in order, bypass the sort.
This one here is probably the best idea of those you list. Note that
you'll save a bit of time avoiding sorts with the current merge sort
that Java uses, but a Tim sort (soon to be the standard sort in Java)
does this already, so in the long run you'll just add an O(n) to your sorts.
If possible, you should get on the Java developer list (it requires a
full release though) and make some suggestions. Returning a boolean for
"I did something" is not a terrible idea. I also see occasionally
people ask for a way to keep to disparate lists in sync when sorting.
This might be useful too. I.e., provide a way to override the "swap"
function in the sort.
Andreas Leitgeb
> Often you sort things when they are already sorted.
> I am interested in simple algorithms to detect whether the sort
> actually did anything.
> Some suggestions:
> 1. do a pairwise compare of the times before the sort, and if all is
> in order, bypass the sort.
> 2. back a copy of the unsorted list of items. After the sort, do a
> pairwise compare for identity. If all are identical, the sort did not
> do anything.
> 3. write your own sort that has a boolean function you can ask if it
> moved anything.
> 4. do some sort of checksum before and after.
5. wrap the Collection such, that certain modifications set an "unsorted"-
flag, e.g. if an element is inserted/replaced/appended that doesn't compare
in the intended way with its neighbours. Then shortcut the sort, if the said
flag is clear.
Daniele Futtorovic
> Often you sort things when they are already sorted.
>
> I am interested in simple algorithms to detect whether the sort
> actually did anything.
>
> Some suggestions:
>
> 1. do a pairwise compare of the times before the sort, and if all is
> in order, bypass the sort.
>
> 2. back a copy of the unsorted list of items. After the sort, do a
> pairwise compare for identity. If all are identical, the sort did not
> do anything.
>
> 3. write your own sort that has a boolean function you can ask if it
> moved anything.
>
> 4. do some sort of checksum before and after.
>
I find the checksum idea quite intriguing, actually. It would have to do
more operations than some kind of perhaps binary seep through, (although
just as many if the list actually /is/ sorted). But the average greater
efficiency of e.g. #hashCode() vs. #compare() might well offset that,
meponders.
Is there any existing research on this?
--
DF.
An escaped convict once said to me:
"Alcatraz is the place to be"
Robert Klemme
> Often you sort things when they are already sorted.
>
> I am interested in simple algorithms to detect whether the sort
> actually did anything.
What would the benefit of this be? When you learn the fact the current
sorting run has been done already. And the data tells you nothing about
what future sorts will do. OK, you know, they won't do anything if you
do not modify the collection / array. But you did know that before,
didn't you? And if you insert in sort order then you also know that
there is no additional sort necessary. If you pull the data from some
external source you also do not know whether next time round you need to
sort. So what is this information useful for?
Btw, couldn't option 3 be tricky? Depending on the sorting algorithm
things might be moved around but the final order might be the same as
before. Not that this would be desirable but I am pretty sure there are
sorting algorithms which have this property (probably quicksort). Now,
how then do you interpret your boolean flag? Basically you only know
sequences are identical if there was no movement whatsoever, but if
there was movement then you do not know. Which means you would need to
apply one of the other strategies additionally...
Kind regards
robert
Tom Anderson
> I am interested in simple algorithms to detect whether the sort actually
> did anything.
Write a Comparator that keeps track of how many times it returns >0, and
keep your fingers crossed that the sort algorithm always passes it
parameters in index order? A quick try seems to indicate that this does
work with Arrays.sort, although i don't believe the spec makes it
something you could rely on.
You could do something with a decorator that associates each element with
its index in the list, then use that information to do the order check in
the comparator. I'm not explaining this well, but it's a pretty bad idea,
so i won't.
If you wrote your own implementation, you could simply count the number of
times you swap elements, and if it's nonzero, you know the list was out of
order. This would be a good opportunity to implement a good sorting
algorithm - something that is, unlike mergesort, adaptive and in-place
(although not necessarily stable), perhaps Smoothsort:
http://www.keithschwarz.com/smoothsort/
You could also half-implement your own algorithm; do a linear scan through
your list, checking that each consecutive pair of elements is in order. As
soon as you hit a pair that isn't, stop, ask Collections.sort to sort the
remainder of the list, then go back and merge that half with the sorted
prefix you scanned through. Then return false. If you made it to the end
of the list without finding anything out of order, return true.
tom
--
Can you make fun of everything? Well, my opinion is: if it's been funny,
you were right to do it. -- Coluche
Tom Anderson
> On 10/05/2011 17:06, Roedy Green allegedly wrote:
>
>> 4. do some sort of checksum before and after.
>
> I find the checksum idea quite intriguing, actually. It would have to do
> more operations than some kind of perhaps binary seep through,
A binary seep? What's that, then?
> (although just as many if the list actually /is/ sorted). But the
> average greater efficiency of e.g. #hashCode() vs. #compare() might well
> offset that, meponders.
Do you think hashCode is generally more efficient than compare? I would
have thought the opposite, because for hashCode, you have to examine all
an object's fields, whereas for a compareTo, you only have to examine as
many as it takes to find some which are different. Unless the hash is
cached, as in String.
> Is there any existing research on this?
The only thing i can think of which is remotely similar is the Rabin-Karp
string searching algorithm, which computes a rolling hash over a string to
search it. And the rsync algorithm, which does something similar. And
those really aren't even remotely similar.
Daniele Futtorovic
> On Tue, 10 May 2011, Daniele Futtorovic wrote:
>
>> On 10/05/2011 17:06, Roedy Green allegedly wrote:
>>
>>> 4. do some sort of checksum before and after.
>>
>> I find the checksum idea quite intriguing, actually. It would have to
>> do more operations than some kind of perhaps binary seep through,
>
> A binary seep? What's that, then?
Uuhh... well... kinda like a binary sort, except you'd return (const
bool NOT_ORDERED) instead of swapping.
>> (although just as many if the list actually /is/ sorted). But the
>> average greater efficiency of e.g. #hashCode() vs. #compare() might
>> well offset that, meponders.
>
> Do you think hashCode is generally more efficient than compare? I would
> have thought the opposite, because for hashCode, you have to examine all
> an object's fields, whereas for a compareTo, you only have to examine as
> many as it takes to find some which are different. Unless the hash is
> cached, as in String.
Yes, I thought so because of the caching. Any instance could cache the
hashCode() at least between mutation of its data (theoretically,
assuming it can track mutation), whereas a comparison cannot, because it
compares against something different every time.
In other words, between mutations, each invocation of hashCode() yields
the same result, but each invocation of compare() potentially a
different one (depending on what's compared against).
Joshua Cranmer
> Btw, couldn't option 3 be tricky? Depending on the sorting algorithm
> things might be moved around but the final order might be the same as
> before. Not that this would be desirable but I am pretty sure there are
> sorting algorithms which have this property (probably quicksort).
The term you are looking for is the stability of the sort. A stable sort
preserves the order of equally-compared object; unstable sorts do not.
Of the major sorts, heapsort and quicksort are the only sorts which are
unstable, although a bad of implementation of any stable sort could be
unstable. Wikipedia claims that quicksort can be implemented stably, but
that comes at an O(n) space price.
Java uses quicksort for primitive types in Arrays.sort and mergesort for
reference types: since you can't distinguish two equal primitive types,
you can't tell that quicksort isn't stable.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
Robert Klemme
> On 05/11/2011 02:40 PM, Robert Klemme wrote:
>
> > Btw, couldn't option 3 be tricky? Depending on the sorting algorithm
> > things might be moved around but the final order might be the same as
> > before. Not that this would be desirable but I am pretty sure there are
> > sorting algorithms which have this property (probably quicksort).
>
> The term you are looking for is the stability of the sort.
No, not exactly. Stability only refers to the _output_ of the
complete sort operation. At least in theory a sort could move things
around even though it is stable.
The question what that bit of information is useful for still remains
unanswered.
Cheers
robert
Roedy Green
<tw...@urchin.earth.li> wrote, quoted or indirectly quoted someone who
said :
>Do you think hashCode is generally more efficient than compare? I would
>have thought the opposite, because for hashCode, you have to examine all
>an object's fields, whereas for a compareTo, you only have to examine as
>many as it takes to find some which are different. Unless the hash is
>cached, as in String.
The object as a whole has a hashCode. that is just a 32 bit
operation. The compare might end up comparing a number of long
strings char by char. HashCodes are cached. The speed comes when it
is already computed.
In some cases you can tolerate a small rate of error. I would think
often mistaking a no-change for a change would not be catastrophic,
though the opposite normally would be. I don't think any
hashCode/checksum method could guarantee 100% accuracy.
Roedy Green
<short...@googlemail.com> wrote, quoted or indirectly quoted
someone who said :
>What would the benefit of this be?
A very simple example would be a sort utility that reads data into RAM
and sorts it. If the sort did not change the order, there is no need
to write it back.
Roedy Green
<Pidg...@verizon.invalid> wrote, quoted or indirectly quoted someone
who said :
>
>Java uses quicksort for primitive types in Arrays.sort and mergesort for
>reference types: since you can't distinguish two equal primitive types,
>you can't tell that quicksort isn't stable.
Java's sort on objects is stable IIRC. There you can tell apart
objects that compare equal by their addresses if not other fields in
the object not used in the compare.
In all my years, I had never noticed that stability is irrelevant for
primitives. It is like a pleasant little backscratch to have that
brought to my attention.
Robert Klemme
> On Wed, 11 May 2011 20:40:43 +0200, Robert Klemme
> <short...@googlemail.com> wrote, quoted or indirectly quoted
> someone who said :
>
>> What would the benefit of this be?
>
> A very simple example would be a sort utility that reads data into RAM
> and sorts it. If the sort did not change the order, there is no need
> to write it back.
Sounds plausible - at first. OTOH in such a situation I would probably
rather remember the last modification time and only sort if it has
changed after the last sorted writing. That way you are even more
efficient because you save the effort of read IO as well.
Maybe it's just that I didn't have such a use case but I am still not
really convinced that what you are proposing is so useful.
Kind regards
robert
--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/
Spock
> In some cases you can tolerate a small rate of error. I would think
> often mistaking a no-change for a change would not be catastrophic,
> though the opposite normally would be. I don't think any
> hashCode/checksum method could guarantee 100% accuracy.
Unfortunately, hashCode/checksum methods will never detect change where
there is none, but may sometimes detect no change when there is one,
which is precisely the type of error that would be more serious.
Lawrence D'Oliveiro
> ... a Tim sort (soon to be the standard sort in Java) ...
Gee, I wonder what language that came from ...
Lew
Irrelevant.
--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
Andreas Leitgeb
> On 05/13/2011 11:33 PM, Lawrence D'Oliveiro wrote:
>> In message<iqbmo6$j47$1...@dont-email.me>, wrote:
>>> ... a Tim sort (soon to be the standard sort in Java) ...
>> Gee, I wonder what language that came from ...
> Irrelevant.
I wonder, why Lawrence isn't using Python instead of Java on
the Android...
Lawrence D'Oliveiro
wrote:
> I wonder, why Lawrence isn't using Python instead of Java on
> the Android...
Guess what I recently installed and started using
<http://code.google.com/p/android-scripting/>.
Lawrence D'Oliveiro
> The object as a whole has a hashCode. that is just a 32 bit
> operation.
Is 32 bits enough for a hash code? Birthday paradox and all that...
Lew
Tim Peters wrote it in C.
http://svn.python.org/projects/python/trunk/Objects/listobject.c
And the algorithm itself came from neither C nor any other computer language;
it came from English.
<http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort>
"The underlying techniques are described in this paper (and may have even
earlier origins): "Optimistic Sorting and Information Theoretic Complexity"
Peter McIlroy SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
pp 467-474, Austin, Texas, 25-27 January 1993."
--
Lew
Plppptththpthpphtpthhph!
Lew
I have no idea what the Birthday Paradox has to do with this, but yes, for the
purposes intended the 32-bit hash code supported natively in Java is
sufficient. Why wouldn't it be?
Gene
> Often you sort things when they are already sorted.
>
> I am interested in simple algorithms to detect whether the sort
> actually did anything.
>
> Some suggestions:
>
> 1. do a pairwise compare of the times before the sort, and if all is
> in order, bypass the sort.
If you suspect that the list is close to sorted, you can do one bubble sort pass moving out-of-place elements to their correct locations. At the same time you can track whether this pass produces a completely sorted list and call the library sort if that's not the case.
Tom Anderson
I still prefer Smoothsort. Smoothsort may be brain-freezingly arcane (i've
never managed to implement it correctly!), but is simple, consistent, and
elegant. Timsort is basically a pile of hacks, special cases, and
judiciously-chosen arbitrary constants. Don't get me wrong, i think it's a
brilliant piece of work, and it is clearly very effective - but it's a
work of software engineering rather than computer science, and i like my
sorts to be scientific!
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?
tom
--
Nullius in verba
Lew
> I still prefer Smoothsort. Smoothsort may be brain-freezingly arcane (i've
> never managed to implement it correctly!), but is simple, consistent, and
> elegant. Timsort is basically a pile of hacks, special cases, and
> judiciously-chosen arbitrary constants. Don't get me wrong, i think it's a
> brilliant piece of work, and it is clearly very effective - but it's a work of
> software engineering rather than computer science, and i like my sorts to be
> scientific!
How is "brain-freezingly arcane" compatible with "simple"?
Lew
conversations due to lack of respect for headers, and is signaled by a
"reply-to" with an email-like "...@googlegroups.com" address. It's also
blazingly useless to cc an "invalid" email address, and rude to write Usenet
business to an individual email account anyway.
Please use a proper newsreader if you cannot get GoogleGroups to respect the
conversations. It's ridiculously annoying and also pretty useless to have
your post isolated from the context to which it applies. It
Comments to your point should be reserved for the connected conversation and
not out in this lonely island of nowhere.
markspace
> 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?
I'm not sure, but I believe the advantage of Timsort over Smoothsort is
that Timsort has O(n) performance for both ascending and descending
sequences, where Smoothsort appears to only have O(n) for ascending
sequences.
There was a recent "shoot out" among various sort algorithms, and
Timsort won. I don't recall exactly which algorithms were included, but
I'm sure if Smoothsort were a serious contender it would have been examined.
Robert Klemme
> Comments to your point should be reserved for the connected conversation
> and not out in this lonely island of nowhere.
Lew, I didn't know you had that poetic side. Nice!
Cheers
Tom Anderson
> Tom Anderson wrote:
>
>> I still prefer Smoothsort. Smoothsort may be brain-freezingly arcane
>> (i've never managed to implement it correctly!), but is simple,
>> consistent, and elegant. Timsort is basically a pile of hacks, special
>> cases, and judiciously-chosen arbitrary constants. Don't get me wrong,
>> i think it's a brilliant piece of work, and it is clearly very
>> effective - but it's a work of software engineering rather than
>> computer science, and i like my sorts to be scientific!
>
> How is "brain-freezingly arcane" compatible with "simple"?
Edsger Dijkstra wrote the formal definition in a language of his own
invention (which has dynamic scoping) using a notation you can't even
completely write in ASCII, and accompanied it with a description in
English couched in terms of a mix of mathematical abstractions and
whimsical terminology he made up on the fly:
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD796a.html
It is possible to rephrase it more comprehensibly:
http://www.keithschwarz.com/smoothsort/
As well as that initial barrier, there is the fact that although it's
fairly easy to see what the algorithm is doing, it's much harder to
understand why it works. Keith Schwarz has done a bang-up job of
explaining it, though.
Basically, Dijkstra was a brilliant guy, but a bit of a bastard.
tom
--
a moratorium on the future
Tom Anderson
> On 5/15/2011 3:20 AM, Tom Anderson wrote:
>
>> 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?
>
> I'm not sure, but I believe the advantage of Timsort over Smoothsort is
> that Timsort has O(n) performance for both ascending and descending
> sequences, where Smoothsort appears to only have O(n) for ascending
> sequences.
Interesting point. You could probably get round that by having Smoothsort
make an initial guess at the direction of the sequence, and then sort
backwards (forwards but with an inverted comparison) if appropriate, but
that's the first step down the path of hackery which Timsort has already
so victoriously travelled.
> There was a recent "shoot out" among various sort algorithms, and
> Timsort won. I don't recall exactly which algorithms were included, but
> I'm sure if Smoothsort were a serious contender it would have been
> examined.
I'd be very interested to see that shootout - do you remember where it
was?
markspace
> I'd be very interested to see that shootout - do you remember where it was?
>
I think this is it:
Lawrence D'Oliveiro
Anderson wrote:
> Basically, Dijkstra was a brilliant guy, but a bit of a bastard.
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”.
Lawrence D'Oliveiro
> In all my years, I had never noticed that stability is irrelevant for
> primitives.
It’s only irrelevant for types where the key is the entire value.
If you were sorting integers based on, say, the units digit, then stability
would most certainly become relevant, even thought integers are a
“primitive” type in Java.
If, on the other hand, you were sorting immutable objects of a Java
“reference” type where the key was the entire object state, then stability
would indeed be irrelevant, notwithstanding such types are not considered
“primitive”.
Joshua Cranmer
In Dijkstra's day, I would say that the greater focus on computer
science was on the algorithmic research. At the very least, I am
guessing that he did not approach computer science from a systems
perspective, and instead approached it from the theory end.
Lew
> Tom Anderson wrote:
>> Basically, Dijkstra was a brilliant guy, but a bit of a bastard.
> He was right about gotos being harmful, but I’m still not sure I understand
He was stretching a point to make a point, of course, and the considered
reader will factor that in.
You cannot have a useful computer program without gotos. It was the
willy-nilly, undisciplined, wild goto that Dijkstra deprecated. He
specifically states, "The unbridled use of the go to statement has as an
immediate consequence that it becomes terribly hard to find a meaningful set
of coordinates in which to describe the process progress." Note that he's
speaking of "unbridled" use.
Great word.
The solution, of course, is to harness the goto as one would a horse - confine
it to the traces of an 'if', 'for', 'while', 'do', 'switch', or method.
> his remark that “computer science is no more about computers than astronomy
> is about telescopes”.
He's saying the science is about the science, not the instrument used. He's
also being intentionally coy. Surely you recognize the pattern.
Patricia Shanahan
...
> If, on the other hand, you were sorting immutable objects of a Java
> “reference” type where the key was the entire object state, then stability
> would indeed be irrelevant, notwithstanding such types are not considered
> “primitive”.
Do you consider the result of System.identityHashCode(x) to be part of
the state of the object referenced by x?
If you do, then keys that are the entire state will be rare.
If not, then two immutable objects that are otherwise equal state may
belong to different buckets in a java.util.IdentityHashMap, so their
order in an array could be relevant.
Patricia
Lawrence D'Oliveiro
Shanahan wrote:
> On 5/15/2011 7:32 PM, Lawrence D'Oliveiro wrote:
>
>> If, on the other hand, you were sorting immutable objects of a Java
>> “reference” type where the key was the entire object state, then
>> stability would indeed be irrelevant, notwithstanding such types are not
>> considered “primitive”.
>
> Do you consider the result of System.identityHashCode(x) to be part of
> the state of the object referenced by x?
It is computed from the state, is it not?
Lawrence D'Oliveiro
> On 05/15/2011 10:28 PM, Lawrence D'Oliveiro wrote:
>>
>> ... I’m still not sure I understand his remark that “computer science is
>> no more about computers than astronomy is about telescopes”.
>
> In Dijkstra's day, I would say that the greater focus on computer
> science was on the algorithmic research.
Ah, the old “algorithm” versus “program” meaningless dichotomy.
> At the very least, I am guessing that he did not approach computer science
> from a systems perspective, and instead approached it from the theory end.
Even from a theory end, I had it drummed into me that everything we build is
an “abstract machine”. The fact that some machines are “hardware” and others
“software” is neither here nor there. Even in the real world, the
distinction is often blurred, if not turned entirely on its head.
javax.swing.JSnarker
Not unless the object's address is considered a part of its state. :)
--
public final class JSnarker
extends JComponent
A JSnarker is an NNTP-aware component that asynchronously provides
snarky output when the Ego.needsPuncturing() event is fired in cljp.
Lew
> Patricia Shanahan wrote:
>> Lawrence D'Oliveiro wrote:
>>> If, on the other hand, you were sorting immutable objects of a Java
>>> “reference” type where the key was the entire object state, then
>>> stability would indeed be irrelevant, notwithstanding such types are not
>>> considered “primitive”.
>> Do you consider the result of System.identityHashCode(x) to be part of
>> the state of the object referenced by x?
> It is computed from the state, is it not?
No. It most certainly is not. The identity hash code is computed once for
each object irrespective of and independently of anything else you might
consider the object's state.
As a cursory reading of the Javadocs makes clear:
<http://download.oracle.com/javase/6/docs/api/java/lang/System.html#identityHashCode(java.lang.Object)>
Even without the rather intelligent step of checking the documentation, you
can reason out that the answer must be no. Either the identity hash code is
part of the state, in which case it is not computed from the state but *is*
part of the state, or it is not, in which case it is not computed from the
state. Which it is depends on your definition of "the state", i.e., whether
you include the identity hash code as part of the state. Yes, it's
tautological, but that's the result of the way you framed the question.
Lew
> Joshua Cranmer wrote:
>> Lawrence D'Oliveiro wrote:
>>> ... I’m still not sure I understand his remark that “computer science is
>>> no more about computers than astronomy is about telescopes”.
>> In Dijkstra's day, I would say that the greater focus on computer
>> science was on the algorithmic research.
> Ah, the old “algorithm” versus “program” meaningless dichotomy.
Ah, the old imitate Maxwell Smart in a meaningless attempt to sound sage trick.
Patricia Shanahan
Only if you consider it to be part of the state. Distinct objects
probably have different identity hash codes regardless of whether their
fields all have the same values.
Its existence ensures that program behavior can be affected by object
sort stability or instability, even if the sort key includes all fields.
The sort key would have to also include the identity hash code to make
stability irrelevant.
Patricia
Lawrence D'Oliveiro
Shanahan wrote:
> Distinct objects probably have different identity hash codes regardless of
> whether their fields all have the same values.
“By contract, any two objects for which equals(Object) returns true must
return the same hash code value.”
<http://developer.android.com/reference/java/lang/Object.html#hashCode%28%29>
“Distinct” would presumably mean “not equal”.
> Its existence ensures that program behavior can be affected by object
> sort stability or instability, even if the sort key includes all fields.
> The sort key would have to also include the identity hash code to make
> stability irrelevant.
The sort key would have to be consistent with the definition of “equality”,
would it not?
javax.swing.JSnarker
> In message<kemdnZVnBva8n0zQ...@earthlink.com>, Patricia
> Shanahan wrote:
>
>> Distinct objects probably have different identity hash codes regardless of
>> whether their fields all have the same values.
>
> “By contract, any two objects for which equals(Object) returns true must
> return the same hash code value.”
>
> <http://developer.android.com/reference/java/lang/Object.html#hashCode%28%29>
>
> “Distinct” would presumably mean “not equal”.
First, that applies to equals and hashCode and to == and
identityHashCode, but not to equals and identityHashCode.
Second, it means that objects that are the same must have the same hash
code, but not the other way around. Different objects are allowed to
have the same hash code.
>> Its existence ensures that program behavior can be affected by object
>> sort stability or instability, even if the sort key includes all fields.
>> The sort key would have to also include the identity hash code to make
>> stability irrelevant.
>
> The sort key would have to be consistent with the definition of “equality”,
> would it not?
If it included the identity hash code, it would have to be consistent
with ==.
Lew
> In message<kemdnZVnBva8n0zQ...@earthlink.com>, Patricia
> Shanahan wrote:
>
>> Distinct objects probably have different identity hash codes regardless of
>> whether their fields all have the same values.
>
> “By contract, any two objects for which equals(Object) returns true must
> return the same hash code value.”
>
> <http://developer.android.com/reference/java/lang/Object.html#hashCode%28%29>
That's the wrong reference, as that is not the method under discussion.
The discussion is about a different method in a different class:
> “Distinct” would presumably mean “not equal”.
except for the little matter of that documentation being not relevant.
>> Its existence ensures that program behavior can be affected by object
>> sort stability or instability, even if the sort key includes all fields.
>> The sort key would have to also include the identity hash code to make
>> stability irrelevant.
>
> The sort key would have to be consistent with the definition of “equality”,
> would it not?
Not in the case of identity hash code, no.
I gave the correct API reference upthread. Note that there is no requirement
or hint for consistency with 'equals()'.
Patricia Shanahan
> In message<kemdnZVnBva8n0zQ...@earthlink.com>, Patricia
> Shanahan wrote:
>
>> Distinct objects probably have different identity hash codes regardless of
>> whether their fields all have the same values.
>
> “By contract, any two objects for which equals(Object) returns true must
> return the same hash code value.”
System.identityHashCode(x) does not necessarily return the same as
x.hashCode(), and usually will not unless x inherits equals and hashCode
from Object. The contracts for System.identityHashCode(x) and
x.hashCode() match if, and only if, x.equals(y) is equivalent to x==y.
> <http://developer.android.com/reference/java/lang/Object.html#hashCode%28%29>
>
> “Distinct” would presumably mean “not equal”.
It means "not the same object".
For example, equality for Integer is based only on the numeric value of
the integer the object represents. Integer objects are Comparable, with
sort order the same as numeric order of the represented integer.
Integer should be the poster child for not caring about sort stability.
This program:
public class IdentityHashCode {
public static void main(String[] args) {
Integer x = new Integer(3);
Integer y = new Integer(3);
System.out.printf("x.equals(y)=%b, x.compareTo(y)=%d, "
+ "x.hashCode()=%d "
+ "System.identityHashCode(x)=%d%n", x.equals(y), x
.compareTo(y), x.hashCode(), System.identityHashCode(x));
System.out.printf("y.equals(x)=%b, y.compareTo(x)=%d, "
+ "y.hashCode()=%d "
+ "System.identityHashCode(y)=%d%n", y.equals(x), y
.compareTo(x), y.hashCode(), System.identityHashCode(y));
}
}
produces as typical output:
x.equals(y)=true, x.compareTo(y)=0, x.hashCode()=3
System.identityHashCode(x)=4072869
y.equals(x)=true, y.compareTo(x)=0, y.hashCode()=3
System.identityHashCode(y)=11077203
Whether the sort algorithm is stable or not can affect subsequent
program behavior even for sorting Integer objects by their natural order.
Patricia
Tom Anderson
He was a European.
tom
--
Everyone in the world is doing something without me.
Lawrence D'Oliveiro
Shanahan wrote:
> 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%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().
>> “Distinct” would presumably mean “not equal”.
>
> 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
>> “Distinct” would presumably mean “not equal”.
>
> 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
Anderson wrote:
> On Mon, 16 May 2011, Lawrence D'Oliveiro wrote:
>
>> In message <alpine.DEB.2.00.1...@urchin.earth.li>, Tom
>> Anderson wrote:
>>
>>> Basically, Dijkstra was a brilliant guy, but a bit of a bastard.
>>
>> 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.
Is that supposed to mean something?
markspace
> Lawrence D'Oliveiro wrote:
>> Joshua Cranmer wrote:
>>> Lawrence D'Oliveiro wrote:
>>>> ... I’m still not sure I understand his remark that “computer
>>>> science is
>>>> no more about computers than astronomy is about telescopes”.
>
>>> In Dijkstra's day, I would say that the greater focus on computer
>>> science was on the algorithmic research.
>
>> Ah, the old “algorithm” versus “program” meaningless dichotomy.
>
> Ah, the old imitate Maxwell Smart in a meaningless attempt to sound sage
> trick.
>
He missed it by *that much*, too.... ;)
Lew
> In message<alpine.DEB.2.00.1...@urchin.earth.li>, Tom
> Anderson wrote:
>
>> On Mon, 16 May 2011, Lawrence D'Oliveiro wrote:
>>
>>> In message<alpine.DEB.2.00.1...@urchin.earth.li>, Tom
>>> Anderson wrote:
>>>
>>>> Basically, Dijkstra was a brilliant guy, but a bit of a bastard.
>>>
>>> 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.
>
> Is that supposed to mean something?
It means that he was from Europe.
Lew
Lawrence D'Oliveiro wrote:
> javax.swing.JSnarker wrote:
>>> “Distinct” would presumably mean “not equal”.
>> 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?
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?
Patricia Shanahan
> In message<noidndppmuNYrEzQ...@earthlink.com>, Patricia
> Shanahan wrote:
>
>> 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%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().
The results will necessarily be the same if the object's class inherited
java.lang.Object implementation of hashCode(). They can be different if
the object's class uses an overridden hashCode().
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.
>> 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.
If the System.identityHashCode(x) result is part of what you mean by the
"entire value" of an Integer referenced by x, then sorting by "entire
value" is so rare that I've never seen it done. If it is not, then
stability matters even for sorting by "entire value".
Patricia
thoolen
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
> On 5/16/2011 2:11 PM, Lawrence D'Oliveiro wrote:
>> In message<noidndppmuNYrEzQ...@earthlink.com>, Patricia
>> Shanahan wrote:
>>
>>> 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%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().
That says a different thing, that it returns the same as *Object* hashCode(),
not x.hashCode().
Gheerax IV
Are you Twisted?
Lawrence D'Oliveiro
> On 5/16/2011 2:11 PM, Lawrence D'Oliveiro wrote:
>
>> In message<noidndppmuNYrEzQ...@earthlink.com>, Patricia
>> Shanahan wrote:
>>
>>> 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%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().
>
> 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
> On Tue, 17 May 2011 09:11:19 +1200, Lawrence D'Oliveiro wrote:
Who is "Twisted", Gheerax IV? There is nobody in this newsgroup using
that alias.
Patricia Shanahan
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.
Patricia
Lew
> Patricia Shanahan wrote:
>> Lawrence D'Oliveiro wrote:
>>>> 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%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().
>>
>> 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.
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
> Lawrence D'Oliveiro wrote:
>> Patricia Shanahan wrote:
>>>> Patricia Shanahan wrote:
>>>>> 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%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().
>>> 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.
> 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
> In message <alpine.DEB.2.00.1...@urchin.earth.li>, Tom
> Anderson wrote:
>
>> On Mon, 16 May 2011, Lawrence D'Oliveiro wrote:
>>
>>> In message <alpine.DEB.2.00.1...@urchin.earth.li>, Tom
>>> Anderson wrote:
>>>
>>>> Basically, Dijkstra was a brilliant guy, but a bit of a bastard.
>>>
>>> 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.
>
> 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
--
Throw bricks at lawyers if you can!
Patricia Shanahan
...
> 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.
>
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
Patricia Shanahan
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?
Patricia
markspace
> In message<noidndppmuNYrEzQ...@earthlink.com>, Patricia
> Shanahan wrote:
>
>> 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%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().
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
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.
Patricia Shanahan
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.
Patricia
RedGrittyBrick
> AFAIK Lew is from UK
You wag!
--
RGB
Boojum
> Patricia Shanahan wrote:
>> 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()'.
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.
--
Michael Wojcik
Micro Focus
Rhetoric & Writing, Michigan State University
Lew
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
> Robert Klemme wrote:
>> AFAIK Lew is from UK
> 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.
Patricia Shanahan
...
> 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".
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.
Patricia
Heike Svensson
> On 5/18/2011 10:07 AM, Lew wrote:
> ...
>> And Patricia is right - I was calling the respondent "Laramie" because I
>> find his antics offensive.
Why "Laramie" in particular?
>> 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".
> ...
>
> 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
Right you are.
On 18.05.2011 19:07, Lew wrote:
>> Robert Klemme wrote:
>>> AFAIK Lew is from UK
>
> 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
--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/
Lew
> Lew wrote:
>> 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?
"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
Lawrence D'Oliveiro
Shanahan wrote:
> 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
central.gen.new_zealand> wrote:
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
fcb1-4cea-8d4...@j31g2000yqe.googlegroups.com>, Robert Klemme
wrote:
> On 20 Mai, 08:49, Lawrence D'Oliveiro <l...@geek-
> central.gen.new_zealand> wrote:
>
>> In message <ir0oj24...@news5.newsguy.com>, Michael Wojcik wrote:
>>
>> > 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.
>
> 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
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
> In message<svudnYzs-fmh3E_Q...@earthlink.com>, Patricia
That was only pointed out about five times, O Lawrence.
Lew
> Patricia Shanahan wrote:
>> 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”?
Please be polite to Patricia. She even stood up for you! For shame!
Patricia Shanahan
"If, on the other hand, you were sorting immutable objects of a Java
“reference” type where the key was the entire object state, then
stability would indeed be irrelevant, notwithstanding such types are not
considered “primitive”."
[http://groups.google.com/group/comp.lang.java.programmer/msg/17e3a8e513ceab46]
Patricia
Patricia Shanahan
To further refresh your memory, the question I raised was whether you
consider System.identityHashCode(x) to be part of the "entire object
state" of the object referenced by x.
If the answer is "yes", then sorts whose key is the entire object state
are so extremely rare that I've never seen one.
If the answer is "no", then even if the sort key is the entire object
state, the subsequent program behavior, such as the performance of an
IdentityHashMap, can be affected by whether the sort is stable or not,
so stability is relevant.
Patricia
Lawrence D'Oliveiro
> On 5/20/2011 5:00 AM, Patricia Shanahan wrote:
>
>> On 5/19/2011 11:46 PM, Lawrence D'Oliveiro wrote:
>>
>>> In message<kYCdnSqcI7kP40_Q...@earthlink.com>, Patricia
>>> Shanahan wrote:
>>>
>>>> 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”?
>>
>> "If, on the other hand, you were sorting immutable objects of a Java
>> “reference” type where the key was the entire object state, then
>> stability would indeed be irrelevant, notwithstanding such types are not
>> considered “primitive”."
>>
>> [http://groups.google.com/group/comp.lang.java.programmer/msg/17e3a8e513ceab46]
>
> To further refresh your memory, the question I raised was whether you
> consider System.identityHashCode(x) to be part of the "entire object
> state" of the object referenced by x.
What is the significance of sorting on a hash function?
Lew
> Patricia Shanahan wrote:
>>> Lawrence D'Oliveiro wrote:
>>>> Patricia Shanahan wrote:
>>>>> 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”?
>>> "If, on the other hand, you were sorting immutable objects of a Java
>>> “reference” type where the key was the entire object state, then
>>> stability would indeed be irrelevant, notwithstanding such types are not
>>> considered “primitive”."
>>>
>>> [http://groups.google.com/group/comp.lang.java.programmer/msg/17e3a8e513ceab46]
>> To further refresh your memory, the question I raised was whether you
>> consider System.identityHashCode(x) to be part of the "entire object
>> state" of the object referenced by x.
> What is the significance of sorting on a hash function?
I believe Patricia is asking you that question, Lawrence. In any event, you
should at least answer her question with an answer instead of another
question, Lawrence. You had made some statements earlier, of which Patricia
reminded you, and she wants to know if the information provided since has
addressed the concerns you raised. Can you not address that first, Lawrence?
Won't you please address that first, Lawrence?
--
Lew
Patricia Shanahan
> In message<e5CdnR_-upYpwUvQ...@earthlink.com>, Patricia Shanahan wrote:
>
>> On 5/20/2011 5:00 AM, Patricia Shanahan wrote:
>> To further refresh your memory, the question I raised was whether you
>> consider System.identityHashCode(x) to be part of the "entire object
>> state" of the object referenced by x.
>
> What is the significance of sorting on a hash function?
Sorting affects the order of events. Suppose there are a lot of equal
objects. At hash map size N, many of them fall in the same bucket. At a
higher size, they gets spread over two or more buckets, reducing
collisions. The stability, or instability, of a sort algorithm can
change the order of appearance, affecting which keys are added before
resizing.
That is just one way in which changing the order in a list of equal
objects may be visible. If that is too subtle for your taste, consider
the following:
for(Integer x : myArray){
System.out.println(x + " " + System.identityHashCode(x));
}
Arrays.sort(myArray);
for(Integer x : myArray){
System.out.println(x + " " + System.identityHashCode(x));
}
If the sort is stable, Integer objects with the same value appear in the
same order in the two printouts. If it is not stable, they may be reordered.
Patricia
RedGrittyBrick
> RedGrittyBrick wrote:
>> Robert Klemme wrote:
>>> AFAIK Lew is from UK
>
>> You wag!
>
> 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.
--
RGB
Lew
> Lew wrote:
>> RedGrittyBrick wrote:
>>> Robert Klemme wrote:
>>>> AFAIK Lew is from UK
>>> You wag!
>> 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.
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.
--
Lew
Steve Sobol
says...
> >> You wag!
> >
> > 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.
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. :)
--
Steve Sobol - Programming/WebDev/IT Support
sjs...@JustThe.net
RedGrittyBrick
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.
--
RGB
RedGrittyBrick
> In article<4dda2828$0$2527$da0f...@news.zen.co.uk>, RedGrittyBrick
> says...
>
>>>> You wag!
>>>
>>> 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.
>
> 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?
--
RGB
Robert Klemme
LOL
Now that I read this sub thread I am really glad I misplaced Lew. :-))
Cheers
Lew
> On 23/05/2011 14:05, Lew wrote:
>> RedGrittyBrick wrote:
>>> Lew wrote:
>>>> RedGrittyBrick wrote:
>>>>> Robert Klemme wrote:
>>>>>> AFAIK Lew is from UK
>>>>> You wag!
>>
>>>> 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.
>>
>> 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.
>
> 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
> On 23/05/2011 16:27, Steve Sobol wrote:
>> In article<4dda2828$0$2527$da0f...@news.zen.co.uk>, RedGrittyBrick
>> says...
>>
>>>>> You wag!
>>>>
>>>> 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.
>>
>> 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.
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."