Programming Pearls, 2Ed
Download 32.32 Kb.
|
- Navigate this page:
- Bulk memory allocations ( in C ) Functions, macros and inline code Sentinel
- Cache-sensitive memory layouts
- Sorted array Sorted
- Space-For- Time
- Time-For- Space
| Programming Pearls, 2Ed
(ISBN: 0-201-65788-0) Column 1 – Cracking the Oyster The right problem Bitmap (BitSet) data structure Multi-pass algorithms Time-Space tradeoff and one that isn’t Simple Design Stages of program design Column 2 – Aha! Algorithms Sorting Binary search (find first occurrence of t) Signatures Problem definition A problem’s solver perspective – know the proper time to code Column 3 – Data Structures Programs Rework repeated code into arrays Encapsulate data structures Use advanced tools: name-value pairs, spreadsheets, databases, etc Let the data structure the program Column 4 – Writing Correct Programs Initialization, Preservation, Termination Assertions (Invariants) Sequential control structures Selection control structures Iteration control structures Functions: precondition, postcondition Column 6 – Perspective on Performance Problem definition System structure – decomposition to modules Algorithms and data structures Algorithm tuning Data structure reorganization Code tuning System software Hardware If you need a little speedup – work at the best level If you need a big speedup – work at many levels Column 7 – The back of the Envelope Two answers are better than one Quick checks Rules of thumb: “Rule of 72” Pi seconds is a nanocentury (1 year = 3.155 x 10^7 seconds) Practice Safety factors 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. The average number of objects in a queue is the product of the entry rate and the average holding time. Column 8 – Algorithm Design Techniques Save state to avoid recomputation Preprocess information into data structures Divide-and-Conquer algorithms Scanning algorithms: N-1 => N Cumulatives (cumulative arrays) Lower bounds Column 9 – Code Tuning Caching Bulk memory allocations (in C) Functions, macros and inline code Sentinel Loop unrolling Data structure augmentation Recursion -> Iteration Swap -> Inline + Optimize Integer remainders: ( sth % N ) = ( sth & N ) or ( sth – N if sth in [N, 2N] ) Column 10 – Squeezing Space Know the cost of space “Hot Spots” of space Don’t store, recompute Sparse data structures Data compression – alternative ways to store the same data (hashing) Allocation policies – dynamic allocation Variable-length records Garbage collection Sharing storage Cache-sensitive memory layouts Tradeoffs Environment Column 11 – Sorting Insertion sort Quicksort: One-sided partition (O(n^2) worst case with N equals!) Two-sided partition Partition around random element or Pivot Don’t partition short arrays and use insertion sort when finished Column 13 – Searching Set: Sorted array Sorted linked list (more memory, worse memory access patterns) Binary tree (TreeSet) Hashtable (HashSet) Bitset (32 bits per word) Column 14 – Heaps See “Beginning Algorithms.doc” Column 15 – String of Pearls Hashtable Balanced trees Suffix arrays Longest duplicated substring: Build suffix array Sort suffix array (to bring together equal siffixes) Generate random text – Markov chain: Build suffix array pointing to word boundaries and sort it Hashtable: prefix -> all possible suffixes Appendix 1 – A Catalog of Algorithms Sorting: Insertion sort Quicksort Heapsort Mergesort Bitmap sort Multiple-pass sort Searching: Sequential search Binary search Hashtable Binary search trees Key indexing (keys are used as array indexes) Appendix 4 – Rules for Code Tuning Space-For-Time: Data structure augmentation Store precomputed results Caching Can backfire if locality is not present in the data Lazy Evaluation Time-For-Space: Packing – dense storage Sparse arrays Overlaying Interpreters Function definition Loop: Code motion out of loop Combining tests (sentinel!) Loop unrolling Loop fusion Logic: Exploit algebraic identities – replace evaluation by equiv expression Short-circuiting monotone functions – exit from loop no later than Reordering tests Precompute logical function Boolean variable elimination Procedure: Collapsing function hierarchies Exploit common cases Coroutines Transformations on recursive functions Iteration Iteration using stack Tail recursion elimination Don’t solve small sub-problems with recursion Parallelism Expression: Compile-time initialization Exploit algebraic identities Common subexpression elimination Pairing computations Exploit word parallelism JBoss Course – Fine Tuning Java EE Applications Serialization and externalization (default, XML) Use collocation, “pass be reference” Use JBoss Serialization Minimize cluster state replication Remote calls (EJB, RMI, etc) Combine many to one Minimal number of arguments Locking, transactions Keep transactions as short as possible Fine-tune transactional tags No transactions for read-only components Optimistic concurrency Data access, DB Cache results Fine-tune schema, SQL, stored procedures Use indexes Adjust transaction isolation levels JVM, GC Directory: 2009 2009 -> The Truth about the Rwandan Genocide 2009 -> Guide to learn how to install, set up and access the music you need today! 2009 -> Lesson #11: Words with 2009 -> Terry L. Root 2009 -> The environment in the news 2009 -> Town of Nags Head Annual Report 2009 -> Cemir international Download 32.32 Kb. Share with your friends:
|