« Academic Irrelevance | Main | Malkovich. Malkovich. Malkovich. Malkovich. »

October 13, 2005


Daniel Lemire

I must have known intuitively about random algorithms for a long time, since my filing system has a lot of randomness to it.

Kidding aside, here's what I do at the office.

1) New piece of paper comes in.

2) I will just drop it into one of the k piles I've got on my desk where k \approx 3.

3) When I search something out, I simply look first if I see it on top of one of the k piles, if not, I start browsing each one of the piles.

4) Once done with the paper, go back to 1.

Intuitively, having k piles is better than having 1. Interestingly, that's what introduces randomness into my sorting.

I'm too lazy this morning to do an analysis of this algorithm, but if someone does, please drop me a line.


This is a 1993 invention? Hmmm, I think that Noguchi-san might have taken this idea from a programmer. Japanese Word Processors allow you to type in hiragana, but when you hit the space key to signal the end of the word, all the kanji that correspond to the phonetic arrangement you just typed pop up in a little menu. The kanji are numbered, and when you choose one, it pops to the #1 on the list, so the next time you type that combination of syllables, it's your first choice (the default setting are by general language frequency of use). It's not out of the question that a writer who saw this applicaiton of the algorithm appear before him on a daily basis would try to apply it somewhere else. Good observational skills, though.

The comments to this entry are closed.