• Post Reply Bookmark Topic Watch Topic
  • New Topic

apparently creating too many objects  RSS feed

 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
a warning to anyone wanting to solve Euler145 on your own. this is a solution although a slow one.
i tried changing from String to StringBuilder, but it is still very slow. any help or observation appreciated.
line 23 looks especially suspect, but i don't see any other way.
the new code:

the previous code:
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
here is the problem statement


Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (109)?

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:i tried changing from String to StringBuilder, but it is still very slow. any help or observation appreciated.

Personally, I wouldn't use either. What about breaking up each number into a List (or array) of int digits?

Winston
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i am going to try moving the declaration of char c and int t out of the loop that might help
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Personally, I wouldn't use either. What about breaking up each number into a List (or array) of int digits?

that sounds good to me i didn't like changing back and forth in the first place. i have no idea how though
primitives don't have a charAt() method. i could get rid of strings by using Integer class i guess.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:i am going to try moving the declaration of char c and int t out of the loop that might help


It won't. All local variables are allocated at cone, at method entry.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:


Personally, I wouldn't use either. What about breaking up each number into a List (or array) of int digits?

that sounds good to me i didn't like changing back and forth in the first place. i have no idea how though
primitives don't have a charAt() method.


They can bet turned into Strings though, and String has a charAt() method. And there are ways to turn that char into an int.

There's also division and modulo math to extract digits.
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff, turning them into Strings and using chatAt() and Character.getNumericValue() is where i started at. i have also been thinking about modulo math as a last resort. what i have decided is to take my best effort and let it run long enough to give an answer.(20 minutes+) then i can go to the forum for that question and see how others solved it
i found i had a lot of fat to trim. my latest has only 2 StringBuilders, and 1 Integer. a small improvement anyway

it takes about 2 minutes to find answer for 100,000,000 1 billion will hopefully only take 10 times as long.
i am going to start it now since i can only stay at McDonalds for sooo long
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:i have also been thinking about modulo math as a last resort.

Why as a last resort? For one thing, it breaks your number up into numeric digits rather than characters; for another, it naturally delivers those digits in reverse order.

Winston
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
could you imagine...
a= x % 10
b = x % 100
c = x % 1000
d = x % 10000
e = x % 100000
f = x % 1000000
g = x % 10000000
h = x % 100000000
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
oh crap! i forgot to change the number back from 100,000,00 to 1 billion before i started it
i cant stay at McDonalds for another half hour or more
oh even worse. i did change it. the answer looked like the same from 100,000,000 so i closed it and assumed i made a mistake
im gonna go drink a beer now and run my battery into the ground getting the answer again
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:could you imagine...
a= x % 10
b = x % 100
c = x % 1000
d = x % 10000
e = x % 100000
f = x % 1000000
g = x % 10000000
h = x % 100000000


I can, but I'd rather imagine an array or a List and repeated multiplication and/or division.

When there's such as obvious pattern as that, it cries out for a loop, rather than repeating the same code over and over.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's another good reason to use numbers rather than characters:(assumes that n >= 0 [Edit: and <= 1000000000 ]) and there may well be quicker methods.

Winston
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:... there may well be quicker methods.

What about creating a lookup table for numbers below 1000 and doing it three digits at a time?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Martin Vajsar wrote:What about creating a lookup table for numbers below 1000 and doing it three digits at a time?

Not sure about the lookup, but I do like the idea of tackling the digits in groups of 3. Gold star from me.

Winston
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston, i can see how that might be better than the way i am doing it. i am going to save that code snippet.
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i finally let it run long enough and got the correct answer. i am still keeping in mind what Winston wrote and am going to see how others solved it.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:i finally let it run long enough and got the correct answer. i am still keeping in mind what Winston wrote and am going to see how others solved it.

How long did it take in the end? After a bit of tweaking (ie, coupling), I got mine down to 550 seconds on my clunky old Dell using brute force; but I have a strong feeling that there may be ways of eliminating more than just numbers ending in 0.

For example: If the first and last digits added together are even, the number can be eliminated; which I think eliminates about 50% of all possibles with only one extra divide.

I also suspect that there are properties of n + reverse(n) that we (or at least I) are missing.

Winston

 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I suspect you're right. I haven't tried this one yet, but while you can have a solution that takes as long as you like, there's an unofficial one minute target. Specifically, they say:
Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:i finally let it run long enough and got the correct answer. i am still keeping in mind what Winston wrote and am going to see how others solved it.

Just FYI, I went off on a geek hunt and found the following two algorithms at Hacker's Delight:mod10() runs about 6 times as fast as 'n % 10' on my computer (only works on positive values though); div10() runs about 3 times as fast as 'n / 10'.

Now THAT'S micro-optimizing. Don't do this at home.

I also suspect it won't come close to bringing my program in under 1 minute.

Winston
 
Aditya Jha
Ranch Hand
Posts: 227
Eclipse IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I started implementing this after reading the original post. The initial program took close to 104 seconds to generate the answer.

After applying the incredibly geeky optimization as mentioned above, thanks to Winston Gutkowski, it came down to 61.101 seconds.

So close!

P.S.: And yes, no String business at all. Just positive integers bliss.
 
Aditya Jha
Ranch Hand
Posts: 227
Eclipse IDE Java Spring
  • Likes 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
More optimization on the Math level (as opposed to code level), and the time comes down to 5.982 seconds.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Aditya Jha wrote:More optimization on the Math level (as opposed to code level), and the time comes down to 5.982 seconds.

Got mine down from 550 to 120, but I know I'm missing something obvious.

Winston

[Edit: Got mine down to 12 seconds now, and I suspect the same trick will work for n < 10^13 too; but I still don't know why ]

[Edit 2: GOT IT!!! Thanks Aditya]
 
Aditya Jha
Ranch Hand
Posts: 227
Eclipse IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hint for those who are still on it: There won't be any reversible numbers with number of digits as (4*x+1). That means no reversible number would ever have 1-digit, 5-digits and so on...

Though, I recommend first proving this theorem for yourself, and then using the technique in code.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Aditya Jha wrote:Though, I recommend first proving this theorem for yourself, and then using the technique in code.

Absolutely. When I said "Got it!", I actually didn't quite. Took me about another half hour to work out the proof; but it's a long time since A-Level Maths for me.

I'm now having a look at the Darts checkout one (#109).

Winston
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i started working on 116. after several days i gave in and cheated by finding a solution on the internet
after looking through the forum after my crime, i found similarities in some of the other solutions to what i was trying. i will still try to work it out but with help now. some solutions were awesome! like the first one i found. i couldn't imagine it could be so simple. several used what they call memoization and dynamic programming. i intend to read some more about both of those subjects. Winston, i am still going to use your method to see how much it helps my solution to 145, i just got distracted
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:Winston, i am still going to use your method to see how much it helps my solution to 145, i just got distracted

The biggest help will be to follow Aditya's advice.

Winston
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
well using Winston's method didn't seem to help any. i have one less StringBuilder and no Integers(just one StringBuilder now) but it seems no faster. 2 minutes or so for 100,000,000. the answer is the same for 1 billion, it just takes over a half hour instead.
 
Randall Twede
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


this is similar to what i have been reading about concerning memoization. however a lookup table is compile time while memoization is done at runtime. i am still reading about this and dynamic programming. it will be worth it if i can understand it all. i have trouble with recursion to begin with.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Randall Twede wrote:i have trouble with recursion to begin with.

Well you know what they say:
To understand recursion, you must first understand recursion.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!