Phelio Gnomi

My words from my mind

The Ruby, C++, PHP and C++

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.

Advertisements

2 responses to “The Ruby, C++, PHP and C++

  1. JonKalb April 23, 2012 at 10:10 pm

    Here are some tips for C++. Avoid native arrays. If you have access to it, you can use C++11’s std::array, std::tr1::array, or boost::array, but only if you know that std::vector won’t work for you.
    Associative arrays are called std::map. This is implemented as a red-black tree and is fast enough for most uses. If you really need a hash it is available with every implementation, but naming differs. If you have access to C++11, it is std::unordered_map. In the TR1 it is std::tr1::unordered_map. There is a TR1 implementation available from Boost.org and some implementations may have it with the (non-standard) name hash_map (sometimes, despite its non-standard name, in the std namespace).

    Good luck and have fun.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: