Estimating Bits and Bytes
The following extremely useful relation, specified in IEEE 1541-2002
Powers of 2^10 (1024) are very close to powers of 1000.
2^0 = 1 ~ 1000^0 [kibi] 2^10 = 1024 ~ 1000^1 [mebi] 2^20 = 1048576 ~ 1000^2 [gibi] 2^30 = 1073741824 ~ 1000^3 [tebi] 2^40 = 1099511627776 ~ 1000^4 [pebi] 2^50 = 1125899906842624 ~ 1000^5 [exbi] 2^60 = 1152921504606846976 ~ 1000^6
How many binary search function calls does it take to find one person in the million-person Manhattan phone book
The above lookup table can be used to answer this question.
The binary search is an O(log n) operation, assuming the array is sorted (like a phone book). In this case, we want log base 2 of one million,
Log base 10 is easy enough, but we have log base 2. Using the above table, 1M ~ 2^20:
How many strings with a specified length of 140 characters are in 10 terabytes?
Rumor has it Twitter generates around 10 TB a day. How many 140 character strings would that be, in Python?
Using compact arrays (which Strings are, by default), storing characters as unicode (16 bits, or 2 bytes, per character).
Taking the overly simplistic view that there is around another 100 characters attached with each tweet to indicate username, dates, etc., would make each string:
Maybe we're generous and allocate a whole 1000 bytes, to make it 1 KB, per tweet.
Then 10 TB is equivalent to:
That would be 10 billion tweets per day... Several orders of magnitude too high. A useful analysis nonetheless.
Computer Sciencenotes on computer science topics on the wiki, for educational and learning purposes
Part of the 2017 CS Study Plan.
Flags · Template:CSFlag · e