2

I'm running Eclipse in Linux and I was told I could use Xdebug to optimize my program. I use a combination algorithm in my script that takes too long too run.

I am just asking for a starting point to debug this. I know how to do the basics...break points, conditional break points, start, stop, step over, etc... but I want to learn more advanced techniques so I can write better, optimized code.

Improve this question
6
  • 1
    Obviously, you're sucking up all 128meg the script is allowed to use. What are you doing that requires storing this much data in memory? The only way to solve this is to reduce storage requirements for your algorithm(s) or raise the memory limit. Without any details of what you're doing, it's like going to a garage and saying "my car's broken, fix it" and then nothing saying HOW it's broken. Commented Apr 22, 2011 at 19:14
  • How do I increase the 128M. I'm using a combination algorithm, specifically the Chase algorithm - netlib.no/netlib/toms/382. For nCk , n = 12 and k = 3, the script uses too much memory. Commented Apr 22, 2011 at 19:21
  • ini_set('memory_limit', NEW_VALUE). Setting new_value to -1 removes the limit, otherwise it's the limit in bytes Commented Apr 22, 2011 at 19:23
  • For algorithms such as the one you're using, their memory requirements explode upwards VERY quickly. You may not want to use PHP for testing this stuff, as even a simple integer variable (4 bytes) will internally use up more than that, so you're wasting a huge amount of memory just on PHP overhead. Commented Apr 22, 2011 at 19:27
  • I had some intermediary arrays that I removed, which solved the memory problem, now the problem is run time. It is basically a type of Traveling Salesman problem...and my understanding is this type of optimization is a branch of combinatorial optimization. So instead of using brute force or all combinations computed from Chase I should have some sort of optimization...probably need a math forum. Thanks for the info. I was not aware PHP had overhead on its variables. Commented Apr 28, 2011 at 0:21

1 Answer 1

Reset to default
7

The first step is to know how to calculate the asymptotic memory usage, which means how much the memory grows when the problem gets bigger. This is done by saying that one recursion takes up X bytes (X = a constant, the easiest is to set it to 1). Then you write down the recurrence, i.e., in what manner the function calls itself or loops and try to conclude how much the memory grows (is it quadratic to the problem size, linear or maybe less?)

This is taught in elementary computer science classes at the universities since it's really useful when concluding how effective an algorithm is. The exact method is hard to describe in a simple forum post, so I recommend you to pick up a book on algorithms (I recommend "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein - MIT Press).

But if you don't have a clue about this type of work, start by using get_memory_usage and echoing how much memory you're using in your loop/recursion. This can give you a hint about were the problem is. Try to reduce the amount of things you keep in memory. Throw away everything you don't need (for example, don't build up a giant array of all data if you can boil it down to intermediary values earlier).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Good guess. I had intermediary arrays I used for debugging, once I took these out, it ran with in memory limits but was too slow due to the run time of computing all possible solutions. I'm pretty sure there exists a optimized combinatorial approach to the problem which I realized is a version of the Traveling Salesman problem. Thanks for the input.
Good work! Knowing the name of your problem will give you tons of help. The problem with NP-hard problems is that they are really hard to solve :-/ I wish you good luck!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.