A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 2

Level Up Your Core Programming Skills

by Jay Wengrow

Want to write code that pushes the boundaries of speed, space savings, and scalability? Then you need more advanced data structures and algorithms. Go beyond Big O notation and evaluate the true efficiency of each algorithm you design. Pull out data structures such as B-trees, bit vectors, and Bloom filters to wrangle big data. Wield techniques like caching, randomization, and fingerprinting to tame even the most demanding applications. With simple language, clear diagrams, and practice exercises and solutions, this book makes these topics easy to grasp. Go beyond the basics and use these next-level concepts to build software that’s ready to take on the challenges of the real world.

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.

• Errata, typos, suggestions

• Source Code (zip file)

Releases:

• B2.0 2024/11/08
• B1.0 2024/10/14

Note: Contents and extracts of beta books will change as the book is developed.

• 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
• String Matching
  • Story Map
  • Substring Search
  • Brute-Force Substring Search
  • The Sliding Window Technique
  • Rabin-Karp Substring Search
  • Rabin-Karp in Action
  • Covering All Our Bases
  • Monte-Carlo Rabin-Karp
  • Converting Monte Carlo to Las Vegas
  • Wrapping Up
  • Exercises
• Bit Vectors
  • Story Map
  • Sets
  • Boolean Arrays
  • Bit Vectors
  • Bitwise Operations
  • Accessing Individual Bits with Masks
  • Code Implementation: Bit Vector
  • Benchmarking Space
  • Space Complexity of Sets
  • Common Set Operations
  • Wrapping Up
  • Exercises
• Bloom Filters
  • Story Map
  • Finding Duplicates Revisited
  • Bloom Filters
  • Using Multiple Hash Functions
  • Using Bloom Filters for Detecting Duplicates
  • Bloom Filters in the Wild
  • Wrapping Up
  • Exercises
• Exercise Solutions
  • Chapter 1
  • Chapter 2
  • Chapter 3
  • Chapter 4
  • Chapter 5
  • Chapter 6
  • Chapter 7
  • Chapter 8
  • Chapter 9
  • Chapter 10