Category Archives: Programming

Bitwise binary search

A binary search is not a very interesting topic as it is a well known and fairly simple algorithm. However, I have encountered an interesting variant of it lately – one that I would like to share.

The Linux Kernel defines one Jiffy as the period of time between two consecutive system timer interrupts, and keeps a “jiffies” counter. Having jiffies, the next handy parameter would be the amount of delay-loop iterations that the CPU is able to fit in a single jiffy. With this number at hand (and known timer frequency) the kernel is able to support fine-grained execution delays, for instance. How would you implement computation of said “loops_per_jiffy” parameter?

Continue reading Bitwise binary search

Python directing C++

Every programming language has its benefits and its drawbacks. Python, for example, provides a dynamic and clean environment for the developer, which boosts productivity by hiding much of the “dirty work”: memory management, type inference (duck typing, in this case), and more. Such benefits usually come at the cost of efficiency, which is something that other programming languages (such as C++) excel in.

The next logical step would then be a way to combine the benefits of such different programming languages in a single system. For instance, we could use C++ solely for the cpu-intensive parts, while the rest of the software could very well be written entirely in Python. The missing piece would then be a way to integrate the two. The common way of doing so is through SWIG, which is a tool that is able to wrap C++ to many different programming languages, Python included. Using SWIG right out of the box, we will be able to invoke C++ code directly from a Python interpreter. But what if we wanted to extend C++ classes in Python, making native C++ seamlessly call Python code?

Continue reading Python directing C++

Fixing incorrect photo data

A few months ago I have been to the states. Naturally, one big outcome of that trip was a handful of photographs documenting it – 1.6GB of these, to be precise. The bad part is that I have forgotten to reset the camera settings beforehand, which made all the pictures date a few years back.

The images I made with my Cannon camera (sx110) use JPEG for compression, and Exif for the metadata – including the date and time the picture was taken, which is what we’re interested in. Being as perfectionist as I am, and having some familiarity with Python, I set out to modify the metadata on the pictures to contain the right dates for the trip.

Continue reading Fixing incorrect photo data

Bounded size priority queue

A priority queue in the STL is nothing more than a regular (maximum-) heap. It is essentially an adapter built on top of another container, usually a vector. Therefore, the offered priority queue can easily contain an arbitrary number of elements (so long as memory permits).

But what if we wanted to keep only the biggest N elements, and just have the queue dynamically throw away all other elements? I am sure you can imagine why such a behavior would be much desired: for instance, keeping the best N suggestions for a specific search term springs to mind. Unfortunately, the STL does not support such an adapter.

Continue reading Bounded size priority queue