Posts tagged optimization

3 o’clock javascript

Mar 28th

I was writing some code to react at a textarea.onKeyUp. I take the size of the current textarea.val().length, update an element and do some other stuff.

yawn

The first version of the code looked like:

$('#message').keyup(function(e){
   $('#chars_num').html( new_len );
   $('#sms_num').html( Math.floor($('#message').val().length / 161) +1) );
});

Working good, but was clearly slow: every keystroke was “giving back the cursor” too slowly for a fast typer like me. I went to take a look at twitter, and their text box was WAY FASTER.
More >

Pascal’s Triangle generator

Jan 11th

Posted by Detro in IT / Comp-Sci / Code

No comments

What’s Pascal’s Triangle? That’s what it is (Wikipedia has all the theory, if you need).

Pascal’s Triangle first 6 rows

The thing I wrote here is a generator of the n-th row of the triangle, that doesn’t use more then the memory needed to store the solution. Instead of allocating a Triangular Matrix, and building every row based on the one above, solution is built in place.

More >

Fibonacci’s numbers calculator

Jan 5th

Posted by Detro in Curiosity

No comments

Another simple-but-yet-interesting problem that I found challenging solving is the to Write a Fibonacci’s numbers calculator. It’s a REALLY SIMPLE problem, but still can demonstrate how superficial thinking in programming can lead to dramatically bad solutions.

What’s a Fibonacci’s number

A Fibonacci’s number is an integer number generated using the following function:

Assumed that:
f(0) = 0
f(1) = 1

for a generic “n” Integer:
f(n) = f(n-1) + f(n-2)

For example, the first 20 Fibonacci’s number are:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

The young-and-entusiast approach

Recursion! We all love the elegance of it. When we manage to write something that uses Recursions, everything seems easier and simpler to our eyes for a while. BUT, in this particular case, using recursion for implementing such simple task is really bad.

Why? Because at every call to this function, it will generate 2ⁿ recursive function calls. A bit of a nightmare for the process call stack if the whole purpose of this thing is calculating a “stupid” integer number.

Functions call tree using a recursive algorithm

Plus, given the nature of the function itself, it will recalculate the same f(x) over and over again, because f(x) is going to be a subproblem shared between a certain y and z, where both y > x and z > x.

Result? An awful implementation. With a quick Big-Oh analysis I would say that the Time Complexity of this “monster” will be O(2ⁿ).
Don’t believe it? Check out the implementation here:

#include <stdio .h>

unsigned long fibonacci_slow(unsigned short i)
{
    if ( i == 0 )
        return (0);

    if ( i == 1 )
        return (1);

    return ( fibonacci_slow(i-1) + fibonacci_slow(i-2) );
}

int main(int argc, char** argv)
{
    unsigned short i, input;
    unsigned long curr = 0, prevprev = 0, prev = 1;

    // Check the Input
	if ( argc == 2 ) input = atoi(argv[1]); else return (1);

	printf("RESULT: fibonacci(%d) = %lu\n\n", input, fibonacci_slow(input));
	return (0);
}

Running it on my Code 2 Duo laptop with n > 40 takes around 10 seconds. For n = 50 I got bored to wait after 1 minute passed by.

If you check out this book, it is going to tell you that such solution is going to take 13 days to come out with a solution, for an average machine (i.e. a machine where O(1) = 0.001 µs).

BUT, of course, I have an alternative solution. Actually, more then one. And the best runs in O(log(n))
More >

Find the non repeating char in O(n) time and O(1) space – v2

Dec 18th

Posted by Detro in Personal

4 comments

My colleague and friend Luca (@lucabox) described a better solution to the problem of “Finding the first non repearing char in a string in O(n) time and O(1) space“. It uses smartly the space, making the solution nicer and slicker.
Or we are just 2 geeks that need to give more attention to their girlfriends

Luca’s solution description

The logic of this solution is based on the usage of an array of unsigned chars.
Every char (assumed to be lowecase) has an associated small byte (1 char = 8 bits), where the bits 0×1 and 0×2 (the 2 least significant) represents, respectively, “present once in the input string” and “present multiple times in the input string“. After the input is “scanned” once, and every letter is marked with the correspondent “presence bit” (once, multiple or none), it get’s scanned a second time to find the first char of the input which has the bit “present once” set to “1″.

Before I show you the code

Again, this comes from Luca Colantonio (http://uk.linkedin.com/in/lucacolantonio), smart ass that is too lazy to maintain a blog and post it himself (or even implementing himself – he just explained to me at work and I had to code it). Thanks Luca

Now, the code.
More >