Too busy with work to blog lately, but here are some random thoughts I've been meaning to write about. Hopefully I'll get a chance to "expound" (thanks SAT prep) on these topics at a later time.
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