Introducing data structures

To start with our journey, we first need to agree on a common language to describe and evaluate algorithms. Describing them is pretty much a standard process: algorithms are described in terms of the input they take and the output they provide. Their details can be illus­trated with pseudo-code (ignoring implementation details of programming lan­guages) [ ...] [ ...]

Packing your knapsack: Data structures meet the real world

Congrats, you have been selected to populate the first Mars colony! Grocery stores on Mars are still a bit short of goods . . . and hard to find. So, you will have to eventually grow your own food. In the meantime, for the first few months, you will have goods shipped to sustain you. [ ...] [ ...]

The Problem and Solutions of Handling priority

1. Theproblem: Handling priority The first problem we are going to tackle is handling tasks based on priority. This is something all of us are familiar with in some way. The problem can be described in these terms: given a collection of tasks with dif­ferent priorities, determine which task should be executed next. We can [ ...] [ ...]

Improving priority queues: Concrete data structures

Let’s now move from abstract to concrete data structures. Knowing how the API of a pri­ority queue works is good enough to use it, but often it is not enough to use it well. Espe­cially on time-critical components or in data-intensive applications, we often need to understand the internals of the data structures and the [ ...] [ ...]

Improving priority queues: How to implement a heap

At this point we have a good idea of how a priority queue should be used and its inter­nal representation. It’s about time we delve into the details of the implementation for a heap. Before we go, let’s once again take a look at our API: class Heap { top() peek() insert(element, priority) remove(element) update(element, [ ...] [ ...]

Improving priority queues: Use case

1. Use case: Find the k largest elements In this section we are going to describe how we can use a priority queue to keep track of the k largest elements of a set. If we have the full set of n elements in advance, we have a few alternatives that don’t need any auxiliary [ ...] [ ...]

Improving priority queues: Analysis of branching factor

Now that we know how d-way heaps work, the next question we need to ask is this: Wouldn’t we be just fine with a regular, binary heap? Is there an advantage in a higher branching factor? 1. Do we need d-ary heaps? Usually binary heaps are enough for all our programming needs. The main advantage [ ...] [ ...]

Improving priority queues – Performance analysis: Finding the best branching factor

We’ve discussed the theory. Now let’s try to apply it to a real case and describe how to profile the implementation of a data structure and an application. We have seen that priority queues are a key component in the Huffman compres­sion pipeline. If we measure the performance of our heap’s methods as the number [ ...] [ ...]

Problem and Solutions of Multi-indexing

Your family runs a small grocery shop, and you’d like to help your parents keep up with the inventory. To impress your family and show everyone those computer science classes are worth the effort, you embark on the task of designing a digital inventory management tool, an archive for stock keeping, with two requirements: Be [ ...] [ ...]

Treap: Using randomization to balance binary search trees

. . . between a tree and a heap! Treap is just the portmanteau of tree and heap. Binary search trees, in fact, offer the best average performance across all standard operations: insert, remove, and search (and also min and max). Heaps, on the other hand, allow us to efficiently keep track of priorities using a tree-like [ ...] [ ...]

Treap Applications: Randomized treaps

So, we are now able to implement our inventory, keep track of the products in stock, and extract the ones closest to running out of stock. That would certainly impress everyone at the next family reunion! Hopefully, our example helped you understand how treaps work, but . . . I have a confession to make: [ ...] [ ...]

Treap: Performance analysis and profiling

As we saw in section 3.3, all API methods on Randomized Treaps require time propor­tional to the height of a tree. As we know (see the introduction to this chapter and appendix C), in the worst case the height of a binary tree can be linear in the number of elements and, in fact, one [ ...] [ ...]

The dictionary problem and Alternatives to implementing a dictionary

1. The dictionary problem: Keeping track of things Let’s go over a hypothetical scenario: you work for a company that is large enough to maintain its own email service. This is a legacy service, providing basic features only. After the last reorganization, the new CTO[1] decides that you need to reinvent the email service to [ ...] [ ...]

Bloom filters: Concrete data structures

So far, so good with the theory, but of course, implementing associative arrays to be used on real systems is a completely different thing. In theory, if the domain (the set of possible keys) is small enough, we can still use arrays by defining a total ordering on the keys and using their position in [ ...] [ ...]

Under the hood: How do Bloom filters work?

Let’s now delve into the details of Bloom filter implementation. A Bloom filter is made of two elements: An array of m elements A set of k hash functions The array is (conceptually) an array of bits, each of which is initially set to 0; each hash function outputs an index between 0 and m-1. [ ...] [ ...]

Bloom filters: Implementation of Reducing the memory for tracking content

Enough with the theory; now it’s time to once again get our hands dirty! As usual, in the next sections we’ll show pseudo-code snippets and comment the key sections. Triv­ial methods will be omitted. On the book’s repo on GitHub, you can also find an implementation with the full code along with unit tests. 1. Using [ ...] [ ...]

Bloom filters: Applications of Reducing the memory for tracking content

I’d like to let you think about this consideration: it is pretty likely that some software you are using right now is leveraging Bloom filters. In fact, if you are reading the digi­tal version of this book, then it’s 100% sure that its download leveraged Bloom filters, because it’s common for internet nodes to use [ ...] [ ...]

Why Bloom filters work

So far, we have asked you to take for granted that Bloom filters do work as we described. Now it’s time to look more closely and explain why a Bloom filter actually works. Although this section is not strictly needed to implement or use Bloom filters, reading it might help you understand this data structure [ ...] [ ...]

Bloom filters: Performance analysis and Estimating precision

1. Performance analysis Before starting on Bloom filter analysis, I suggest a deep dive into metrics for classifi­cation algorithms in appendix F. We have seen how and why Bloom filters work; now let’s see how efficient they are. First, we’ll examine the running time for the most important operations provided by a Bloom filter. Next, [ ...] [ ...]

Bloom filters: Improved variants

Bloom filters have been around for almost 50 years, so it’s natural that many variations and improvements have been proposed in the meantime. Let’s examine some of them, with a focus on those that improve accuracy. 1. Bloomier filter As we hinted at, Bloom filters corresponds to faster, lighter versions of HashSets, since they can [ ...] [ ...]