(Sorry for the hiatus, etc)
If you're using a Mac, QuickSilver becomes an invaluable add on very, very quickly. If you're not using, it stop reading and install it now.
Really, I'll wait.
Now that you have QS installed, here's a way to do really quick dictionary lookups:
Open QS preferences
Go to plugins
Add the Services Menu Module.
Note: Do *not* add the dictionary module - that will not work in 10.5.
Once this is done, you can open a normal QS window using your hotkey (mine is Apple-Space)
Hit "." to start typing free text.
Hit "Tab" to go the secondary window containing a list of actions.
Start typing "Lookup in Dictionary.app". Usually, I have to type "Loo" before QS figures it out.
Et voila!
Much better than going to dictionary.com or dict.org or even doing "define: foo" in Google.
Wednesday, August 6, 2008
Monday, June 16, 2008
[books] Lord of Light
Lord of Light by Roger ZelaznyMy review
rating: 5 of 5 stars
I just reread Lord of Light and I'm promoting it to my favourite sci-fi/fantasy book of all time. It is extremely well written, its a fast read, and the Buddha kicks some serious butt. What more can one ask for.
View all my reviews.
Tuesday, May 27, 2008
[books] The Queen's Gambit
The Queen's Gambit: A Novel by Walter TevisMy review
rating: 4 of 5 stars
Bobby Fischer story; except that Bobby is a "she". Really good stuff, fun, fast read. Predictable ending, but if that is the best I can come up with, it must be pretty good.
View all my reviews.
[books] Marooned in Realtime
Marooned in Realtime by Vernor VingeMy review
rating: 4 of 5 stars
Great fiction from an accomplished writer. It is not a Fire Upon The Deep, but it is still an extremely compelling and rather fast read. Armchair detective novel - except with statis based time travel.
View all my reviews.
Sunday, April 13, 2008
Solving the iPhone headphone problem
Inspired by http://www.blogger.com/img/gl.link.gif comparing iPhone headphone adapters, I took a pair of scissors and a knife to my own headphones and fixed the problem. For those that are unaware of the problem here's the short version: iPhone has an almost normal female headphone plug, except that its a tad too deep to accommodate the mic. As a result, almost all "regular" headphones don't work. This has led to a whole industry of adapters, ranging from $5 to $10 that fix this problem. Turns out, a knife does the same. For free (as in beer). Results below:
Those are my JVC headphones, not iphone headphones. That little ring on the side is what I cut out. All you need is about a 1mm cut and that does the trick.
Do *not* blame me if you try this on your $200 Bose headphones and end up cutting the wire instead. I am not liable, YMMV, and all that.
Those are my JVC headphones, not iphone headphones. That little ring on the side is what I cut out. All you need is about a 1mm cut and that does the trick.
Do *not* blame me if you try this on your $200 Bose headphones and end up cutting the wire instead. I am not liable, YMMV, and all that.
When the problem is really hard...
... change the problem!
This sounds like a cop-out, but by that measure, most of engineering is a cop-out.
This sort of engineering happens in all fields, but since I am most familiar with CS, I'll go over an example from there.
The problem domain arises from the design of caches. It is also applicable to any general search / query optimization and I'll talk about that briefly at the end. On to caches - I'm talking about the web sort here not the processor sort. So on to the problem itself:
Imagine you're building a large cache of webpages. You have the webpage itself on disk, but ideally you don't want to hit disk to avoid the 8ms hit. You can reference each webpage by some id, which is, say, a hash on the URL. One easy thing to do is to store all the ids in a hashtable using some reasonable hashing function. Even with perfect hashing, your hashtable is going to be size O(n) if you have to store n elements. This is fine if the number of documents you're storing is small , but if you have a large number of documents (1 billion docs * 8 bytes = 8G memory), and realistically you don't have a perfect hashing function, this can become quite cumbersome. So what do we do?
Enter bloom filters. Bloom filters are a type of probabilistic data structures that use some fixed number of bits and provide the guarantee that if an element is not found in the bloom filter, it does not exist in the cache. If an element is found, then it is in the cache, with very high probability. What this realistically means is that your bloom filter can say that you have something, when in reality you don't. In most cases this is okay, because the probability of this happening is sufficiently small.
The simplest kind of bloom filter is conceptually pretty easy to explain too. Lets suppose that you're hashing a set of elements S = {x1, x2, .. xn}. Lets use a bitset of a fixed size - say 1024 bits. Now we hash x1 => k1 where {k1..kn} is a number in 2^1024. Inserting an element x1, we hash it to k1 and flip that bit to 1. Thus your bloom filter looks like this:
x1 => k1
x2, x3 => k12
When we search for x1, the bit is 1, its a hit, we look for it and its there.
Similarly x2 hashes to k12 and the bit is 1, we look for it and its there.
Lets assume x3 is not there in our cache. We search for x3 and it hashes to k12 and the bit is 1 and we try to look for it and its not - its a false positive.
x5 hashes to k17 (or something like that) and the bit is 0, so we know definitively that the element is not in our set.
This is a brilliant optimization that helps out in a surprising number of search problems where the time hit on a false positive is acceptable.
I'm sure I didn't do a good enough job explaining bloom filters, so here's a great talk on the same. The first 10 minutes are really good and then he gets into a lot of very complicated stuff that optimizes various aspects of bloom filters. If you're implementing your own, I'd recommend the whole talk, else just the first 10 minutes or so.
Thus in the end, if you look at the problem definition of hash - "tell me, with certainty, whether a particular element exists in a set or not", its difficult (for space reasons). But if you change the problem definition to "tell me, with certainty, whether a certain element is not in a set, but you can be wrong about it being in the set", suddenly the problem becomes solvable along the space axis.
This sounds like a cop-out, but by that measure, most of engineering is a cop-out.
This sort of engineering happens in all fields, but since I am most familiar with CS, I'll go over an example from there.
The problem domain arises from the design of caches. It is also applicable to any general search / query optimization and I'll talk about that briefly at the end. On to caches - I'm talking about the web sort here not the processor sort. So on to the problem itself:
Imagine you're building a large cache of webpages. You have the webpage itself on disk, but ideally you don't want to hit disk to avoid the 8ms hit. You can reference each webpage by some id, which is, say, a hash on the URL. One easy thing to do is to store all the ids in a hashtable using some reasonable hashing function. Even with perfect hashing, your hashtable is going to be size O(n) if you have to store n elements. This is fine if the number of documents you're storing is small , but if you have a large number of documents (1 billion docs * 8 bytes = 8G memory), and realistically you don't have a perfect hashing function, this can become quite cumbersome. So what do we do?
Enter bloom filters. Bloom filters are a type of probabilistic data structures that use some fixed number of bits and provide the guarantee that if an element is not found in the bloom filter, it does not exist in the cache. If an element is found, then it is in the cache, with very high probability. What this realistically means is that your bloom filter can say that you have something, when in reality you don't. In most cases this is okay, because the probability of this happening is sufficiently small.
The simplest kind of bloom filter is conceptually pretty easy to explain too. Lets suppose that you're hashing a set of elements S = {x1, x2, .. xn}. Lets use a bitset of a fixed size - say 1024 bits. Now we hash x1 => k1 where {k1..kn} is a number in 2^1024. Inserting an element x1, we hash it to k1 and flip that bit to 1. Thus your bloom filter looks like this:
x1 x3 x5
| | |
v v v
10010101010100000001100000
^
|
x2
x1 => k1
x2, x3 => k12
When we search for x1, the bit is 1, its a hit, we look for it and its there.
Similarly x2 hashes to k12 and the bit is 1, we look for it and its there.
Lets assume x3 is not there in our cache. We search for x3 and it hashes to k12 and the bit is 1 and we try to look for it and its not - its a false positive.
x5 hashes to k17 (or something like that) and the bit is 0, so we know definitively that the element is not in our set.
This is a brilliant optimization that helps out in a surprising number of search problems where the time hit on a false positive is acceptable.
I'm sure I didn't do a good enough job explaining bloom filters, so here's a great talk on the same. The first 10 minutes are really good and then he gets into a lot of very complicated stuff that optimizes various aspects of bloom filters. If you're implementing your own, I'd recommend the whole talk, else just the first 10 minutes or so.
Thus in the end, if you look at the problem definition of hash - "tell me, with certainty, whether a particular element exists in a set or not", its difficult (for space reasons). But if you change the problem definition to "tell me, with certainty, whether a certain element is not in a set, but you can be wrong about it being in the set", suddenly the problem becomes solvable along the space axis.
Monday, March 31, 2008
Snowboarding!
More snowboarding videos!
This time its Chris shooting the video with me (in yellow) going down the mountain.
The video was edited using iMovie, which is a nifty little program, if you ignore the really obvious bugs.
Enjoy!
Friday, March 21, 2008
Koenig lookup in C++
This is a nerdcentral post, so non-nerds (all two of you) can stop reading now.
I was dealing with some piece of code at work which looked like this:
// In some header file
namespace N {
class C {
...
};
void DoStuff(const C& c_obj) { ... }
} // namespace N
// In some .cc file
N::C c_obj;
...
DoStuff(c); // <-- Look! No need for N::DoStuff
I looked at DoStuff(c) without the N:: prefix and figured that it must be a bug. Someone forgot to put it in. But this code compiles fine - what gives?
I remember reading about this way back when I was really into C++ and thought it was the hottest stuff on the planet. Thankfully those days are behind me, but not everything that I learnt. So I dug into this a bit and finally came across Herb Sutter's article explaining exactly this.
Before you read the article or even read this one furthur, its a good exercise to try and figure out what's going on. What are the possibilities that would make this work? A good guess is someone did a
using namespace N;
somewhere up above. This would indeed make things work and this is why using namespace declarations are a very, very bad idea in header files. They're usually a bad idea in .cc files too, but less so than headers.
However, the above example isn't because of a using namespace somewhere up above. Instead, it is because of a feature of C++ called Koenig lookup. The basic idea is that besides the usual places where a compiler looks to resolve a symbol (local scope, global scope, etc) it must also look in the namespaces containing each of the parameters of the function. As a result, our good ol' compiler looks within namespace N as well, and lo and behold, there's DoStuff defined in N.
Why is this useful?
STL uses this feature quite a bit. Its "normal" to declare things like this:
namespace stl {
template
class datastructure {...}
}
} // namespace stl
template
void operator+(stl::datastructure& s1, const stl::datastructure& s2)
I'm not certain why this is better than declaring operator+ to be a part of datastructure itself (it will have the same effect), but this is C++ arcane voodoo that is beyond me. Anyway, I prefer using better tools these days, but now and then, we have to deal with languages that were really not intended for the ordinary mortal programmer.
I was dealing with some piece of code at work which looked like this:
// In some header file
namespace N {
class C {
...
};
void DoStuff(const C& c_obj) { ... }
} // namespace N
// In some .cc file
N::C c_obj;
...
DoStuff(c); // <-- Look! No need for N::DoStuff
I looked at DoStuff(c) without the N:: prefix and figured that it must be a bug. Someone forgot to put it in. But this code compiles fine - what gives?
I remember reading about this way back when I was really into C++ and thought it was the hottest stuff on the planet. Thankfully those days are behind me, but not everything that I learnt. So I dug into this a bit and finally came across Herb Sutter's article explaining exactly this.
Before you read the article or even read this one furthur, its a good exercise to try and figure out what's going on. What are the possibilities that would make this work? A good guess is someone did a
using namespace N;
somewhere up above. This would indeed make things work and this is why using namespace declarations are a very, very bad idea in header files. They're usually a bad idea in .cc files too, but less so than headers.
However, the above example isn't because of a using namespace somewhere up above. Instead, it is because of a feature of C++ called Koenig lookup. The basic idea is that besides the usual places where a compiler looks to resolve a symbol (local scope, global scope, etc) it must also look in the namespaces containing each of the parameters of the function. As a result, our good ol' compiler looks within namespace N as well, and lo and behold, there's DoStuff defined in N.
Why is this useful?
STL uses this feature quite a bit. Its "normal" to declare things like this:
namespace stl {
template
class datastructure {...}
}
} // namespace stl
template
void operator+(stl::datastructure& s1, const stl::datastructure& s2)
I'm not certain why this is better than declaring operator+ to be a part of datastructure itself (it will have the same effect), but this is C++ arcane voodoo that is beyond me. Anyway, I prefer using better tools these days, but now and then, we have to deal with languages that were really not intended for the ordinary mortal programmer.
Monday, March 10, 2008
Ted's mornings
This is my model of what Ted's mornings are like. Much cleaner room, of course, etc, but you get the point.
The Cult of Obama
It started with this twitter from obama's campaign:
"BarackObama: In Columbus,MS & wondering how somebody who's in second place is offering the vice presidency to the person who's in first place. Vote Tues!"
Hil-a-rious!
All things lead to YouTube and this message was no exception. In the links that followed on the reply twitters, I came across this video:
I'm a die hard obama supporter. I think the guy is awesome in many, many ways.
But that video freaked me out. That video is so singularly cult like that its not even funny. This follows on the heels of a piece I heard on NPR (podcasts) where the Wait, Wait folks make fun of Obama comparing him to Scientologists and got hordes of angry letters from the Obama supporters. Kind of like when they made fun of Scientologists and got hordes of angry letters from the Scientologists.
Edit: Kristin sent me this over IM:
Translation:
To the candidate who is Barack Obama
I sing this corrido with all my soul
He was born humble without pretension
He began in the streets of Chicago
Working to achieve a vision
To protect the working people
And bring us all together in this great nation
Viva Obama! Viva Obama!
Families united and safe and even with a health care plan
Viva Obama! Viva Obama!
A candidate fighting for our nation
It doesn't matter if you're from San Antonio
It doesn't matter if you're from Corpus Christi
From Dallas, from the Valley, from Houston or from El Paso
What matters is that we vote for Obama
Because his struggle is also our struggle, and today we urgently need a change
Let's unite with our great friend
Viva Obama! Viva Obama!
Families united and safe and even with a health care plan
Viva Obama! Viva Obama!
A candidate fighting for our nation
My take: OMG.
"BarackObama: In Columbus,MS & wondering how somebody who's in second place is offering the vice presidency to the person who's in first place. Vote Tues!"
Hil-a-rious!
All things lead to YouTube and this message was no exception. In the links that followed on the reply twitters, I came across this video:
I'm a die hard obama supporter. I think the guy is awesome in many, many ways.
But that video freaked me out. That video is so singularly cult like that its not even funny. This follows on the heels of a piece I heard on NPR (podcasts) where the Wait, Wait folks make fun of Obama comparing him to Scientologists and got hordes of angry letters from the Obama supporters. Kind of like when they made fun of Scientologists and got hordes of angry letters from the Scientologists.
Edit: Kristin sent me this over IM:
Translation:
To the candidate who is Barack Obama
I sing this corrido with all my soul
He was born humble without pretension
He began in the streets of Chicago
Working to achieve a vision
To protect the working people
And bring us all together in this great nation
Viva Obama! Viva Obama!
Families united and safe and even with a health care plan
Viva Obama! Viva Obama!
A candidate fighting for our nation
It doesn't matter if you're from San Antonio
It doesn't matter if you're from Corpus Christi
From Dallas, from the Valley, from Houston or from El Paso
What matters is that we vote for Obama
Because his struggle is also our struggle, and today we urgently need a change
Let's unite with our great friend
Viva Obama! Viva Obama!
Families united and safe and even with a health care plan
Viva Obama! Viva Obama!
A candidate fighting for our nation
My take: OMG.
Subscribe to:
Posts (Atom)