My words from my mind
Monthly Archives: April 2012
I’m taking the Stanford Online Course called the Design and Analysis of Algorithm 1. So far so good, and then the Programming Exercise 4 hit me hard.
First of all, we are allowed to use any programming language. They only want the final result, regardless of how you process them. So, at week 4, we are supposed to read through a file that represent a Graph with thousands of nodes. And we are asked to find the five largest strongly connected components or SCC.
So, I started with Ruby, which is my language of choice for this course. The algorithm that the professor teaches use recursive. So, after finishing the program and running it trough few test cases which seems to work properly, I run it on the actual file (the thousands of nodes graph). It crashed in the first few seconds saying that “stack level Too deep”. Apparently the recursive is too deep for my Ruby to process. I tried to find how to increase the stack level allowed, but it’s either I don’t understand what they are talking about or the solution is for Mac or Linux. I’m working on a Windows 7.
So, I think maybe I should do it on C++. One reason is because it’s fast, and it’s difficult (so I can learn to be a better programmer, not just a guy who get pampered by modern programming language). Then, if you know C++ and also know Ruby or PHP, you can see that C++ is so much different. So much more difficult. PHP pretty much take care of many things behind the screen for you,things like dynamic array or array with random index name (hash in Ruby, associative array in PHP), or passing the array around like tossing pancake from the pan to the plate. They are not that simple in C++. Array is just a pointer with the size. Passing array is complicated, not to mention about multilevel arrays. It doesn’t have hash or associative array.
I have to admit that I’m too pampered by modern (high level) programming language and it’s not the C++ fault, and creating your own function to search an array or to enable dynamic index naming is just too much for me. So, I go back to PHP and try out it’s maximum stack level allowed. First try, it return error on the 100th recursive. But don’t worry, it turned out that it’s just the limitation that X-Debug set. I remove X-Debug and it can run for as deep as your computer memory can supply (which is a lot and a good news).
I immediately converted the Ruby code into PHP code and voilà, it works on the test cases. Working on PHP is like returning home. It feels natural for me as if I’m talking in my mother tongue. However, When I run it on the real graph, I hit a lot of memory limit error. I increase it few times, from 128M to 256M, to 1024M to 2048M. It consumed more than 1GB or RAM to process 5 millions connections of 800 thousand of nodes. And it run forever. And ever. I never get the result back yet. And I’m suspecting an infinite loop, but can’t really find the proof of it. Therefore, I have to conclude that it’s the PHP problem. It’s simply to slow.
So, my only hope is C++ now, which I’m not good at, and I have to build many functions from scratch. Well, probably I can find some library online. But, I don’t know. It feels like I’m forced to speak Spanish when I only know a few words like “la nina come pan” and “el niño bebemos leche”. And I’m literally not sure is it bebemos or beben? Oh, I’m screwed.