Too busy with work to blog lately, but here are some random thoughts I've been meaning to write about.
Burst Tries
Several prominent (Google ranking) articles on implementing autocomplete suggest using a trie data structure. Unfortunately, none of those articles point out how horribly space consuming tries are. A naive, non-compacting trie structure is exponential in space. With an a-z alphabet you have 26 exponent word length nodes. That's a lot of nodes. If you want the best of both worlds, the memory requirement of a binary search tree and the speed of a trie, try the burst trie. Burst tries: A Fast, Efficient Data Structure for String Keys by Steffen Heinz, Justin Zobel and Hugh E. Williams.
John Mitchell
In my blog on F-Bounded Polymorphism I forgot to credit John Mitchell as one of the authors of F-Bounded Polymorphism for Object-Oriented Programming. This was purely accidental and has nothing to do with the fact that he's a Stanford guy.
Memcached
Memcached is awesome. Locks, CAS, is there anything it can't do? PHP's support for memcached makes PHP just barely tolerable as a language. The "M" in LAMP needs to be officially changed to Memcache, not MySQL.
PHP
What a mess of a language. It has deviated too far from its original goals. Really miss type safety, because, "after all, run time is a little late to find out whether you have a landing gear." (Eiffel dude) Really miss all of Java's built in libraries. I find it incredible that no one using PHP has had the need for a red-black tree, because I can't seem to find an implementation of one. I do like PHP's request processing model better than Java's, though. Adios threads, synchronized, volatile.
Read Only Sessions
I find it really puzzling that PHP doesn't have a notion of read-only sessions. Seems like this would be a no-brainer considering that PHP web apps are typically read dominant. And you can't write your own quickly because there's no function to decode a session string, except to decode it and overwrite the current session. Someone did provide a function to decode the session string here, but I'm not sure if I fully trust it to decode everything correctly.
Think that's about it for now.
Comments