Algorithms and Data Structures In Action Version 13

Data Structure

To begin our journey, we first need to agree on a common language for describing and evaluating algorithms. 

Describing them is almost a standard process: algorithms are described in terms of the inputs they accept and the outputs they provide. Their details can be described in pseudocode (ignoring the implementation details of the programming language) or in actual code. 

Data structures follow the same conventions, but they go a little further: we must describe the operations you can perform on data structures; Usually each action is described in an algorithm, so there are inputs and outputs, but beyond that, for DSs, we also need to describe side effects, changes that the action might cause to the data structure itself. 

To fully understand what this means, we first need to define data structures correctly.

The problem: handling priority

The first problem we have to solve is to approach tasks according to priority. To some extent, this is something we are all familiar with.
The problem can be described as: Given a set of tasks with different priorities, determine which tasks should be executed next.
We can find plenty of examples in the real world where we have consciously or unconsciously applied technology to help us decide what to do next. Our daily lives are full of tasks: often, the order in which we perform them is a result of time constraints and the importance we assign to them.
A common example of a prioritized environment is the emergency room, where patients come not according to the order in which they arrive but according to how urgent their condition is. If we get closer to our IT domain, many tools and systems have the same behavior. For example, consider your operating system scheduler. Or you’re using a mobile app to keep track of your to-do list.

Problem: Multi-Indexing

Here is a scenario: you runs a small store, and you would like to keep inventory. Therefore, you set out to design a digital inventory management tool, a file for inventory preservation, with two requirements:
  • Ability to search products by name and update inventory (efficiently);
  • Always get the lowest inventory so you can plan your next order.
Sure, you could just buy a ready-made spreadsheet, but where’s the fun? Besides, is anyone really impressed? So, we designed an in-memory data structure that could be queried against two different criteria.
Obviously, the scene is more complicated than that of the real world: you can imagine, each product delivered to you need a different time, ordered some products from the same vendor (so you may want to group them in the same order to save transportation costs), the price of the product may vary with time, you can choose the cheapest brand, say, braking and suspension). Even some products may not work at times.
All of this complexity, however, can be captured in a heuristic function that calculates scores and remembers all your subtleties: conceptually, you’ll be able to handle this aspect of simple inventory counts in the same way, so we can make things simple in our example, just using them.
One way to address these requirements is to use two different data structures: one for efficient searches by name, such as using hash tables, and the other for priority queues to get the items that most urgently need to be resupplied.
As we will see in Chapter 7, it is sometimes best to combine two data structures to achieve your goals; Now is not the time, but now you need to remember the problem of reconciling the two containers, and you may need more than twice as much memory.

More resources:

Views: 43

Leave a Reply

Your email address will not be published. Required fields are marked *