Programming the 6502 Book

Indeed Programming Pearls!

Short Summary
Part I: Preliminaries
Column 1: Cracking The Oyster (defining the problem correctly)
Principles: Defining the right problem is critical Problem: How do I sort a large file?
The programmer wanted to sort a large file with limited memory but the critical piece of information was that the numbers are in a specific range (7 digits only) and so the solution was to use a bit vector.

Column 2: AHA! Algorithms (designing the algorithm for the problem)
Principles: Sorting can be used to accomplish tasks that are not related to ordering records for example with grouping anagrams (Problem 3 in the chapter). Binary search is a very important algorithm as well. Good programmers sit and wait for an insight rather than rushing to code. The problems in this chapter are beautiful problems. Find the missing number, rotating an array and finally grouping anagrams. Detailed implementation of each beautiful solution is included.

Column 3: Data Structures Programs (choosing the right data structure)
Principles: Don't write a big program if a little one can do. Don't write 300 variables if you can use a simple array for example. If you need fancy data structures, use classes. Sometimes solving the general problem for n is easier that targeting a specific case (Inventor's paradox). Stressing on Data Structures. Data Structures can replace complicated programs.

Column 4: Writing Correct Programs
Don't write programs and fix the bugs later. Sometimes a real understanding of the problem and the solution will lead to correct programs This column studies binary search in details, although it seems trivial, many programmers fail to write binary search correctly from scratch! Use program verification and assertions to make sure your programs are correct!

Column 5: A small matter of programming
Detailed implementation of binary search along with testing it emphasis on using assert.

Part II: Performance
Column 6: Perspective On Performance
If you need to speed up your program, consider first all possible levels and see which level will give you the best speedup but if you need a big speed up you will need to work at each level.

Column 7: The Back of the Envelope
Basic estimation skills are important. Example: struct node { int i; struct node *p; };
will two million such nodes fit in a memory of 128mb?
4 bytes for the int and 4 bytes for the pointer => 2M * 8Bytes = ~ 16MB
Another useful tip is Little's Law: The average number of things in the system is the product of the average rate at which things leave the system and the average time each one spends in the system.
Example: If you're waiting in line for a place that holds 60 people, each person spends on average 3 hours at the place then the rate of entering the place is 20 people per hour. If the line has 20 people then the wait will be an hour!

Column 8: Algorithm Design Techniques
This column describes several design techniques used to develop a solution to the problem of find the maximum sum found in any contiguous subarray of the array given. (Hint: Kadane)
The first solution presented was the naive solution which will take n^2. Two techniques are presented at the beginning to reduce the time slightly but not enough to reduce the overall complexity of n^2.
Divide and Conquer is used after that to reduce the complexity (very nice technique here, I should go back to this again and look at it more, page 79). The linear algorithm is presented at the end with a beautiful explanation as well. I should go back to this.

Column 9: Code Tuning

- Profiling can be used to identify the hot spots of the code. Which piece is accessed the most. Once that is known (in the example it was malloc! so caching was implemented) you can find a solution faster.
- Mod in another example was expensive, how to get rid of Mod? There is a nice little trick (k = j + rot); if ( k >= n ) { k -= n; }.
- Another useful thing is to use inline functions for faster access.
- Linear search: for (i = 0; i <= n; i++) { if (a[i] == t) { return i; } return -1. This can be optimized with this magical trick. replace the last element with t. hold = x[n]. x[n] = t. now for (i = 0; ; i++) { …. } now put back x[n] = hold. if i == n return -1 else return i (though shouldn't we test if hold == t?) from (4.06 nanoseconds to 3.87)
- Further reduction to linear search: (1.70 nanoseconds)

x[n] = t
for (int i = 0; i += 8) {
if (x[i] == t) { break; }
if (x[i+1] == t) { i += 1; break; }
if (x[i+2] == t) { i += 2; break; }
if (x[i+3] == t) { i += 3; break; }
if (x[i+4] == t) { i += 4; break; }
if (x[i+5] == t) { i += 5; break; }
if (x[i+6] == t) { i += 6; break; }
if (x[i+7] == t) { i += 7; break; }
}

- Computing Spherical Distances to find the nearest neighbor example: instead of using longitudes and latitudes, they converted them to coordinates x, y and z and so the distance function became much simpler.
- Binary Search major code tuning

Column 10: Squeezing Space
Do you really need 32 bit for each integer or can you do with 16? Do you really need a matrix representation for the graph? or can a linked list representation work? Many strategies are discussed: recomputing (use a function to test for prime numbers instead of storing all prime numbers) data compression, allocation policies (dynamic allocation instead of static), garbage collection.

Part III: The Product
Column 11: Sorting
Code tuning techniques to speed up insertion sort by a factor of 4 and quick sort by a factor of 2

Column 12: A Sample Problem
Discussion of the problem, given n and m where m < n, choose m random elements from 0 to n - 1. Each element is selected once (no repetition).

Column 13: Searching
A discussion and comparison of five different data structures to represent a set of integers (Sorted Array, Sorted List, Binary Trees, Bins and Bit Vectors).

Column 14: Heaps
Implementation and a discussion of those sexy heaps.

Column 15: Strings of Pearls
First an implementation and a discussion of a hash table. The second part discussed the problem: give a text file, find the longest duplicated substring of characters which is solved by suffix arrays!