 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / First Aid / November 2004efficiency problem
Hi, i hope you can help me... Im trying to implement a heap, but ive run across an efficiency issue. im storing the heap in an array of size x. if i insert 1000000 items into the heap where x=1000001, it takes 650ms. if i insert 1000000 items into the heap where x = 1 (and when the array is full it uses arraycopy to quadruple the size) it takes 550ms. Why is this??? How can addressing a larger array be slower than resizing the array ~= 11 times? Cheers Andrew Bullock > Hi, i hope you can help me... > [quoted text clipped - 10 lines] > How can addressing a larger array be slower than resizing the array ~= > 11 times? Change `<' to `<=' in line 326, and all will be well. (In other words: Where's the code?)  SignatureEric.Sosman@sun.com >:Hi, i hope you can help me... >: [quoted text clipped - 14 lines] >: >:Andrew Bullock Maybe the clue is in the code sample you didn't provide. What do you consider a "heap"? How do you define "insert" in your design? And is total execution time really an accurate way of defining efficiency? Not always. = Steve = SignatureSteve W. Jackson Montgomery, Alabama > And is > total execution time really an accurate way of defining efficiency? Not > always. Ok, maybe efficiency was the wrong word, what i was reffering to was execution time. ok heres the code: option a) tasks is of size 1, do this 1000000 times takes 550 ms: try { Tasks[++lastNode] = x; } catch (ArrayIndexOutOfBoundsException e){ newArray = new Task[this.Tasks.length * 4]; System.arraycopy(this.Tasks, 0, newArray, 0, this.Tasks.length); this.Tasks = newArray; Tasks[lastNode] = x; } option b) tasks is of size 1000000, do this 1000000 times takes 650ms: Tasks[++lastNode] = x; There is other code obviously but that is no different between options. I wont paste it all because its 100+ lines. If you think you need it then please just say so (no sarcasm required) Andrew > > And is > [quoted text clipped - 26 lines] > > There is other code obviously but that is no different between options. I tried to duplicate your results, but didn't succeed. Not knowing what a Task object might be I simply used int[] arrays, and I also changed the suspicious-looking `++lastNode' to `lastNode++' and made the corresponding adjustment in the catch block. Then I wrapped it up in a simple program that used each of "option a" and "option b" ten times to insert a million values. Counting only the final nine cycles (the first was probably subject to JIT and other "warm-up" effects), "option a" took 113-153 milliseconds while "option b" took 36-47. That is, "option b" was more than three times faster than "option a." Efficiency questions aside (they should be "aside" more often than people seem to put them there), "option a" is a bletcherous approach. If you want to grow the array in stages, go right ahead -- but detect the edge condition with an `if' rather than by catching an exception. There have been several threads about using exceptions in non-"exceptional" situations, and everyone with experience is against it. All "ordinary" or "foreseeable" or "routine" changes of control flow should be handled without exceptions; use exceptions only for the truly exceptional situations. SignatureEric.Sosman@sun.com > I tried to duplicate your results, but didn't succeed. > Not knowing what a Task object might be I simply used int[] [quoted text clipped - 18 lines] > flow should be handled without exceptions; use exceptions > only for the truly exceptional situations. Hi, thanks for your swift reply. Thank you for putting so much effort in, i feel really bad now, and im really grateful!! I understand what you're saying about the try/catch, however the "if" method seemed to make it slower rather than faster for me (probably because it has to to the comparison every cycle, most of which times it will be false?) A task is a tuple (can you say that in java?) of a string and an int, so assuming it as an int is ok. ive chopped down my code to just the insert and next functions (insert inserts a new node, then performs an upHeap operation, next returns the root, then replaces with the last and downHeaps) and ive written a quick tester program to demonstrate what i mean. Below are links to it (ive uploaded them because posting them here just messes with the formatting - i hope you dont mind) http://www.190385.com/java/myHeap.java http://www.190385.com/java/Task.java http://www.190385.com/java/Tester2.java I'd be really appreciative if you could help me out some more because this is really bugging me. Many thanks in advance, Andrew Bullock > I understand what you're saying about the try/catch, however the "if" > method seemed to make it slower rather than faster for me (probably > because it has to to the comparison every cycle, most of which times it > will be false?) Since the array index is checked anyway (otherwise, how would the Exception ever be generated?) you do not lose much by an explicit if. Maybe your JIT will even see that you checked the array size already, and omit the later check. If the horrendous control flow doesn't convice you, consider this: Exceptions are _expensive_. They cost over a thousand times more runtime then a simple if-then-else. The Exception needs to be constructed, the normal method needs to be destroyed, the corresponding catch-block needs to be looked up, the stack squashed to that level, the old method reanimated... SignatureWhom the gods wish to destroy they first call promising. > I understand what you're saying about the try/catch, however the "if" > method seemed to make it slower rather than faster for me (probably > because it has to to the comparison every cycle, most of which times it > will be false?) Please refer to my recent unseemly diatribe on essentially the same topic over in comp.lang.java.programmer, in a thread titled "Performance of null tests?" (Not self-promotion: it's just that I'm trying to cut down on writing and re-writing the same diatribe -- bad for the blood pressure.) (For extra credit, spot the error in my broadside -- not in the assumptions, which are intentionally optimistic to the point of bending over backwards, but in the conclusions I drew from them. Hint: Spaces are not lines.) "It stands to reason" that your option a should be slower, and when I replicated your experiment (based on an incomplete description), that's exactly what happened. You're seeing the opposite -- and I strongly suspect that it has nothing whatever to do with the `if', but everything to do with some other part of your code, or with a sloppy time measurement. Seek elsewhere for the source of your troubles -- but don't seek harder than the troubles themselves are worth. Remember that you'll need to realize your 100ms savings 36,000 times to recoup just one hour spent achieving it ... SignatureEric.Sosman@sun.com 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 ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.