Hands-On Data Structures and Algorithms in Rust

Name: Hands-On Data Structures and Algorithms in Rust
Rating: 4.5 (233 reviews)

Learn about common and useful Data Structures and Algorithms

Created byPackt Publishing

Last updated 6/2020

English

What you'll learn

How Rust can help you keep your memory access safe and effective
How we can use Rust to build Generic Algorithms that we can use again and again across our codebase
Greedy, dynamic, and Iterative algorithms and when to use them
Different data structures such as Maps, Trees, and Linked lists, and when it is appropriate to use them.
Why and how an Entity Component System separates the different parts of the object into different storage areas
How we can build files that work like simple databases using BTrees
How we can run our programs even faster-using Multithreading

Course content

7 sections • 49 lectures • 6h 55m total length

Course Overview5:30
This video provides an overview of the entire course.
Install Rust and Running a Simple Program3:53
We need a mechanism to run the code we are writing. So, we need to get the Rust compiler installed.
• Download Rustup.sh
• Run rustup
• Build a simple Hello World project
Build complex structures with Struct and Enum8:57
In order to do anything in programming in Rust, we need ways to organize our data.
• Introduce the Struct
• Introduce the Enum
• Get printouts of each showing what they can do and hold
Results and Options6:58
Some functions may need to let the caller know there was a problem. How can we pass that message back?
• Introduce the Result and Option enum types
• Demonstrate how these works generically
• Show a function returning an Error
Looping Mechanisms in Iterators8:31
Every program needs to perform some task multiple times. How can we do that in Rust?
• Introduce the loop, while, and for
• Show how an iterator works by returning an option
• Demonstrate a for loop on a new iterator type
Stack Data Structure in Rust9:46
Programs often need to grab memory to be able operate. Can we understand when they need to?
• Introduce the stack
• Demonstrate the stack in a set of function calls
• Show how the stack can be avoided in tail recursive situations
Mutability, Variables, Copying, and Cloning6:22
Making sure that our code does not write to something it should not, is tricky. How can we work with the Rust compiler?
• Show how an object can be copied between variables
• Show that in order to change a variable which need to make it mutable
• Show how these two features interact
Use Memory Effectively with Pointers and Lifetimes9:09
Rust protects us from pointing to things that do not exist anymore. How can we work with this?
• Introduce the borrow notation for pointers
• Show how when you have a pointer to something, you cannot change it elsewhere
• Demonstrate that mutable pointers require mutable objects
Own Memory on the Heap with Box, String, and Vecs9:06
How do we handle objects where we do not know how big they will need to be?
• Demonstrate how a pointer is needed to make a linked list
• Show how Box creates that pointer
• Build Dynamic arrays using vec
Difference Between Str and String9:54
In this video, we will look at the difference between Str and String.
• Understand their differences
• Explore their uses
Uploading to Crates4:57
How can we make our code available to others to use?
• Show how to get a token from crates
• Show how to set up our crates for upload
• Show how to upload our crate and check it is uploaded
Test your knowledge

Sorting Using Bubble Sort9:56
What is the simplest way we can sort a list?
• See if each element should swap left in the vec
• Repeat until sorted
• Calculate how long this takes to run and if we can save time
Divide and Conquer Sorting with Merge Sort11:32
Can we go faster when sorting data?
• Introduce the concept of divide and conquer
• Show how to split the data into two smaller sections to sort
• Bring those two small sorted lists together in linear time
Sorting in Place with Quick Sort6:43
Can we do it without needing to grab so much memory?
• Show how to pivot data around a single item
• Sort the two sides separately
• Test that it works
Improving Our Quick Sorter with Pseudo Random Numbers10:15
How can random numbers help us build faster solutions?
• Show that quick sort worst case is n squared
• Create a random generator
• Add that to our quick sort and show that removes the worst case
Spiting Quick Sort Using Multiple Threads8:55
Can we use all our processors to speed up the operation?
• Introduce threading
• Explain why this case unsafe and why it must
• Show how this works across all the threads
Let Rayon Speed It Up with Work Stealing2:50
Can we limit the number of threads we use to solve a problem?
• Introduce the Rayon library
• Show how the join method uses threads
• Implement quick sort to use join
Cut the Right Corners to Increase Your Speed with Dynamic Programming7:07
How can we avoid performing the same calculation?
• Show how a naive fibonacci calls the same function many times
• Show how iterative solutions avoid that
• Show how by storing previously calculated results, we can save ourselves a lot of calculation
Test your knowledge

Creating a Linked List5:49
How can we store lists in the simplest way possible?
• Show how we can use Box to make a list
• Append and remove elements
• Show how linked list is fast for the front but not the back
Viewing Data in Both Directions with Doubly Linked Lists10:09
How can we access both ends of a linked safely?
• Introduce Rc and Weak
• Show why one direction must be Weak
• Add and remove elements from both ends of the list in linear time
Building a Binary Tree to Efficiently Store and Sort Data8:09
How can we add data to a list in just Log(n) time?
• Introduce trees that have two branches
• Show how to add data to a list
• Show how to read data back in order
Converting Binary Tree to a Binary Balance Tree14:45
What if we add data in a sorted manner, doesn’t that create just a linked list?
• Show that adding sorted data wastes the binary tree
• Demonstrate tree rotation
• Use stored heights to calculate when to rotate the tree
Learning About Skip Lists and Their Potential Advantages12:57
How can we use random data to quickly find tree elements?
• Introduce the idea of a layered linked list
• Show how the random data allows us to access parts quickly
• Begin building the skip list
Managing the Heights of a Skip List11:49
Can we finish this skip list?
• Add a layer tracker to the front of the list
• Show how we can flip a coin to add layers as needed
• Test our skip list
Computing Huffman Encoding and to Compress Data15:34
How can Trees be used to compress data?
• Create a Huffman tree
• Show how this puts frequent elements near the top
• Show how to compress and decompress a string of data
Test your knowledge

Consider the Options for Creating and Storing Graphs7:38
What is the best way to store a graph?
• Introduce different options for storing a graph
• Show the costs and benefits of each
• Select one for the rest of this section
Filling the Graph8:35
In order to test it, our graph needs data.
• Make sure our graph has enough add and delete methods
• Add data to the graph
• Look at the data we have added and how it works
Route Structure6:00
How can we store routes in a composable way?
• Show how Rc can have many clones
• Show many routes with the same beginning
• Get our routes printable
Finding the Shortest Path9:45
How can we find the shortest path between two points on the graph?
• Add all paths from the start node to a list
• Take the shortest path on the list and repeat from there
• Do not search from the node we have already searched from
A Greedy Solution to the Travelling Salesman9:06
How can we solve complicated problems on such as the Traveling Salesman on graphs?
• Introduce Traveling Salesman
• Introduce greedy algorithms
• Try a greedy algorithm to solve Traveling Salesman
Improve the Solution Using Iterative Methods9:01
Can we do better than a greedy solution?
• Introduce an iterative method
• Generate a random path
• Make random changes only keeping improvements
Test your knowledge

What a HashMap Is and Why and When Do We Use Them2:51
Can we store data with constant time access?
• Introduce the idea of a HashMap
• Show how a set of buckets can be selected from
• Explain we are going to build this
Building HashMap from Scratch8:20
How do we choose a random, but consistent bucket?
• Introduce the idea of a Hasher
• Show how the Hash and Hasher Traits work together
• Build a Hasher
Building a Bucket List for the HashMap to Use9:14
Can we create a functioning bucket list?
• Create a list of buckets that stores data based on its hash
• Show how we can add and remove data from this list
• Test it
Finishing the HashMap8:57
How can we get our HashMap to grow without needing to break our const time rules?
• Create a wrapper around two Bucket Lists
• When one bucket is too full, create a new bigger one
• Move the data across in small chunks
Testing and Improving Our HashMap8:53
Can we know for sure our HashMap does what it should?
• Build tests for inserting into our HashMap
• Build tests for the growth of our HashMap
• Show that we need to double the size every time
HashMap versus BTreeMap2:37
When should we use which kinds of maps or sets?
• Show how Rust optimizes maps to act as sets
• Show when each kind of map is more appropriate
• Show when each kind of map is less appropriate
Test your knowledge

Understand What an ECS Is and How It Differs from Traditional Structures3:50
How can we organize our data for real time processing on modern systems?
• Introduce ECS
• Show how it separates the components of an entity across stores
• Explain how systems then operate on the data
Creating an ID Generator8:15
How can me make sure we do not treat a new element as an old one?
• Introduce generation tracking
• Show how we can do this all in constant time across many adds and drops
• Build a complete generation manager
Creating Data Stores10:09
How do we store our data so that we cannot grab the wrong element by mistake?
• Show the kinds of operations a store need
• Show how we can use a Vec store with marked generations
• Show how we can loop over the elements in a store
Building ECS Systems16:31
How do the systems of ECS interact with each other?
• Show how simple systems can loop over the data they need
• Show how more complex systems can loop in different ways
• Build all the systems needed for a simple CLI game
Combining It All into a Simple CLI Game8:26
How can we run this ECS game?
• Show how to access the terminal and raw input
• Show how we can count passes
• Show how we can manage quitting our application
Introduction to Specs4:03
Are there any tools to make doing ECS easier?
• Introduce the Specs crate
• Show a simple example from the Specs docs
• Explain each part of the code required
Test your knowledge

Creating a Blob Data File6:32
How can we maintain persistent data with fast access?
• Explain the new problems of data size when working across files
• Prepare the crate with needed libraries
• Prepare an error type to handle the Blob store we are building
Converting Any Data Size to Byte String13:11
How can we make any data work as a string of bytes
• Create a Blob store type
• Show how Serdes and bincode make conversions possible
• Test our Blob object
Creating a Blob Store13:08
How can we access the file with Random Access?
• Show how we can create a file
• Set up the control data for a new file
• Open an existing file and read the control data
Adding to the Blob Store6:11
How can we add data to the file?
• Show how we can add data with marked length
• Show how we can find the right place to add it
• Test we can add data
Reading from the Blob Store7:43
How can we read data from the file?
• Show that we can find the data following the same path
• Show that we can convert it back to the right type
• Test we get the right data back
Removing an Element from the Blob Store6:56
How can we remove data from the file?
Show that when we remove data, we now have two blocks that need to be joint
Join the two blocks
Test that remove works as expected
Test your knowledge

Requirements

No Rust programming knowledge is required as we will be covering the basics at the beginning.

Description

Rust is a modern systems programming language designed with safety to simplify the development of large, complex software projects. Data structure and Algorithms are key to help in the collection and organization of the data for performing operations on the data and set instructions/logic to accomplish tasks in these projects. This course will be your guide for implementing classic data structures and algorithms in Rust, helping you to get up and running as a confident Rust programmer.

You will begin with a primer to Rust and its syntax. You will then explore the language of Time and Memory complexity by comparing different sorting methods. You’ll then learn about Lists and Binary Trees, implement them, and compare them, to show the advantages and use cases of each. Next, you will cover different algorithms in-depth such as sorting, graph, dynamic programming, greedy, divide and conquer, and more. You will learn how counterintuitive techniques can actually make it easier to build scalable projects!

By the end of the course, you will have a sound knowledge of the key data structures and algorithms in Rust to confidently implement them in your applications.

About the Author

Matthew Stoodley is a programming expert and enthusiast, who was drawn to learn about Rust and master its features initially due to its low power usage and memory safety capabilities. He primarily uses Rust to build board games.

In addition, he also possesses several years of experience in Go, PHP, and JavaScript.

Who this course is for:

This course is for programmers who want to get to grips with all data structures and algorithms in the latest version of Rust programming language, to help organize your code better and accomplish predefined tasks.

Hands-On Data Structures and Algorithms in Rust

What you'll learn

Explore related topics

Course content

Getting to Grips with Rust and its Syntax11 lectures • 1hr 23min

Algorithm Complexity and Sorting Algorithms7 lectures • 57min

Building Linked Lists and Binary Trees7 lectures • 1hr 19min

Model Real Situations as Graphs of Connected Nodes6 lectures • 50min

Getting Constant Time Data Access Using HashMap6 lectures • 41min

Organizing Your Data by Type with Entity Component Systems6 lectures • 51min

Persistent Storage Data Structure6 lectures • 54min

Requirements

Description

Who this course is for: