Tag Archives: Algorithms

May 13, 2015

Bloom Filter for JavaScript

I wrote a very fast bloom filter implementation in JavaScript called bloomfilter.js. It uses the non-cryptographic Fowler–Noll–Vo hash function for speed. We can get away with using a non-cryptographic hash function as we only care about having a uniform distribution of hashes.

The implementation also uses JavaScript typed arrays if possible, as these are faster when performing low-level bitwise operations.

January 22, 2014

Smaz

Smaz is a simple compression library suitable for compressing very short strings. General purpose compression libraries will build the state needed for compressing data dynamically, in order to be able to compress every kind of data. This is a very good idea, but not for a specific problem: compressing small strings will not work.

March 27, 2012

The monkeys have succeeded

I wrote about Jesse Anderson’s Infinite Monkey Theorem experiment back in October of last year. I haven’t followed his progress until now — as it turns out, Jesse’s virtual monkeys managed to recreate every single work of Shakespeare:

The monkeys accomplished their goal of recreating all 38 works of Shakespeare. The last work, The Taming Of The Shrew, was completed at 2 AM PST on October 6, 2011. This is the first time every work of Shakespeare has actually been randomly reproduced. Furthermore, this is the largest work ever randomly reproduced. It is one small step for a monkey, one giant leap for virtual primates everywhere. This page shows what day each work of Shakespeare was completed on.

December 12, 2011

FXAA

Coding Horror’s excellent overview of not only FXAA, but SSAA and MSAA as well.

October 10, 2011

Today's acronym: SS2PL

SS2PL stands for strong strict two-phase locking; it’s a locking mechanism widely used in database systems today. It is based on the notion of two-phase locking:

  • Expanding phase: locks are acquired and none are released
  • Shrinking phase: locks are released and no new locks are acquired

In addition to the above requirements, SS2PL requires that both read and write locks are held until the transaction that acquired them has commited. Essentially, this means that there isn’t a shrinking phase — only an expanding phase. May I ask why, then, is it called strong strict two-phase locking and not something completely different?

I love computer science acronyms.

October 1, 2011

A few million monkeys randomly recreate Shakespeare

This project comes from one of my favorite Simpsons episodes which has a scene where Mr. Burns brings Homer to his mansion. One of his rooms has a thousand monkeys at a thousand typewriters. One of the monkeys writes a slightly incorrect line from Charles Dickens “It was the best of times, it was blurst of times.”  The joke is a play on the theory that a million monkeys sitting at a million typewriters will eventually produce Shakespeare.  And that is what I did.  I created millions of monkeys on Amazon EC2 (then my home computer) and put them at virtual typewriters (aka Infinite Monkey Theorem).

So far, Jesse’s virtual monkeys and typewriters have randomly created The Tempest, The Winters Tale, The Merchant of Venice and many more. I  recommend bookmarking his post so you can follow the progress. (via Ars Technica)