You are previewing F# for Scientists.

F# for Scientists

Cover of F# for Scientists by Jon Harrop Published by Wiley-Interscience
  1. Copyright
  2. Foreword
  3. Preface
  4. Acknowledgments
  5. List of Figures
  6. List of Tables
  7. Acronyms
  8. 1. INTRODUCTION
    1. 1.1. PROGRAMMING GUIDELINES
    2. 1.2. A BRIEF HISTORY OF F#
    3. 1.3. BENEFITS OF F#
    4. 1.4. INTRODUCING F#
      1. 1.4.1. Language overview
      2. 1.4.2. Pattern matching
      3. 1.4.3. Equality
      4. 1.4.4. Sequence expressions
      5. 1.4.5. Exceptions
    5. 1.5. IMPERATIVE PROGRAMMING
    6. 1.6. FUNCTIONAL PROGRAMMING
      1. 1.6.1. Immutability
      2. 1.6.2. Recursion
      3. 1.6.3. Curried functions
      4. 1.6.4. Higher-order functions
  9. 2. PROGRAM STRUCTURE
    1. 2.1. NESTING
    2. 2.2. FACTORING
      1. 2.2.1. Factoring out common subexpressions
      2. 2.2.2. Factoring out higher-order functions
    3. 2.3. Modules
    4. 2.4. OBJECTS
      1. 2.4.1. Augmentations
      2. 2.4.2. Classes
    5. 2.5. FUNCTIONAL DESIGN PATTERNS
      1. 2.5.1. Combinators
      2. 2.5.2. Maps and folds
    6. 2.6. F# DEVELOPMENT
      1. 2.6.1. Creating an F# project
      2. 2.6.2. Building executabies
      3. 2.6.3. Debugging
      4. 2.6.4. Interactive mode
      5. 2.6.5. C# interoperability
  10. 3. DATA STRUCTURES
    1. 3.1. ALGORITHMIC COMPLEXITY
      1. 3.1.1. Primitive operations
      2. 3.1.2. Complexity
    2. 3.2. ARRAYS
      1. 3.2.1. Array literals
      2. 3.2.2. Array indexing
      3. 3.2.3. Array concatenation
      4. 3.2.4. Aliasing
      5. 3.2.5. Subarrays
      6. 3.2.6. Creation
      7. 3.2.7. Iteration
      8. 3.2.8. Map
      9. 3.2.9. Folds
      10. 3.2.10. Sorting
      11. 3.2.11. Pattern matching
    3. 3.3. LISTS
      1. 3.3.1. Sorting
      2. 3.3.2. Searching
      3. 3.3.3. Filtering
      4. 3.3.4. Maps and folds
      5. 3.3.5. Pattern matching
    4. 3.4. SETS
      1. 3.4.1. Creation
      2. 3.4.2. Insertion
      3. 3.4.3. Cardinality
      4. 3.4.4. Set-theoretic operations
      5. 3.4.5. Comparison
    5. 3.5. HASH TABLES
      1. 3.5.1. Creation
      2. 3.5.2. Searching
      3. 3.5.3. Insertion, replacement and removal
      4. 3.5.4. Higher-order functions
    6. 3.6. MAPS
      1. 3.6.1. Creation
      2. 3.6.2. Searching
      3. 3.6.3. Higher-order functions
    7. 3.7. CHOOSING A DATA STRUCTURE
    8. 3.8. Sequences
    9. 3.9. Heterogeneous Containers
    10. 3.10. TREES
      1. 3.10.1. Balanced trees
      2. 3.10.2. Unbalanced trees
      3. 3.10.3. Abstract syntax trees
  11. 4. NUMERICAL ANALYSIS
    1. 4.1. NUMBER REPRESENTATION
      1. 4.1.1. Machine-precision integers
      2. 4.1.2. Machine-precision floating-point numbers
    2. 4.2. ALGEBRA
    3. 4.3. INTERPOLATION
    4. 4.4. QUADRATIC SOLUTIONS
    5. 4.5. MEAN AND VARIANCE
    6. 4.6. OTHER FORMS OF ARITHMETIC
      1. 4.6.1. Arbitrary-precision integer arithmetic
      2. 4.6.2. Arbitrary-precision rational arithmetic
      3. 4.6.3. Adaptive precision
  12. 5. INPUT AND OUTPUT
    1. 5.1. PRINTING
      1. 5.1.1. Generating strings
    2. 5.2. GENERIC PRINTING
    3. 5.3. READING FROM AND WRITING TO FILES
    4. 5.4. SERIALIZATION
    5. 5.5. LEXING AND PARSING
      1. 5.5.1. Lexing
      2. 5.5.2. Parsing
  13. 6. SIMPLE EXAMPLES
    1. 6.1. FUNCTIONAL
      1. 6.1.1. Nest
      2. 6.1.2. Fixed point
      3. 6.1.3. Within
      4. 6.1.4. Memoize
      5. 6.1.5. Binary search
    2. 6.2. NUMERICAL
      1. 6.2.1. Heaviside step
      2. 6.2.2. Kronecker δ-function
      3. 6.2.3. Gaussian
      4. 6.2.4. Binomial coefficients
      5. 6.2.5. Root finding
      6. 6.2.6. Grad
      7. 6.2.7. Function minimization
      8. 6.2.8. Gamma function
      9. 6.2.9. Discrete wavelet transform
    3. 6.3. STRING RELATED
      1. 6.3.1. Transcribing DNA
      2. 6.3.2. Word frequency
    4. 6.4. LIST RELATED
      1. 6.4.1. count
      2. 6.4.2. positions
      3. 6.4.3. fold_to
      4. 6.4.4. insert
      5. 6.4.5. chop
      6. 6.4.6. dice
      7. 6.4.7. apply_at
      8. 6.4.8. sub
      9. 6.4.9. extract
      10. 6.4.10. shuffle
      11. 6.4.11. transpose
      12. 6.4.12. combinations
      13. 6.4.13. distribute
      14. 6.4.14. permute
      15. 6.4.15. Power set
    5. 6.5. ARRAY RELATED
      1. 6.5.1. rotate
      2. 6.5.2. swap
      3. 6.5.3. except
      4. 6.5.4. shuffle
    6. 6.6. HIGHER-ORDER FUNCTIONS
      1. 6.6.1. Tuple related
      2. 6.6.2. Generalized products
  14. 7. VISUALIZATION
    1. 7.1. WINDOWS FORMS
      1. 7.1.1. FORMS
      2. 7.1.2. Controls
      3. 7.1.3. Events
      4. 7.1.4. Bitmaps
      5. 7.1.5. Example: Cellular automata
      6. 7.1.6. Running an application
    2. 7.2. MANAGED DIRECTX
      1. 7.2.1. Handling DirectX devices
      2. 7.2.2. Programmatic rendering
      3. 7.2.3. Rendering an icosahedron
      4. 7.2.4. Declarative rendering
      5. 7.2.5. Spawning visualizations from the F# interactive mode
    3. 7.3. TESSELATING OBJECTS INTO TRIANGLES
      1. 7.3.1. Spheres
      2. 7.3.2. 3D function plotting
  15. 8. OPTIMIZATION
    1. 8.1. TIMING
      1. 8.1.1. Absolute time
      2. 8.1.2. CPU time
      3. 8.1.3. Looping
      4. 8.1.4. Example timing
    2. 8.2. PROFILING
      1. 8.2.1. 8-queens problem
    3. 8.3. ALGORITHMIC OPTIMIZATIONS
    4. 8.4. LOWER-LEVEL OPTIMIZATIONS
      1. 8.4.1. Benchmarking data structures
      2. 8.4.2. Compiler flags
      3. 8.4.3. Tail-recursion
      4. 8.4.4. Avoiding allocation
      5. 8.4.5. Terminating early
      6. 8.4.6. Avoiding higher-order functions
      7. 8.4.7. Use mutable
      8. 8.4.8. Specialized functions
      9. 8.4.9. Unboxing data structures
      10. 8.4.10. Eliminate needless closures
      11. 8.4.11. Inlining
      12. 8.4.12. Serializing
  16. 9. LIBRARIES
    1. 9.1. LOADING .NET LIBRARIES
    2. 9.2. CHARTING AND GRAPHING
    3. 9.3. THREADS
      1. 9.3.1. Thread safety
      2. 9.3.2. Basic use
      3. 9.3.3. Locks
      4. 9.3.4. The thread pool
      5. 9.3.5. Asynchronous delegates
      6. 9.3.6. Background threads
    4. 9.4. RANDOM NUMBERS
    5. 9.5. REGULAR EXPRESSIONS
    6. 9.6. VECTORS AND MATRICES
    7. 9.7. DOWNLOADING FROM THE WEB
    8. 9.8. COMPRESSION
    9. 9.9. HANDLING XML
      1. 9.9.1. Reading
      2. 9.9.2. Writing
      3. 9.9.3. Declarative representation
    10. 9.10. CALLING NATIVE LIBRARIES
    11. 9.11. FOURIER TRANSFORM
      1. 9.11.1. Native-code bindings
      2. 9.11.2. Interface in F#
      3. 9.11.3. Pretty printing complex numbers
      4. 9.11.4. Example use
    12. 9.12. METAPROGRAMMING
      1. 9.12.1. Emitting IL code
      2. 9.12.2. Compiling with LINQ
  17. 10. DATABASES
    1. 10.1. PROTEIN DATA BANK
      1. 10.1.1. Interrogating the PDB
      2. 10.1.2. Pretty printing XML in F# interactive sessions
      3. 10.1.3. Deconstructing XML using active patterns
      4. 10.1.4. Visualization in a GUI
    2. 10.2. WEB SERVICES
      1. 10.2.1. US temperature by zip code
      2. 10.2.2. Interrogating the NCBI
    3. 10.3. RELATIONAL DATABASES
      1. 10.3.1. Connection to a database
      2. 10.3.2. Executing SQL statements
      3. 10.3.3. Evaluating SQL expressions
      4. 10.3.4. Interrogating the database programmatically
      5. 10.3.5. Filling the database from a data structure
      6. 10.3.6. Visualizing the result
      7. 10.3.7. Cleaning up
  18. 11. INTEROPERABILITY
    1. 11.1. EXCEL
      1. 11.1.1. Referencing the Excel interface
      2. 11.1.2. Loading an existing spreadsheet
      3. 11.1.3. Creating a new spreadsheet
      4. 11.1.4. Referring to a worksheet
      5. 11.1.5. Writing cell values into a worksheet
      6. 11.1.6. Reading cell values from a worksheet
    2. 11.2. MATLAB
      1. 11.2.1. Creating a .NET interface from a COM interface
      2. 11.2.2. Using the interface
      3. 11.2.3. Remote execution of MATLAB commands
      4. 11.2.4. Reading and writing MATLAB variables
    3. 11.3. MATHEMATICA
      1. 11.3.1. Using .NET-link
      2. 11.3.2. Example
  19. 12. COMPLETE EXAMPLES
    1. 12.1. FAST FOURIER TRANSFORM
      1. 12.1.1. Discrete Fourier transform
      2. 12.1.2. Danielson-Lanczos algorithm
      3. 12.1.3. Bluestein's convolution algorithm
      4. 12.1.4. Testing and performance
    2. 12.2. SEMI-CIRCLE LAW
      1. 12.2.1. Eigenvalue computation
      2. 12.2.2. Injecting results into Excel
      3. 12.2.3. Results
    3. 12.3. FINDING N TH-NEAREST NEIGHBORS
      1. 12.3.1. Formulation
      2. 12.3.2. Representing an atomic configuration
      3. 12.3.3. Parser
      4. 12.3.4. Lexer
      5. 12.3.5. Main program
      6. 12.3.6. Visualization
    4. 12.4. LOGISTIC MAP
    5. 12.5. REAL-TIME PARTICLE DYNAMICS
  20. A. Troubleshooting
    1. A.1. Value Restriction
    2. A.2. MUTABLE ARRAY CONTENTS
    3. A.3. NEGATIVE LITERALS
    4. A.4. ACCIDENTAL CAPTURE
    5. A.5. LOCAL AND NON-LOCAL VARIABLE DEFINITIONS
    6. A.6. MERGING LINES
    7. A.7. APPLICATIONS THAT DO NOT DIE
    8. A.8. BEWARE OF "IT"
  21. Glossary
  22. Bibliography
O'Reilly logo

Chapter 8. OPTIMIZATION

Thanks to advances in computer technology, performance is no longer a concern for the majority of programs. However, many applications exist, particularly in the context of scientific computing, where performance is still important. In such cases, programs can be optimized to run faster by exploiting knowledge about the relative performance of different approaches.

This chapter examines the most important techniques for optimizing F# programs. The overall approach to whole program optimization is to perform each of the following steps in order:

  1. Profile the program compiled with automated optimizations and running on representative input.

  2. Of the sequential computations performed by the program, identify the most time-consuming one from the profile.

  3. Calculate the (possibly asymptotic) algorithmic complexity of this bottleneck in terms of suitable primitive operations.

  4. If possible, manually alter the program such that the algorithm used by the bottleneck has a lower asymptotic complexity and repeat from step 1.

  5. If possible, modify the bottleneck algorithm such that it accesses its data structures less randomly to increase cache coherence.

  6. Perform low-level optimizations on the expressions in the bottleneck.

The mathematical concept of asympotic algorithmic complexity (covered in section 3.1) is an excellent way to choose a data structure when inputs will be large, i.e. when the asymptotic approximation is most accurate. However, many programs perform a large number ...

The best content for your career. Discover unlimited learning on demand for around $1/day.