Comparison of Internal Sorting Algorithms

Sorting algorithm
Given an array of size N, sorting can be done in O(N log(N)) in average. The most frequently used sorting algorithms that can achieve this time complexity are quicksort, heapsort and mergesort. They usually require O(log(N)), O(1) and O(N) working space, respectively (the space complexity of mergesort can be improved at the cost of [...]

Read Full Post »

C++ Reduces Coding Time?

Just now I got an email from a mailing list, saying that C++ helps to greatly reduce coding time in comparison to C. I have heard a lot about this argument. But is that true?
C++ can possibly accelerate development in two ways: firstly, OOP (Object-Oriented Programming) helps to organize large projects, and secondly, STL (Standard [...]

Read Full Post »

Derivative-Free Optimization (DFO)

You can find good subroutines in GSL for multivariable nonlinear optimization, but the only method it provides for DFO is Nelder-Mead simplex method, which, claimed by Numerical Recipes, is “almost surely” slower than the Powell’s direct set method “in all likely applications”. You can find some DFO solvers here, but few of them are implemented [...]

Read Full Post »

Improved GNU sort (from textutils-1.22)

GNU sort is one of my favorite program. It is fast and highly flexible. However, when I try to sort chromosome names, it becomes a pain. In bioinformatics, chromosomes are usually named as chr1, chr2, …, chr10, chr11, … chr20, …, chrX and chrY. It seems to me that there is no way to sort [...]

Read Full Post »

Garbage Collection for C

I was ignorant. An hour ago, I thought it is impossible to implement a garbage collector (GC) for C, but this is certainly wrong.
For an interpretated language like Perl, it is cheap to keep track of memory that is not referenced and therefore it is not so hard to identify and free unused memory in [...]

Read Full Post »

Memory Allocation on the Heap vs. on the Stack

This topic sounds pretty elementary, but I did not know the difference a week ago. Just explain it here as a record. You may also want to have a look at this page.
Memory can be allocated on the heap or on the stack. When a program calls malloc() family, the memory will be allocated on [...]

Read Full Post »

C++ iostream can be Slooow…

A colleague of mine just told me that C++ iostream is typically an order of magnitude slower than printf. His example shows that printing out a string like “%s\t%d\tabc\t%s\t%s\n” with C++ iostream is 3 times slower than printf in Perl! This observation agrees my experience, although I have never done any benchmark. I abandoned iostream [...]

Read Full Post »

Mastering C Pointers (or not)?

C pointer is the most powerful and nasty concept. Whether marstering C points or not separate intermediate C programers from the elementary ones. Want to know whether you have mastered C pointers? Have a look at this program. If the basic idea is clear to you, you are qualified to be an intermediate programmer. If [...]

Read Full Post »

Language War

Language war denotes the debate over which is the best programming language, especially between languages with similar applications like C/C++, C++/Java and Perl/Python. A lot of programmers, including me, are absorbed in this debate. They write articles; they design benchmarks. However, they can never come to a unanimous conclusion. Language war is never ending.
The long-lasting [...]

Read Full Post »