Hands-On Data Structures and Algorithms in Rust

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

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

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

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

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

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

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

In this video, we will look at the difference between Str and String.

   •  Understand their differences

   •  Explore their uses

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

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

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

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

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

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

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

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

Can we do better than a greedy solution?

   •  Introduce an iterative method

   •  Generate a random path

   •  Make random changes only keeping improvements

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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