Program optimization?

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Postposted on Fri May 21, 2004 6:26 am

I'm glad my programming classes are in object pascal at the moment... that C++ code looks like it would make my brain melt :o

of course, half the problem is not knowing how to mathematically solve the initial problem in the first place =)
blitzy
Gerbil Jedi
 
Posts: 1779
Joined: Thu Jan 01, 2004 6:27 pm
Location: New Zealand

Postposted on Fri May 21, 2004 7:46 am

MorgZ wrote:wats the quickest java implementation?

Im tempted to give it a go since im pretty nifty at speedy algorithsm :o

Well, Yahoolian's Java port of my version was running mac_h8r1's original test case so fast that the elapsed time was coming up as zero. Running multiple test cases through it to get a measurable benchmark time is actually kind of problematic, since the cached implementation means it will keep getting faster unless the cache array is cleared between test cases; but clearing the cache will also take time. Suffice it to say that the current implementation is "damn fast". :wink:

blitzy wrote:I'm glad my programming classes are in object pascal at the moment... that C++ code looks like it would make my brain melt :o

Once you get out into the "real world" you'll come over to the Dark Side... muahahaha! :evil:

Seriously... if you actually want to get a job programming, C++, Java, or even specialized (but "real world") languages like Transact-SQL are more marketable skills than Object Pascal (which is used commercially to some extent, but not much). Pascal is great for teaching general algorithm and data structure concepts though; that's why it is used a lot in programming classes.

of course, half the problem is not knowing how to mathematically solve the initial problem in the first place =)

Yes, the original problem is a bit of a brain-bender. As mac_h8r1 discovered, the obvious brute-force solution gets horribly inefficient for large input values.

My family probably thought I was on drugs or something a couple of nights ago during dinner -- I was trying to work through potential algorithms in my head, and must've seemed like I was on another planet. :lol:
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37739
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Fri May 21, 2004 8:53 am

just brew it! wrote:My family probably thought I was on drugs or something a couple of nights ago during dinner -- I was trying to work through potential algorithms in my head, and must've seemed like I was on another planet. :lol:


Sounds like something I used to do to keep myself busy when at work.

I've got a cd-mp3 player. I ended up spending any free moments in an 8 hour shift trying to work out how much music I can fit on a 700 meg cd at 128Kbps.

Amount of music = (700*1024KB) / (16KB/s * 60 s/min * 60min/hr)

Suffice to say, I forgot a carry somewhere :lol:,
-Mole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Fri May 21, 2004 9:44 am

Yahoolian, 928131635 is the value I get when I run your program for 55.75. Any thoughts?

JBI, Glad to keep you on your toes! :wink:

So, considering that this was one problem of 9, who thinks that, working with two others, they could win a competition given 4.5 hours? This was not the most difficult, btw :). I posted this one 'cause it was the only one I worked on that didn't get accepted. There may be another that I post, as I'm COMPLETELY in the dark regarding that one.
mac_h8r1.postCount++;
Chaos reigns within. Reflect, repent, and reboot. Order shall return.
Slivovitz owns you.
mac_h8r1
Minister of Gerbil Affairs
 
Posts: 2962
Joined: Tue Sep 24, 2002 6:57 pm
Location: Alpha Epsilon Pi for life

Postposted on Fri May 21, 2004 10:13 am

mac_h8r1 wrote:Yahoolian, 928131635 is the value I get when I run your program for 55.75. Any thoughts?

Did you just copy-paste his code, or could it be a transcription error? Have you tried the C++ version?

JBI, Glad to keep you on your toes! :wink:

So, considering that this was one problem of 9, who thinks that, working with two others, they could win a competition given 4.5 hours?

That sounds pretty rough! You'd all need to be really sharp, and it would take a little luck too.

This was not the most difficult, btw :). I posted this one 'cause it was the only one I worked on that didn't get accepted. There may be another that I post, as I'm COMPLETELY in the dark regarding that one.

Bring 'em on! :lol:
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37739
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Fri May 21, 2004 10:16 am

mac_h8r1 wrote:Yahoolian, 928131635 is the value I get when I run your program for 55.75. Any thoughts?

The cents are getting truncated somewhere. 928131635 appears to be the correct answer for an input of 55.00. Maybe you typed a comma instead of a decimal point?
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37739
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Fri May 21, 2004 11:37 am

Yahoolian wrote:That would explain it. I'd doubt that Java is faster than C++/C, because it does bounds checking on all array lookups.


Nitpick (unrelated to current thread): not necessarily. In this particular instance (unless the JVM is really smart), array bounds checks are required (though maybe not on all references). But in an iterative implementation, it probably wouldn't be too hard to convince the JVM that array bounds checks are unnecessary.

Assuming, of course, that your JVM contains a just-in-time compiler.
froydnj
Gerbil
 
Posts: 17
Joined: Mon Apr 21, 2003 10:59 pm
Location: Houston, TX

Postposted on Fri May 21, 2004 12:02 pm

MorgZ wrote:wats the quickest java implementation?

Im tempted to give it a go since im pretty nifty at speedy algorithsm :o

You won't be able to beat JBI...

Unless, you do it mathematically (look at JBI's link). It would be an interesting problem if you could specify any number of coin types and find the solution (mathematically).
moog
Gerbil Elite
 
Posts: 836
Joined: Wed Jun 11, 2003 9:10 am
Location: Here

Postposted on Fri May 21, 2004 6:02 pm

But in an iterative implementation, it probably wouldn't be too hard to convince the JVM that array bounds checks are unnecessary.

Assuming, of course, that your JVM contains a just-in-time compiler.


Well if the JIT compiler does have that optimization, then yes, it wouldn't have to check for out of bounds. But I haven't heard of such a thing until now.

Did you just copy-paste his code, or could it be a transcription error?


Hmm, it was working fine before, one of the modifications made it produce incorrect results. I'll go over the code again. But I'm pretty sure the code is rigoriously identical to your money2.cpp.

edit: Hmm, I switched to version 1 and I get an infinate loop.
Yahoolian
Grand Gerbil Poohbah
 
Posts: 3576
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD

Postposted on Fri May 21, 2004 6:37 pm

When you said it was the value for $55, I figured it meant that the value was being rounded before being multiplied.

Found the problem:
Code: Select all
int cents = (int)Double.parseDouble( s ) * 100;

needs to be
Code: Select all
int cents = (int)(Double.parseDouble( s ) * 100);

Order of operations makes it so that in the first one, the string is converted to a number, then turned into an int [and rounded] then multiplied by 100. The second one takes the string, multiplies it by 100, THEN turns it into an int [and rounds in the case that you put in too many decimal values]

Ey, at least I got to put the final touch on my program!
mac_h8r1.postCount++;
Chaos reigns within. Reflect, repent, and reboot. Order shall return.
Slivovitz owns you.
mac_h8r1
Minister of Gerbil Affairs
 
Posts: 2962
Joined: Tue Sep 24, 2002 6:57 pm
Location: Alpha Epsilon Pi for life

Postposted on Fri May 21, 2004 6:56 pm

anyone care to show how the program works through pseudocode? It's quite an interesting problem

JustBrewIt wrote:Seriously... if you actually want to get a job programming, C++, Java, or even specialized (but "real world") languages like Transact-SQL are more marketable skills than Object Pascal (which is used commercially to some extent, but not much). Pascal is great for teaching general algorithm and data structure concepts though; that's why it is used a lot in programming classes.


yeah, definately... we have been doing some basic things like performing a linear search within a textfile and creating database tables from a legacy binary file, not entirely useful in the real world the way we went about them, but it keeps things simple for us
blitzy
Gerbil Jedi
 
Posts: 1779
Joined: Thu Jan 01, 2004 6:27 pm
Location: New Zealand

Postposted on Fri May 21, 2004 9:36 pm

blitzy wrote:anyone care to show how the program works through pseudocode? It's quite an interesting problem

I'll give it a shot... but if you've never used recursion before, it may still be a bit difficult to get your head around. I still have a hard time following it, and I wrote the damn thing... :o

Code: Select all
This algorithim recursively calculates the number of unique ways to
make change for a given amount of money, using coins of specified
denominations. Inputs are the list of denominations to be used, and
the value to make change for. All values are in cents.

If list of denominations to use is empty, then

    the result is 0.

Else if amount to make change for is 0, then

    the result is 1.

Else if we've already calculated a value for this list of denominations and
amount of money, then
 
    the result is the value calculated previously (retrieve from 2D
    array indexed by the largest denomination of coin currently in the
    list, and amount we're making change for).

Else if the largest denomination in the list is less than or equal to
the amount we're making change for, then
   
    subtract the largest denomination from the amount we're
    making change for, and recursively calculate how many ways we can
    make change for the remaining amount, using the same list of denominations.
    Also recursively calculate the number of ways we can make change for the
    total amount, using only denominations smaller than the largest one.
    The sum of these two values is the result.

Else

    recursively try again using the total amount, but only considering denominations
    smaller than the largest one currently in the list.

If we calculated a new value, save it in a 2D array indexed by the largest
denomination in the list of coins, and the amount we're making change for.

It might be helpful to try working through the above algorithm with pencil and paper, using a small list of coin denominations and a few small test inputs.
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37739
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Fri May 21, 2004 11:49 pm

I don't think I fully understand the way you're handling the calculation, the way you're caching the previous calculations and using the arrays escapes me at this point, but thanks for explaining anyway (I have used some basic recursion in one of my projects, so I do have a rough idea how that works).

I can think of an ugly way to do it using lists of numbers but it's nowhere near as clean as yours is and would be full of redundancy(would require a hell of a lot more code than you used also). I wish I had more free time to spend looking at this problem, but unfortunately I've got several assignments looming at the moment :-?
blitzy
Gerbil Jedi
 
Posts: 1779
Joined: Thu Jan 01, 2004 6:27 pm
Location: New Zealand

Postposted on Mon May 24, 2004 4:25 pm

Oh yeah, I forgot to add that I moved the
Code: Select all
if (cache[start][target] != 0)
      return cache[start][target];


lines to the front of the function, that makes it go from 16 milliseconds to 0 on my computer( AXP 2500+ @ 200 * 10.5 ).

Since then I did a few other minor changes, some for clarity, some for speed.

Now the coin value array is in ascending order, which makes more sense to me.

Code: Select all
import java.io.*;
import java.util.*;

class Money{
  public static final int MAX_CENTS = 30000;
  final static int value[] = { 0, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
  static long cache[][] = new long[ value.length ][ MAX_CENTS + 1 ];
  static final String filePath = "D:\\Money\\src\\";
   
  public static void main ( final String []args)
  {
    long beginTime = System.currentTimeMillis();
    try {
      BufferedReader file = new BufferedReader (new FileReader (filePath + "dollars.txt") );
      String s = file.readLine();
      while (s != null)
      {
        int cents = (int)(Double.parseDouble( s ) * 100);
        System.out.println( s + "\t" + maxWaysToMake( cents ) );
        s = file.readLine();
      }

    } catch (Exception e) {
      System.out.println(e);
    }
    System.out.println( "Elapsed milliseconds: " + ( System.currentTimeMillis() - beginTime ) );

  }
 
  public static long maxWaysToMake( final int cents )
  {
    int start = value.length - 1;
    while ( value[start] > cents )
      start--;
     
    return maxWaysToMake( start, cents );
  }
   
  public static long maxWaysToMake( int start, final int cents)
  {
   
 //   System.out.println( "\ncall: " + ++call + "\nstart: " + start + "\ntarget: " + target);
   
    // if value already computed, return previously computed value
    // doing this first results in a huge speed up
    if (cache[start][cents] != 0)
      return cache[start][cents];
   
    // check for trivial terminal conditions
    else if (start == 0)
      return 0;
     
    else if (cents == 0)
      return 1;
       
    else if (value[start] <= cents)
      cache[start][cents] = maxWaysToMake(start, cents - value[start]);
     
    cache[start][cents] += maxWaysToMake(start - 1, cents);
   
    return cache[start][cents];
  }
 
}


Edit: Note that you must change filePath to the path to your numbers.txt file.
Last edited by Yahoolian on Mon May 24, 2004 5:06 pm, edited 2 times in total.
Yahoolian
Grand Gerbil Poohbah
 
Posts: 3576
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD

Postposted on Mon May 24, 2004 4:31 pm

Yahoolian wrote:Oh yeah, I forgot to add that I moved the
Code: Select all
if (cache[start][target] != 0)
      return cache[start][target];


lines to the front of the function, that makes it go from 16 milliseconds to 0 on my computer( AXP 2500+ @ 200 * 10.5 ).

Interesting... I would not have expected that. The only other two tests ahead of it were simple tests for values being equal to 0, which should be nearly instantaneous in the grand scheme of things. I suspect that this may be a peculiarity of the Java compiler, or within the margin of error of the timing routine used.
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37739
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Mon May 24, 2004 4:40 pm

Interesting... I would not have expected that. The only other two tests ahead of it were simple tests for values being equal to 0, which should be nearly instantaneous in the grand scheme of things.


Well for the input of 55.75 the function is called 4939 times, and 1348 times when the value is cached, I guess those two less comparisions and one less array lookup add up quite a bit.

I suspect that this may be a peculiarity of the Java compiler, or within the margin of error of the timing routine used.

Well I doubt the timing routine would give me the same value multiple times if it was due to an error. I don't know about the compiler though.
Yahoolian
Grand Gerbil Poohbah
 
Posts: 3576
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD

Postposted on Mon May 24, 2004 5:00 pm

Yahoolian wrote:Well for the input of 55.75 the function is called 4939 times, and 1348 times when the value is cached, I guess those two less comparisions and one less array lookup add up quite a bit.

Yeah, I suppose it could be a net win if those two other branches aren't taken very frequently. I didn't do a detailed analysis of how often each branch is taken, beyond a few trivial (small) inputs.

Edit: Maybe Microsoft should hire us to optimize Windows for them. How much smaller/faster do you think we could make it? :lol:
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37739
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Previous

Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 2 guests