Shining || Responsive?

Google recently previews its new Google Maps. The new interface looks more comprehensive and stunning:

However, the trade-offs are speed and memory comsumption.
 
At the time of writing this post, I still favor the classic Google Map which offers a much simpler UI but more responsive experience.

New Google Map 

Image Name                     PID Session Name        Session#    Mem Usage
========================= ======== ================ =========== ============
iexplore.exe                  1804 Console                    1    461,972 K 
firefox.exe                   4800 Console                    1    645,508 K

Classic Google Map

Image Name                     PID Session Name        Session#    Mem Usage
========================= ======== ================ =========== ============
iexplore.exe                  4148 Console                    1    160,116 K
firefox.exe                   1204 Console                    1    221,092 K

Software design needs to strike a balance between performance and functionality and UI in order to provide great user experience for customers. So,

1. Do you really prefer the Shining map to the Responsive one, when you are running out of time for catching a flight, but only eager to know the fastest route to the airport?
2. User-oriented is good, but not glod-plating

Evolution of a Programmer :)

http://www.ariel.com.au/jokes/The_Evolution_of_a_Programmer.html

Subset, Combination and Permutation (Recursion)

#define MAX_K 100 

void subset_rec(
    const char *cont, 
    const size_t start, 
    const size_t n,
    char *res, 
    const size_t last)  
{
    size_t i;

    // print (res, last);
    for (i = start; i < n; i++) {
        res[last] = cont[i];
        subset_rec(cont, i+1, n, res, last+1);
    }
}

void subset(const char *content, const size_t n) {
    char *result;
    result = (char*)malloc(MAX_K * sizeof(char));
    subset_rec(content, 0, n, result, 0);
    free(result);
    result = NULL;
}

void comb_rec(
    const char *cont,       // pointer to combination's content
    const size_t start,     // starting index of the content
    const size_t n,         // n of C(n,k)
    const size_t k,         // k of C(n,k)
    char *res,              // pointer to one combination generated so far
    const size_t last)      // length of the result
{
    size_t i;

    if (k == 0) {
        // print (res, last);
    } else {
        for (i = start; i < n; i++) {
            res[last] = cont[i];
            comb_rec(cont, i+1, n, k-1, res, last+1);
        }
    }
}

void combination(const char *content, const size_t n, const size_t k) 
{
    char *result;
    if (k > n || k == 0 || n == 0)  return;
    result = (char*)malloc(MAX_K * sizeof(char));
    comb_rec(content, 0, n, k, result, 0);
    free(result);
    result = NULL;
}

void perm_rec(
    char *cont, 
    const size_t n, 
    const size_t k, 
    char *res, 
    const size_t last)  
{
    size_t i;
    char t;

    if (k == 0) {
        // print (res, last);
    } else {
        for (i = 0; i < n; i++) {
            t = cont[i];
            res[last] = t;                          // A B C D
            memmove(cont+i, cont+i+1, n-i-1);       // A C D
            perm_rec(cont, n-1, k-1, res, last+1); 
            memmove(cont+i+1, cont+i, n-i-1);       // A A C D
            cont[i] = t;                            // A B C D
        }
    }
}

void permutation(const char *content, const size_t n, const size_t k) 
{
    char *result;
    if (k > n || k == 0 || n == 0)  return;
    result = (char*)malloc(MAX_K * sizeof(char));
    perm_rec((char*)content, n, k, result, 0);
    free(result);
    result = NULL;
} 

For the permutation of set that contains duplicates, the solution can be found here:
https://oj.leetcode.com/discuss/16264/a-simple-recursion-solution-c

Tail Call

// Non tail-call optimization
// Because the last statement is n+sum1() in the function call, 

// which triggers the saving of sum1()'s current context, then do the next call
int sum1(int n) {
 return (n <= 0) ? 0 : n+sum1(n-1);
}

// We can skip this step by passing the current sum as an argument in the function
int sum2(int n, int cur) {
 return (n <= 0) ? cur : sum2(n-1, cur+n);
}

The processor time it takes to execute these two functions are (N is the # of repetitions):

   N      sum1      sum2
 1000     1123      1061
10000    13213     12839

Ref.: http://c2.com/cgi/wiki?TailCallOptimization

Thoughts on Sorting

I compared the basic in-memory sorting algorithms against the standard sorting functions in C/C++ (qsort/sort) on my x86 machine today. Although the results were preliminary, it did confirm some ideas in sorting techniques:

       Sort Type    Sorted       Nearly Sorted              Random            Reversed           All Equal
       =========    ------       -------------              ------            --------           ---------
  Selection Sort    29.1090             29.2660             33.7420             28.9850             29.0480
  Insertion Sort    0.0000              0.0150             21.3410              0.0000              0.0000
      Merge Sort    0.0310              0.0160              0.0310              0.0310              0.0310
        Qck Sort    57.6120              1.5760              0.0460             57.7990             18.6420
   Rand Qck Sort    0.0150              0.0160              0.0150              0.0310             18.5490
  R.Qck+Ins Sort    0.0000              0.0160              0.0310              0.0000              0.0150
     C lib qsort    0.0000              0.0160              0.0160              0.0000              0.0000
    C++ lib sort    0.0000              0.0000              0.0150              0.0000              0.0160

• 100K integers are used to perform the test and the CPU time is recorded
• The 1st column lists the sorting methods.
• The 1st row is the arrangement of integers in the test array: already sorted, almost sorted (99.99% sorted), unsorted (random order), reversely sorted and all equal.

The comparison shows that:

1. The qsort/sort in standard library outperforms other user defined sorting functions in many cases. So use them when in doubt;
2. Insertion sort works fine if the input data is sorted or "mostly" sorted;
3. Merge sort performs nearly same under all cases, so does selection sort; but the former one is O(n*lgn) in time with O(n) in space;
4. Not randomized quick sort works OK only if the input data is in random order; it performs badly O(n^2) when data is sorted or nearly sorted (beware of the deep recursion! set the stack size accordingly); 
5. Quick sort works faster when partitioned from two sides, optimized by randomization and combined with insertion sort (Programming Pearls, Sorting);
6. Choose the "right" sorting strategy based on the data size, data order, memory/time req., ...

Test on gcc 4.6.2