Tag Archives: Fight

[Programming Pearls] Column 7 – The Back of the Envelope

Well, I understand the phrase “the back of the envelope” as fast rough estimation / calculation that people can do on the back of en envelope…So this column is mainly about rough calculation / estimation…I’ll mark some of the points from the book here.

How much water flows out of the Mississippi river every day
This is the beginning question in this column. But if you look at the river as a big long cube, then the result = speed (meter/day) * depth (meter) * width (meter)

- One point here is to make sure that dimension-wise, the calculation is correct ( meter^3 / day ).
- The other point is we can look at the problem from different angles, like the rainfall is X m / day, and the ‘flat size’ of the river is Y m^2, then the result = X * Y. Because roughly speaking, the water that flows in should equal to that flows out.

Casting out nines
This is a trick (that I didn’t learn in my childhood but I should…) to quickly verify if the sum / difference / multiplex is correct or not. Like 2045 + 5331 = 7376.
2045: 2 + 0 + 4 + 5 (- 9) = 2
5331: 5 + 3 + 3 + 1 (- 9) = 3
7376: 7 + 3 + 7 + 6 (- 18) = 5
2 + 3 = 5.

Rule of 72
This is pretty useful. Basically it calculates m = n * (1 + x%)^y. If x * y = 72 then roughly m = 2n

Constants…Rule of thumb
- Well, roughly, 2^10 = 1,000 (K), 2^20 = 1,000,000 (M), 2^30 = 1,000,000,000 (G), etc
- PI second is a nano-century, which is 100 * 10^(-9) = 10^(-7) year => 1 year = PI * 10^7 second. OK let’s look at the dimensions: micro (-3), milli (-6), nano (-9), etc

Little’s Law
This is interesting, IT example here: suppose you have an online system, the incoming request rate is N requests / second, and it takes M seconds to process it in the system; so at one point on average there will be N * M requests that is in processing.

Another restaurant sample: assume you are waiting in line for a restaurant that can tolerant N people, and on average people eating there spend M hour in there; then the speed of entering that restaurant is N / M people / hour. So what you can do is look at how many people in the line are in front of you, then you can make a calculation how long do you need to wait…

- (This is from real life) One of my colleague has a program that has 600 threads, each thread sleeps for 50ms and then wakes up to do some IO (database ops) for 10ms, etc. So what is the active thread count at one point on average?
Answer: Applying little’s law – so the activation is 50 + 10 = 60 ms / activation, or 1/60 activation/ms; the living time is 10ms. So the average count is 600 * 1/60 * 10 = 100 threads.

- In what situation, hand over materials by postman on bicycle is faster than high-speed Internet?
Answer: Huge size of materials that can be put in a U-disk. Prove it with data (Internet speed, etc).

- The death rate in your city?
Answer: According to the little’s law, assuming city population is somewhat fixed at N, and on average people stay in the city (living…) spend 70 years, then the rate is N / 70…

[Programming Pearls] Column 6 (Part II Beginning) – Performance

So, another post without code…- -

Part I covers different aspects of programming. And Part II is going to focus on one area: performance. Column 6 is the first chapter and it gives a case where a certain program (movement simulation in gravitational situation) can be speed up by 400 times. This is achieved by optimizing at different levels: algorithm, data structure, code tuning, data structure tuning, hardware upgrading, etc. So as program or IT solution is multi-level thing, performance optimizations are multi-level too.

[Programming Pearls] Column 5 – Small Matters of Programming

OK so in this post I won’t include any code actually…honestly it’s just to mark that I’ve gone through column 5. BTW it’s also the closure of part I – programming preliminaries.

The content of programming pearls is very well design and organized. So far (for part I) it shows the process and the keys for programming: understand and define the problem – design algorithms – design data structure – the practice of writing correct program and verification – then comes to this column: different matters during programming, like scaffolding, assertions, functional / unit test, perf benchmarking, etc.

On a side note, programming is not a fixed thing: there are far more than one models to define a problem, there are lots of choices of algorithms depending on your problem model and primitives, there are a lot of data structure choices that could impact your algorithm or even problem definition. Things are linked together and reflect each other. It’s a process of evolution: understand the problem gradually, refine algorithm / data structure gradually, etc. And the usage of different skills like debugging, asserting, scaffolding will help speed up the process.

BTW, it’s interesting to see it’s mentioning a book published by M$ which talks about M$ assertion best practices…