Counting Cards
Posted by Phil Aaronson at 8:47 PM
I attended a talk today entitled Data Stream Algorithms given by
Ravi Kumar. Apparently data stream computation was big back in the 60s and 70s when computer memory was expensive and data didn't fit. It fell out of favor over the last couple decades as the cost of RAM dropped and the data sizes stayed relatively the same. But lately data stream algorithms have come back in vogue as a way to deal with massive data sets.
I don't know much about the field, but as he was describing a few algorithms it struck me: these are all in a sense, like counting cards. The idea is to make a pass through the data without trying to hold the whole thing in memory, just keep a few cleverly chosen indicators. In just the same way card counters don't try to memorize all the cards seen, but instead keep a running set of indicators on how "hot" the deck is.
Coincidentally Ed Thorp came up with card counting in the sixties, and wrote a book on it.
Just for fun, pull out a deck of cards. Make a pass through and keep track of how many aces you've seen. As you get to the last few cards, I'm sure you'll have no problem saying how many aces remain. Shuffle and make another pass through and try and keep track of how many aces as one count and how many tens and face cards as another count and try to predict the number remaining in the last few. Now go for more. The best I seem to be able to do is three sets of numbers. And even then I start to noticeably slow down.
Ravi Kumar. Apparently data stream computation was big back in the 60s and 70s when computer memory was expensive and data didn't fit. It fell out of favor over the last couple decades as the cost of RAM dropped and the data sizes stayed relatively the same. But lately data stream algorithms have come back in vogue as a way to deal with massive data sets.
I don't know much about the field, but as he was describing a few algorithms it struck me: these are all in a sense, like counting cards. The idea is to make a pass through the data without trying to hold the whole thing in memory, just keep a few cleverly chosen indicators. In just the same way card counters don't try to memorize all the cards seen, but instead keep a running set of indicators on how "hot" the deck is.
Coincidentally Ed Thorp came up with card counting in the sixties, and wrote a book on it.
Just for fun, pull out a deck of cards. Make a pass through and keep track of how many aces you've seen. As you get to the last few cards, I'm sure you'll have no problem saying how many aces remain. Shuffle and make another pass through and try and keep track of how many aces as one count and how many tens and face cards as another count and try to predict the number remaining in the last few. Now go for more. The best I seem to be able to do is three sets of numbers. And even then I start to noticeably slow down.
1 Comments:
... and then you have to learn to count multiple indicators while looking relaxed, chatting a bit, and drinking the free drinks :)
Post a Comment
<< Home