3 ms·
So she went linearly through the whole alphabet until he found the letter he wanted? Sounds like somebody should have used a binary search! Hey-oooo!
by mckilljoy 17y ago
So she went linearly through the whole alphabet until he found the letter he wanted? Sounds like somebody should have used a binary search! Hey-oooo!
- albertni 17y agoI wonder which would actually faster - binary search on the standard ordered alphabet or going linearly in order of letter frequency. Even better - some hybrid algorithm that goes through the most common letters then goes into binary search for the remaining letters (many of which appear at approximately equal frequency)
- mckilljoy 17y agoYou could probably also have a tree of the ~32 most common words. At the very beginning you could have a branch to choose whether you want to pick the 'word' tree or the 'letter' tree.
- ajuc 17y agoBinary search in unbalanced tree with shorter branches to more frequently used letters will be probably best (this is really huffman coding, isn't it?
- jey 17y agoFrequency order is analogous to Huffman coding while still being easy enough for a human to use, so it's probably better than binary search.