Description

The applications you write get more complex by the day. To keep up, you need to ensure your knowledge and techniques grow, too. A mastery of data structures and algorithms lets you write software more quickly; software that works, performs, and scales. Volume 2 of the series takes your knowledge of data structures and algorithms to the next level. With this practical and easy-to-understand guide, you’ll create software that can tackle today’s challenging problems head on. This Python edition uses Python exclusively for all code examples, exercises, and solutions.

Benchmark your Python code to learn its true speed. Design fast and elegant solutions by connecting different data structures together. Use Monte Carlo algorithms to push the limits of your application’s speed and memory savings in surprising ways. Wrangle big data with B-trees and other specialized algorithms. Design efficient algorithms by cleverly sprinkling in a bit of randomization. Cram tons of data into tiny bit vectors and Bloom filters. And leverage caching to make your software blazingly fast.

Learn these sophisticated techniques and create great software that meets today’s challenges.

Contents and Extracts

• Preface
  • Who Is This Book For?
  • What’s in This Book?
  • How to Read This Book
  • A Note About the Code
  • Online Resources
  • Connecting
• Getting Things in Order with Mergesort excerpt
  • Merging Arrays
  • Merging in Action
  • The Efficiency of Merging
  • Mergesort
  • Mergesort in Action
  • The Efficiency of Mergesort
  • Comparing Mergesort and Quicksort: Lessons Learned
  • Wrapping Up
  • Exercises
• Benchmarking Code
  • Benchmarking
  • Using the timeit Module
  • Benchmarking Gotchas
  • Benchmarking Sorting Algorithms
  • Mergesort vs. Insertion Sort
  • Mergesort vs. Quicksort
  • Using Python’s Built-In Sorting Algorithm
  • Quicksorting a Sorted Array
  • Wrapping Up
  • Exercises
• How Random Is That?
  • Randomized Quicksort
  • Randomized Algorithms
  • Generating Random Numbers
  • TRNGs vs. PRNGs
  • The Fisher-Yates Shuffle
  • The Fisher-Yates Shuffle in Action
  • The Efficiency of the Fisher-Yates Shuffle
  • Shuffling the Wrong Way
  • Binary Search Tree Randomization
  • Randomization for Distribution
  • Load Balancing
  • Wrapping Up
  • Exercises
• Cache Is King excerpt
  • Caching
  • Eviction Policies
  • LRU Cache
  • The LRU Cache Data Structure
  • Fixing the LRU Worst-Case Scenario with Randomization
  • The Memory Hierarchy
  • Writing Cache-Friendly Code
  • Spatial Locality
  • Wrapping Up
  • Exercises
• The Great Balancing Act of Red-Black Trees
  • Online Algorithms and Self-Balancing Trees
  • Red-Black Trees
  • The Red-Black Rules
  • Red-Black Tree Insertion
  • The Efficiency of Red-Black Trees
  • Red-Black Tree Deletion
  • Wrapping Up
  • Exercises
• Randomized Treaps: Haphazardly Achieving Equilibrium
  • Treaps
  • Treap Insertion
  • Self-Balancing Treaps in Action
  • The Power of Random Priorities
  • Treap Deletion
  • Wrapping Up
  • Exercises
• To B-Tree or Not to B-Tree: External-Memory Algorithms excerpt
  • External Memory
  • Count I/Os, Not Steps
  • External Binary Search
  • Optimizing External-Memory Algorithms
  • Binary Search Trees in External Memory
  • B-Trees
  • Implementing B-Trees
  • B-Tree Insertion
  • B-Tree Deletion
  • The Balance of B-Trees
  • B-Trees as Database Indexes
  • Wrapping Up
  • Exercises
• Wrangling Big Data with M/B-Way Mergesort
  • External-Memory Sorting
  • A First Attempt: Two-Way External Mergesort
  • M = Main Memory Size
  • A Second Attempt at External Mergesort
  • Merging K Sorted Lists
  • M/B-Way Mergesort
  • Wrapping Up
  • Exercises
• Counting on Monte Carlo Algorithms
  • Monte Carlo Algorithms
  • Monte Carlo Algorithms vs. Las Vegas Algorithms
  • Obtaining Averages Through Random Sampling
  • Primality Testing
  • Monte Carlo Primality Testing
  • Fermat’s Little Theorem
  • Fermat’s Primality Test
  • Wrapping Up
  • Exercises
• Designing Great Hash Tables with Randomization
  • Hash Functions: A Quick Review
  • Scalable Hash Functions
  • The Division Method
  • Randomized Hashing
  • Wrapping Up
  • Exercises
• Keeping Your Text Search Sharp with a Little Rabin-Karp
  • Substring Search
  • Brute-Force Substring Search
  • The Sliding Window Technique
  • Rabin-Karp Substring Search
  • Covering All Our Bases
  • Perfecting Rabin-Karp with Base 26
  • Handling Long Needles
  • Monte-Carlo Rabin-Karp
  • Converting Monte Carlo to Las Vegas
  • Wrapping Up
  • Exercises
• Saving Space: Every Bit Helps
  • Sets
  • Boolean Arrays
  • Bit Vectors
  • Bit Manipulation
  • Bit Masks: The Key to Zeroing in on a Bit
  • Benchmarking Space
  • The Space Complexity of Sets
  • Classic Set Operations
  • Wrapping Up
  • Exercises
• Cultivating Efficiency with Bloom Filters
  • Finding Duplicates Revisited
  • Bloom Filters
  • Use Multiple Hash Functions
  • Using Bloom Filters for Detecting Duplicates
  • Bloom Filters in the Wild
  • Wrapping Up
  • Parting Thoughts
  • Exercises
• Solutions
  • Chapter 1
  • Chapter 2
  • Chapter 3
  • Chapter 4
  • Chapter 5
  • Chapter 6
  • Chapter 7
  • Chapter 8
  • Chapter 9
  • Chapter 10
  • Chapter 11
  • Chapter 12
  • Chapter 13