janak's mus·ing and con·tem·pla·tion

I have been reading about bloom filter for quite some time but never used in practice. Adding few points of future reference.

Basic idea is as below:
Have a bit-vector array of size M. Take entry as input. Pass this entry through K different hash functions. Each hash function will return value between 1 to M. Mark the bit representing each of this value's bit to 1.

To check if given entry is present, pass entry to same hash functions and make sure that all values in that bit-vector are 1. Return FAIL otherwise.

1. Bloom filter has efficiency of HashTable and very less space requirement like bit-vector.
2. Very widely used in applications where reading actual data is costly(I/O, network delays) but checking for presence/absent of given entry is very useful first step.
3. You can only add entries but cant remove them easily. Note: Can be fixed with additional counter for each bit in bit-vector.
4. False positives are possible. False negative are not.
5. Ratio for M/N of 10+ is good enough. (N is number of expected entries. M is bit-vector size).
6. K > 5 is good enough. (K = Number of hash function)
7. Use Jenkins, Murmur and SHA as hash functions for sure. Pick few others from your past experience.

Cite
http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
http://0pointer.de/blog/projects/bloom.html
https://github.com/clearspring/stream-lib

Found this interesting data structure. Difficult to understand in first shot but this link explains it very well.

What I really liked about it is:
1. As your keys grows, it scales very nicely.
2. Dynamic scaling is possible easily. Just add one more column (2^n)
3. Easy to code once understood :)

Since past few days, I am using terminator in Linux as alternate utility for GNU terminal.
Its quite good so far.
Simple, elegant, minimal options and does what I expect it to.

I use main 3-4 commands for day to day use.
1. ctrl + shift + e => split the screen vertically
2. ctrl + shift + x => zoom-in/out specific terminal
3. ctrl + shift + n => rotate over different terminal
4. ctrl + page-up/page-down => rotate different tabs

Use it if you are terminal heavy programmer and likes multiple things in same terminal.

Here is the link:
software.jessies.org/terminator/

From our last trip to Kerala..

Came across this article about random numbers and realizes that rand() is not perfectly random.

In other words, for a dice rolling school project, rand() is just peachy. But for a slot machine in Las Vegas, you need the very best you can get, and rand() isn't it.

So true..

Usually we play badminton every evening after challenging ride in Bangalore traffic from office to back home. Its quite refreshing 40-50 mins of exercise on weekdays and sometimes on weekends as well. We see kids swimming in nearby pool and their parents proudly watching them getting thrashed by coach. Play continues after sunset under artificial lights for a while and then we give up with drenched T-shirt.

Now all of suddenly, today, we got audience!
Two kids from nearby house came in and started cheering. Thats something pretty new for us considering remoteness of ground. One kid started asking me why I am not playing particular shot and so on. Suddenly you realize that people are watching you and your game starts improving. You may tell it pressure to perform in front of stranger eyes. Even if those are smaller eyes :)

Once the audience is left after few curses from their mom, we are back to same game :D

Just read something interesting about prime number:
Every prime number can be expressed as 30k±1, 30k±7, 30k±11, or 30k±13 for some k. Except for 2, 3 and 5.
I didn't tried all combinations but it seems to be true.

Edit: Its not :(

Came across this Q and thought of writing it down.
Input: Two strings
Output: true if they are rotationally* equal, else false.

*rotationally equal means: abcd == bcda == cdab

Shorter the code, higher the points.
As its python, no extra points for performance :)

This is so cool, as real as it gets!
Look at the attire, background and gadgets.
Redefining gravity like never before..

Came across some nice macro in C..

#define COMPARE(x, y) (((x) > (y)) - ((x) < (y)))
#define SIGN(x) COMPARE(x, 0)

And... how to get string length faster:
http://tsunanet.net/~tsuna/strlen.c.html