Want to write code that’s faster, leaner, and ready for anything? Then you need to go beyond the basics and dive into advanced data structures and algorithms. Forget just knowing Big O notation – learn to truly evaluate the efficiency of your algorithms. This guide will show you how to use powerful tools like B-trees, bit vectors, and Bloom filters to handle massive datasets. Discover techniques like caching, randomization, and fingerprinting to build applications that can handle even the most demanding tasks.
This book breaks down complex topics with clear explanations, easy-to-understand diagrams, and plenty of practical exercises and solutions. It’s designed to help you move beyond the fundamentals and build real-world software that’s ready to tackle any challenge.
Note: This is Volume 2 in a series. If you’re new to data structures and algorithms, A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1 is a great place to start. This volume builds upon the concepts covered in the first book.
Why You Need Advanced Data Structures and Algorithms
As applications become more complex, you need to expand your knowledge and skill set. Mastering data structures and algorithms allows you to write software more quickly and efficiently – software that not only works but also performs well and scales effectively. This guide provides a practical and accessible approach to taking your knowledge to the next level. All code examples, exercises, and solutions are presented exclusively in Python.
Learn to benchmark your Python code to accurately measure its performance. Craft elegant and efficient solutions by combining different data structures. Explore Monte Carlo algorithms to achieve surprising improvements in speed and memory usage. Handle big data with specialized algorithms like B-trees. Design efficient algorithms by strategically incorporating randomization. Store vast amounts of data using compact bit vectors and Bloom filters. And leverage caching techniques to make your software lightning-fast.
Key Concepts You’ll Master
This book covers a range of advanced topics, including:
-
Benchmarking Code: Learn how to use the
timeitmodule and avoid common pitfalls to accurately measure the performance of your Python code. -
Randomized Algorithms: Discover how to use randomization to improve the performance and efficiency of your algorithms, including randomized quicksort and the Fisher-Yates shuffle.
-
Caching: Explore different caching strategies, such as LRU (Least Recently Used), and learn how to write cache-friendly code that takes advantage of spatial locality.
-
Self-Balancing Trees: Delve into red-black trees and treaps, which are self-balancing binary search trees that provide efficient search, insertion, and deletion operations.
-
B-Trees: Understand how B-trees work and how they are used to store and retrieve data from external memory, such as hard drives or SSDs.
-
External-Memory Sorting: Learn how to sort large datasets that don’t fit in memory using algorithms like M/B-Way Mergesort.
-
Monte Carlo Algorithms: Explore Monte Carlo algorithms, which use random sampling to obtain approximate solutions to complex problems, such as primality testing.
-
Hash Tables with Randomization: Design scalable hash functions using techniques like the division method and randomized hashing.
-
String Matching: Implement substring search algorithms, such as the Rabin-Karp algorithm, which uses hashing to efficiently find patterns in text.
-
Bit Vectors: Discover how to use bit vectors to store sets of data in a compact and efficient manner.
-
Bloom Filters: Learn about Bloom filters, which are probabilistic data structures that can be used to quickly check whether an element is a member of a set.
Who This Book Is For
This book is ideal for Python developers who:
- Want to improve their core programming skills.
- Need to write code that performs well and scales effectively.
- Are interested in learning about advanced data structures and algorithms.
- Want to build real-world software that can tackle complex challenges.
While familiarity with the concepts covered in Volume 1 of this series is helpful, it’s not required.
What You Need
To explore and execute the code examples in this book, you’ll need:
- Your favorite text editor
- An environment that can run Python 3
Table of Contents
-
Preface
-
Getting Things in Order with Mergesort
-
Benchmarking Code
-
How Random Is That?
-
Cache Is King
-
The Great Balancing Act of Red-Black Trees
-
Randomized Treaps: Haphazardly Achieving Equilibrium
-
To B-Tree or Not to B-Tree: External-Memory Algorithms
-
Wrangling Big Data with M/B-Way Mergesort
-
Counting on Monte Carlo Algorithms
-
Designing Great Hash Tables with Randomization
-
String Matching
-
Bit Vectors
-
Bloom Filters
-
Exercise Solutions
About the Author
Jay Wengrow is an experienced educator and software engineer. He’s the founder of Actualize, a coding bootcamp that has helped many people launch their careers as software engineers. He’s passionate about making software development more accessible by breaking down complex concepts into simpler parts.
With this book, you’ll gain the knowledge and skills you need to write high-performance, scalable software that’s ready to tackle the challenges of the real world.
