Some thoughts on your (and my) thoughts.

SQL Query Optimization - Part-9 (Covering Indexes)

2012-01-24T10:20:00.000-08:00

To speed up query performance, use a Covering Index that covers (indexes) not just columns that will be used in the WHERE clause, but also columns that will be used in the projection list of the SELECT query.

See this video for a more detailed explanation.

Converting Regular Expressions to a DFA

2012-01-22T22:44:00.000-08:00

Instead of writing anything on this most researched topic, I'm just posting some links here.

http://www.youtube.com/watch?v=dlH2pIndNrU
http://projectsseminar.blogspot.com/2011/06/regular-expression-to-dfa.html
http://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times
http://swtch.com/~rsc/regexp/regexp1.html

Solve this recurrence

2012-01-08T01:29:00.000-08:00

T(n) = T(n - √n) + T(√n) + n

Post your answers/solutions in the comments. We were asked this in the final exam in CSE-548 (Analysis Of Algorithms taught by Dr. Michael Bender).

Ayurvedic Way of Life

2012-01-08T00:43:00.000-08:00

Follow the principles mentioned here and you should be good to go!!

Also, here is another very informative article about the ayurvedic view on food.

Broccoli should be had fresh!!

2012-01-08T00:35:00.000-08:00

Broccoli should be had fresh and not frozen.

Frozen Broccoli is not as firm as Fresh Broccoli
Frozen Broccoli doesn't taste as good as Fresh Broccoli
Frozen Broccoli doesn't contain the broccoli stalk which is not only more nutritious, but also more fibrous than the brocolli florets
According to this page, "frozen broccoli has twice as much sodium as fresh (up to 68 mg per 10 oz. package), about half the calcium, and smaller amounts of iron, thiamin, riboflavin, and vitamin C."

Peas on the other hand should be had frozen since (from here), "Peas are high in sugar content, so they have to be blanched before freezing to stop enzyme activity from turning sugars into starch and ruining their fresh sweet flavor."

Focaccia reprise

2012-01-08T00:12:00.000-08:00

Made Focaccia Bread again after about 2 years of absence from baking. Contains garlic, thyme, oregano, dried basil and olive oil. This is how it turned out:

Ingredients, motivation and housing courtesy Poorvi Matani, and oven & electricity courtesy Panna Parikh. A big thanks to my teachers at IHM and my mom who encouraged my culinary streak ;)
This version lacked rosemary since I didn't have ready access to any. Next batch should have that plus olives, sun-dried tomatoes and maybe some other veggies.
The last post about something similar was this recipe for Garlic & Herb Chapati.

What business do you want to be in?

2011-10-24T15:34:00.000-07:00

Dr. Bender once mentioned in class that memories are created when one experiences ~~joy~~ strong emotions, and in the context of algorithms, when one discovers a solution to some problem.

About a month down, I've noticed that experiences are what I'm going to die with. I vividly remember this episode in school when we were in the middle of the gymnastics competition and were one short of someone on the roman rings. I decided to give it a shot (even though I had never tried it before) and 2 minutes later I found myself stuck "up there". I don't remember all the things that I did right or who eventually won, but I surely do remember getting stuck!

If you are from my school and remember this episode, please leave a comment. I'll be looking forward to hearing from you!

I want to be in the business of creating memories.

Edit: Fixed the incorrect quote in the first line.

The Integer (0/1) Bounded Knapsack Problem

2011-09-20T19:42:00.000-07:00

Quoting the problem statement from Petr's blog:

"The bounded knapsack problem is: you are given n types of items, you have u_i items of i^th type, and each item of i^th type weighs w_i and costs c_i. What is the maximal cost you can get by picking some items weighing at most W in total?"

Here, we assume that the knapsack can hold a weight at most W.

We shall describe 3 solutions to this problem, each of which reduces the complexity of the solution by a certain amount.

O(W*n*M): The first solution is the standard knapsack solution solution, which just involves copying each item instance of every item type to get a total of u_i items of the i^th type, each of which represents a different item having the same w_i & c_i as the item of the i^th type.

It is easy to see that if we have a mean of M number of items of each type, the complexity of this solution is O(W * n * M)
O(W*n*log(M)): The second solution involves rewriting items such that we have a fewer number of items of each type to work with. We shall then solve the transformed problem using the same technique as the standard knapsack problem (as in the solution above).

Suppose we have 21 instance of the i^th item type, weighing w_i and costing c_i. We observe that 21 can be rewritten (using powers of 2) as:
21 = 1 + 2 + 4 + 8 + 6

We basically add powers of 2 till we exceed the sum we want to create (21 in this case). When we exceed the sum, we just add the difference (6 in this case) between the number (21 in this case) and the current sum we have (15 in this case = 1+2+4+8).

Now, the new items are created by combining 1, 2, 4, 8, and 6 items of the original instances. These newly created items will have the following weights and costs:

Number of items of the original type combined Weight Cost
1 1*w_i 1*c_i
2 2*w_i 2*c_i
4 4*w_i 4*c_i
8 8*w_i 8*c_i
6 6*w_i 6*c_i

Hence, we have effectively reduced the number of items from 21 to 5. In general, we replace the M in the solution above with log(M) to get a final complexity of O(W * n * log(M)).
O(W*n): The third and most efficient solution to this problem is the one that took me almost 3 days to figure out and understand. The short post on petr's blog actually contains all the information needed to understand it, but I'm not that comfortable reading terse explanations; especially when it's a new idea, so here is something more verbose.

There is also a paper and a section in a book dedicate to this problem, but I find them quite hard as well.

Let's assume that this row (in the DP table of Items (rows) v/s Weight (columns)) represents the best configuration (maximum cost) for the knapsack at every weight 0 .. W that includes all item types from 1 .. (k-1)

Weight 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Item (k-1) 0 5 5 7 15 15 19 20 21 23 30 33 42 42 49 51

So, the basic observation is that DP_{(k-1), w} represents the best solution including all items from 1 .. (k-1) (both inclusive) with a knapsack of weight (w).

To compute DP_{k, w}, we consider the possibility of including either 0, 1, 2, 3, 4, ..., u_i items of the i^th type to the previous best solution including all items from 1 .. (k-1). This gives us the following recurrence:

DP_{k, w} = max (
    DP_{(k-1), w},
    DP_{(k-1), w-1*w_k} + 1*c_k,
    DP_{(k-1), w-2*w_k} + 2*c_k,
    DP_{(k-1), w-3*w_k} + 3*c_k,
    ...,
    DP_{(k-1), w-u_i*w_k} + u_i*c_k)

An interesting observation here would be that we only deal with every w_k^th element from the previous array to decide on any element in the current array.

Let us for a minute ignore the fact that we have only a fixed number of items of each type and assume that we have an infinite number of items of each type. Let us assume that item i weighs 3 and costs 9. If we make that assumption, we see that the best solution at DP_{k, 12} is represented by taking the maximum of the cells colored in green below.

Weight 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Item (k-1) 0 5 5 7 15 15 19 20 21 23 30 33 42 42 49 51
36 34 37 32 42

What we have essentially done is added:
0*9 to DP_{(k-1), 12}
1*9 to DP_{(k-1), 9}
2*9 to DP_{(k-1), 6}
3*9 to DP_{(k-1), 3} and
4*9 to DP_{(k-1), 0}

The problem has reduced to finding the maximum value among all the values of the array that is formed by picking every w_k^th element from the previous best solution and adding some multiple of c_k to it.

We also notice that it doesn't matter what values we add to DP_{(k-1), w} (for the k^th item) as long as they are c_k apart. Hence, if the weight of the knapsack is W and the weight of the k^th item is w_k, we can add the following to every w_k^th element in the previous array.

Column to which value is added Value Added
0 (W/w_k)*c_k
1*w_k (W/w_k - 1)*c_k
2*w_k (W/w_k - 2)*c_k
3*w_k (W/w_k - 3)*c_k

If we now reintroduce the requirement that each item type will have only a bounded or fixed number of instances (i.e. u_k is bounded), then the problem reduces to finding the maximum value in every window of size u_k in the array we just computed. This can easily be done by pre-processing the array to maintain the largest element in every window of size u_k.

However, the actual value of the cost at any cell needs to be computed by adding back any differential that we may have subtracted to ensure that every entry is c_k apart and that the first entry is the one which has the maximum multiple of c_k subtracted from it. For the j^th array element in the current sub-array we are processing, this value will be (W/w_k - j)*c_k (since we have subtracted that much extra from those elements, we must now add it back).

Hence, we can safely say that we shall have w_k different sub-problems that we shall try to solve assuming that we can use a single computation for every w_k^th element.

This allows us to find the value at every cell of the (k x W) matrix is amortized time O(1) (we have amortized the cost of pre-computing the w_k arrays across all the element accesses). This makes the total running time of this algorithm O(W * n).

Number of items of the original type combined	Weight	Cost
1	1*w_i	1*c_i
2	2*w_i	2*c_i
4	4*w_i	4*c_i
8	8*w_i	8*c_i
6	6*w_i	6*c_i

Weight	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Item (k-1)	0	5	5	7	15	15	19	20	21	23	30	33	42	42	49	51

Weight	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Item (k-1)	0	5	5	7	15	15	19	20	21	23	30	33	42	42	49	51
	36			34			37			32			42

Column to which value is added	Value Added
0	(W/w_k)*c_k
1*w_k	(W/w_k - 1)*c_k
2*w_k	(W/w_k - 2)*c_k
3*w_k	(W/w_k - 3)*c_k

Vegetable Ratatouille

2011-07-14T01:54:00.000-07:00

Here we go!!

So, we'll be following this recipe for the most part. There are some diversions that I shall mention here. These are the only things I changed from the recipe above.

Tomatoes: We shall make a Ratatouille that has a red (tomato) gravy and the vegetables will be added to that gravy. For this, you'll need more tomatoes (at least 4 more).

Basil: I used dry basil instead of fresh basil, since I couldn't find any where I stay. I used lesser oil at every stage (use about half the amount of oil everywhere).

Olive Oil: Do NOT use Extra-Virgin Olive Oil for cooking. Do NOT use Olive-Pomace Oil since it doesn't have a good taste. Use ONLY Pure-Olive-Oil.

Salt: ALWAYS use Salt to-taste instead of measuring it since the saltiness of salt varies from region to region.

Ginger: I also use grated ginger (or ginger paste) along with the garlic pieces.

Bay Leaf: I also used bay-leaves (3 nos.) while sautéing the onions (along with the garlic and ginger).

After the onions are half done, add pieces of (at least) 4 tomatos and cook till the tomatoes are soft. Mash them to form a paste. Follow the recipe mentioned here. Once the other vegetables are cooked, add them to this tomato gravy and cook for about 3 mins. (or till steaming). Cover and let the vegetables soak in the smell for about 15 mins. Serve with rice (you can use brown rice since it tastes really good and is a healthier option when compared with white rice).

You know you are working with the right people when ...

2011-07-06T10:45:00.000-07:00

... you get this in the post :) :)

Thanks @yegg :-)

A plea to all software developers: Use Units

2011-06-10T05:31:00.000-07:00

Have you ever come across configuration files that read:

MAX_BUFFER_SIZE = 4096
MAX_TIMEOUT     = 20

WTF!!

4096 what?? bits, bytes, kilobytes, megabytes?

20 what?? mill-second, second?

Please, please make units part of the config. option and say:

MAX_BUFFER_SIZE_BYTES = 4096
MAX_TIMEOUT_MILLISEC  = 20

Why DuckDuckGo is good for mother

2011-05-15T14:24:00.000-07:00

My mother wastes a lot of time online visiting MFA sites because she can't differentiate between the legitimate ones and the scammy ones. I've set up DuckDuckGo for her as her default search engine and she's been complaining lesser about "Why does this site not have what I want?".

I also feel that DDG can have a bang page organized by target audience (such as Mother/Father/Student, etc...). For Mother, these would need to go in:

!allrecipes
!epicurious
!w
!yt
!lyrics
!gimages
!gmaps
!bloomberg
!reuters
!songmeanings
!news

It would surely make it easier for mother to navigate the shortcuts!!

Faster Javascript String matching

2011-05-08T13:50:00.000-07:00

Ever had to match a lot of strings (say article titles or names of people) to a user entered query? I'm sure you always:

Looped around the values and
Performed a substring search on these strings

Well, it turns out that both are suboptimal. Let us for a minute assume that the data you have is relatively static (doesn't change too much over time) and that queries really should be satisfied quickly. If that is the case, then you would be better off:

Maintaining all the data to be queried in a single string (delimited by a $ or # sign - something that is not expected to be present in the data itself)
Performing a regular-expression match on the aforementioned string

Assuming that the regular expression engine is optimized (and mostly they are), a regexp match would be much faster than a naive O(n²) search.

Let's look at some code and the resulting running time for either approach.

function random_string(len) {
    var s = '';
    for (var i = 0; i < len; ++i) {
        s += String.fromCharCode(Math.round(97 + Math.random()*26));
    }
    return s;
}

var rs = [ ];
var total_length = 0;
// Stores the start index of each string in rs.join('$');
var indexes = [ ];

for (var i = 0; i < 300000; ++i) {
    var s = random_string(40);
    rs.push(s);
    indexes.push(total_length);
    total_length += (s.length + 1);
}

function test_01(rs) {
    // Returns the number of elements in 'rs' that match the regexp /ret/
    var re = /ret/g;
    var cnt = 0;
    for (var i = 0; i < rs.length; ++i) {
        var m = rs[i].match(re);
        if (m) {
            cnt += 1;
        }
    }
    return cnt;
}

function test_02(rs) {
    // Returns the number of elements in 'rs' that match the regexp /ret/
    var re = /ret/g;
    var s = rs.join('$');
    // Indexes of strings in 'rs' that matched
    var idx = [ -1 ];
    var ii = 0;
    var m = re.exec(s);
    while (m) {
        while (ii < indexes.length && indexes[ii] <= m.index) {
            ++ii;
        }
        if (idx[idx.length-1] != ii) {
            idx.push(ii);
        }
        m = re.exec(s);
    }
    return idx.length - 1;
}

d1 = new Date();
console.log("test_01:", test_01(rs));
d2 = new Date()
console.log("test_01 time:", d2-d1);

d1 = new Date();
console.log("test_02:", test_02(rs));
d2 = new Date()
console.log("test_02 time:", d2-d1);

This is the output that running this code produces:

test_01: 665
test_01 time: 935
test_02: 665
test_02 time: 257

Which means that the longer code is actually 2.63 times faster than the more beautiful looking code.

When the difference between 200ms and 300ms is felt by the user (for UI centric applications), this can be a huge improvement to the perceived responsiveness of the application.

Computing the Cumulative sum of a range of elements in a binary tree

2011-05-08T08:48:00.000-07:00

Let us assume the alternative definition of a BST (Binary Search Tree), namely: "The left subtree shall contain elements less than or equal to the element at the root and the right subtree shall contain elements greater than or equal to the element at the root".

This means that if we want to compute the cumulative sum of all numbers ≤ to a given number, we need to update some metadata every time a node is added to the tree or removed from the tree (and for a balanced BST also when rebalancing occurs). Fortunately, this implementation of the AVL Tree allows us to do just this by way of hook functions that you can pass to it via the constructor.

We define a function binary_tree_summer that computes the cumulative sum of a node and its child nodes and stores in the sum attribute of the node.

To query the cumulative sum, we define a function query_sum that basically employs the following strategy (given our definition of the BST above):

If the value at the node is ≤ than the value we are looking for, we take the cumulative sum at the node, subtract from it the sum in it's right subtree (since we don't know how many elements in the right subtree will match our query) and then add the result of querying the right subtree
If the value at the node is > the value we are looking for, we are assured that the complete range lies in the node's left subtree, so we query the left subtree

You can see that at every stage, we decide to go either left or right, which means that our runtime is bounded by the height of the tree, which fortunately in case of an AVL Tree is at most O(log n).

The code for such a use-case is shown below:

function cumulative_sum() {
    var items = [ 4, 9, 2, 5, 4, 2, 1, 2, 3, 2, 1, 7, 3, 2 ];

    function binary_tree_summer(node) {
        var _s = (node.left ? node.left.sum : 0) + 
         (node.right ? node.right.sum : 0) + node.value;
        node.sum = _s;
    }

    var tree = new algo.AVLTree(algo.cmp_lt, binary_tree_summer);
    for (var i = 0; i < items.length; ++i) {
        tree.insert(items[i]);
    }

    function query_sum(node, value) {
        // We do the query like we do for a Segment Tree
        if (!node) {
            return 0;
    }

    if (node.value <= value) {
        var sub = node.right ? node.right.sum : 0;
        return node.sum - sub + query_sum(node.right, value);
    }
    else {
        // node.value > value
        return query_sum(node.left, value);
    }
}

console.log("<= 2:", query_sum(tree.root, 2));
console.log("<= 5:", query_sum(tree.root, 5));

Let's look at summing all numbers ≤ 2. The diagram below shows us how the call flow looks like. Note:

The green lines are the paths followed down the root
The red lines are the paths that are rejected (not followed)
The numbers in blue above each node denote the value of the sum attribute for that node

The sum is obtained in the following manner for values ≤ 2: 47-39+4

The diagram below shows us the call flow for summing all numbers ≤ 5.

The sum is obtained in the following manner for values ≤ 5: 47-39+39-25+25-16

Binary Trees with Repeated elements

2011-05-08T03:42:00.000-07:00

In school/college, we all learnt about Binary Trees and while we were taught how to implement them, the implicit assumption was that elements would not be repeated. However, in the real-world, we need to deal with repeated elements all the time. Most standard library implementations of popular languages (read Java) provide a TreeMap that is reduced to something very powerless because it doesn't support repeated elements!! The C++ std::multimap class however supports repetitions and is IMHO much more powerful than any other Balanced Binary Tree implementation that I have come across.

Today, I shall make an attempt to de-mistify the process of creating a Binary Tree with repeated elements. It's really simple and I think that the process can be summarized in one sentence: "Instead of the left subtree containing elements strictly less than the element at the root and the right subtree containing elements strictly greater than the element at the root, the left subtree shall contain elements less than or equal to the element at the root and the right subtree shall contain elements greater than or equal to the element at the root". Simple, isn't it!!

Now, let's see why it works.

The simple case of asking whether an element exists or not can be easily implemented the same way as before. If the element is present, we shall hit it while traversing down the tree.

Finding the first instance of an element (if it exists) is called locating the lower_bound of that element. This can be accomplished by running down the left of the node till you have an element at the node that is greater than or equal to the element to be found. We keep a track of the node every time we take a left turn. Othwerise (the element at the node is less than the element we are interested in), we go down the right. Since the lower_bound of an element is never less than the element itself, we don't keep track of nodes when we take a right turn.

Finding one-past the last instance of an elemnt (if it exists) is called locating the upper_bound of that element. This can be accomplished by running down the left of the node till you have an element at the node that is greater than the element to be found. We keep a track of the node every time we take a left turn. Othwerise (the element at the node is less than or equal to the element we are interested in), we go down the right. Since the upper_bound of an element is never less than or equal to the element itself, we don't keep track of nodes when we take a right turn.

On the following pages, can find very high quality implementations of a Red-Black Tree and an AVL Tree respectively that both support repeated elements as well as the lower_bound and upper_bound functions.

No special handling is required during re-balancing the tree during an insertion or a deletion.

Here is a sample instance of the AVL Tree after the following elements have been inserted into it in this same order (the numbers after the - sign are just to disambiguate nodes with the same key while plotting the tree):

4, 9, 2, 5, 4, 2, 1, 2, 3, 2, 1, 7, 3, 2

Computing the Running Median of an Array of numbers

2011-05-07T08:49:00.000-07:00

The problem of computing the running median of an array of numbers involves choosing a window size for which you want to compute the median for. For example, suppose you have the following list of 10 integers:

4, 6, 99, 10, 90, 12, 17, 1, 21, 32

and you want to compute the running median for a window of size 7, you will get the following list of 4 medians:

Median for 4, 6, 99, 10, 90, 12, 17  : 12
Median for 6, 99, 10, 90, 12, 17, 1  : 12
Median for 99, 10, 90, 12, 17, 1, 21 : 17
Median for 10, 90, 12, 17, 1, 21, 32 : 17

The naive way would be to always sort the array and pick the middle element. This costs O(n.log n) per operation (when an integer leaves and enters the window). A slightly smarter solution will try to keep the array sorted and remove and insert the integers in O(n) time. Even though this is better, we hope to do better.

You can find many resources online that try to solve the problem, but surprisingly, very few mention an O(log n) solution (per insertion and removal of an integer), which I believe is quite easy to implement.

I shall first describe a general (data structure independent) procedure for computing the running median of a set of integers and provide other specific tricks that use a balanced binary tree to achieve the same.

General Technique:
The general technique involves keeping the data (we assume that all integers are distinct for the sake of simplicity) partitioned into 3 sets, namely:

All elements less than the median
The median
All elements greater than the median

Set-1 should support the following operations with the below mentioned runtime complexity:

Insertion of an element: O(log n)
Removal of an arbitrary element (given its handle - the handle is returned by the data structure when the element is inserted): O(log n)
Query the maximum valued element: O(log n)

Any operation on Set-2 is pretty trivial to implement, so I'll skip to the next set.

Set-3 should support the following operations with the below mentioned runtime complexity:

Insertion of an element: O(log n)
Removal of an arbitrary element (given its handle - the handle is returned by the data structure when the element is inserted): O(log n)
Query the minimum valued element: O(log n)

What we shall do is initially sort the first 'k' (window size) elements in the stream and create the 3 sets as described above. We also maintain a queue of handles as returned by each of the data structures managing Sets 1 & 3. This will help us remove the oldest element from these sets.

When a new integer is to be inserted, we follow these steps:

Get the handle to the oldest element and remove it from the set in which it currently is
Insert the new element in Set-1 (or Set-3) and push the returned handle into the queue
If the median element goes missing, we pick up the largest element from Set-1 (or the smallest element from Set-3), remove that from the set and set that as the median element
If we notice that the sizes of Sets 1 & 3 are not within 1 of each other, we shift the elements via the median from one set to the other
We always shift the largest element from Set-1 or the smallest element from Set-3
We ensure that the handles get updated whenever the elements move from one set to the other. This requires the handle to be smart and contain a reference to its parent set

If we follow the steps mentioned above, we are ensured that the median is always present in Set-2 (Set-2 always has just 1 element).

A Max-Heap can be used to implement Set-1 and a Min-Heap can be used to implement Set-3. Alternatively, a Min-Max-Heap can be used to implement both. We can also use a balanced binary tree (such as an AVL Tree, Red-Black Tree, AA Tree) to implement Sets 1 & 3.

Balanced Binary Tree Technique:
We can use a Balanced Binary Tree such as an AVL Tree or a Red-Black Tree with order-statistic querying to implement the running median algorithm. Insertions and deletions can be performed in O(log n) time (as before, we maintain a queue of the elements - we do not need handles in this case since a balanced binary tree can delete an element in O(log n) given the element's value). Furthermore, we can query the tree for the WINDOW_SIZE/2 ranked element (which is the median) at every stage. This is by far the simplest and cleanest technique. You can find an implementation of an AVL Tree that supports querying the k-th smallest element (for any k) here.

Example code to use the AVLTree linked above:

var algo = require('algorithm');
var items = [4, 6, 99, 10, 90, 12, 17, 1, 21, 32];

function print_median(tree) {
  console.log("Median:", tree.find_by_rank(Math.ceil(tree.length / 2)));
}

function running_median(items, window_size) {
  var tree = new algo.AVLTree();
  for (var i = 0; i < items.length; ++i) {
    tree.insert(items[i]);
    if (tree.length == window_size) {
      print_median(tree);
      tree.remove(items[i - window_size + 1]);
    }
  }
}

running_median(items, 7);

Bajra Roti/Parantha

2011-04-18T22:57:00.000-07:00

Ingredients:

Bajra atta (Pearl millet flour):	2 cups
Water:	Enough to bind the flour (keep 2 cups handy)

Procedure:

Add little water and try to bind the flour. Keep adding a water as and when required
Once the flour is hydrated, add a little more water to make it smooth
Take a plastic sheet and place it on the chakla (flat circular rolling board)
Ensure that you heat the tava (flat skillet) before you begin. Turn the flame to low when it is heated up
Take about 100-150g of dough and place it on the plastic sheet
Sprinkle some millet flour on top of it so that it doesn't stick to your hand
Using your hand, gently press down the dough ball into a flat circular disc - rotating the dough all the time. It should be easy to rotate the dough since the plastic sheet will slide very easily on the rolling board
Keeping the flame on low, place the flattened dough (top side down) on the tava
Once you see small bubbles popping up on the surface, turn the roti over
Heat till you see brown spots on the under-surface
Turn the flame to high and momentary place the roti (turned over again) on the flame directly. This should make the roti balloon. The ballooning of the roti means that it has been cooked properly
Turn over to other side to cook consistently (as desired - but don't burn it please!!)
Serve with dahi (curd), butter, jaggery and vegetables. Enjoy!!

News these days

2011-04-18T22:15:00.000-07:00

Being the beneficiary of a headache yesterday, I had the privilege of being unproductive and just fixing myself in front the of television set and watching the daily news with the rest of the family. The news reader almost mechanically read out these 2 news items back to back (in the same segment):

Police firing in The Ratnagiri district of Maharashtra kill 1 and injures 5, and
Indian Ministers oppose the wastage of food at weddings and ask the organisers to provision accurately

It just seems so weird that these 2 news items come together - any way you look at it!! And I'm not even going into whether the people opposing the wastage are themselves practicing what they preach.

Segment Trees and Bitmaps

2011-04-17T05:25:00.000-07:00

Bitmaps are used all the time to keep track of free lists since they are a very compact way of keeping track of true/false information. They are used in the ext2/ext3 file system to keep track of free inode and data blocks, in the bitmapped_allocator to keep track of free memory blocks, and in many many other places.

However, in almost all places, a linear search technique is used to get the first set (or unset) bit. This works very well for small sets of data, but say you have 40 million items that you want to keep track of, you'll land up linear searching 40x10⁶/8/1024/1024 = 4.7 MB of data, which is more than the cache size of most CPUs these days. What this effectively means is that you will land up filling up the CPU cache with the bitmaps, leaving very ittle space for your application's real data

.

This is obviously bad news and we should do something to fix it.

Welcome Trees!!

We take some inspiration from Segment Trees and use a hierarchial structure to store range data that will help us divide-and-conquor the free list in a zippy fashion.

Let's assume that each byte on our fictitious machine can hold just 2 bits. A bit 0 means that the object that that bit represents is free, whereas a bit 1 means that the object that that bit represents is taken (or allocated).

The root node gives us information about the complete range (all the 8 bits in the leaves). The nodes at the 1^st level give us information about 4 bits each, and each of the leaf nodes give us information about 2 bits each (this is a base case since each byte on our machine can hold just 2 bits).

Now, finding a free node is just a simple tree traversal down a path that has 0 in one of the bit positions. While coming up, we set the 0 bits in each level (that we followed down) to a 1 bit ONLY if all the children of that 0 bit are all 1. We unconditionally set the 0 bit in the leaf node to 1 and go up the tree.

Hence, you can see that we have converted a O(n) operation to a O(lg n) operation by increasing the space requirements to 2x the original. Even though the space requirement is 2x the original, the tree based algorithm is much better not just from a time complexity perspective, but is also much more cache friendly. You should expect to have only the first 2 levels entirely in the cache. The remaining levels will come and go as necessary. This is the exact reason why B-Trees are better as an on-disk indexing and retrieval structure.

On a 32-bit machine, we need just a little over 5 levels of the tree to store 40 million bits (34 million bits can be stored completely in just 5 levels).

Update: You can achieve the same runtime complexity of O(lg n) and NO extra space overhead (compared to the linear scan solution) by using a Fenwick Tree instead of a Segment Tree.

Lazy Logging on Javascript (2)

2011-04-16T23:14:00.000-07:00

A few weeks ago, I wrote about how to do lazy logging in Javascript by passing functions to the logging functions. These functions would actually do the CPU intensive evaluation (if needed) and return something that would subsequently be printed on the screen. The key thing to notice is that the item(s) to be printed would be computed ONLY if they were actually going to be printed (using the current logging level and the 1^st parameter to the logging function).

I noticed that a lot of code had started looking quite ugly.

log_it("DEBUG", function() {
  return [ some_var1.toString(), some_var2.toString() ];
});

Note: Any expensive computation that should be performed MUST go inside the toString() method of some_var1 and some_var2.

I have instead decided to solve it by making a function do what the caller was earlier doing:

// toString() Promise
function tsp() {
  var args = arguments;
  return {
    toString: function() {
      return Array.prototype.slice.call(args).map(function(v) {
        return v.toString();
      }).join(' ');
    }
  };
}

As a result of this modification, all code that does logging now looks like this:

log_it("DEBUG", tsp(some_var1, some_var2));

The reason why this works is because log_it() is going to call toString() (if required) on each of its arguments before printing them.

Much neater eh?

A comment on an email signature

2011-04-07T22:12:00.000-07:00

I've added this signature to my outgoing emails at work

n="63686180107683"; n.split('').splice(0,7).map(function() {
   t=n%100; n=n/100; return parseInt(t);
}).reverse().map(function(v) {
   return String.fromCharCode(v+6*6);
}).join('');

and was pleasantly surprised to receive a fairly long and detailed analysis of what Joel Rosario had to say about it.

I wonder how many people have run and tried to understand your signature. I just did. It is devious, and evil.

* What you really want is a loop. Why splice the large string from 0 to 7? It unnecessarily misleads the reader into thinking you're doing a meaningful string operation.
* Why use map with an anonymous function that takes no parameter? This trips up the unwary reader into reading the function, and wondering what it is being applied to.
* The use of n % 100 and n=n/100 seems to show off javascript's perlish ability to treat strings as numbers.
* The above might also confuse the hapless reader. What happens when you cross a string with a number, hmmm?
* By this time, having nearly given up trying to understand what's going on, the reader is hit with reverse(), surprised by a map(), and presented with a function that expects a parameter that is clearly an integer. The arithmetic operations of +6*6 applied to an already mystical parameter v will be too much for any sane person to bear. By now your reader has already succumbed to his fear and fled for a coffee break.

Why lay such traps for the unwary? Why risk the equanimity, the morale, indeed the sanity of your esteemed colleagues? Why couldn't you just have signed your mail with console.log('chat.pw')?

- Joel Rosario.

Needless to say, some of my emails will randomly have console.log("chat.pw") in them ;)

Emails like this make my day; nay week!!

Lazy Logging on Javascript

2011-03-26T03:01:00.000-07:00

One of the things that I like about C/C++ is compile time macros. What they mean is that if I have debug print statements, not only will they be compiled out, but also the expressions passed to the printing statement will not be evaluated.

I have code like this in javascript:

var logging = false;
function log() {
  if (logging)
    console.log.apply(console, arguments);
}

var xml = an_xml_stanza();
log("XML Stanza:", xml.toString());

Even if logging is false, the expression xml.toString() will be evaluated, which can be quite costly in a production setup (I'm talking about node.js and not on a browser).

The way I've solved this is by making sure that my log() function can accept functions as well. Hence, code such as this becomes possible:

var xml = an_xml_stanza();
log(function() {
  return ["XML Stanza:", xml.toString()];
});

The log() function needs to be patched to look like this:

log = function() {
  if (!logging)
    return;

  if (arguments.length == 1 && typeof arguments[0] == "function")
    arguments = arguments[0]();

  console.log.apply(console, arguments);
}

This essentially means that you've gotten rid of the runtime cost of calling xml.toString() when logging is disabled.

Node and the Proxy/Decorator Pattern

2011-03-21T05:00:00.000-07:00

The proxy pattern.
The decorator pattern.

Proxies & Decorators are patterns that abstract away or enhance certain functionality in an entiry.

Since they are both almost the same, it isn't very helpful to know the finer differences between the two, but here they are just for completeness.

Example of a Proxy:
When you proxy some functionality, you generally delegate the responsibility to someone else. The most practical example is an HTTP Proxy that forwards requests on your behalf to the real web-server.

Example of a Decorator:
When you decorate some functionality, you generally add more functionality to it. For this example, I shall discuss the code that is presented below. It is basically an EventEmitter that transparently decompresses the string that is passed to it and re-raises the events that the original EventEmitter raised. You can use it to transparently read a compressed/secure stream given that you have a decorated EventEmitter for it.

File: gzip.js

var compress = require('compress');

function _inflater(stream) {
 this._stream = stream;
 var self = this;
 var gunzip = new compress.Gunzip;
 gunzip.init();

 this._stream.on('data', function(d) {
  var _d = gunzip.inflate(d.toString('binary'), 'binary');
  self.emit('data', _d);
 })
 .on('end', function() {
  self.emit('end');
 })
 .on('error', function() {
  var args = Array.prototype.splice.call(arguments, 0);
  args.unshift('error');
  self.emit.apply(self, args);
 });
}

_inflater.prototype = new process.EventEmitter();


function _deflater(stream) {
 this._stream = stream;
 var self = this;
 var gzip = new compress.Gzip;
 gzip.init();

 this._stream.on('data', function(d) {
  var _d = gzip.deflate(d.toString('binary'), 'binary');
  self.emit('data', _d);
 })
 .on('end', function() {
  self.emit('end');
 })
 .on('error', function() {
  var args = Array.prototype.splice.call(arguments, 0);
  args.unshift('error');
  self.emit.apply(self, args);
 });
}

_deflater.prototype = new process.EventEmitter();



exports.inflater = function(stream) {
 return new _inflater(stream);
};

exports.deflater = function(stream) {
 return new _deflater(stream);
};

File: test.js

var gz   = require("./gzip.js");
var http = require("http");

var req = http.request({
 host: "duckduckgo.com", 
 port: 80, 
 path: "/"
}, function(response) {
 console.log("response headers:", response.headers);

 //
 // We check if we need to create a proxy event emitter that
 // inflates data on the go.
 //
 if (response.headers['content-encoding'].search('gzip') != -1) {
  //
  // The response object is now the proxy object. A similar 
  // technique is used to support TLS encrypted sockets too.
  // We just wrap up the original EventEmitter instance in 
  // a proxy instance that does its magic.
  //
  response = gz.inflater(response);
 }

 response.on('data', function(d) {
  console.log("Got:", d.toString());
 });
});

req.setHeader("Accept-Encoding", "gzip");
req.end();

Issue list in code

2011-03-20T05:47:00.000-07:00

A few weeks ago, there was a debate/argument/discussion about what issue tracking tool should be used for our project. The 2 main contenders were JIRA and Basecamp. I'll try to capture the essence of the discussion.

Things going for JIRA:

Very customizable and configurable
Offers many workflows and views
Lots of plugins
Easy for manager to generate reports (good reporting features)

Things going against JIRA:

Not the most convenient to use for developers
Too much (unnecessary) detail to be filled in for each task at times

Things going for Basecamp:

Easy to use. Clean interface. More like a todo list
Developers like it

Things going against Basecamp:

No easy custom report generation facility
Not reporting/manager friendly

We've decided to try both out for a few months and see which one "works out" for us. We were using JIRA before, but the enthusiasm seems to have died out after a few months and the issue tracker is not in sync. with the actual issues/reports/bugs/features being developed.

I have an entirely different point of view though. For me what has worked best is comments in code that say something like:

// TODO: Such and such is broken. It needs to be fixed in so and so way.

The reason is that it's too much tedium for me to update things in 2 places (code and issue tracker) when I fix an issue. If I forget, then it's even harder to related the issue to the actual change made. This method offers a way of alleviating that problem.

I'm also okay with having comments that are verbose just so that they can explain in sufficient detail the reason (or purpose) of the code below.

However, this has been mostly for projects where I have been the sole developer. I don't know how well it would scale for projects with 2-3 developers, 5-6 developers and > 6 developers.

I would guess that it's fine for projects with up to 6 developers, but beyond that it would get cumbersome. Also, this way of tracking issues lacks a good reporting method which allows you to track changes across versions. Of course, if you want to adopt this as a workflow, I'm sure some tooling around this general idea can be developed which works by generating diffs between revisions to track which bugs this revision (or set of revisions) fixes.

node-xmpp-bosh: A BOSH (connection manager) session manager for the XMPP protocol

2011-03-19T06:45:00.000-07:00

You can find out all about what BOSH is from XEP-0124 and XEP-0206.

Most respectable XMPP servers out there such as Openfire, Ejabberd, and Tigase support BOSH as part of the server.

This is where you can download the node-xmpp-bosh BOSH server from.

I'll just discuss some of the reasons that it's good to have a BOSH session manager running outside of the XMPP server.

Easier to scale the BOSH server and the XMPP server independently (independently being the key here). See my previous blog post for a detailed explanation
You can support users from multiple domains such as gmail.com, chat.facebook.com, jabber.org, pandion.im, etc... using the single BOSH server
Any customizations to the BOSH server are easier made if it is running out of process (restart it independently of your XMPP server - since getting an XMPP server warmed may be more expensive than getting a BOSH server warmed up)
Use protocols other than XMPP at the back, but still retain the same interface as far as clients are concerned. This will still require you to use XMPP for the actual communication (Note: This can be accomplished via transports [for yahoo, msn, aim, etc...] available for any XMPP server [that supports XEP-0114] as a Jabber Component). But, if you please, you can also write a small drop-in replacement server that speaks basic XMPP, but does something entirely bizarre at the back!!

Scale out with services - Scale the services separately

2011-03-19T06:21:00.000-07:00

Whatever I am writing about here has been taught to me by this brilliant write up that I quote from the DBSlayer project page.

"The typical LAMP strategy for scaling up data-driven applications is to replicate slave databases to every web server, but this approach can hit scaling limitations for high-volume websites, where processes can overwhelm their given backend DB's connection limits. Quite frankly, we wanted to scale the front-end webservers and backend database servers separately without having to coordinate them. We also needed a way to flexibly reconfigure where our backend databases were located and which applications used them without resorting to tricks of DNS or other such "load-balancing" hacks."

What this means is that it is better (from a scaling perspective) to split your application into services rather than have them run as one monolothic application on some very powerful machine.

Why is it better to do so? That's because each "service" may have different performance requirements and characteristics which can be better addressed in isolation if the service is running as a separate entity.

For example, consider a typical web-stack which consists of:

Load balancer (nginx)
Web server/script execution engine (apache/php)
Data Store (mysql/pgsql)
Caching service (redis/memcached)
Asynchronous processing infrastructure (RabbitMQ)

For a medium to high load web site (a few million hits/day => about 20-30 req/sec), you could make do with just a single instance of nginx, 2 machines running apache/php, 2 machines running MySQL and one machine running RabbitMQ. Even for this deployment, you can see that each of the components have different requirements as far as the machine (and hardware usage) characteristics are concerned. For example,

nginx is network I/O heavy. You could deploy it on a machine with a modest (1GB) amount of RAM, no hard disk space, and not a very fast CPU
The Apache/php servers on the other hand would need more RAM as well as more CPU, but no disk space
The MySQL nodes would need a lot of RAM, CPU as well as fast disks
The node running RabbitMQ (a message queue) could again comfortably run on a machine with a configuration similar to nginx (assuming that data is stored on MySQL)

Thus, we have sliced our stack into components we can club together not just based on function, but also based on the charasteristics of the hardware that they would best be able to run on. Aside: This reminds me of Principal Component Analysis.

Node.js as "the next BIG thing".

2011-03-19T05:12:00.000-07:00

I generally hate to talk about "the next BIG thing" because there seem to be (relatively) fewer things (as compared to all the things that we encounter) that influence our lives in significant ways these days (simply because we encounter so many things these days).

However, I feel that node.js is going to be quite influential in the years to come.

So, what is "node.js"? Node (put briefly) is a javascript execution engine. It incorporates asynchronous I/O as part of its design and hence can be considered asynchronous by design. This is where it starts getting fascinating for me.

Do you remember all those $.ajax() requests you made in the browser? Well, what if you could so the same on the server side? What if stitching together a page on the server was as easy as making AJAX calls and filling in empty <div> tags? You needn't stretch your imagination too much because that's exactly what Node lets you do!!

Even more exciting is that fact that this asynchronous API isn't limited to just HTTP/AJAX calls, but extends to protocols such as SMTP, POP, XMPP, and Database handlers such as PGSQL, MySQL, and Sqlite. This is because the Socket & file system I/O on Node is asynchronous by design. (almost??) All the APIs which do I/O are asynchronous in nature. For some, blocking counterparts are provided solely for convenience.

Toy task: Make 10 HTTP web calls and present the output as the result of each of these 10 calls separated by a new line. Assume that each HTTP call takes 1 sec to produce the result.

Sample code (in your favourite programming language; using blocking I/O):

out = "";
for i = 1 to 10:
 # We assume that http_call blocks till the fetch completes.
 response = http_call(url);
 out += (response + "\n");
write_output(out);

You notice that the code takes 10 sec to run - 1 sec for each HTTP web call. We ignore the time taken to write out the results.

Sample code (using non-blocking I/O):

out = "";
res [10] = [ ];
for i = 1 to 10:
 # We assume that http_call does NOT block and retiurns immediately, 
 # processing the task in the background (another thread or using
 # non-blocking I/O)
 res[i] = http_call(url);

for i = 1 to 10:
 # We assume that the when statement blocks execution till the 
 # condition is met
 when res[i].complete:
  out += (res[i].data + "\n");

write_output(out);

You notice that the code takes 1 sec to run - 1 sec for each HTTP web call; all of which fire at the same time. We ignore the time taken to write out the results.

That's a phenominal increase of 10x from the blocking version. Now, why wouldn't anyone use Node for such a use case??

jQuery stack == evolution

2011-03-08T07:26:00.000-08:00

So, twitter was kinda cramped, so I'm writing this here. A bunch of context around this. @addyosmani posted a tweet/link:

"Tools For jQuery Application Architecture – The Printable Chart http://bit.ly/fryIKW"

which I re-tweeted and to which @rakesh314 replied with this tweet/link:

"@addyosmani http://t.co/xWddsTK /cc: @dhruvbird"

So, there's one thing I strongly believe, which is that the jQuery stack seems to be a product of evolution, and evolution is generally not wrong - but that's a separate debate. Lots of people have tried different things and jQuery has evolved to permit all of them to co-exist in (relative) harmony.

The LAMP stack was not THE LAMP STACK before people realized these set of tools that were always used together. It was only after the fact that they decided to bundle them. Different Linux distros. are healthy in the sense that they package what they think their users want.

Similarly, I feel that the jQuery stack is progressing in that general direction and I won't be surprised to see vendors releasing their "version" or "distro" of the jQuery stack.

I'm not as much "against" dodo as I am "for" jQuery.

HTTPS for all browsing

2011-03-06T10:18:00.000-08:00

I've been thinking about using HTTPS for everything (even sites that don't support HTTPS) by routing all my traffic through a proxy that makes connections to the actual site (possibly on HTTP). This at least secures my traffic from packet sniffing on the local LAN.

What this means is that if you are at school or office, no colleague can run Wireshark or TCPDump on the the local LAN and capture/sniff your traffic. Also, you can now safely browse the web over http on insecure/potentially sniffed networks such as stray wireless networks without having to worry about your data being compromised! Welcome starbucks internet :-p

Traditionally, if the browser connects directly to a public proxy, then HTTP traffic still goes unencrypted (to the best of my understanding). Hence, this is what I've thought of doing.

Set up a local proxy on the same machine, which connects to a remote proxy over HTTPS.
Ensure that the remote proxy is running on a safe/trusted network (it could be your home PC if you want to use insecure wireless networks securely)
This remote proxy can now make HTTP connections and the issue of local packet sniffing is resolved.
However, it doesn't prevent remote packet sniffing (on the network where the remote proxy resides), which is why it is important to have the remote proxy sitting on a secure network.

If you are seriously planning to use this proxy, and you aren't yet using HTTPS Everywhere, I would strongly suggest that you start using it since it will reduce the load on the proxy and is more secure (since the encryption is end-to-end and not proxy-to-end).

Mamma says that there shall be a day when browsers pop up a warning when you view an http based page (as opposed to an https based one).

Update: You can grab the code for this proxy here

Attitude - and a bit of tea!!

2011-02-06T02:45:00.000-08:00

Yesterday, I had gone to have Chai (tea) and Brun Pav at Yazdani Bakery. When I was paying the owner (Rashid Zend in the photograph on the previous link) the amount due, he asked one of the waiter to bring a half eaten pav (bread) that a customer seemed to have left behind. He picked it up from the plate, examined it carefully and asked the waiter (in Hindi) "Why did he leave this uneaten?" I was quite taken by surprise by what he had just asked, but was also very very excited about having eaten at a place where the owner himself took such a keen interest in produce and tried to rectify even a single small error that may have occurred on his (bakery's) part.

Now, if we (as programmers) take every customer feedback this seriously and act upon it, I am fairly sure that the quality of the final product will go up by leaps and bounds!!

Fixing javascript variable leaks

2011-01-31T03:44:00.000-08:00

Today I happended to have a look at my application's window object and was shocked to see that 'i' was defined on it! I doggedly started searching my code to see where the leak had perpetrated itself from. After an hour of debugging, which included using Google's online closure compiler (Thanks Sandy!!) and jslint, I came up with nothing.

It struck me that it could be some of the js-libraries that I was using that were causing the leak, and not my code. I tried doing a binary-search on the js-includes, but that didn't work since the code wouldn't even run without most of those includes. At this point I really didn't know how to even go about trying to fix it!!

A few hacky thoughts later, I decided to introduce this code in my application:

var _iv = setInterval(function() {
  if (typeof window.i != "undefined") {
    clearInterval(_iv);
  }
}, 10);

Of course, this relied on the fact that I had inserted a verbiage of console.log() statements in my code at various points (It actually helped to have them!!)

This bit of hackery at least helped me determine that the error happened after a certain set of statements (functions) had executed. From here, it was manual work, checking every function and callback (yes) in my code as well as any library that I was using.

After about 30 minutes, I was able to trace the leak to embed.ly's jQuery library. I also discovered that the fb-complete jQuery library I was using had this leak, but it wasn't the one responsible for the specific instance of the variable 'i' that I was seeing then.

When to use events & when to use callbacks?

2011-01-30T12:37:00.000-08:00

With the recent spate of javascript programming that I've been subject to, I've found myself asking this question quite often to myself "Should I use callbacks here or should I use events (jQuery trigger & bind)?"

I've found this initial approximation quite useful till now: "If the operation that will follow depends upon the exact instance of this operation, then wrap the state in a closure and use a callback. Otherwise, use events." The advantage of using events is that:
1. You need not think of all the actions that could result in this event handler being called.
2. You need not tell anyone that this particular event handler needs to be invoked. Everyone just publishes some data (like a tweet) and all those interested (followers) just gobble that data up.
3. You can dynamically attach event handlers. So, if some component in the system suddenly decided to react to certain events, it can just plonk itself into to the listeners queue for that event.

jQuery goes one step further and allows you to trigger (and bind) events on specific DOM nodes only!! And then it goes a step further and lets you define an event namespace to try and prevent event name conflicts.

SQL Query optimization - Part-8 (Indexes Schmindexes)

2011-01-18T05:45:00.000-08:00

The "Why are my queries slow despite indexes on all columns" Edition.

Consider the following table:

CREATE TABLE florist_orders(
 order_id INT NOT NULL PRIMARY KEY AUTO_INCREMENT, 
 basket_color INT (1) NOT NULL, -- This can be either 0, 1, 2 or 3
 num_roses INT NOT NULL, 
 num_sunflowers INT NOT NULL, 
 num_daisies INT NOT NULL, 
 processed INT(1) NOT NULL DEFAULT 0, 
 created TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

Let's assume that the packaging for every basket of a different color is done by a diffrent person. Additionally, baskets packaging also differs based on the maximum number of flowers of each type. If there is more than 1 of any type, the packaging differs from when there is at most 1 of each type of flower. Each packager wants to check the orders that she needs to process.

The following query works fine:

SELECT * FROM florist_orders
WHERE
 basked_color = 2 AND
 processed = 0 AND
 (num_roses > 1 OR num_sunflowers > 1 OR num_daisies > 1)
ORDER BY created ASC -- Process older orders first to avoid starvation
;

However, as the size of the florist_orders tables gorws, you realize that each query is taking too long. Why is this? You have an index on every column and yet queries are slow?

You decide to create composite indexes. As a first attempt, you create an index on

(basket_color, processed, num_roses, num_sunflowers, num_daisies)

but notice that it hasn't really affected the query's execution time. Additionally, EXPLAIN says that no indexes are being used!! What to do now?

To solve this issue, you would need to modify your table and make it friendly for this specific query. These are the steps you would need to take:

Add a column named num_flowers which is set to MAX(num_roses, num_sunflowers, num_daisies) on every INSERT and UPDATE via TRIGGERS.
Then, create an index on:
```
(basket_color, processed, num_flowers)
```

Modify your query to read:

SELECT * FROM florist_orders
WHERE
 basked_color = 2 AND
 processed = 0 AND
 num_flowers > 1
ORDER BY created ASC -- Process older orders first to avoid starvation
;

This should pretty much fix any speed issues with the aforementioned query and ensure that all queries remain responsive. This trick will work ONLY if all the flowers are being checked to be greater than the SAME number.

Firefox, I love you!!

2011-01-04T11:03:00.000-08:00

The day was saved by Firefox's page cache. I typed in a reply on a forum thread, clicked "post reply" and then closed the tab, only to realize that I wasn't logged in and that a login dialog had popped up just as I had closed the tab. I right-clicked the tab-list and clicked "Undo Closed Tab" and poof!! the complete tab with all its state was there, awaiting my credentials!!

Awesome stuff Firefox... I love you!!

Peer-2-Peer systems at their best!!

2011-01-01T02:32:00.000-08:00

Recently, the skype network went down. You can read all about it here.

However, the exciting take away from this is (quoting from the link above) "In order to restore Skype functionality, the Skype engineering and operations team introduced hundreds of instances of the Skype software into the P2P network to act as dedicated supernodes, which we nick-named “mega-supernodes,” to provide enough temporary supernode capacity to accelerate the recovery of the peer-to-peer cloud."

Which is exactly my idea of how a self-healing peer-2-peer system should behave. Introducing more nodes into the mix should ideally help solve scaling and availability issues, which is exactly what the Skype team did. I would like to congratulate them for that!!

Practical SVD for the curious reader

2010-12-29T14:47:00.000-08:00

Let's see an example of how SVD can be used perform seemingly daunting tasks.
Consider that we are implementing a rating system for a contest and we want to know player that may have similar skill. Additionally we would like to know the hardness of the tasks in the contest since they are not known apriori.

We build a a matrix that holds player number on the y-axis and task number on the x-axis. Let us suppose that we roughly know the first 3 problems to be easy, the next 3 to be of medium difficulty and the next 3 to be hard. The built matrix would look like this:

# 0  1  2  3  4  5  6  7  8
[ 1, 1, 1, 0, 0, 0, 0, 0, 0 ], #0
[ 1, 1, 1, 1, 0, 0, 1, 0, 0 ], #1
[ 1, 0, 0, 0, 0, 1, 1, 1, 0 ], #2
[ 1, 1, 1, 1, 1, 1, 0, 0, 0 ], #3
[ 1, 0, 1, 1, 0, 0, 1, 1, 1 ], #4
[ 1, 0, 1, 0, 0, 0, 0, 0, 0 ], #5
[ 1, 0, 0, 1, 1, 1, 0, 0, 0 ], #6
[ 1, 0, 0, 1, 1, 1, 1, 1, 1 ], #7

Now, we compute the SVD of this matrix and keep only the best 4 feature sets.

We get [U=]

[[-0.22828916 -0.50341088  0.06758431 -0.27577721]
 [-0.3796649  -0.38290566  0.21189598  0.16725752]
 [-0.29514798  0.33343393  0.18247298 -0.80693185]
 [-0.4283514  -0.28592541 -0.50767041  0.05970937]
 [-0.42379852  0.09624233  0.5690528   0.38393312]
 [-0.18451958 -0.30010945  0.12296957 -0.24683212]
 [-0.31511921  0.15603403 -0.56486439  0.03629706]
 [-0.46924257  0.53231036 -0.03863212  0.17781851]]

We get [S=]

[[ 4.86583872  0.          0.          0.        ]
 [ 0.          2.40125574  0.          0.        ]
 [ 0.          0.          2.02979097  0.        ]
 [ 0.          0.          0.          1.29857912]]

We get [V=]

[[-0.55984867 -0.14756061  0.02109021 -0.38852126]
 [-0.21297571 -0.48817872 -0.11242051 -0.03758748]
 [-0.33799385 -0.57307894  0.22851232  0.06799022]
 [-0.41435336  0.0482063  -0.16268579  0.63532176]
 [-0.24923004  0.16758689 -0.54742924  0.21086504]
 [-0.3098872   0.30644504 -0.45753181 -0.41053094]
 [-0.32221659  0.24115755  0.45560831 -0.06000612]
 [-0.24418998  0.40061814  0.35121531 -0.18880653]
 [-0.18353282  0.26176     0.26131788  0.43258946]]

Next, we need to compute U*S and V*S.
What is the significance of these matrices?
The matrix U*S will allow us to find user that are similar in skill to each other.
The matrix V*S will allow us to determine problems that have been misclassified or are actually similar in difficulty to each other.

After computing the U*S and V*S matrices, we will take the row-wise sum of squared differences (SOSD)and check the pairs of rows that have the least such difference. These are the rows that are of interest to us.

We get [SOSD(U*S)=]

[(0, 1, 1.0430999999999999),
 (0, 2, 4.6740000000000004),
 (0, 3, 2.7736000000000001),
 (0, 4, 4.7484000000000002),
 (0, 5, 0.29770000000000002),
 (0, 6, 4.4981999999999998),
 (0, 7, 7.9534000000000002),
 (1, 2, 4.7319000000000004),
 (1, 3, 2.2631000000000001),
 (1, 4, 1.9745999999999999),
 (1, 5, 1.2628999999999999),
 (1, 6, 4.2881999999999998),
 (1, 7, 5.2785000000000002),
 (2, 3, 5.8609),
 (2, 4, 3.7233999999999998),
 (2, 5, 3.1476999999999999),
 (2, 6, 3.6909999999999998),
 (2, 7, 2.7824),
 (3, 4, 5.7964000000000002),
 (3, 5, 3.2058),
 (3, 6, 1.4441999999999999),
 (3, 7, 4.8299000000000003),
 (4, 5, 3.7522000000000002),
 (4, 6, 5.8014999999999999),
 (4, 7, 2.7383999999999999),
 (5, 6, 3.6880000000000002),
 (5, 7, 6.3265000000000002),
 (6, 7, 2.5535000000000001)]

Analysis of SOSD(U*S): User #0 & user #5 seem to be skilled similarly. Similarly, the following pairs of users also seem to be of similar calibre: (0, 1), (0, 5), (1, 4), (1, 5), (3, 6), (4, 7), (6, 7)
Some of this analysis may seem questionable especially considering that we designated the last 3 problems to be hard. How are user #1 & #4 similar if this is the case?
Let's look at the V*S matrix.

We get [SOSD(V*S)=]

[(0, 1, 3.7989000000000002),
 (0, 2, 2.7381000000000002),
 (0, 3, 2.629),
 (0, 4, 4.7946),
 (0, 5, 3.6124999999999998),
 (0, 6, 3.1680999999999999),
 (0, 7, 4.6081000000000003),
 (0, 8, 5.6936999999999998),
 (1, 2, 0.9093),
 (1, 3, 3.3931),
 (1, 4, 3.3944000000000001),
 (1, 5, 4.5884),
 (1, 6, 4.6798999999999999),
 (1, 7, 5.5022000000000002),
 (1, 8, 4.2117000000000004),
 (2, 3, 3.5369999999999999),
 (2, 4, 5.8647999999999998),
 (2, 5, 6.8044000000000002),
 (2, 6, 4.0688000000000004),
 (2, 7, 5.8483000000000001),
 (2, 8, 4.8121),
 (3, 4, 1.6414),
 (3, 5, 2.8456000000000001),
 (3, 6, 2.806),
 (3, 7, 3.6351),
 (3, 8, 2.3344),
 (4, 5, 0.88270000000000004),
 (4, 6, 4.4261999999999997),
 (4, 7, 3.9102999999999999),
 (4, 8, 2.931),
 (5, 6, 3.6707999999999998),
 (5, 7, 2.931),
 (5, 8, 3.7172000000000001),
 (6, 7, 0.36359999999999998),
 (6, 8, 1.0225),
 (7, 8, 0.88270000000000004)]

The following pairs of problems seem to be equally difficult/easy: (3, 4), (1, 2), (4, 5), (6, 8), (7, 8), (6, 7)
You can immediately see a clique of (6, 7, 8) which were all originally designated as hard problems!
Similarly, (3, 4, 5) seem to be related and so do (1, 2). The reason that problems #0 can not be classified by the system could be that since it has been solved by everyone, not much can be said conclusively about it.
You would have noticed that users #1 & #4 have both solved problems #0, #2, #3 & #6. As it turns out, it seems that the features (as deduced by the system) have given a higher weightage to one or more of these problems, which is why users #1 & #4 have been clustered together.

SVD 101

2010-12-28T10:08:00.000-08:00

I've been trying to find out more about SVD (Singular Value Decomposition) in the last few days, and here is what I have come up with (links marked with a star[*] MUST be READ). I'll try updating it as and when possible.

SVD can be used to:

Determine Document Similarity
Determine User similarity in a competition (or in a rating-based system such as movie recommendations)
Perform Image compression
Perform Principal Component Analysis
and much more...

You can use the following tools to compute the SVD of a matrix:

Suggest more recipients (in a chat conference)

2010-12-25T12:53:00.000-08:00

If you don't already know, gmail has had a feature called Suggest more recipients for a while now.

From the link above, "Gmail will suggest people you might want to include based on the groups of people you email most often. So if you always email your mom, dad, and sister together, and you start composing a message to your mom and dad, Gmail will suggest adding your sister. Enter at least two recipients and any suggestions will show up like this."

I am planning on extending this even for the chat conversation start page in the chat client that I'm working on. So, if you start entering JIDs of people you want to chat with, the client should automatically suggest more participants.

Thanks to Sandy for the providing the link to gmail blog!!

Update (02/01/2011): This feature is now implemented and part of the dev. versions.

Debugging PHP's $_REQUEST

2010-12-23T21:40:00.000-08:00

The $_REQUEST page in the PHP manual, says that "$_REQUEST is an associative array that by default contains the contents of $_GET, $_POST and $_COOKIE. The variables in $_REQUEST are provided to the script via the GET, POST, and COOKIE input mechanisms and therefore could be modified by the remote user and cannot be trusted. The presence and order of variables listed in this array is defined according to the PHP variables_order configuration directive."

I was under the impression that $_REQUEST would only contain data from the $_GET and the $_POST variables. In my application, I was setting cookies that had the same key as one of the GET parameters that I was expecting. The script was hence getting data set by the cookie and not the GET parameter!! I went half mad trying to debug this and was suspecting some caching issue. Things got queerer when changing some of the GET parameters worked, but others refused to budge from their original value!! You can imagine the perplexing situation I was in. Thankfully, though it dawned on me to check the PHP manual to see what the $_REQUEST was supposed to contain and I was able to fix my code to use $_GET.

Since then, I have come across this very useful page which mentions the exact problem I had and also says why one should avoid using $_REQUEST.

Shortest Slowest path

2010-12-23T13:15:00.000-08:00

A few weeks ago, I had was presented with a question: "You are given an n X n matrix. Each cell has a non-negative integer that denotes the cost of landing on that cell. Start from the top-left corner, compute the cost of the least-cost-path to reach the bottom-right corner of the matrix such that the sum of all costs incurred during the traversal is the least. Additionally, you are allowed to move only down or right."

Of course, this is just a slight variation of Dijkstra's Shortest Path problem, but I was surprised at the first solution that came to mind. I was trying really hard to not use Dijkstra's shortest path algorithm to solve this problem. I landed up linearizing all the n² cells into n² vertices in a graph and applied the Floyd-Warshall algorithm on the resulting matrix (of having side n²). Hence, the total complexity shot up to a whooping O(n⁶) (n being the side of the original matrix). If I had used a standard BFS or Dijkstra's algorithm, I would have been able to solve it with a runtime complexity of O(n² log(n)).

However, this was a very interesting exercise in functional programming since I was able to piece together a solution by chaining solutions to existing problems. The composition looks something like this:
Solution(matrix) = FloydWarshall(Linearize(matrix))

Dyslexia Friendly

2010-12-23T12:44:00.000-08:00

I made my home page Dyslexia Friendly today. Click here to find out more.

Help on selected text

2010-12-17T02:31:00.000-08:00

Today, I've added this new feature that I call "Help on selected text."

If you select any word or phrase on my blog, a small window will pop-up that will ask you to if you want more information on the selected phrase. If you click on the More Info link, you will be shown some more information if it is available. Pictures if available will also be shown. I am using Duck Duck Go's API to fetch this information. If nothing is found, an appropriate message will be displayed. If you select a block of text that is greater than 60 characters in length, it will be ignored and no prompt for more information will be shown.

Let me know if you find it useful or want to integrate it on your site!!

Update: Sandy suggested making the opacity of the box depend upon the distance of the mouse pointer from the info-box. Implemented this.

Update: A separate page documenting this widget, providing samples and examples has been put up here.

Update: My homepage: http://dhruvbird.com/ is now enabled with the zero-click plugin!!

TDDB: What I would do differently if I were to re-implement it

2010-12-16T22:22:00.001-08:00

Working on TDDB was a lot of fun (for all of us) and we learnt a lot!! Probably much more than what we initially thought. From not knowing anything about databases to implementing our own meant that we really hit the jackpot in terms on learning stuff and being hand-on. Watching theory and practice collide head on is something we experienced then!!

If I were to work on TDDB from scratch all over again, these are the things I would do differently:

Use HTTP for the transport layer. We implemented our own protocol for the transport. We got to learn a lot while doing so. However, since there's such a huge eco-system already built around HTTP, it would make sense to use it. Another advantage of using HTTP is that making clients in various languages (and even a client for the browser) is much less of an issue.
Use sqlite/MySQL/postgreSQL/BerkeleyDB or some other underlying DB for the actual storage. We implemented our own disk format and transaction subsystem instead of using something already available. We learnt a HELLUVA LOT while doing so. However, if I were to do it again, I'd go with something I can just build on. I would need to implement the query parser, the optimizer, the execution engine and the lock manager though since for a distributed DB, these things would define the system.
In general, use as many existing systems and build on them rather than implementing your own. While the latter approach means that one can learn much more, it also means that some of the "interesting" things won't get as much time and thought as they should.
Research the common use-cases more thoroughly. I think we just scratched the surface of use-cases when it came to distributed query processing and I think that there is a much wider audience for such a system. Exploring this in more detail is something I hope to do in the future.

Interesting problem (string based)

2010-12-16T22:21:00.000-08:00

Find the longest prefix of a string that is a palindrome.
O(n²) is easy, but you need come up with something that's O(n).

Hint: KMP

The psychological effects of a bad API

2010-12-16T12:16:00.000-08:00

It makes everyone sick and your developers lose their creativity and grapple with the API rather than solving interesting problems and innovating.

Anyone can code, but only the fearless can be great

2010-12-16T12:14:00.000-08:00

I personally think that every programming task needs to be approached from the perspective of being completely bug-free. When you write code, think that it is going to be deployed on a rocket or a space-craft and that the lives of a few hundred depend on the robustness of the code. Of course, you can cut yourself some slack by making practical simplifying assumptions about the specific task at hand, but I'd rather programmers started with the strictest requirements and then loosened them rather than the other way around (which seems to be happening more often these days).

Library v/s Framework

2010-12-16T12:13:00.000-08:00

I sort of dislike frameworks (except for the ones that actually make your life easier). Libraries on the other hand are really great things!! Frameworks say: "This is all you are allowed to do and these are the ways you could do it. Additionally, I allow you the freedom of doing this insignificant operation in any way you see fit." On the other hand, libraries say: "If this is the input you feed me, this is the output you shall get. It's up to you to feed me the input and then you are free to do whatever you wish with the output I give you."

This change of mindset makes a world of difference while writing applications that do different things or just things differently from what the "framework" architect thought to be "the" way of doing things.

Django is a GOOD framework. It goes a long way to obviate all the mundane tasks, but at the same time provides a rich library-like interface to many convenience functions. IMHO, the Library way is the functional way where you can compose a complex operation from many small operations chained or composed together. A framework on the other hand reminds me of OO and something like the a template method pattern. Now, I really like the template method pattern when it is used minimally and with care. However, using this pattern for everything you do is just brainless. In the same way, frameworks aren't the solution to all design related problems.

jQuery is an awesome library. It's been true to its slogan of "Write less, do more". It's literally packed with a lot of convenience functions that lets you create really nice looking and functional UIs and web-applications without breaking a sweat. I think it gels in very well with the javascript and DOM eco-system. It doesn't try to be different and OOish (like Dojo) which is where I think it scores.

Frameworks cramp creativity whereas Libraries liberate the artist within the programmer. I hear a lot of people say "tell, don't ask", but I would say "ask and you shall be told."

SQL Query optimization - Part-7

2010-11-16T04:16:00.000-08:00

(The you need referential integrity for more than referential integrity edition)

Why do we tag our blog posts with well, tags, so that people can glean meaningful information from these terse blocks of text. A post tagged with vacation or tutorial says so much about the blog post. Similarly, hinting the DB that a certain column has a similar looking entry in some other table means a lot to the execution planner. Yes, I'm talking about Foreign Key references.

If it finds such a hint, it can infer that:

Every value in this column has some unique value in the column that it refers to.
Since it is pointing to a UNIQUE column, joining a column from this table will match exactly 1 row from the table to which it refers to. Hence, while NATURAL JOINing the 2 tables, the execution engine can stop when it finds one match.
A Foreign Key constraint forces you to make the referenced column UNIQUE. This means that a WHERE clause on that column will never match more than one row and the optimizer can take advantage of that. If such a query occurs as a subquery, then the optimizer can evaluate the sub-query first and replace the sub-query with a single constant which is the result of the inner query's execution.

All these optimizations can significantly reduce your query's execution time.

SQL Query optimization - Part-6 (How NATURAL JOINs work)

2010-11-15T22:23:00.000-08:00

(The devil lies in the details edition)

To show how JOINing in databases works, we'll take up a very simple example and make some simplifying assumptions (which are true) about databases & indexes so that we can reason clearly about certain concepts and yet still understand the key insights required for comprehending how NATURAL JOINs work.

Let's assume that we have 2 tables X & Y that we want to join on a column named 'c'.
SELECT * FROM X JOIN Y ON X.c=Y.c WHERE <condition>

For the sake of simplicity, we shall draw parallels between the tables X & Y and 2 arrays AX & AY that are in-memory. Also let the size of the table X & Y be sA & sY. We shall consider a few cases and try to analyze how JOINing would work in these scenarios:

No index on 'c' in either table: The DB is forced to perform a O(sX.sY) operation by running code that looks like a nested loop. Hence, this type of join is called a nested loop join. This is the most expensive type of join and must be avoided if the tables X & Y are very large.
B-Tree index on 'c' only in table X: (This case is symmetrical to a B-Tree index being present on 'c' only in table Y -- but not really). This case is akin to one of the arrays being sorted and the other being unsorted. Here, the execution engine can loop over the table that doesn't have an index (the unsorted array in our analogy) and for each element, lookup the corresponding value in the table with the index (sorted array lookup using binary search). The cost for joining is O(sX.log sY) or O(sY.log sX). This is why which table has the index is important and the 2 cases aren't exactly symmetrical. It is advisable to have an index on the larger table -- to keep the linear component in the complexity as low as possible.
Hash index on 'c' only in table X: (This case is symmetrical to a Hash index being present on 'c' only in table Y -- but not really). Again, this case is similar to the one above and depending up on whether table X or table Y has an index, the JOIN complexity will be either O(sY) or O(sX) respectively. Again, it is advisable to have an index on the larger table.
Hash index on 'c' in both tables: This case isn't much different from the previous case except for the fact that the execution planner can decide whether to iterate over table X or table Y depending up on which table has a fewer number of rows.
B-Tree index on 'c' in both tables: This is a very interesting and common case and is similar to the problem of trying to find the intersection of 2 sorted arrays AX & AY. It should be clear that the complexity of doing so is O(sX + sY). This bound is NOT tight and may be as low as theta(min(sX, sY)). Hence, it should be clear that some of the join strategies above can (in theory) be faster than this one. However, the execution planner may not always choose to use both indexes if it has heuristic data that suggests that iterating over one of the tables would be much cheaper (say because it contains only 2 rows). This join is most commonly referred to as the Merge Join because it looks like you are merging 2 arrays.

SQL Query optimization - Part-5 (Motivation)

2010-11-15T13:49:00.000-08:00

(The better late than never edition)

I'm sure many of you have worked on web-apps (you know stuff like wikipedia, gmail, facebook, codechef, reddit, digg, duckduckgo or even your personal web-site which has some dymnamic/interactive content). I'm sure that out of these many, many of you have worked on sites that get traffic to the tune of a few hundred visitors per second. I'm sure you know how painstaking it is to run such a site and keep it up and running and responsive for all its users. Lots of things like the web-server, DB, file system, OS, etc... need to be tweaked and tuned and retro-fitted to suit the needs of the things around it.

The one place (in my experience) that can easily introduce bottlenecks is the DB (database). That's because it is something that is a real work-horse and is programmed by you (the application writer), who may not know what food it likes. It's very easy to write a query that runs 10x slower than what it really should be running and not notice this for a very long time.

Imagine the time you get slashdotted and need to support 5000 requests instead of the customary 50 requests/second. Don't you wish your DB doesn't just die due to the load?? Well, if you are one such person who is pedantic about the performance of your database, you are thinking right!

You will mostly learn how to optimize your DB through experimentation, but since others have been burned before, you might as well stay and take advantage of their experiences.

SQL Query optimization - Part-4 (Myths)

2010-11-15T13:17:00.000-08:00

If I have an index on every column of my table, all my queries will run fast. This is the equivalent of saying that adding all the good ingredients in a bowl and mixing away to glory will result in the world's best dish. Doesn't happen. The sooner you snap out of it, the better it is for you.
Joins are expensive. Everything should be completely denormalized. This isn't an SQL optimization myth, just a SQL myth in general. Loosely speaking though, if your joins are all natural joins and the join columns are mostly unique and all your filter conditions are connected with a conjunction (AND clause) and you don't go crazy with GROUP BY, ORDER BY and HAVING, you will have made yourself a pretty fast query. The key to remember is to try and (anyhow) maximize the ratio of Rows returned to Rows visited by the DB engine to produce the result set.
If I have an index on a column that I want to ORDER BY then that index will be used and the DB won't use a temporary table to sort the result set. Not really. If the JOIN is not on the first column that you want to ORDER BY, then the DB will most likely use a temporary table and sort. Having said that, even if you join on a column that you will later ORDER BY, the execution planner might decide to not order intermediate results by that column because it thinks that that would be the most efficient query execution plan. This can happen when exactly one table in the JOIN doesn't have an index on the join column and that will be the column that the DB will decide to iterate over.
Streaming result sets. I really don't know how many DBs actually do this, but it is a killer feature to have. Of course, you need to craft your queries very smartly to take advantage of this.

I you've gotten this far and don't feel lost, you are into this shit big time, and it's time to read some stuff by the big boys (here and here).

SQL Query optimization - Part-3

2010-11-14T12:26:00.000-08:00

Now for some trivial stuff:

Make sure that every column you query on has an (appropriate) INDEX. Creating a full-text index on something that you will do exact matching won't help. Neither will creating a HASH index on a column on which you intend doing < and > comparisons
Avoid complex mathematical expressions in your WHERE clauses if you want indexes to be used. Databases are pretty dumb that way and practice and theory is still some way off in this area (which is why I want to bridge this gap!!). Don't do stuff like: WHERE 2*col1+3 < col2. This will probably NOT be optimized by the execution engine. Of course, if there is no other way out, then you must do it. I suggest you create another column (col3) which always gets the value: 2*col1+3, and query using col3 whenever you need this expression
(This is an ugly condition and probably won't be optimized). Suppose you have 2 columns (col1 & col2) on the same table and want to select all rows WHERE col1 < col2. This will most likely result in a full table scan even if all columns have an index on them. Try to create a new column to flag this condition and select on that column if you need speed. Update: I can definitely see a way in which databases could use an index on (col1, col2) or (col2, col1) (if one exists), but you'll have to check with your particular database if that is the case (by doing an EXPLAIN or its equivalent).

I just noticed

2010-11-14T12:12:00.001-08:00

This has been my most active year of blogging. 36 posts including this one till now. (see the bar on the right). Which probably means that I haven't been working as much this year as compared to the last few years.

SQL Query optimization - Part-2

2010-11-14T12:06:00.000-08:00

Today we'll talk about whether to use JOINs or nested queries. TDDB (my db engine :D) doesn't support nested queries so I don't talk about them much, but that's just selfish of me (actually even MySQL didn't support them for a long time), but I've grown out of that, so here it goes. Nested queries can actually speed up your query by a HUGE amount.

Consider you have say 6 tables which you are joining and only 2 of them are actually involved in any logical reasoning like generating unique rows. The rest of the tables are vestiges of an over-enthusiastic DB architect or a graduate fresh out of college who thinks that everything should be in BCNF (been there; done that).

Now the other 4 tables are being used just to provide data for the purpose of projection and really have no reason being part of the JOIN. Hence, we refactor the query and create a temporary relation from the 2 tables that actually mean something. Most real queries are interested in the top 10 or 20 results only (ordered by some criteria) so we do whatever we want to on the join of these 2 tables.

This temporary relation is then joined with the other 4 relations and viola! This recipe serves 100 queries for the cost of 1 ;)

This is possible since all the extraneous tables have been avoided in the join that involved ordering, grouping and potentially many other expensive operations.

This can be optimized even more by using a materialized view for the inner query. However, that will increase the insertion time for those tables, and should be used with care. Besides, I don't think all DB engines support materialized views.

SQL Query optimization - Part-1

2010-11-14T11:48:00.000-08:00

I'm planning to write some random posts on query optimization. Here's the first one. I'll get straight to the point 'cause I don't like beating about the bush (well not usually), so here it goes.

This post will mainly talk about optimizing queries that use the LIKE keyword.

Try to avoid it if you can. Databases are generally bad at optimizing LIKE queries no matter how good they may be. More often than not, a LIKE query will result in a full-table-scan
If your LIKE query looks something like this: colname LIKE 'something%' then there is some good news for you. You can convert this to colname ≤ 'something' AND colname ≥ 'somethingz' (I'm assuming that colname contains only ASCII text. If it contains unicode, use the last UNICODE character in place of 'z')
No matter how hard you pray, colname LIKE '%something' will NOT be optimized by your favoirite DB engine. You will HAVE to reverse the contents of colname, store them in colname_reversed and query on that as colname_reversed LIKE 'gnihtemos%'
colname LIKE '%something%' is just asking for trouble
And so is stuff like LOWER(colname) = 'something'. This is because anything that transforms the column data can NOT use the index since the index indexes the ORIGINAL value, not the transformed value
If you are using MySQL, the LIKE operator is case-insensitive so you can always replace all statements that look like LOWER(colname) = 'something' with colname LIKE 'something' and it will always work. Silly but useful
To get a more detailed understanding of how indexes work, read up on B-Trees

Undecidable

2010-11-14T11:30:00.000-08:00

Many times have I come across concepts that mimic the concept of an Undecidable problem. So, for all you people who don't know what an Undecidable (or partially decidable -- please pardon the terminoloty) problem is, you can check out the wiki page here or read the layman's definition below:

If a solution to the problem has a "yes" answer then it WILL be found, but if it has a "NO" answer, you'll never know so because you'll keep running the algorithm in the hope of finding the "YES" answer.

Now, it turns out that in the last few months I've come across many instances of such "undecidable" problems. I'll list out a few here:

If you have good marks on a test, you are a good student, but if you don't then it doesn't mean that you are a bad student
If you have lots of fans on your facebook page, then you are famous but if you don't, it doesn't necessarily mean that you aren't

So, the next time I have an argument/discussion with anyone and I mention "this is undecidable", I'll try to give them a link to this post as well.

Why Mongrel2 Rocks

2010-10-29T20:30:00.000-07:00

I used Mongrel2 for my latest project lib-face and it was actually quite a pleasure to work with. Without wasting any more of your time, here are the reasons:

It's fast
It's simple to install and use. Though getting all dependencies is a bit time consuming
It's very well documented
The documentation isn't outdated
I mailed the author asking for some clarifications and got a reply pretty fast. This means that if I get stuck using it, there is someone out there to help me till a community develops
It gives out meaningful error messages that actually help
Writing aync handling code is very very simple because you need to explicitly call a function to return. This means that you can hold on to a request for as long as you want
Mongrel2 uses ZeroMQ as the transport. This means that I can potentially implement some other (non-HTTP) protocol and have my code handle requests for that protocol since it is now only talking to ZeroMQ
It gives out meaningful error messages that actually help
It's simple yet powerful
It supports a lot of languages -- remember it's language agnostic!!

A very fast approach to auto complete (or search suggestions)

2010-09-15T04:29:00.000-07:00

You've seen search engines suggest queries when you begin typing the first few letters of your search string. This is being done by Duck Duck Go as well as Google (to name a few). This is typically done by maintaining a list of past queries and/or important strings that the search engine thinks are worthy of being suggested to a user that is trying to find something similar. These suggestions are effective only if the search engine spits them out very fast since these should show up on the screen before the user has finished typing what he/she wanted to type. Hence the speed with which these suggestions are made is very critical to the usefulness of this feature.

Let us consider a situation (and a possible way of approaching this problem) in which when a user enters the first few letters of a search query, he/she is presented with some suggestions that have as their prefix, the string that the user has typed. Furthermore, these suggestions should be ordered by some score that is associated with each such suggestion.

Approach-1:

Our first attempt at solving this would probably involve keeping the initial list of suggestions sorted in lexicographic order so that a simple binary search can give us the 2 ends of the list of strings that serve as candidate suggestions. These are all the strings that have the user's search query as a prefix. We now need to sort all these candidates by their associated score in non-increasing order and return the first 6 (say). We will always return a very small subset (say 6) of the candidates because it is not feasible to show all candidates since the user's screen is of bounded size and we don't want to overload the user with too many options. The user will get better suggestions as he/she types in more letters into the query input box.

We immediately notice that if the candidate list (for small query prefixes say of length 3) is large (a few thousand), then we will be spending a lot of time sorting these candidates by their associated score. The cost of sorting is O(n log n) since the candidate list may be as large as the original list in the worst case. Hence, this is the total cost of the approch. Apache's solr uses this approach. Even if we keep the scores bound within a certain range and use bucket sort, the cost is still going to be O(n). We should definitely try to do better than this.

Approach-2:

One way of speeding things up is to use a Trie and store (pointers or references to) the top 6 suggestions at or below that node in the node itself. This idea is mentioned here. This results in O(m) query time, where m is the length of the prefix (or user's search query).

However, this results in too much wasted space because:

Tries are wasteful of space and
You need to store (pointers or references to) 6 suggestions at each node which results in a lot of redundancy of data

We can mitigate (1) by using Radix(or Patricia) Trees instead of Tries.

Approach-3:

There are also other approaches to auto-completion such as prefix expansion that are using by systems such as redis. However, these approaches use up memory proportional to the square of the size of each suggestion (string). The easy way to get around this is to store all the suggestions as a linear string (buffer) and represent each suggestion as an (index,offset) pair into that buffer. For example, suppose you have the strings:

hello world
hell breaks lose
whiteboard
blackboard

Then your buffer would look like this:
hello worldhell breaks losewhiteboardblackboard
And the 4 strings are actually represented as:
(0,11), (11,16), (27,10), (37,10)

Similarly, each prefix of the suggestion "whiteboard" is:

w => (27,1)
wh => (27,2)
whi => (27,3)
whit => (27,4)
white => (27,5)
whiteb => (27,6)
and so on...

Approach-4:

We can do better by using Segment (or Interval) Trees. The idea is to keep the suggestions sorted (as in approach-1), but have an additional data structure called a Segment Tree which allows us to perform range searches very quickly. You can query a range of elements in Segment Tree very efficiently. Typically queries such as min, max, sum, etc... on ranges in a segment tree can be answered in O(log n) where n is the number of leaf nodes in the Segment Tree. So, once we have the 2 ends of the candidate list, we perform a range search to get the element with the highest score in the list of candidates. Once we get this node, we insert this range (with the maximum score in that range as the key) into the priority queue. The top element in the queue is popped and split at the location where the element with the highest score occurs and the scores for the 2 resulting ranges are computed and pushed back into the priority queue. This continues till we have popped 6 elements from the priority queue. It is easy to see that we will have never considered more than 2k ranges (here k = 6).

Hence, the complexity of the whole process is the sum of:

The complexity for the range calculation: O(log n) (omitting prefix match cost) and
The complexity for a range search on a Segment Tree performed 2k times: O(2k log n) (since the candidate list can be at most 'n' in length)

Giving a total complexity of:
O(log n) + O(2k log n)
which is: O(k log n)

Update (29^th October, 2010): I have implemented the approach described above in the form of a stand-alone auto-complete server using Pyhton and Mongrel2. You can download it from here.

Some links I found online:
LingPipe - Text Processing and Computationsal Linguistics Tool Kit
What is the best open source solution for implementing fast auto-complete?
Suggest Trees (SourceForge): Though these look promising, treaps in practice can degenerate into a linear list.
Autocomplete Data Structures
Why is the autocomplete for Quora so fast?
Autocomplete at Wikipedia
How to implement a simple auto-complete functionality? (Stack Overflow)
Auto Compete Server (google code)
Three Autocomplete implementations compared
Trie Data Structure for Autocomplete?
What is the best autocomplete/suggest algorithm,datastructure [C++/C] (Stack Overflow)
Efficient auto-complete with a ternary search tree

What you've always wanted to know about GRE preparation

2010-08-18T21:31:00.000-07:00

When I was preparing for the General GRE, it was a completely mad rush, with me having to ask anyone and everyone for help and advice. So, the conglomeration of all that information is what guided me throughout. Today, I am going to put that all down (combined with my own experiences) so that others don't have to grapple with the same questions and uncertainties and can really concentrate on studying for the exam.

Don't fall into the trap of not booking a date!! You will find it hard to study if you haven't booked a date
Book a date sufficiently into the future (say 2-3 months) and work towards it as if the date can not be postponed. I've seen many people postpone the date just because they can. Don't fall into that trap
I used the Barron's book for everything
Don't take the quant section lightly. Even though it is easy, it is time critical and there are many trick questions
Even though the word list will seem daunting at first, keep at at and try to do as much of it as you can. I must have landed up knowing close to 3000 (out of the 3500) words in the Barron's word list
Attack the High Frequency Words first (about 350). Make sure you use the list from both Barron and Kaplan. This file contains all such words and words that I found hard. Use the Barron's and Kaplan's list from here and make you own list of "hard" words (everyone will find a different set hard)
Then do the words list-by-list. There are about 50 word lists in the Barron's book. Each word list can take you anywhere from 1 to 3 hours to do if you are doing it the first time. Towards the end, you should be able to do all the word lists in 2-3 days (assuming 5-6 working hours each day)
Solve as many exercise problems in the Barron's book as you can in the quant section
For quant practice, use The Nova GRE prep. book. The quant in this book is easier than what you will get in the GRE, so use this as your first round of preparation
Take the 5 sample tests given at the end of the Barron's book. They are very close to the actual GRE test in terms of difficulty
The Kaplan tests too are of GRE difficulty level (I would say a tiny bit more difficult, but that shouldn't be something you should factor in). The 6 practice exercises in Kaplan are way too easy (for quant) and the 30 min you get to solve them is sufficient. The quant in the 3 sample tests is harder and is of GRE difficulty level
POWERPREP (the official GRE prep. software) is something you must do before the test. They give you 2 sample tests. Take them 1-3 days before the real test when you are sudo prepared for the test. These will give you a great indicator of what score you might land up getting. If you do badly in some section, try to spruce up your act in that section. The drawback of taking it so late (just before the test) is that you don't give yourself enough time to rectify your weak areas. However, I wouldn't want anyone to "waste" these tests before they are fully prepared for the simple reason that these tests are really good indicators of how much you might land up getting
None of the other tests I took were of the GRE difficulty level, so make sure that you take all of the tests above before you take the GRE
On the day of the test, make sure you arrive at the test center on time and have all the required documents
That's about it and all the best!!

How things go wrong (reprise)

2010-08-11T14:16:00.000-07:00

About 3 years ago, I wrote a post on How things go wrong. I should have made everyone I know read it since we just ran into an issue that bit us in the ass... Yes, it was caused as a result of:

Lack of return value checking from system calls and
Lack of sufficient error checking/handling code

and further complicated by a lack of logging in the application.

I can't begin saying how important each of them are. Oh well, I only have 2 things to say:

You need to learn for yourself
You can never be too careful
You can't learn from other's mistakes (yes, this and the 1^st one are the same thing)

Using Titanium Desktop to test web sites

2010-08-05T22:18:00.000-07:00

I have been using Titanium Desktop for a while now at work, and am not at all impressed with the implementation or stability of the product and wouldn't want to see it being used in any serious project. HOWEVER, it is a brilliant concept which if done well can be humongously successful.

I was faced with the daunting task of testing a web-site written in Drupal the other day. Now, I don't know Drupal but have been told that its got these magic form elements which it used for validation. That couples with cookies meant that I would have to do a lot of work to test even slightly complex flows using python/perl/ruby::Mechanize. That apart, I can NEVER simulate the javascript and other asset loads that a normal user would exercise. For complete end-to-end-testing, I couldn't find anything that I would like using.

Here is where Titanium comes in. It doesn't have the sandboxing rules that normal browsers have, so you can load pretty much any page in a Titanium IFrame and do pretty much anything you want with it!!!!

I have given here an example of using Titanium to search for some text on Duck Duck Go.

To run the example, start Titanium Desktop as kboot --query "Your Search String"

Enjoy!!

Update: Here is a video showing how the automation works.

Aaloo, mutter and tamater sabzi

2010-07-03T22:51:00.000-07:00

This is the recipe for my current favourite vegetable. Translated to english, it means Potato, peas and tomatoes. (makes sabzi to serve 4). Dedicated to my mom since she makes this dish in the most awesome way I have ever tasted it to be and to sandy since he is going to learn it this time ;)

Ingredients:

Medium sized aaloo(potatoes); boiled:	about 3 nos
Fresh green peas:	about 100g
Medium sized tomates:	about 4 nos.
Clarified Butter (Ghee):	1 Tbsp
Hing (asafoetida):	¹/₂ tsp
Cumin seeds (jeera):	1 ¹/₂ tsp
Turmeric (haldi):	¹/₄ tsp
Salt (namak):	to taste
Red chilli powder (this is mainly used for the red color):	¹/₄ tsp (or to taste)
Fresh green chilli (cut and seeded):	¹/₂ nos.
Dhania and jeera powder:	1 tsp
Fresh corriander leaves:	(to garnish)

Procedure:

You need not skin the boiled potatoes. Just cut it into about ¹/₂" X ¹/₂" cubes
Heat the ghee and when it is hot, add the hing, jeera and green chilli to it. When the jeera starts popping, and water to it
Add peas to the water, and boil them till they are soft
Now, cut the tomatoes (unskinned) into small pieces and add it to the boiling water and peas. Keep boiling till the tomatoes have softened
Now, add the cut potatoes into the mixture and add red chilli powder, dhania and jeera powder, turmeric and salt
Boil for about 2 more minutes till the potatoes have soaked the gravy
Garnish with fresh corriander leaves and cover or serve

Actions speak...

2010-06-28T10:42:00.003-07:00

... louder than words

Guess what?

2010-06-24T10:06:00.000-07:00

            _________
            |*      |
            |       |
    (------------   |-------)
    (               |       )
    (       |--------       )
    (       |               )
     -------|   ------------
            |       |
            |      *|
            ---------

Or this (if you are having a problem with the one above ;))
            _________
            I *     |
            I       |
    (------------   |-------)
    (               |       )
    (       |--------       )
    (       |               )
     -------|   ------------
            |       I
            |       I
            |_____*_I

+5 to the first one who guesses correctly

Murphy's Law (for Python programmers)

2010-06-24T02:20:00.000-07:00

Download it here
Please rename the file to murphy.py and from your interpreter:
import murphy

YASNOSC

2010-06-23T22:12:00.000-07:00

Yet another SQL and NoSQL comparison

Scalability != NoSQL

Performance != NoSQL [not always]

Scalability == Good schema design

Performance == Good schema design

But...

Performance != Scalability

Scalability != Performance

(but we should also note that NoSQL isn't NOt SQL, but Not Only SQL)

A new water pump for our washing machine

2010-06-22T09:11:00.000-07:00

(This blog post has the potential to be discursive and go in no particular direction, so I'll try my best to remain as unwavering as I can)

It all started off when our washing machine konked off and decided to stop working. My grandma sent it off to the repairers who fixed it and then had the brilliant idea to suggest attaching a water pump so that water from the tank above would flow in much faster. Now, anyone who has played with a syringe would know that no matter how hard you push (or pull), you just can NOT for the love of anything (or anyone) get more than a certain amount of liquid through the syringe (or in this case the pipe).

Now, our pipes are really old and are rusting from the inside. This is the reason that the flow of water has gone down as compared to the time when they were first installed. Even though I suggested getting the pipes changed due to the above mentioned reason (since that is the real problem, my grandma would hear nothing from me... Oh well... so be it...)

The brilliant engineer's suggestion came as a massive shock to me and it almost felt funny. Anyways, the pump has been installed and guess what... The flow of water in the pipe is still the same!! I wonder how that happened. Isn't the pump working (scratch head, etc...)

The rate of flow of water in a pipe depends upon many things. One of them being the inner diameter of the pipe and another being the friction offered by the sides of the pipe. I don't know the exactly formula, but I am guessing it is easy to come by. The pressure exerted by the water in the tank is more than sufficient to max. out the flow rate in the pipe and I would have guessed those engineers to know that. I guess it's back to the drawing board for them ;)

How to write bug-free code

2010-06-11T05:36:00.000-07:00

Listen hard and listen fast. Listen once; I won't repeat myself...

While writing code, if you ever say to yourself:

Oh! but this will hardly ever happen OR

The user will never do this OR

What are the odds of this happening??

Please please please go ahead and write some code and comments to handle that situation. You can't ever be too careful.

Signing off,
Captain S.K.Eptic

Python generators and the dict.items() function

2010-06-01T22:21:00.001-07:00

During the course of yesterday's session, there was an example of iterating over a dictionary(dict) in python. The code looks something like this:


d = {
     "name": "chuck norris",
     "age": "positive infinity",
}
for k,v in d.items():
    print "Key: " + str(k) + ", Value: " + str(v)

The d.items() function returns a list which will take up a non-trivial amount of memory for large dicts that we wish to iterate over. For simplicity's sake if we assume that each pointer takes up 8 bytes and the python tuple type takes up 32 bytes(say) and there are 1 million(10⁶) entities in the dict(d), then we land up with 10⁶ x 56 (Two 8 byte pointers, each to each the key and the value objects, 8 for a pointer to the tuple and 32 for the tuple object itself) which is about 56MB of memory used for just iterating over the dictionary.

If however, we use generators, then we can save all that memory.
However, you can directly print the result of d.items(). Printing a generator object doesn't do anything spectacular, so we will need to create a proxy object to print the result of generation if string coercion is requested. The code for doing so is shown below. Notice that we use the .keys() function within our custom generator. We won't need to use it if we really were the dict object and had handles to the internal variables.


d = {
     "name": "chuck norris",
     "age": "positive infinity",
}

def dict_items(d):
    """
    Returns an object which can be iterated over in a for loop
    as well as printed. This is achieved by returning an object
    which is both iterable as well as convertible to a string.
    However, iteration involves using a generator for fetching
    the next value in the sequence
    """
    def dict_generator():
        dkeys = d.keys()
        for k in dkeys:
            yield (k, d[k])
    dg = dict_generator()

    def dgen_to_str():
        return str(d.items())

    class Dummy(object):
        def __getattr__(self, attr):
            return getattr(dg, attr)
        def __str__(self):
            return dgen_to_str()
        def __iter__(self):
            return dg

    proxy = Dummy()
    return proxy

diter = dict_items(d)
print diter

for k,v in diter:
    print "Key: " + str(k) + ", Value: " + str(v)

However, the major difference comes when you try to do something like this:


for k,v in d.items():
    d.clear()
    print "Key: " + str(k) + ", Value: " + str(v)

The code above will work as expected and print all the elements of the dict(d)


for k,v in diter:
    d.clear()
    print "Key: " + str(k) + ", Value: " + str(v)

However, the code above will throw an exception since our generator caches all the keys and dereferences the dict(d) to get the value for the corresponding key.

So, applications that mutate the dict while iterating over it won't quite work as expected.

Python Interest Group(PIG) Act-1; Scene-1

2010-06-01T21:26:00.000-07:00

We had the first session of the python interest group(affectively called PIG) at Directi yesterday (1st June, 2010).

Here are the links to the presentation in:

.odp(open office)

.ppt(excel) format

along with the code snippets in a .zip archive

You will need python 2.5 to run the sample programs.
The documentation for python 2.5 is available here

Happy Hacking!!

5 months of salad... and counting...

2010-06-01T21:16:00.000-07:00

I started having salad for lunch daily sometime early January, 2010. Since then, it's been fairly smooth sailing and I've added a few ingredients to the mix.

A lot of people have asked me if I got bored of the monotony of salad, but I highly disagree with them all. The deal with salad is that you get so many flavours in every bit that it's really hard to get bored of it. Besides, it's fairly juicy and crunchy that you enjoy having it -- really!!

Either ways, I have added a few extra ingredients over the months, so would like to share those with the very few and faithful readers of this blog.

Hazelnuts (halves)

Cashews (halves)

Pomegranates (in season)

Dates

Dried Anjeer (figs)

I've pretty much knocked off the mixed herbs in the dressing and just stick to Olive Oil and Honey

The baby corn is fresh baby corn, which needs to be stripped off it's covering; like you would for normal corn. The baby corn which results is really so sweet that you can eat it as-is!!

Enjoy your salad people!!

Can't come to terms with inheritance

2010-05-31T11:23:00.000-07:00

I've been racking my brains over inheritance for a while now, but am still not completely able to get around it.

For example, the other day I was thinking about relating an Infallible Human and a Fallible Human. Let's first define the two:

Infallible Human: A human that can never make a mistake. It's do_task() method will never throw an exception

Fallible Human: A human that will occasionally make a mistakes. It's do_task() method may occasionally throw a ErrorProcessingRequest Exception

The question was:
IS an infallible human A fallible human OR IS a fallible human AN infallible human?

The very nice answer I received was in the form of a question (I love these since it gives me rules to answer future questions I may have).

"Can you pass an infallible human where a fallible human is expected OR can you pass a fallible human where an infallible human is expected?"

It seems apparent that you can pass an infallible human where a fallible human is expected, but not the other way around. I guess that answered my question.

However, it still feels funny saying "An infallible human is a fallible human". Does anyone else feel queasy when they say it? It almost feels as if speaking out inheritance trees is like reading out statements from propositional calculus in plain English (the if/then implication connectives don't mean the same as that in spoken English). Does anyone else feel the same?

update: This thread on stackoverflow discusses the same issue.

A few rules to live by

2010-05-29T22:11:00.000-07:00

you can only lie to others, never to yourself
don't hurt others -- it will only come back to you
you can justify anything -- we all can -- but don't try too hard. you might end up lying
python rocks
java bites shite
java has resulted in more deaths and cases of insanity than road accidents world-wide
the average lifespan of a java programmer is 10 years less than that of a python programmer and 7 years less than the average for a human
what can kill chuck norris -- programming in java
listen to music you like -- don't pretend
eat food you like -- don't pretend
wear what you like (if you want to wear anything that is) -- don't pretend
criticize -- don't be diplomatic when you don't need to
praise -- it spreads good vibes -- but don't praise falsely -- it doesn't help at all
music will set you free ;)
do what you want to, not what you have to or need to -- sometimes you may "need/have" to do the things though; but don't stretch it too much
listen to "sunscreen" if you haven't yet
don't recommend it to others because it's "cool", but because you think it's worth doing
don't do anything "just" because it's "cool"
don't not to anything just because it's not cool
the arts are purgative and cathartic; write, act, sing, cook, code... anything is art and art is everything...
you may need to twist your finger to get the fat out(transated from a hindi proverb); but do it only if it's absolutely necessary
talk is cheap; actions are not
neither is code
show me the code you piece of shite

We aren't responsible

2010-05-22T06:55:00.000-07:00

I was reading the paper and The Mumbai Mirror's headlines a few days ago went something like this "Criminal Negligence Leaves WR Commuter Critical". The article was with reference to a commuter who had been injured by a plank that fell on him because of negligence on part of the workers working at Churchgate station. This injury unfortunately has left him comatose and he is currently in a critical state in hospital. I wish him a speedy recovery.

Coming from a software centric world where EULAs and licenses accompany any piece of code that is shipped, it seems only natural that no one is really responsible for anything that they do and that any action on their behalf may have negative influences on others. Others need to watch out for anything that may hurt or otherwise injure them. It is the user's and only the user's sole responsibility to ensure his/her fitness and properiety and the user must account for anything that may go wrong during the course of using the product/software mentioned.

I have yet to see any license that says that they take sole responsibility for their product and that they could be held responsible for any damage arising due to negligence on their behalf. The closest I have come to it is Knuth's exponentially increasing reward for finding bugs in TeX. As far as free software is concerned, we shouldn't expect it. However in case we are paying for the software, shouldn't we demand it? I mean we are literally shelling out hard cash for that piece of code. We seem to have a right to want it to be bug-free...

Either ways, it seems no one wants to take responsibility for their code, so why not make it a de-facto standard. Instead, if someone out there is willing to say that they will take responsibility for screw ups (of any) then they should include it in the license agreement.

It starts off with software saying that it may not work well and ends up at coffee cups and hot dogs saying that their contents may be too hot for consumption.

What next? From what I see, there may now be notices on every pavement saying that people should walk on it on their own risk. Each lift will say that it could crash any minute and if it does; even due to any manufacturing defect or installation glitch, then company providing it should not be held responsible. Airplane and trains will warn travelers before they enter saying "Please account for the fact that you may not make it if you step in". Books may say "Read at your own peril. Your eyes may gouge out while reading this book, but don't blame us!!". When will all this end???

Events: How to use them to your advantage

2010-05-15T07:33:00.000-07:00

A very interesting conversation between a colleague and me resulted in some equally interesting learnings as far as I was concerned.

The topic of discussion was about whether certain functionality in a software should be implemented via events or via function calls directly to the concerned component. More concretely, should the coupling be via events as in a pubsub based system or should it be via known function end-points on specific objects.

If the event based approach is used, there is lose coupling, and the coupling is on events. Using the other approach, there is strong coupling and one component needs to know about the interfaces of the other component.

Let's take a toy example to analyze this situation.

Consider an interior stylist that is developing an integrated home theatre system. Say there are multiple components involved:
1. Speaker system
2. Television
3. CD player
4. Satellite system

For all practical purposes, users should not need to turn on each of the separate components separately (as they do today). They need not even know what the individual constituents of the system are. For that purpose, having a separate button that turns on the Television, one that turns on the speakers and one that controls the CD player seem overkill. Just the press of a single "start CD" button should do the needful.

Let's discuss various ways in which we can achieve the desired effect:

Strongly couple all the components together so that starting the CD player also triggers the TV and the speaker system.

What happens if the satellite system is turned on? It must also turn on the TV and speaker system. Tomorrow if there is a new device "USB photo viewer" that needs to use the display that the Television provides, it will also need to do the needful.

This method seems to waste a lot of developer time and seems to be prone to errors. What if someone forgets to turn on the TV? Also each component needs to handle the case of when the TV/speaker is already on, etc...

The CD player will work only with that TV set and speaker system that speaks a language that it understands (tied to an interface). Vendors will try to tie users to their interface in the hope of selling them all the components.
Instead, if we just decouple all the system and couple them on events, things become much clearer and easier to work with.

The "button.enterteinment.cdplayer", "button.enterteinment.satellite" and "button.enterteinment.usbdevice" events should be listened to by each of the components and they should react accordingly.

Another thing to remember is how to name the events. We should NOT name events as "start.enterteinment.cdplayer". That sounds very imperative. Naming plays a very important role in how the rest of our system is built around these events. Wrongly named events can cause a lot of confusion and screw up the system even more than what you thought capable of doing!!! Event names should be suggestive of "something happening" and not of "something being asked for".

Accordingly, events should not be named "do-this" and "do-that". Instead, prefer names like "this-happened" and "that-happened" so that listeners can react to these events in the way they deem most fit.

By naming events imperatively, we immediately constrict their use cases to what we think they should be; defeating the original purposes of using events -- which is to free event raisers from thinking of what is to be done in reaction to a raised event.

One line to teach you Object Oriented Programming (OOP)

2010-05-09T21:47:00.000-07:00

"When modeling objects, model behaviour, not attributes"
Courtesy: Ramki

Probably the hottest summer I've seen in Mumbai

2010-05-09T11:34:00.000-07:00

This is by far the hottest and stickiest summer I have seen in Mumbai since my stint on this planet.

Protocol Buffers v/s HTTP

2010-05-02T11:10:00.000-07:00

I was discussing serialization costs with my immediate superior, Ramki when one thing lead to another and I landed up wanting to compare the serialization and deserialization costs of protocol buffers (a binary format) to those of HTTP (a text based protocol) in python.

After performing some tests (in python), I observed that protobuf was taking almost 4 times the amount of time to deserialize data as compared to the simplistic HTTP based header parsing. Of course, these 2 are meant for different purposes and Ramki mentioned that a fixed format protocol would save data on the wire since the attribute names (header names in HTTP) need not be sent on the wire; just the values (header values in HTTP) are sufficient.

Also a binary protocol should be much faster as far as serialization and deserialization is concerned, but we found out that python's pack and unpack are a bit slow OR it is blazingly fast at doing string operations.

Here is a representative output from one such run of the program below:


ramki serialization time: 0.125000 seconds
ramki deserialization time: 0.156000 seconds
protobuf serialization time: 0.453000 seconds
protobuf deserialization time: 0.453000 seconds
http serialization time: 0.047000 seconds
http deserialization time: 0.125000 seconds

The code:


import sys
import message_pb2
import time
import struct

def multi_serialize(o, n):
    fragments = []
    for i in xrange(0, n):
        data = o.SerializeToString()
        fragments.append("%d\r\n" % len(data))
        fragments.append(data)
    return "".join(fragments)

def multi_parse(input, n):
    il = len(input)
    start = 0
    objects = []
    for i in xrange(0, n):
        rnPos = input.find("\r\n", start)
        if rnPos == -1:
            print "Premature end of input. Terminating..."
            return None
        lenStr = input[start:rnPos]
        start = rnPos + 2
        lenInt = int(lenStr)
        # Read off lenInt bytes off the stream
        data = input[start:start + lenInt]
        start += lenInt
        obj = message_pb2.Header()
        obj.ParseFromString(data)
        objects.append(obj)
    return objects


def http_header_create(request, headers):
    line1 = "GET %s HTTP/1.1" % request
    hLines = [line1]
    for k,v in headers.items():
        hLines.append(k + ": " + v)
    return "\r\n".join(hLines) + "\r\n\r\n"

def http_header_parse(input):
    parts = input.split("\r\n")
    line1 = tuple(parts[0].split())
    headers = { }
    for i in xrange(1, len(parts)):
        h = parts[i].split(": ")
        if len(h) == 2:
            k,v = h
            headers[k] = v
    return (line1, headers)

def http_multi_serialize(request, headers, n):
    fragments = []
    for i in xrange(0, n):
        fragments.append(http_header_create(request, headers))
    return "".join(fragments)

def http_multi_parse(input, n):
    il = len(input)
    start = 0
    objects = []
    for i in xrange(0, n):
        delimPos = input.find("\r\n\r\n", start)
        if delimPos == -1:
            print "Premature end of input. Terminating..."
            return None
        headerString = input[start:delimPos]
        headerObject = http_header_parse(headerString)
        objects.append(headerObject)
        start = delimPos + 4
    return objects

def ramki_serialize(obj):
    totalLength = 0
    attrs = [ ]
    for k,v in obj.__dict__.items():
        totalLength += (2 + len(v))
        attr = struct.pack("H", len(v)) + v
        attrs.append(attr)
    attrs.insert(0, struct.pack("H", totalLength))
    return "".join(attrs)

class RamkiDummy(object):
    pass

shortStruct = struct.Struct("H")

def ramki_deserialize(input):
    # For now, we lose attribute names
    d = RamkiDummy()
    packetLength = shortStruct.unpack(input[0:2])[0]
    s = 2
    ctr = 0
    while s < packetLength+2:
        # print "CTR: " + str(ctr)
        attrLength = shortStruct.unpack(input[s:s+2])[0]
        s += 2
        # Read attrLength bytes of data
        attrValue = input[s:s+attrLength]
        s += attrLength
        setattr(d, "attr" + str(ctr), attrValue)
        ctr += 1

    return d

def ramki_multi_serialize(obj, n):
    stream = []
    for i in xrange(0, n):
        stream.append(ramki_serialize(obj))
    return "".join(stream)

def ramki_multi_deserialize(input, n):
    objects = []
    s = 0
    for i in xrange(0, n):
        objectLength = shortStruct.unpack(input[s:s+2])[0] + 2
        obj = ramki_deserialize(input[s:s+objectLength])
        s += objectLength
        objects.append(obj)
    return objects

def main():

    class Dummy(object):
        pass

    d = Dummy()
    d.request = "GET"
    d.resource = "/user/ramki/getVcard/"
    d.version = "1.1"
    d.destination = "localhost:8080"
    d.custom1 = "434552"
    d.custom2 = "no"

    s = time.time()
    input = ramki_multi_serialize(d, 10000)
    print "ramki serialization time: %f seconds" % (time.time() - s)

    s = time.time()
    ramki_multi_deserialize(input, 10000)
    print "ramki deserialization time: %f seconds" % (time.time() - s)

    h = message_pb2.Header()
    h.request = "GET"
    h.resource = "/user/ramki/getVcard/"
    h.version = "1.1"
    h.destination = "localhost:8080"
    h.custom1 = "434552"
    h.custom2 = "no"

    s = time.time()
    stream = multi_serialize(h, 10000)
    print "protobuf serialization time: %f seconds" % (time.time() - s)

    s = time.time()
    objs = multi_parse(stream, 10000)
    print "protobuf deserialization time: %f seconds" % (time.time() - s)

    hh = { "Host": "localhost",
           "X-MessageID": "33",
           "X-ACKMessage": "100",
    }

    s = time.time()
    stream = http_multi_serialize("/user/ramki/getVcard/", hh, 10000)
    print "http serialization time: %f seconds" % (time.time() - s)

    s = time.time()
    objs = http_multi_parse(stream, 10000)
    print "http deserialization time: %f seconds" % (time.time() - s)

    return 0

sys.exit(main())

This page claims that protobuff deserialization time is 3478ns whereas I am seeing a time of 4530ns which is expected since we are running on different hardware.

From: here, it seems as it protobuf is good at packing ints but not strings.

In fact, none of the deserialization times even come close to the 1250ns that I see for http parsing. This is mainly because those methods do type conversion which HTTP is not doing.
If that is introduced into the mix, I guess those costs will add up too. However, the application that I want it for doesn't really need it, and there will be many applications that don't.

In the link above, many of the methods, serialization takes more time than deserialization which is slightly curious.

Inheritance and extension

2010-04-22T21:59:00.000-07:00

I have been stumped by this issue for a while, so I decided to write about it.

Say you have an element container called SimpleList which exposes the following methods(apart from others of course):
1. add(element): Adds 'element' to the SimpleList
2. addAll(elements): Adds 'elements' to the SimpleList

These methods are extensible(can be overriden and hence extended).

They are implemented as follows in SimpleList.


# Contract: Will add 'element' to SimpleList or throw an 
# exception in case of an error.
method add(element)
  # Adds element to the underlying data store/array

# Contract: Will add 'elements' to SimpleList or throw an 
# exception in case of an error. This method may throw an 
# exception after adding 'some' of the elements from 'elements'.
method addAll(elements)
  for element in elements
    this.add(element)

Fair enough till now.

Up comes someone who decides they can do better and they extend SimpleList and create ABetterSimpleList!!

They are implemented as follows in ABetterSimpleList.


# Contract: Will add 'element' to ABetterSimpleList or throw 
# an exception in case of an error.
method add(element)
  # Adds element to an underlying cache since SimpleList 
  # may take a while to add() this element.
  if cache.size() > 20:
    this.addAdd(cache)
    cache.clear()

# Contract: Will add 'elements' to ABetterSimpleList or throw 
# an exception in case of an error. This method may throw an 
# exception after adding 'some' of the elements from 'elements'.
method addAll(elements)
  # Just call the base class' addAll method

All contracts have been satisfied, but can you spot the subtle bug?

Yes, there is an infinite recursion here!! Calling add() on ABetterSimpleList will add elements to the cache till the cache grows to 20 elements in length. Once that happens, it will call addAll() which will call the base class' addAll() which will call (what it thinks is) it's add() function, except that it had been overridden by us to call addAll()!!

Well, how do you solve this?? I don't have a concrete answer myself, but just scratching the surface has lead me to believe that there are 2 type of class extensions:
1. Extending for the base class (I call this framework extension)
2. Extending for users/subclasses (I call this normal extension)

In case [1], it is expected that the base class will consume your interfaces so you program for the base class. However, in case [2], your consumers are externals and not internals like your base class. Hence, you should now program for them.

An important side effect of this is that classes that are meant to be consumed by subclasses (case [2]) should NOT use their own overridable methods in their own implementation or else they CAN NOT give any guarantees to their consumers (subclasses in this case). However, framework extended classes (case [1]) SHOULD use their own public interfaces since that IS the purpose of them allowing method overriding on those interfaces. They are expected to be the consumers of their subclass' funtionality.

Examples of each type of class:
1. Framework Extension: Java's Runnable, C++'s streambuf
2. Normal Extension: Java's LinkedList, AbstractList. Typically anything that is layered falls into this category

Patterns for Concurrent, Parallel, and Distributed Systems

2010-04-22T21:54:00.000-07:00

I happened to chance up on this great site which describes Patterns for Concurrent, Parallel, and Distributed Systems.

I landed up here searching for the proactor and reactor patterns, both of which are described very well.

http://www.cs.wustl.edu/~schmidt/patterns-ace.html

An experiment with carbs

2010-02-02T20:32:00.000-08:00

About a month ago, Appu, Abbas and myself met and Appu happened to mention that an increased intake of carbs. generally lent itself to hunger pangs if one did not eat for a while.
For the last month, I've been having only salad for lunch, and daal, vegetables and chapati(3 nos.) for dinner and have also been limiting my carb. intake by way of reducing the amount of sugar I add to my hot beverages.
However, yesterday I had 4 liquor chocolates (which Devdas had so generously brought back from New Zealand), 5 milk pedhas (courtesy Jaineev) and 2 Kaju Katris (courtesy Mukesh), which considerably increased my carb intake for that day. Furthermore, I had 5 chapatis and extra helpings of other stuff yesterday for dinner. I don't know if it had any direct link to the carb. intake, but I will be monitoring this more closely now.

Moments

2010-02-02T00:19:00.000-08:00

I visited Sandeep in Bangalore when I had gone for the Agile 2010 conference in Jan 2010. Good times followed ;)

Neela Aasmaan Soo Gaya

Tere Khushboo Mein Basee Khat

Jhuki Jhuki See Nazaar

Mainee Tere Liye Hii Saat Rang Kee (Part-1)

Mainee Tere Liye Hii Saat Rang Kee (Part-2)

Vanilla Milk using natural vanilla extract

2010-02-01T22:57:00.000-08:00

I started making vanilla extract in July 2009 using adaptations of the innumerable recipes available online. It's now been 7 months since I started so I decided to try out the extract for making vanilla milk (which btw I absolutely love and up to this point made using pulverized vanilla beans).

Attempt-1: Measure about 1 cup (approx. 200 ml) of milk in a glass, pour it in a vessel and heat. Add 1/2 tsp vanilla extract to the glass (which has traces of cool milk). The last bit caused the trace amounts of milk in the glass to curdle. However, pouring the heated milk and sugar in the glass did not curdle the rest of it. The whole drink smelt of alcohol though.

Attempt-2: This time, I decided to not leave trace amounts of milk before adding the extract to the glass. Again however, I did get some smell of alcohol.

Attempt-3: This time, I decided to do some research online and figure out if anyone else is facing the problem of an alcoholic smell in their extract. As it turns out, it is expected to be this way for a real extract!! (feature, not a bug ;) ). I also happened to read that adding sugar reduces the alcoholic smell, and that when this extract is used in cooking, most of the alcohol will in fact evaporate and hence not leave behind that alcoholic smell. So, this time, I added some sugar to the glass before adding the vanilla extract, and after pouring in the hot milk, I stirred for about 4-5 minutes before consuming the drink. Viola!! No smell now!!

Another nice link explaining a lot of things.

Eggless Brownies Recipe

2010-01-29T12:37:00.000-08:00

Makes 1kg Eggless Brownies

Ingredients:

Flour (sifted):	195g
Dark Chocolate:	160g
Fat (Butter + Oil)	120g (80g + 40g)
Water:	255ml
Cocoa powder:	2-3tsp
Sugar (castor or powder sugar):	2 cups
Salt (if not using salter butter):	1/2 tsp
Vanilla extract/essence:	1 ¹/₂ - 1 ⁴/₅ tsp
Baking powder:	1 ¹/₅ tsp(for guey brownies) - 1 ¹/₂ tsp(for cakey/fluffy brownies)
Chopped walnuts:	40g

Procedure:

Grease and dust an 8" X 9" pan (basically 72 square inches in area), and pre-heat the oven to 180 degree celcius.

Heat the water on a low flame till it is warm/mildly hot and add to it ¹/₃^rd of the flour (65g). Do not remove the utensil from the flame, and continue stirring till the mixture thickens.

Add the oil to the chocolate and melt the chocolate either in a microwave oven or on a double boiler.

For making cakey(not guey) brownies, mix the sugar with the butter and whisk/beat till the mixture is light and fluffy. For making guey brownies, just mix the sugar with the flour and water mixture you just made.

Mix the baking powder, cocoa powder and salt (if using unsalted butter) with the rest of the flour and sift it again a couple of times to mix them uniformly well.

Add the vanilla extract with the flour and water mixture and mix it well.

Now, mix all the portions that you have with each other and add the walnuts to this mixture. Make sure you mix it well. Perform this step quickly and briskly so that the baking powder doesn't wear out by the time you start baking it.

Transfer the contents to the greaded and dusted pan, and bake in the oven for 45-55 minutes (or till you think it is done).

Remove frm over and wait for it to cool a bit (about 30-45 minutes), cut into pieces and enjoy!!

One week of salad

2010-01-16T23:35:00.000-08:00

I started having salad last week for lunch every day, and it's going pretty well as of now. Bought supplies for the next week today.

Ingredients:

Iceberg lettuce

Lettuce

Purple/Green cabbage

Brocolli

Red/Green/Yellow Capsicum

Tomatoes

Cherry Tomatoes

Baby corn

Fresh Green Peas

Finely chopped carrots

Green/Black Olives

Soaked and sprouted moong and moth

Extra Virgin olive Oil (for the dressing)

Honey (for the dressing)

Salt (for the dressing, added just before eating)

Mixed Herbs (for the dressing)

Procedure:

Cut and mix whatever you want to have in the salad. I generally choose about 6-8 items every day, and mix and match in any order I feel fit.

Introduce the dressing (generally just olive oil and honey) except for the salt since the salt will make the vegetables dehydrate and lose their water. I take this tossed salad to office, so it is about 3hrs time from the time I mix it to the time that I consume it.

It's funny to know....

2010-01-09T10:14:00.000-08:00

.... that something you have thought of doing and have done has been thought of by someone else across the world and done in almost exactly the same way as you have....

It's saddening and encouraging at the same time. Saddening because it's not something novel any more. Someone has "been there.. and done that..". Encouraging because you know that you are not having any insanely weird and impractical thoughts and ideas and that you are solving some real problem out there.

This is the second time that this has happened to me, and it is a real confidence booster I should say!!

The project under question is StickyLinks. The exact same thing was done in 1997 and is called WebCite. The funny thing is that it was made for the exact same problem that I was trying to solve, which probably explains why it turned out to be so similar.

The thing that still gets to me is that even the layout of the version page (view where a version of a certain page is displayed) is almost identical. Both projects use frames. Both projects have a bookmarklet.

However, there are ways I plan to extend StickyLinks, so stay posted!!

ps. My next idea: To develop a search engine that will let you search for already existing ideas/concepts/implementations of thoughts that you may have and may think are novel. I use the internet (esp. the search engines) a lot to search for projects that I may want to undertake, just to check if it's already been done by someone else. Most of the time I have to search a lot of times, tweaking my search keywords ever so slightly in the hope of a match. Many a times, I fail to chance upon the right set of keywords (the words that the original author used to describe his/her idea/project) and am under the impression that the idea I have is novel/un-thought of. However, many times it does happen that such a thing does not exist. However, it is only time that lets you ascertain this (if a similar concept exists, you hear of it sooner rather than later, assuming you have shared it with friends).

Chocolate Rum Balls

2010-01-09T09:07:00.000-08:00

This is been pending for a while now.
Barbara asked me how to make these last year!!!! (realistically, about a month ago) and I haven't yet gotten back to her. That is pretty bad of me.
Here goes nothing....

Ingredients:

Chocolate sponge cake:	about 250g
Dark chocolate:	about 250g (preferably &ge 40% cocoa)
Fresh Cream:	about 100g
Walnuts:	about 100g (or to your taste)
Rum:	to taste

Procedure:

Crumble the cake well into.... well crumbles.... Use very soft hands to do this.

Mix the rum with the crumbled cake, but don't form a paste.

Melt the chocolate (always over steam).

Heat the cream in a saucepan till it is simmering and mix it well with the melted chocolate.

Make small pieces of the walnuts and add them to the chocolate and cream mixure and mix well again.

Empty the cake crumbs into the mixture above and mix till it forms a solid paste which can be rolled into balls. Note: You may need more/less of the cake crumbs depending on how watery/viscous the chocolate and cream mixture is.

Roll them into balls!!!! You can put a thin layer of melted butter or ghee (clarified butter) on your palms so that the stuff doesn't stick to your palms while mixing.

Merry Christmas, and have a Great New Year!! :) :)

Gaajar Halwa

2010-01-09T08:24:00.000-08:00

I met Appu and Abbas today, and we had this nice talk about carbs. and how the lesser there are around and within us, the better it is for our kind of lifestyle. I have steadily reduced the amount of sugar I have with my cup of tea or ukada (or ukado since it is a gujarati recipe) and am okay with it.
The recipe below is in complete defiance of the statements above. However in my defense, I used much less sugar than I usually would have.

Ingredients:

Grated fresh red carrots(gaajar):	about 1kg
Cow's Milk (preferably full fat containing ≥ 9% SNF):	about 2ltr
Sugar:	to your taste, but you could start off with 200g
Cow's Ghee (clarified butter):	2-3 Tbsp
Elaichi:	seeds of 4-5 pods, well separated
Elaichi powder:	1 tsp (or to taste)

Procedure:

Take the Ghee in a saucepan and add the elaichi seeds, and heat the ghee till it is hot, and just till you hear a pop sound.

Add the grated carrots and coat every bit of them with the Ghee (on a slow flame).

Heat the milk in a saucepan till it is hot.

Pour some (about 500ml) of the hot milk into the carrot and ghee mixture, turn up the flame to medium and stir continuously.

The milk will come to a boil.

We want to make mawa (or khoa) from the 1.5ltr of remaining milk. You can find out how this is done. Basically it involves simmering the milk till the water almost vaporizes. The semi-solid mass that is left will be used later in the making of our halwa.

Once the mawa is made, mix it with the rest of the carrot mixture (which should have considerably thickened by now. I hope you were continuously stirring it all this while!!).

Also add the sugar. The sugar will immediately melt and give off a lot of water. We need to burn off all this water.

Stir continuously till the water evaporates and we are left with a semi-solid mass (more liquidy though).

Evenly sprinkle the elaichi powder over this mass and stir continuously.

Till the mixture thickens to a consistency of your choice.

Let it cool, and enjoy!!!! :)

btw, this is the 100^th post on this blog!!

An O(1) approach to the LFU page replacement algorithm

2009-11-24T08:12:00.000-08:00

LFU: Least Frequently Used

The LFU algorithm evicts pages that have been least frequently used. If the cache is full, and one more page needs to be added, the page that has been used the least number of times is evicted from the cache.

How can we efficiently implement this algorithm? Each operation of the LRU algorithm can be implemented in worst case O(1) complexity. We can do the same for LFU as well.

For this, we maintain a doubly linked list where each node of the linked list looks like this:


struct CountNode
{
 CountNode *prev, *next;
 PageNode *root;
 int count;
};

Each node of this linked list points to the root of another doubly linked list which holds the actual pages. All the pages in this 2^nd linked list have the same usage count. The node for this linked list looks like this:


struct PageNode
{
 PageNode *prev, *next;
 CountNode *parent;
 char pageData[4096];
};

The PageNode's parent member points to that CountNode of which it is a child. So there is a direct pointer from every PageNode to the corresponding CountNode it falls under. These extra links are not shown in the diagram to keep it simple.

The CountNode linked list's count member holds the usage count of each element under that node. So each PageNode under a CountNode having a count value of 6 will have been accessed 6 times.

How to implement the various operations?

Insetion: To insert, we always add the new PageNode to the CountNode list with the count value of 1. This will always be the first node in the linked list pointed to by head. If the first CountNode pointed to by head is greater than 1, we just add a new CountNode with a count value of 1 and then perform the insertion. All this can be done in time O(1).

Deletion: We will delete nodes, only if the cache is full, and this deletion will always happen from the CountNode list which has the least count. So, we just follow head, and delete a PageNode in such a CountNode. Additionally, if that CountNode happens to become empty because of this deletion, we also delete that CountNode. This too takes time O(1).

Access: Access involves incrementing the count of a PageNode, i.e. moving the accessed PageNode from it's CountNode list to a CountNode list with a count value that is 1 greater than it's current count value. We maintain pointers to the CountNode in the PageNode. This makes deleting the PageNode(and possibly the CountNode to which it belonged) a constant time operation. After that is done, we can insert a new CountNode that has a count value of 1 more than the CountNode from which the accessed PageNode was removed. If such a CountNode does not exist, we can always create it first. All this can also be done in constant time, making the whole process O(1).
A lot of people have asked me how they can get to a PageNode in the first place. The answer to that question is that we maintain a hash table which hashes an object(page address, integer, etc...) such that accessing it (getting to the PageNode that that object corresponds to) can be accomplished in O(1) time.

This implementation takes advantage of the fact that:

When we add a new object to the cache, it is always going to start off with a use count of 1, and

Whenever we access an object, it's use count will go up by exactly 1.

I haven't found any resource that says that LFU can be implemented in time O(1). If you (reader) find any, please do let me know.

The Missionaries and Cannibals Problem

2009-11-21T08:11:00.000-08:00

Some reading before you start: http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

Problem Statement:
[From the link above] "In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board."

Solution:
We will solve the generalized version of this problem, wherein there are C cannibals and M missionaries, and at most P people are allowed on the boat simultaneously.

This problem can be solved by noticing that at every stage, we can encode the state of the problem by using 3 variables, (nc, nm, shore). nc is the number of cannibals, nm is the number of missionaries and shore is either 0 or 1, which signifies whether nc and nm represent the count on the source or the destination shore respectively.

Thus, there are at most 2 x n² states that the problem can be at any point in time.

We can use BFS (breadth first search) to perform an exhaustive search on the search space to find a solution if one exists. The run-time complexity of doing so is O(CM P²). Below is the Python2.5 code that solves this problem using the BFS search method.


import sys
import string
from collections import deque


states = [[], []]
dq = deque()
nc = 0
nm = 0
c = 0
combinations = [ ]


def gen_combinations():
    global c, combinations

    for i in xrange(0,c+1):
        for j in xrange(0,c+1):
            if i+j>0 and i+j<=c:
                combinations.append((i,j))


def init_states():
    global nc, nm, states
    for i in xrange(0, nc+1):
        states[0].append([])
        states[1].append([])
        for j in xrange(0, nm+1):
            states[0][i].append(-1)
            states[1][i].append(-1)


def is_valid_state(nc, nm):
    return (nm>=nc) or (nm==0) or (nc==0)


def bfs():
    global dq, states, nc, mn, c, combinations

    while (len(dq) > 0) and states[1][nc][nm] == -1:
        (x,y,depth,boat) = dq.popleft()

        present = boat
        next = 1-boat

        if states[present][x][y] != -1:
            continue

        states[present][x][y] = depth

        for comb in combinations:
            (dx,dy) = comb

            if x>=dx and y>=dy:
                new_st = (nc-(x-dx),nm-(y-dy),depth+1,next)
                (lx,ly) = (nc-(x-dx),nm-(y-dy))
                (rx,ry) = (nc-lx,nm-ly)

                if is_valid_state(lx, ly) and is_valid_state(rx, ry) \
                       and states[next][lx][ly] == -1:
                    dq.append(new_st)



def main():
    global dq, nc, nm, c, combinations, states
    input = string.split(raw_input())
    nc = int(input[0])
    nm = int(input[1])
    c  = int(input[2])

    init_states()
    gen_combinations()

    dq.append((nc, nm, 0, 0))
    bfs()

    print states[1][nc][nm]

    return 0


if __name__ == "__main__":
    sys.exit(main())

The Capacity C Torch Problem

2009-11-20T08:32:00.000-08:00

I stumbled upon the Capacity C Torch problem, and found it really interesting.
I'll start off with a few resources:

http://aps.cs.nott.ac.uk/2008/05/06/the-capacity-c-torch-problem-2/

http://www.tutor.ms.unimelb.edu.au/bridge/

http://en.wikipedia.org/wiki/Bridge_and_torch_problem

http://www.springerlink.com/content/935641175550x527/

Problem Definition:
There is a group (G) of people that wishes to cross a bridge in the dark. Each person takes a certain amount of time to cross the bridge. There is only 1 torch available. The bridge can hold at most C people at any one time. Every time a group of people cross the bridge, they need to carry the torch with them. One torch is sufficient to light the path for at most C people at a time. When multiple people cross at the same time, the entire group moves at the speed of the slowest person in the group. Given the values for G, C and the time that each person takes to cross, find the least amount of time that would be required to get the whole group across to the other side.

Expected Complexity of the solution: This solution can be solved using a computer program having a run-time complexity of O(n²), where n is the number of people in the group G [ |G| = n ].

Solution:
Step-1: Let us first concentrate only on how we will divide up the people into sets and in what order we will take them across(from size A to side B). We shall re-visit the problem of which person to get back to bring the torch back from side B to side A.

Let us take some values for the variables G and C.

Example-1: Let |G|=15 and C=5

In this case, we can easily divide people into 3 sets of size 5 each.

We'll sort all the people according to the time they take and group them starting from the slowest person. It can be seen that it is beneficial to club all the slow people together. So, we group the 15^th, 14^th, 13^th, 12^th and 11^th person in one group, and so on..

We'll take the 1^st group(the one with the 5 fastest people) and move them across first. Since someone needs to come back with the torch, it had rather be the quickest person, so we make sure he is across so that he can return.

We then take the 2nd group followed by the 3rd.

Example-2: Let |G|=16 and C=5

In this case, we are left with 1 person after dividing into sets of 5 each. No matter what we do, we will have 4 sets to deal with. We also note that it makes no sense to move just 1 person across. So, the way we make sets is {2,4,5,5}.
Why not divide as {3,3,4,4}? Well, if we do it like the latter case, then the 1^st group will have the time of the 3^rd person, and not the 2^nd like in the former case. In both case, everything else remains the same, except if the 3^rd person is slower than the 2^nd one, we will have increased the total time required to cross. This is why we optimally divide in the former way.

Example-3: Let |G|=17 and C=5

Again, in this case, we optimally divide as {2,5,5,5}. We note that no other division is possible.

Example-4: Let |G|=18 and C=5

Again, in this case, we optimally divide as {3,5,5,5}. We note that no other division is possible.

Example-5: Let |G|=19 and C=5

Again, in this case, we optimally divide as {4,5,5,5}. We note that no other division is possible.

Step-2: Now, we shall concentrate on the problem of which people should bring the torch back from side B to side A, so that the next group on side A can cross the bridge to side B. Let us call these people torch bearers. The same problem also asks and how many at a time to bring back (i.e. How many torch bearers should move from side B to side A without returning) when sets of people are being transferred from side A to side B.

[This is where you should try figuring out for yourself whether you will send 1, 2, 3, 4, 5 (or more) groups at a time (without the torch bearers returning to side B)]

For example, suppose we have a group of people, [1,1,1,1,1,1,4,5,6,7] and C=3.
It is easy to see that once we have 2 people across, we can always get more across without having the torch bearers coming back to side B.

If we decide to work such that every time 2 torch bearers cross over to side A, they return to side B, we get the following scenario: The mean cost of transferring a set from side A to side B, and back would be 1(1^st torch bearer from B to A) + 1(2^nd torch bearer from B to A) + 1(1 and 2 back from side A to side B) = 3/1 (since we were able to get only 1 set across).

If we decide to work such that every time 3 torch bearers cross over to side A, they return to side B, we get the following scenario: The mean cost of transferring a set from side A to side B, and back would be 1 + 1 + 1 + 1(1, 2 and 3 back from side A to side B) = 4/2 (since we were able to get 2 sets across).

Similarly, if we decide to work such that every time 5 torch bearers cross over to side A, they return to side B, we get the following scenario. The mean cost of transferring a set from side A to side B would be 5+1(1, 2 and 3 back from side A to side B)+1(1 from side B to side A)+1(1, 4 and 5 back from side A to side B) = 8/4 (since we were able to get 4 sets across).

We observe that the mean cost went down if we took more torch bearers at a time. However, it is also easy to see that this is not always true. It depends entirely on the time that each torch bearer takes to cross the bridge.

We could also have a case where we have more than 3 torch bearers crossing from B to A, without coming back (like we sent 5 torch bearers at once in the example above).

We can NOT make a greedy choice as to how many sets to take across. i.e. How many torch bearers to send from B to A without them returning. This is where dynamic programming comes to the rescue.

Suppose |G|=47 and C=5
We will optimally divide into sets {2,5,5,5,5,5,5,5,5,5}.

The best way to take all 10 sets across is the best of:

The best way to take all across without any torch bearer coming back unless all initial groups are across

The best way to take the first 9 groups plus the best way to take the last group

The best way to take the first 8 groups plus the best way to take the last 2 groups

The best way to take the first group plus the best way to take the last 9 groups

The cost for computing these values using dynamic programming or memoization is O(n²). We can use these techniques because there are many overlapping sub-problems, and the other requirements for dynamic programming match.

We can pre-compute the cost required to take 1, 2, 3, 4, etc... groups at a time and store it in a lookup table. The time required to do this is O(n²).

Thus, we can solve the whole problem in time O(n²).

Wordlist for GRE

2009-10-25T05:30:00.000-07:00

Hello people, I have made a simplistic wordlist tool for GRE preparation. I've been asked by a well-wisher to post it here, so here it is: http://wordlist.dhruvbird.com/.

Masala Matrix

2009-10-17T23:53:00.000-07:00

Just a ready reckoner for me to look up to figure out how vegetables and lentils are made at my home.

Recipe	Fat	Rai (mustard seeds)	Jeera	Methi seeds	Hing (asafoetida)	Green chilli (whole)	Kadi patta	Haldi	Salt	Ginger paste	Dhania and jeera powder to season
Dudhi (bottle gourd)	Ghee	No	Yes	No	Yes	No	Yes	No	Yes	Yes	No
Tendli	Ghee/Oil	Yes	No	No	Yes	Yes	No	Yes	Yes	No	Yes
Karela (bitter gourd)^[1]	Ghee	Yes	No	No	Yes	Yes	No	Yes	Yes	Yes	Yes
Dudhi + Dal (chana or tur daal)^[2]	Ghee	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No
Cauliflower (fool gobi)	Oil	Yes	No	No	Yes	Yes	No	Yes	Yes	No	Yes
Cabbage (patta gobi)^[3]	Oil	Yes	No	No	Yes	Yes	No	Yes	Yes	No	Yes
Tur Daal^[4]	Ghee	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No
Aaloo mutter and tomato sabzi^[5]	Ghee	No	Yes	No	Yes	Yes	Yes	Yes	Yes	No	Yes
Pumpkin (bhopda) sabzi	Ghee/Oil	No	No	Yes	Yes	Maybe	No	No	Yes	No	Yes
Fanshi (french beans) sabzi	Ghee/Oil	Yes	No	No	Yes	Yes	No	Yes^[6]	Yes	Yes	Yes
Moong daal (yellow)	Ghee/Oil	Yes	Yes	No	Yes	Yes	Yes	Yes	Yes	Yes	No

[1]: Also put jaggery(gud), kaju(cashew) and kishmish(sultanas).
[2]: Also put jaggery(gud), kokam and corriander leaves to season.
[3]: You may optionally add tomatoes halfway through cooking the cabbage, and also add jaggery(gud) if you add tomatoes.
[4]: You can also add jaggery(gud) and kokam. It gives a very good taste to the daal. If you don't want to add gud and kokam, you can add lasun(garlic) to give it a nice taste and aroma. A 3^rd option is to add tomatoes. If adding tomatoes, leave out the kokam, but you should add jaggery and may optionally add garlic.
[5]: You can also put a bit of jaggery(gud) into this preparation.
[6]: Add Haldi only if you are adding potatoes to the sabzi.
* Dhania powder is generally added only to vegetable preparations and not to daal preparations.

Online hindi dictionary

2009-10-08T10:40:00.000-07:00

I've been trying to find an online hindi dictionary where I can enter the text in english, and the system transcribes it and searches for the meaning. However, the best results I have got are by using google's transliteration tool(http://www.google.com/transliterate/indic) followed by a google search for the resulting word.
That apart, this site: http://www.websters-dictionary-online.org/ seems to have a lot of words. Make sure you choose the "non-english" option when you search.

Lip-smacking Rasgulla recipe

2009-07-26T21:43:00.000-07:00

I have tried for long to make rasgullas that taste like the ones I had a Ganguram's in Kolkata. I tried buying rasgullas from many shops, and tried making on my own in the hope of being able to reproduce that taste and texture that had lulled me into have a lot many Rasgullas that rainy day in Kolkata, but to no avail. None came even a close second.... Then, I read somewhere the milk that is curdled should be curdled slowly, taking care not to shock it, so I decided to try it out.... The rest is history....

The secret of making good, no GREAT tasting rasgullas is in what milk you use and how you go about curdling it and then processing it. Every step is very important, but I wasn't able to get the 2^nd one right for quite a while. I finally tasted success (and moth-watering rasgullas) after a long time yesterday. I'll mention how you can go about reproducing them at home....

Buy cow's milk for making rasgullas. 3.5% to 6.0% fat content is alright. Do not get low fat milk

Boil it till about 10% of it boils off, taking care to not let it stick to the vessel. To ensure that, keep stirring as you boil it

For 1 litre of milk, you will need about 2-3 tsp of vinegar or about ³/₄^th of a lime's juice. IMPORTANT: Dilute this juice in about 1 cup(240ml) of water

Now, slowly keep adding this juice to the boiling milk, making sure to stir all the time. You can add about ¹/₄^th every time, and stir for a minute. Do this about 4 times, and keep stirring and heating the milk on a low-medium flame. The milk should continuously keep curdling

The milk is completely curdled when it separates into while solid and a greenish liquid

Make sure that you do this curdling VERY VERY slowly, otherwise the paneer will result in rubbery rasgullas

Now, separate the solid part(paneer) using a muslin cloth and squeeze out as much water as your possibly can. You can wash the paneer to remove the acidic part and squeeze out again, as much water content as you can

Let this paneer dry up for about 30-45mins

Now, you can follow any standard rasgulla recipe that tells you to knead the dough, form balls and cook them in boiling sugar syrup. However, I would like to clarify a few things

The ratio of sugar:water in the boiling syrup should be 1:6 or lesser. I have heard some people boil the paneer balls in just water

Make sure you roll the paneer balls tight and their surface is smooth. You can smear a bit of ghee(clarified butter) on your hands while rolling to ensure that they don't stick to your palm, and result in smooth balls

Use these rasgullas as rasgullas by dipping them in 1:2(sugar:water) syrup or by squeezing out the water(on cooling) and dipping them in rabri(to make yummy rasmalai!!!!)

Some lessons learnt

2009-07-26T21:37:00.000-07:00

I have been working closely with this person called "Ramki", and have learnt a lot of interesting things from him that I wish to share. I don't know if I'll keep appending them to this post or create a new one each time. I guess it depends on my mood and the context and other such stuff....

Never use filenames or variable names in an application that have the name of the product in it. If you ever decide to change the name of the application, you'll have to change all those file and variable names too. This can be a nightmare.

When creating database tables which hold the email address of the user, also use a unique user ID. This allows users to change their email IDs when they please. If you use the email ID as the primary key(like how I was going to), it would not allow a change of email address in a cheap fashion. You would probably have to do an ON UPDATE CASCADE, etc.... and it would be quite an expensive operation.

Sita Sings The Blues

2009-07-19T10:22:00.000-07:00

I have to start off by saying that "Sita Sings The Blues" has to be one of the most influential movie I have ever seen. In the sense that it has prompted me to notice and think about a lot of things, and I think especially since I am from India.

There are many aspects of the movie I really like and I'll try talking about each one in as much detail as I feel necessary.

Lots of things have been left to the imagination of the audience even though a lot many have been explained by way of the random conversations that happen between the 3 narrators in the movie. I think it was very natural to make them say the things that they did, and the way that they casually argue with each other. Also, the conversations weren't casual enough to call them loose.

The music given is quite apt and makes you want to listen to it more often. The title track "Sita in Space" is trance-like in nature and makes use of instruments that sound Indian as well. I felt that the way Lord Rama is first shown being waited upon by Sita and the last scene which has the same scene with the roles reversed is quite an outstanding and representative of a lot of things.

The way that all the characters and their relationships to each other are shown upfront is something really neat. There have been times when I've seen movies and only towards the end have I fully understood how each of the characters are related to each other(when the story depended upon the viewer knowing these relationships up front).

I found the scene is which Kaikayee is shown to be a nurse taking care of Raja Dashrath quite hilarious.

There is another scene in which Nina is shown almost completely undressed, sleeping by her husband's side and her husband wants nothing to do with her when we hear a dog barking in the background. This was a scene that I was most impressed by because it felt so real, since that is exactly what I hear at many places(a dog barking in the night time). The level of attention to detail at places in the movie is really commendable!

This is a post in progress, and I shall keep updating it regularly.... Till then, you can watch the movie for free here. The song "Sita In Space" is really nice....

Garlic and Herb Chapati

2009-07-18T23:08:00.000-07:00

As always, I'm a bit lazy and don't want to spend time baking bread(it is a very long and drawn out process). However I felt like having focaccia(yes the yummy bread with herbs, garlic and loooots of olive oil), so I decided to make a similarly flavoured chapati and see how it turns out.

Ingredients:

Whole Wheat Flour:	2 cups + more for dusting
Water:	Enough to make a really hard dough(we'll soften it up using lots of Olive Oil!!)
Softened Salted Butter:	5 Tbsp
The Best Extra Virgin Olive Oil that you can get your hands on and afford:	5 Tbsp
Mixed Dried Herbs(Parsley, Basil, Oregano, Rosemary, Thyme):	1-2 Tbsp
Salt:	¹/₄ tsp or to taste
Fresh Garlic Paste(it needs to be FRESH!!):	of about 10 cloves
An appetite:	as much as you can squeeze in!!

Procedure:

Make a very hard dough from the whole wheat flour, water, herbs and garlic paste(take a really deep sniff, close your eyes, and savour the smell for a while).

Use all the Olive Oil and mix it with the dough to make it hard(very hard to hard).

Use this dough to make about 8-10 portions for rolling out.

Keep tava(pan) for heating up on a slow flame. This will ensure that your tava is heated up evenly and your chapati won't get burnt or cooked unevenly.

Roll out the chapati apply dusting flour regularly to prevent it from sticking. Roll out slightly thicker than standard chapatis because we have garlic and herbs in the dough. They may cause the chapati to puncture if we roll it out too thin. If the chapati gets punctured, then it won't balloon like we want it to.

Cook the first size on a slow flame on the tava just until small boils begin to appear on the top surface.

Turn the chapati over and cook on medium flame, turning the chapati so that the sides are cooked well. Always keep the sides in the center of the flame. The center of the chapati will get cooked well automatically. Now, larger boils will appear on the surface, and the under-surface will have brown spots on it.

Make the flame high, remove the chapati from the tava quickly, remove the tava from the stove and turn the chapati up-side-down on the direct flame. Watch it balloon!!!! (if you've done everything well till now. It took me a month and lots of flat chapatis to get to this stage).

Turn it around for just 1 second(or for symmetry as Appu would put it).

Take it off the flame and apply a little of the melted butter while it is still steaming hot.... Smell it again and again till you think you've attained nirvana....

Eat it!!!!

YAVFS

2009-07-17T08:30:00.000-07:00

Yet Another Versioning File System....

I've been reading about Versioning and Snapshoting File Systems and here is a mini-dump of what I think so far. Please correct me if I'm mistaken....

I saw a few file systems with slightly more than a cursory glance, and here are my comments:

ext3cow: This is very close to what I have in mind for a versioning and continuous snapshoting file system. However, it does not agree with some of my "requirements of a versioning and continuous snapshoting file system"(below).

Elephant File System: This is probably one of the earlier snapshoting/versioning file systems and has been implemented on BSD. It is modeled on BSD's FFS. It does a great job of doing what it says it does. I like everything about it except that I can't use it on Linux.

NetApp's WAFL: This again is mainly solving a different problem, that of providing very fast and safe storage on a storage appliance. To the best of my knowledge, you need to trigger a snapshot(though the process itself does not take more than a few seconds), and the number of snapshots are restricted to a fixed number(32 or 256). This may be done using hourly cron jobs, etc.... The interface of getting previous versions of files is a little clumsy though.

Requirements of a Versioning and Continuous Snapshoting file system:

It should be able to store a large number of versions of files and directories alike

It should be able to do so very fast and without any user intervention. ie. Snapshoting should not be user-triggered, but should be done automatically on every close()

You should not need to re-compile the kernel to get this functionality

You should be able to apply this to a specific directory root. This means that you should be able to snapshot parts of your directory tree. You should not incur a performance penalty for accessing file out of this region of interest

You should have policies for controlling which file to snapshot and version files based on file attributes such as size, name, MIME type, etc....

The interface for accessing continuous-in-time file versions should be very clean and fairly intuitive, and it should be fairly easy to write tools around it so that GUI/web-based access can be enabled

You should be able to enable this functionality on any file system(and not require to re-format the partition on which you wish to enable it)

You should be able to disable this operation at any point in time and get back to accessing the most recent versions of the versioned files using the earlier access methods without any performance penalty. ie. Users should be able to turn on and off this functionality at will and it should allow users to proof this on real workloads without them having to make any drastic changes in their environments

The operations performed should be safe, and should not result in data corruption

The system should be easy to install and set up

I have in mind something that satisfies the requirements mentioned above....

NextGen Storage??

2009-07-14T23:54:00.000-07:00

I've been thinking about what storage systems have in store for us in the future. I mean I've been trying to follow the progress of these beasts, and the next big thing I think should be storage devices that have in-built support for some form of transactional memory. Lots of file-system drivers are building consistency mechanisms into their implementation by using logging in some form or the other. This logging is happening on the same medium as the one where data is being stored. A consistent view of the data is formed by looking at (data+log) as a unit of storage.

I think that logging implementations would benefit a great deal if they had some sort of hardware support. For example, NetApp's WAFL is utilizing Flash memory to store it's writes. This I think is a nice way to look at the problem at hand, and if device manufacturers could integrate some of this on to their device using some nice interface, I think that file-systems of the future could be much faster than they presently are.

The only problem that I do however see with this approach is that the flash memory may wear out and cease to function much faster than the magnetic stable storage. A log-based file-system(or storage structure) would be needed to store the writes on the flash storage(something like JFFS maybe).