Hash Functions (Part I)

September 29, 2015

Hash tables are a great way of ensuring O(1) access to your data. Well, it does, but as long as the hash function is good.

7e4156dfac4d82e9a5cab4987ecc3a15

But what exactly makes a hash function a good hash function?

Read the rest of this entry »


Coding by ear

September 22, 2015

I just got one of my computer’s fans repaired. It was still working, but noisy like a diesel engine. While I started savoring the relative quietness of my study again, I noticed that I lost something with that repair. I lost a source of information about what my computer is doing.

vroum-vroum

The fan speed—and noise—varied with the CPU temperature, which in turn varies with its clock speed and workload. The harder the machine works, the noisier it got. At first, you night think (correctly, for that matter) that having a noisy computer is annoying, but I think you can turn that to your advantage while coding.

Having an actual, noisy, grinding fan is an annoyance. But what if we paid attention to the noise our computer makes, use it as a development tool?

It’s easy to forget that a computer is just a machine like any other, and that an intensive computation, in addition of taking time, also consumes power, dissipates heat, and cause wear—especially when disk IO is used intensively. Therefore being aware of what our code does to our computer may make us better coders.

If you don’t benefit from a noisy fan, you can still use the machine’s sensors to keep you informed on what goes on in your box.

  • Sensors. You can use Linux’s sensors command to get a snapshot of your box’s health. The package you need to install varies from a distribution to another, on Debian-like it’s the package lm-sensors. Invoking sensors, maybe within a pretty-printing script, combined with watch (say, watch -n 1 sensors) will let you see what happens.
  • htop, iotop, and nethogs. htop is a prettier, configurable, version of top. It does the essential: processes, process trees, threads, etc. The iotop command needs to be run as root, but will show you what happens with disk IO. nethogs does the same thing for network bandwidth.
  • Conky and other system monitors. A good while ago, I wrote a piece on conky, a simple but highly configurable system monitor. It’s kind of old school (no rounding plasma 3D widgets) but gets the job done. I’ve integrated sensors to it so it also displays the CPU temperature and fan speeds.

*
* *

Listening to your computer doesn’t replace good software practices (good algorithms, profiling and hunting for hot spots) but complements them. If you hear your HD scratching a whole lot more that it should, you have gained a few bits of information—something unexpected is happening.

*
* *

In a way, that noisy fan helped me refine my code in more than one occasion. It reminded me that I should be coding for a Pentium III (something I think I advocated before), and that if my program was making my computer noisier, then it probably consumed more resources—CPU, IO, power—than it should have. Keeping my computer quiet forced me to write better, faster, more frugal code.

Keeping an eye on the machine exertion symptoms may help you write better code, especially when scaling is considered. If your program adds 20 degrees to your computer’s internal temperature, how will it scale to service a hundred time more requests?


π like an Egyptian

September 15, 2015

In the Rhind Mathematical Papyrus (RMP) we find that the Egyptians used the approximation

\displaystyle 4\times\left(\frac{8}{9}\right)^2 =4\times\frac{64}{81} =\frac{256}{81} \approx{3.16}

For \pi. The RMP shows how to arrive at this result: you construct a 9\times{9} grid and draw an octagon on it that approximates the circle. Turns out this irregular octagon as \frac{7}{9} of the area of the bounding square. But the ancient Egyptians rounded that value, for reasons unknown, from 63 to 64 (I have a theory on why; but that may be a later post). This gives the above approximation.

egyptian-pie-crop-small

Read the rest of this entry »


King Solomon’s Bath

September 8, 2015

In 1 Kings 7 (King James version), we read the description of Solomon’s molten sea:

And he made a molten sea, ten cubits from the one brim to the other: it was round all about, and his height was five cubits: and a line of thirty cubits did compass it round about.

bath

…which I take is some kind of bath. Superficially, it seems to state that \pi=3, since the circumference of a circle of diameter d given by \pi d=2\pi r. But what if “round about” doesn’t strictly means “perfect circle”?.

Read the rest of this entry »


Optimizing JPEG for bandwidth

September 1, 2015

Optimizing web content is always complicated. On one hand, you want your users to have the best possible user experience, but on the other hand, you don’t really want to spend much bandwidth delivering the bits.

compteur-small

This week, let’s have a look at how we can optimize images for perceptual quality while minimizing bandwidth. While we could proceed by guesswork—fiddling the parameters until it kind of looks OK—or we can take 5 minutes to write a script that searches the parameter space for the best solution given a constraint, say, perceptual quality.

Read the rest of this entry »