• Post Reply Bookmark Topic Watch Topic
  • New Topic

Iteratively and Recursively Summing and Reversing an a array of Longs  RSS feed

 
Stephanie Below
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay so my program is supposed to use recursion and iteration to sum and reverse elements in an array of Longs.
The array is supposed to be 1000000 cells and I am supposed to compute the average times of 99999 trials.
When I try to run the program, it keeps saying running.... but doesnt ever do anything. Does anyone have any suggestions?
I've been at this for a while now :/

 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephanie Below wrote:Does anyone have any suggestions?

A million or ten elements can take a long time to finish. What is its time complexity supposed to be? What I would suggest first instead of 1000000 elements run it with say a dozen elements. See if it ever ends. If it doesn't step through it in debug and find out why not.
 
Stephanie Below
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have already tried using smaller numbers and it does stop, but when trying to use the numbers my professor wants, it just keeps running and never prints out anything.
 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In that case, leave it alone for a few hours and see if it either finishes or gives an error, if you haven't done that.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Then what you have is an endless loop.



Try with:



Does that make things clearer?
 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
if StackOverflowError isn't for flow control, you could just get rid of the try/catch and let it bomb there, and if so change the stack size or program.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Guillermo - it looks like the StackOverflowError IS being used for flow control.
As in make this recursive call as long as you can, figure out what that maximum number is, and then restart, theoretically using that number as the limit.
However that doesn't appear to be working

@OP
Which calls in your program can produce a StackOverFlow Exception?
There are at least two
Do they have the same "breaking" point?
When you call it with "getCycles()" is that the number that broke it already, and therefore should you call it with a smaller number?
 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Does catching stack overflow give you a fresh stack to start over with? Does the error occurring reset the stack pointer?


 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You could print out a status message every so often inside your loops to show that things are progressing and another status message when the loop exits. For example,
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Were you given the method signatures by your professor and asked to fill in the code for the bodies or did you come up with the method signatures yourself? Just wondering what your constraints are for this because there are a few things I would change about the way you've written the recursive methods.
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You have

One of your class mates has

Are you sure you don't have too many digits in your parameters?
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't think it matters how many digits are on there. Suffice it to say it is more than the computer can handle.
The point is to detect the 'break' limit, and then re-run the test with that limit in mind.

So 100,000 or 1,000,000 won't matter if that actual limit is 20,000 or so.

And I would second Junilu's comment.
Passing the array to the methods and having them return a value as opposed to modifying 'global variables' would make for a much nicer program :-)
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stefan Evans wrote:I don't think it matters how many digits are on there. Suffice it to say it is more than the computer can handle.
The point is to detect the 'break' limit, and then re-run the test with that limit in mind.

So 100,000 or 1,000,000 won't matter if that actual limit is 20,000 or so.

And I would second Junilu's comment.
Passing the array to the methods and having them return a value as opposed to modifying 'global variables' would make for a much nicer program :-)

Yes, but increasing the number of iterations by a factor of 10 will have an impact.
 
Stephanie Below
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I let my program run for a while and it came up with a heap error. My professor didn't specify any particular methods, I made them myself. I spoke with my classmate that had the wrong digits and he fixed his and now his works, but we have two completely different programs. Its at the point where I have looked at the program for too long and I cant really think of how to fix it anymore. Thank you for the help but I might just cut my losses and turn it in as is if I cant figure it out soon because it is already past the date it was due.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The good:
1. You have broken down the big problem into a bunch of smaller more manageable problems
2. You are using mostly private instance methods. That's good because you want to start with the least access for your methods to preserve encapsulation, then slowly increase the access as little as possible when the need to do so is justifiable.
3. You have chosen some pretty good method names that accurately reflect what the methods are doing. In other words, many of the method names you chose help reveal their intent.

The "could be better":
1. You could get rid of some of those "global" variables and, as Stefan said, pass things into methods as parameters.
2. Some of the variable names you chose could be better. For example, the variable start is an array of start times. A better name for this variable would be startTimes. Similarly end would be better as endTimes.
3. And finally, I wouldn't call the runProgram() method from the constructor of the same class. And I wouldn't catch the StackOverflowError and recursively call runProgram either. Both of these things need to be done from outside this class.


You can still continue running the program after a StackOverflowError as long as you allow execution to fall out of the method that started the recursive calls. See http://stackoverflow.com/questions/22128485/why-is-it-possible-to-recover-from-a-stackoverflowerror
 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephanie Below wrote:already past the date it was due.

Rule of thumb handed down to me by gurus, sages, mad bosses, eggheads, old hands, hot shots, and the power elite is double your estimate, then double it again. Best case you have a lot of free time on your hands. Worst case, you get it done in the nick of time. People handle waiting much better than a missed delivery date. Hope you can get it figured out before the hard deadline.
 
Campbell Ritchie
Marshal
Posts: 56546
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can't use a Stream can you? Only works in Java8+.
Arrays.stream(myArray).sum();
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!