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
Tuesday, July 30, 2013
Monday, June 24, 2013
Friday, March 22, 2013
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
Saturday, March 16, 2013
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
Thursday, January 24, 2013
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
The comparison shows that:
Test on gcc 4.6.2
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:
- The qsort/sort in standard library outperforms other user defined sorting functions in many cases. So use them when in doubt;
- Insertion sort works fine if the input data is sorted or "mostly" sorted;
- 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;
- 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);
- Quick sort works faster when partitioned from two sides, optimized by randomization and combined with insertion sort (Programming Pearls, Sorting);
- Choose the "right" sorting strategy based on the data size, data order, memory/time req., ...
Test on gcc 4.6.2
Subscribe to:
Posts (Atom)