Programming Pearls, 2Ed



Download 32.32 Kb.
Date02.05.2018
Size32.32 Kb.
#47320
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


Download 32.32 Kb.

Share with your friends:




The database is protected by copyright ©ininet.org 2024
send message

    Main page