{"id":11,"date":"2005-10-17T22:35:00","date_gmt":"2005-10-18T05:35:00","guid":{"rendered":"http:\/\/www.mccambridge.org\/blog\/2005\/10\/lesson-learned-1-billion-times\/"},"modified":"2022-09-11T00:40:50","modified_gmt":"2022-09-11T00:40:50","slug":"lesson-learned-1-billion-times","status":"publish","type":"post","link":"http:\/\/www.mccambridge.org\/blog\/2005\/10\/lesson-learned-1-billion-times\/","title":{"rendered":"Lesson Learned. 1 billion times."},"content":{"rendered":"

I learned a valuable lesson today. Specifically, one billion<\/font> is a huge number that should never be considered as an acceptable dataset size to do a sequential search on. Possibly the most retarded thing I’ve done this week was decide that it would be a good idea to look through a billion pieces of data one by one to solve a computer program. To get an idea for how infernally stupid<\/font> that was, pick a number from zero to 1 billion. I am now going to guess your number in the same fashion as my retarded program.<\/p>\n

Is it one?
\nIs it two?
\nIs it three?
\n…
\nIs it four million, three hundred-twenty-four thousand, six hundred and
\nfive?
\n…<\/p>\n

You see the idiocy? Now consider the smart way. I bet you I can guess your number in 30 questions or less. (Pretend we picked 103,456)<\/p>\n

Is it greater or less than…
\n1: 500 million? less<\/em>
\n2: 250 million? less<\/em>
\n3: 125 million? less<\/em>
\n4: 62,500,000? less<\/em>
\n5: 31,250,000? less<\/em>
\n6: 15,625,000? less<\/em>
\n7: 7,812,500? less<\/em>
\n8: 3,906,250? less<\/em>
\n9: 1,953,125? less<\/em>
\n10: 976,562? less<\/em>
\n11: 488,281? less<\/em>
\n12: 244,140? less<\/em>
\n13: 122,070? less<\/em>
\n14: 61,035? greater<\/em>
\n15: 91,553? greater<\/em>
\n16: 106,812? less<\/em>
\n17: 99,182? greater<\/em>
\n18: 102,966? greater<\/em>
\n19: 104,904? less<\/em>
\n20: 103,934? less<\/em>
\n21: 103,449? greater<\/em>
\n22: 103,692? less<\/em>
\n23: 103,570? less<\/em>
\n24: 103,509? less<\/em>
\n25: 103,479? less<\/em>
\n26: 103,464? less<\/em>
\n27: 103,456? equal<\/strong><\/em><\/p>\n

That definitely seems to be an improvement. My program agreed. Last time, it ran for 15 minutes before I gave up and killed it, far from an answer. This time it took 1.042 seconds.<\/p>\n

Lesson Learned.<\/p>\n","protected":false},"excerpt":{"rendered":"

I learned a valuable lesson today. Specifically, one billion is a huge number that should never be considered as an acceptable dataset size to do a sequential search on. Possibly the most retarded thing I’ve done this week was decide that it would be a good idea to look through a billion pieces of data […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/posts\/11"}],"collection":[{"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/comments?post=11"}],"version-history":[{"count":1,"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/posts\/11\/revisions"}],"predecessor-version":[{"id":1888,"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/posts\/11\/revisions\/1888"}],"wp:attachment":[{"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/media?parent=11"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/categories?post=11"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.mccambridge.org\/blog\/wp-json\/wp\/v2\/tags?post=11"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}