Tuesday, March 09, 2010

[LIFE] Keeping the PACE of productivity is very hard.

This is the first of the posts I'll start writing some thing different from Technology. Spring break started last Friday (03/05/2010). I'm back to the out-of-core assembly project. Well I had this idea of out-of-core de Bruijn graph construction for a long time and in fact we did demonstrate the efficiency in parallel context. However the main focus has been to format the bi-directed de Bruijn graph in the format required by Velvet. I started of this quest some time mid October and finally I had a complete algorithm which generates the 'Graph' file in Velvet format. I was very happy last night when I got that but soon realized that there is a lot of difference in the number of CONTIGS. Went home with full of despair that I'm totally stupid. Today I came back and started it again. Productivity is something I strive for. KARMA is something I really believe in. However it seems to me that keeping up with the PACE of productivity is something very hard, the harder you try to focus the harder it might become. I strongly feel that continuous non-stop productivity is only possible when it becomes a HABIT rather than MOTIVATION. It might start off initially as MOTIVATION, but cultivating it as a HABIT is something on the lines of KARMA YOGA. Finally a true KARMA YOGI seems to be a person for whom continuous productivity is a HABIT rather than anything else.
Posted by at No comments:

Monday, February 01, 2010

[TECH] An efficient External sorting API

Sorting is one of the most fundamental operation on data. Very efficient algorithms exists to perform this operation. Most of the programming languages are shipped with some sorting API with them. Most of them are in-memory sorting algorithms. However I find all these APIs are so bloated which are unfortunately by produces of abusing and overusing the object oriented concepts. On the other hand the bloated code may run fine as long as the input size is bounded by some constant -- which is most of the case for many applications. Any way I guess I'm getting into a little off-topic but if you are interested see the flames between C++ and C hackers on the Linux kernel mailing list here

On the other hand most of these programming APIs lack a solid External sorting algorithms. External sorting is * THE MOST * fundamental operation especially when you want to build algorithm on monster and massive datasets. You can try my new -- well old but wrapped in a new API, External sort please get it here . I'll try to post some examples how to use if when I get more time.

Posted by at 3 comments:

Saturday, January 30, 2010

Rounding An Integer To The Next Maximal Mutliple Of A Given Radix Power

Let $ (\ldots d_3d_2d_1)_b$ be the modulo-$ b$ representation of an integer $ A$, where each $ d_i$ is a symbol/digit corresponding to values $ \{0,1,2\ldots b-1\}$. Often we are encountered with problems where we need to find smallest integer $ A' \geq A$ such that $ A'\vert b^y$ (i.e. $ b^y$ divides $ A'$ without any reminder), where $ y\in I^+$. Some of the very common applications include rounding the number of bits required to represent a data structure to the nearest byte (i.e. power of $ 2^y$). Before we see how to address this problem its worth while to understand the following interesting property of modulo representation. Given a modulo-$ b$ representation of $ A$ we can get corresponding modulo-$ b^y$ representation of $ A$ by replacing every group of $ y$ digits (in modulo-$ b$ representation), by the corresponding digit (i.e. $ d_{i_y}\times b^{y-1} + d_{i_{y-1}}\times b^{y-2} \ldots d_{i_1}$) in modulo-$ b^y$. For instance if we would like to convert an integer $ A$ in binary (i.e. $ b=2$) representation to hexa-decimal representation ($ b^y = 2^4$). We start from left to right and replace every $ 4-$bits with the corresponding digit in hexa-decimal system. For example if we see $ 1101$ we will replace it with digit $ D$, $ 1110$ by $ E$ and so on. So the hexa-decimal system is providing us with a one-one function $ H: \{0,1\}^4 \rightarrow \{0,1,2\ldots A,B,C,D,E,F\}$ for every $ 4-$bit string, in fact we can use any one-one function here when we move for modulo $ 2$ representation to modulo $ 2^4$. However the one-one function $ H$ has become a standard for module $ 2^4$ system.

So coming back to our original problem given the modulo-$ b$ representation $ A$, we would like to round $ A$ to $ A'$ , where $ A'$ is the smallest multiple of $ b^y$ such that $ A' \geq A$. To accomplish this task we need to examine the first (from right) $ y$ digits in the modulo-$ b$ representation of $ A$. In fact the value of in those $ y$ bits is the reminder we get when we divide $ A$ by $ b^y$, so if $ V$ is the value in those $ y$ bits then $ A' = A + (b^y-V)$. When $ b=2$ we can elegantly use the bit-wise operators to accomplish this. So if some one gives an integer $ X$ and ask to find a smallest $ X'\geq X$ which is a multiple of $ 2^y$ then we use the following C-statement to accomplish this $ X += ((1\ll y)-(x\&((1\ll y)-1)))\&((1\ll y)-1)$. Where $ \&,\ll $ are the standard bit-wise operators in C.

Posted by at No comments:
Subscribe to: Posts (Atom)