Java Forum / General / May 2008
Java Arrays.sort throws exception
captain - 14 May 2008 15:37 GMT When the number of elements gets above around 2700 the Arrays.sort inside the Collections.sort throws an exception:
java.lang.ArrayIndexOutOfBoundsException
Any ideas?
Thanks
Roedy Green - 14 May 2008 16:15 GMT On Wed, 14 May 2008 07:37:00 -0700 (PDT), captain <bdvoltaire@yahoo.com> wrote, quoted or indirectly quoted someone who said :
>When the number of elements gets above around 2700 the Arrays.sort >inside the Collections.sort throws an exception: > >java.lang.ArrayIndexOutOfBoundsException We will have to see your code. In the meantime have a look at http://mindprod.com/jgloss/sort.html to learn how to write sorts.
Presumably your Comparator is doing some indexing which is failing. Look carefully at the stack trace for the precise line that is failing.
 Signature Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
captain - 14 May 2008 19:32 GMT Roedy,
Thank you very much for your response.
My code:
List adminItems = new ArrayList();
loop: adminItems.add(administeredItem);
Collections.sort(adminItems);
------------ Collections.class (Sun Code):
public static void sort(List list) { Object a[] = list.toArray(); Arrays.sort(a); // THROWS EXCEPTION ListIterator i = list.listIterator(); for (int j=0; j<a.length; j++) { i.next(); i.set(a[j]); } }
Thanks,
Fred
On May 14, 11:15 am, Roedy Green <see_webs...@mindprod.com.invalid> wrote:
> On Wed, 14 May 2008 07:37:00 -0700 (PDT), captain > <bdvolta...@yahoo.com> wrote, quoted or indirectly quoted someone who [quoted text clipped - 16 lines] > Roedy Green Canadian Mind Products > The Java Glossaryhttp://mindprod.com Andrea Francia - 14 May 2008 21:00 GMT > Roedy, > [quoted text clipped - 8 lines] > > Collections.sort(adminItems); You don't need to post the library code.
You didn't post yet enough information however.
The code is not a SSCCE (is not compilable). Where administeredItem is defined? Why you did not post the loop part? It's impossible help you if you don't post a code which is compilable. And it's impossible to help you if the code does not reflect your code enviroment.
Please read the http://sscce.org and post a SSCEE.
You should also post the Exception stack trace.
Please read in http://mindprod.com/jgloss/newsgroups.html the section How To Get Newsgroup Responses
Ciao -- Andrea Francia
Patricia Shanahan - 14 May 2008 21:34 GMT >> Roedy, >> [quoted text clipped - 26 lines] > Please read in http://mindprod.com/jgloss/newsgroups.html the section > How To Get Newsgroup Responses Even without its use for communicating with the newsgroup, building an SSCCE would be a good strategy for this type of problem. The library sort code is very well tested and widely used, so it is almost certainly not the problem.
The very fact that you are stuck suggests that the problem is somewhere you are not looking. In the process of building the SSCCE you will probably find that removing or simplifying some aspect of your program makes the problem go away.
Patricia
Roedy Green - 14 May 2008 21:56 GMT On Wed, 14 May 2008 20:00:05 GMT, Andrea Francia <andrea.francia@REMOVE-FROM-HERE.ohoihihoihoih.TO-HERE.gmx.it> wrote, quoted or indirectly quoted someone who said :
>It's impossible help you if you don't post a code which is compilable. >And it's impossible to help you if the code does not reflect your code >enviroment. The problem is nearly always in the code you DON'T post. That why the SSCCE. See http://mindprod.com/jgloss/sscce.html
 Signature
Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
Roedy Green - 14 May 2008 21:55 GMT On Wed, 14 May 2008 11:32:07 -0700 (PDT), captain <madison223@gmail.com> wrote, quoted or indirectly quoted someone who said :
> List adminItems = new ArrayList(); > [quoted text clipped - 15 lines] > } > } You did not tell us the type of administeredItem. I assume for purposes of argument AdministeredItem.
You want something like this:
List<AdministeredItem> adminItems = new ArrayList<AdministeredItem>( 100 );
loop: adminItems.add(administeredItem);
Collections.sort(adminItems);
Your class AdministeredItem class will need to implement Comparable<AdministeredItem>
See http://mindprod.com/jgloss/comparable.html for how.
If administeredItem is a String then you need
List<String> adminItems = new ArrayList<String>( 100 );
The piece of code of most interest is the compareTo method of AdministeredItem. You did not reveal it yet.
 Signature
Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
Lew - 15 May 2008 06:23 GMT captain said :
>> loop: >> adminItems.add(administeredItem); captain, why are you using a label? That is highly unidiomatic.
 Signature Lew
Patricia Shanahan - 15 May 2008 14:53 GMT > captain said : >>> loop: >>> adminItems.add(administeredItem); > > captain, why are you using a label? That is highly unidiomatic. I'm not sure whether it is part of captain's code, and therefore a label, or outside the code, saying that the add call is in a loop.
I really hope captain is off either writing an SSCCE, or unit testing the compareTo or compare method.
Patricia
Roedy Green - 15 May 2008 19:46 GMT >captain, why are you using a label? That is highly unidiomatic. I presumed pseudocode.
 Signature
Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
Eric Sosman - 14 May 2008 16:59 GMT > When the number of elements gets above around 2700 the Arrays.sort > inside the Collections.sort throws an exception: > > java.lang.ArrayIndexOutOfBoundsException > > Any ideas? It is conceivable that the sort() implementation has a bug. But it is far, Far, FAR more probable that the bug is in the code you haven't shown ...
 Signature Eric.Sosman@sun.com
captain - 14 May 2008 19:31 GMT Eric,
Thank you very much for your response.
My code:
List adminItems = new ArrayList();
loop: adminItems.add(administeredItem);
Collections.sort(adminItems);
------------ Collections.class (Sun Code):
public static void sort(List list) { Object a[] = list.toArray(); Arrays.sort(a); // THROWS EXCEPTION ListIterator i = list.listIterator(); for (int j=0; j<a.length; j++) { i.next(); i.set(a[j]); } }
Thanks,
Fred
> > When the number of elements gets above around 2700 the Arrays.sort > > inside the Collections.sort throws an exception: [quoted text clipped - 9 lines] > -- > Eric.Sos...@sun.com Eric Sosman - 14 May 2008 19:57 GMT > Eric, > [quoted text clipped - 7 lines] > > Collections.sort(adminItems); My code:
import java.util.ArrayList; import java.util.Collections;
public class Foo {
public static void main(String[] unused) { final int COUNT = 2700; ArrayList<Integer> list = new ArrayList<Integer>(COUNT); for (int i = 0; i < COUNT; ++i) list.add(new Integer( (int)(Math.random() * Integer.MAX_VALUE))); Collections.sort(list); }
}
Runs like a champ, both as shown and with COUNT = 1000000.
There's something I'd like you to notice, a difference between your code and mine: Mine actually runs, while yours won't even compile. I can get yours to compile and run by "filling in the blanks," as it were -- but that probably means that the problem is in the blanks, the part you still haven't revealed.
Hint, hint.
 Signature Eric.Sosman@sun.com
captain - 14 May 2008 20:38 GMT This is my very first post and I am not up on the etiquete yet.
I realize that the problem must be in my code. Actually, I didn't right this code, I inherited it. I have a lot of programming experience but not in this particular environment.
Here, a list is populated in a loop and then Collections.sort is called on that list. I would like to know what the possible problems may be, what to look for.
Thanks
> > Eric, > [quoted text clipped - 38 lines] > -- > Eric.Sos...@sun.com Roedy Green - 14 May 2008 22:01 GMT On Wed, 14 May 2008 12:38:11 -0700 (PDT), captain <madison223@gmail.com> wrote, quoted or indirectly quoted someone who said :
>This is my very first post and I am not up on the etiquete yet. It is not etiquette. It is simply a matter of showing us ALL the relevant code so we can find them problem.
What you are doing is like going to the doctor, wrapped in packing bubbles with only your hand exposed.
You say "I feel terrible. Dr. Green, you will have to figure out why my stomach hurts only by examining my hand. I'm sure it has something to do with my hand, because that is the hand I eat with."
 Signature Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
Lew - 15 May 2008 06:29 GMT > On Wed, 14 May 2008 12:38:11 -0700 (PDT), captain > <madison223@gmail.com> wrote, quoted or indirectly quoted someone who [quoted text clipped - 4 lines] > It is not etiquette. It is simply a matter of showing us ALL the > relevant code so we can find them problem. What is etiquette is to eschew top-posting and post inline with the comments to which you are responding. There is more, easily found if you read the FAQ post to this newsgroup which appears every five days [1], and the links to which it points. This will give you the background not to be a Usenet chump but a Usenet champ.
It helps to read the newsgroup for a while.
[1] "comp.lang.java.{help,programmer} - what they're for ..." posted by David Alex Lamb every five days.
 Signature Lew Use a single line containing only "dash dash blank" to set off your signature. Good newsreaders won't quote that part. Google Groups sucks. Don't use it.
Eric Sosman - 15 May 2008 02:24 GMT > This is my very first post and I am not up on the etiquete yet. > > I realize that the problem must be in my code. Actually, I didn't > right this code, I inherited it. I have a lot of programming > experience but not in this particular environment. > [...] It is astonishing, or perhaps sobering or depressing, to find that someone with "a lot of programming experience" is unable to form a coherent problem report nor able to produce a usable test case. Astonishing, sobering, or depressing: it is beyond my feeble powers to render you any help. Good luck, and Godspeed.
 Signature Eric Sosman esosman@ieee-dot-org.invalid
Mark Space - 15 May 2008 02:53 GMT >> This is my very first post and I am not up on the etiquete yet. >> [quoted text clipped - 7 lines] > unable to form a coherent problem report nor able to produce > a usable test case. Or spell "write."
Eric Sosman - 15 May 2008 15:28 GMT >>> This is my very first post and I am not up on the etiquete yet. >>> [quoted text clipped - 9 lines] > > Or spell "write." He could be trying to "right the code" as one would right a wrong or an overturned dinghy. (And no, that's not a misspelling of "dirty, unclean, shabby, squalid.")
 Signature Eric.Sosman@sun.com
Tom Anderson - 15 May 2008 15:22 GMT >> This is my very first post and I am not up on the etiquete yet. >> [quoted text clipped - 7 lines] > unable to form a coherent problem report nor able to produce > a usable test case. I'm guessing that the 'programming' is the type they have on TV. In this case, probably watched with a beer in hand, packet of cheetos in lap, trucker cap on head, and drool escaping from mouth.
tom
 Signature ... but when you spin it it looks like a dancing foetus!
Roedy Green - 15 May 2008 19:48 GMT On Thu, 15 May 2008 15:22:57 +0100, Tom Anderson <twic@urchin.earth.li> wrote, quoted or indirectly quoted someone who said :
>I'm guessing that the 'programming' is the type they have on TV. it could be simply some quite different language, like LISP.
 Signature
Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
Tom Anderson - 15 May 2008 20:43 GMT > On Thu, 15 May 2008 15:22:57 +0100, Tom Anderson > <twic@urchin.earth.li> wrote, quoted or indirectly quoted someone who [quoted text clipped - 3 lines] > > it could be simply some quite different language, like LISP. I doubt it. Programming is basically the same in all languages, just with different spelling. The idea that we could diagnose a problem in which library routine A calls user-written routine B without seeing the text of routine B is pretty bizarre in any language.
Also, i believe LISPers tend to be towards the smarter end of the spectrum of programmers, and this guy, well, not so much,
If we widen the definition of 'programming' to mean 'coding', i could maybe believe he was experienced with HTML, or something else really, really unlike a programming language. Maybe perl?
tom
 Signature The real romance is out ahead and yet to come. The computer revolution hasn't started yet. -- Alan Kay
Mark Space - 14 May 2008 17:48 GMT > When the number of elements gets above around 2700 the Arrays.sort > inside the Collections.sort throws an exception: [quoted text clipped - 4 lines] > > Thanks Yeah, it's line 115 of your code. Just fix that up and you'll be ok.
captain - 14 May 2008 18:55 GMT I am brand new here and don't mean to be flippant, but is this a joke?
> > When the number of elements gets above around 2700 the Arrays.sort > > inside the Collections.sort throws an exception: [quoted text clipped - 6 lines] > > Yeah, it's line 115 of your code. Just fix that up and you'll be ok. Lasse Reichstein Nielsen - 14 May 2008 19:18 GMT >> Yeah, it's line 115 of your code. Just fix that up and you'll be ok.
> I am brand new here and don't mean to be flippant, but is this a joke? Yes, it's a joke, with a point. The point being that we can't find the problem if you don't show us code that exhibits the problem.
In the unlikely event that Arrays.sort had a bug that showed already at 2700 elements, and that we knew of it, we could, in theory, guess that it was that bug you were hitting.
As someone else said, the probability of the bug being in the standard library vs. the probability of it being in your code suggests that you should just go ahead and show your code ... or rather show a nicely reduced example without unnecessary distractions but which still exhibits the problem.
Often, the act of cutting down to a SSCCE (Small Self-Contained Compilable Example) will reveal the bug along the way.
Also remember to note which JVM version you are running on. If the bug is related to the standard library, then that might also be important.
In general, when you need help with a programming problem, you should provide enough information for us to do the "Three R's". We need to be able to: Reproduce the problem: Say what you do. Be precise (give a SSCCE that exhibits the problem). Further details are good. Recognize the problem: Say what happens that you consider as the problem. It might be expected behavior. It might not happen to to someone with a different configuration. Repair the problem: Say what you expected to happen. Can't fix the problem if we don't know what to fix it *to*.
/L
 Signature Lasse Reichstein Nielsen - lrn@hotpop.com DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html> 'Faith without judgement merely degrades the spirit divine.'
Mark Space - 14 May 2008 20:04 GMT >>> Yeah, it's line 115 of your code. Just fix that up and you'll be ok. > >> I am brand new here and don't mean to be flippant, but is this a joke? > > Yes, it's a joke, with a point. The point being that we can't find the > problem if you don't show us code that exhibits the problem. Pretty much. And a cursor search of this news group for various "help" topics always yields the same replies:
1. Post an SSCCE 2. Post an SSCCE 3. Post an SSCCE
Assuming you did a search first to try to solve your problem, you should have hit these. So I can only conclude that you did very little research of your own before posting your message. And it's getting irritating to keep making the exact same reply to each of these requests.
Post an SSCCE.
captain - 14 May 2008 20:36 GMT This is my very first post and I am not up on the etiquete yet.
I realize that the problem must be in my code. Actually, I didn't right this code, I inherited it. I have a lot of programming experience but not in this particular environment.
Here, a list is populated in a loop and then Collections.sort is called on that list. I would like to know what the possible problems may be, what to look for.
Thanks
> >> Yeah, it's line 115 of your code. Just fix that up and you'll be ok. > > I am brand new here and don't mean to be flippant, but is this a joke? [quoted text clipped - 34 lines] > DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html> > 'Faith without judgement merely degrades the spirit divine.' Roedy Green - 14 May 2008 22:03 GMT On Wed, 14 May 2008 12:36:06 -0700 (PDT), captain <madison223@gmail.com> wrote, quoted or indirectly quoted someone who said :
>I realize that the problem must be in my code. Actually, I didn't >right this code, I inherited it. I have a lot of programming >experience but not in this particular environment. You may not have enough skill to write an SSCCE, but you can post the entire class, huge and ugly as it may be, and see if you can find someone willing to eyeball it.
 Signature
Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
Andrea Francia - 14 May 2008 19:20 GMT > I am brand new here and don't mean to be flippant, but is this a joke? If you don't post your code nobody can help you.
Owen Jacobson - 14 May 2008 22:52 GMT > When the number of elements gets above around 2700 the Arrays.sort > inside the Collections.sort throws an exception: [quoted text clipped - 4 lines] > > Thanks I've seen this happen when the Comparator (or Comparable) implementation is not consistent. Arrays.sort relies on the compare operation producing consistent results for all possible pairs; it elides operations where it can "guess" the result from previous comparisons.
Since you haven't shown us what the implementation of Comparable<T> looks like (the compareTo (T other) and related methods) for whatever objects you're adding to the collection are, it's very hard to assert that this is your problem, but it looks *likely* to me.
-o
Tom Anderson - 14 May 2008 23:51 GMT >> When the number of elements gets above around 2700 the Arrays.sort >> inside the Collections.sort throws an exception: [quoted text clipped - 7 lines] > I've seen this happen when the Comparator (or Comparable) > implementation is not consistent. My money is on some kind of bug in compareTo too. I don't see what else it can be.
tom
 Signature THE DRUMMER FROM DEF LEPPARD'S ONLY GOT ONE ARM!
Philipp - 15 May 2008 10:03 GMT >>> When the number of elements gets above around 2700 the Arrays.sort >>> inside the Collections.sort throws an exception: [quoted text clipped - 10 lines] > My money is on some kind of bug in compareTo too. I don't see what else > it can be. Could it be that the comparator must be consistent with equals for the sort to work?
Phil
Lew - 15 May 2008 13:31 GMT >>>> When the number of elements gets above around 2700 the Arrays.sort >>>> inside the Collections.sort throws an exception: [quoted text clipped - 13 lines] > Could it be that the comparator must be consistent with equals for the > sort to work? That would be Owen's point.
 Signature Lew
Philipp - 15 May 2008 14:20 GMT >>>>> When the number of elements gets above around 2700 the Arrays.sort >>>>> inside the Collections.sort throws an exception: [quoted text clipped - 15 lines] > > That would be Owen's point. I understood it as: "the comparator itself is not fulfilling its contract". Contract which is (for the OP, see also "Effective Java" by Bloch, Item 11):
Transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0
Symmetric: sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) in particular x.compareTo(y) must throw an exception if and only if y.compareTo(x) throws an exception
Coherence: x.compareTo(y) == 0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z))
Phil
Owen Jacobson - 15 May 2008 15:50 GMT > >>>> When the number of elements gets above around 2700 the Arrays.sort > >>>> inside the Collections.sort throws an exception: [quoted text clipped - 15 lines] > > That would be Owen's point. Not as such. My point was that identities like a < b && b < c is implied by and implies that a < c, along with simpler ones like a < b implies that b > a, must be implemented by the compareTo or compare method in use. None of the sort implementations in the JRE bother checking for .equals equality; they rely on .compareTo/.compare equality.
-o
Lew - 16 May 2008 02:43 GMT >>>>>> When the number of elements gets above around 2700 the Arrays.sort >>>>>> inside the Collections.sort throws an exception: [quoted text clipped - 15 lines] > checking for .equals equality; they rely on .compareTo/.compare > equality. To Owen and the OP: When you use the term "consistent" with Comparator, whose Javadocs are fully laden with a thick discussion of being "consistent with equals", the reader is of course going to think that's what you're talking about. If you mean something different, you should either say so to avoid the natural confusion or pick a different term, one that isn't so signally important in the documentation of the artifact under discussion.
 Signature Lew
Patricia Shanahan - 15 May 2008 14:33 GMT >>>> When the number of elements gets above around 2700 the Arrays.sort >>>> inside the Collections.sort throws an exception: [quoted text clipped - 15 lines] > > Phil Unlikely.
I have sorted arrays by Comparator criteria that are definitely inconsistent with equals, and have never got an exception from sort doing so. There is no requirement that a Comparator order have anything to do with equals.
Even for a Comparable sort, there is no reason for sort to use equals, rather than testing for zero compareTo result. I have sorted arrays of Double, which has documented inconsistencies between equals and compareTo.
It is much more likely that the OP's compareTo is inconsistent with itself, so that it does not represent a total order.
Patricia
Roedy Green - 15 May 2008 19:51 GMT >It is much more likely that the OP's compareTo is inconsistent with >itself, so that it does not represent a total order. consider that the sort also uses Comparator.compare where the algorithm rarely has any connection whatsoever to equals.
 Signature
Roedy Green Canadian Mind Products The Java Glossary http://mindprod.com
Lew - 16 May 2008 02:46 GMT > I have sorted arrays by Comparator criteria that are definitely > inconsistent with equals, and have never got an exception from sort > doing so. There is no requirement that a Comparator order have anything > to do with equals. And yet the Javadocs for Comparator make a big deal out it. Why should they do that if it doesn't matter?
> If the ordering imposed by c on S is inconsistent with equals, the sorted set > (or sorted map) will behave "strangely." In particular the sorted set (or > sorted map) will violate the general contract for set (or map), which is > defined in terms of equals.
 Signature Lew
Patricia Shanahan - 16 May 2008 04:51 GMT >> I have sorted arrays by Comparator criteria that are definitely >> inconsistent with equals, and have never got an exception from sort [quoted text clipped - 3 lines] > And yet the Javadocs for Comparator make a big deal out it. Why should > they do that if it doesn't matter? It matters, but not for Arrays.sort.
The issue they discuss is a class, such as TreeSet, that is bound by an contract described in terms of equals, but that will fail to conform to it unless the Comparator is consistent with equals.
The Arrays.sort contract does not depend on equals, so it can fully conform to its contract provided the Comparator represents a total order over the array elements, regardless of whether that order is consistent with equals.
Patricia
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|