Skip to content

Latest commit

 

History

History
218 lines (142 loc) · 6.69 KB

maps_mapsets_keyword_lists.livemd

File metadata and controls

218 lines (142 loc) · 6.69 KB

Maps, Mapsets, and Keyword Lists

Mix.install([
  {:youtube, github: "brooklinjazz/youtube"},
  {:hidden_cell, github: "brooklinjazz/hidden_cell"},
  {:tested_cell, github: "brooklinjazz/tested_cell"},
  {:utils, path: "#{__DIR__}/../utils"}
])

Navigation

Return Home Report An Issue

Setup

Ensure you type the ea keyboard shortcut to evaluate all Elixir cells before starting. Alternatively you can evaluate the Elixir cells as you read.

Overview

In this lesson, we will study the internal details of Maps, MapSets, and Keyword Lists to determine when to use each data type.

Keyword Lists

Keyword lists have the same properties as Lists.

Operation Time Complexity
Access $O(n)$
Search $O(n)$
Insertion $O(1)$ for prepending, otherwise $O(n)$
Deletion $O(1)$ if first element, otherwise $O(n)$

Because they are simply lists of {:atom, value} Tuples.

[{:key1, "value"}, {:key2, "value"}] == [key1: "value", key2: "value"]

Maps

Maps are a key-value data type that typically has $O(log(n))$ time for any operation involving accessing a key.

Operation Time Complexity
Access $O(log(n))$
Search $O(log(n))$
Insertion $O(n)$ for <= 32 elements, otherwise $O(log(n))$
Deletion $O(n)$ for <= 32 elements, otherwise $O(log(n))$

Maps with 32 or fewer keys are sorted lists. Therefore they have $O(n)$ performance, but this effect is negligible.

Notice that the map below retains its sort order.

map = Map.new(1..32, fn x -> {x, "#{x}"} end)

Under the hood, a map with 32 or fewer keys uses a sorted list.

Generally, we should avoid relying on this property. When a map grows beyond 32 keys, it loses its sorting order.

Notice the map below is no longer ordered now that it has 33 keys.

map = Map.new(1..33, fn x -> {x, "#{x}"} end)

Maps in Elixir are Hash Array Mapped Trie (HAMT) structures.

We won't dive deeply into the implementation of this data structure as it is beyond the scope of this course.

For practical purposes, be aware most operations on a map will have $O(log(n))$ complexity.

Maps scale better for large values when compared with lists or keyword lists, which grow linearly instead of logarithmically.

Your Turn

Accessing any key in a map with a million elements is nearly instant, regardless of which key is accessed!

First, we'll create the large map. This may take a moment.

large_map = Map.new(1..10_000_000, fn x -> {x, x} end)

While creating the map took some time, reading a value should be extremely fast.

Evaluate the cell below and notice how quickly we can access a value. Try changing key to any integer between 0 and 999_999. Notice there is no significant affect on the speed of accessing a value.

key = 500_000

{micro_seconds, _result} = :timer.tc(fn -> Map.get(large_map, key) end)

micro_seconds

On the other hand, Lists are slow compared to Maps because they need to enumerate each element.

large_list = Enum.to_list(1..1_000_000)

Try changing index to any integer between 0 and 999_999 and notice that the larger the index value, the slower it takes to access an element.

index = 500_000

{micro_seconds, _result} = :timer.tc(fn -> Enum.at(large_list, index) end)

micro_seconds

MapSets

MapSets are a set data structure. They function like a list that only allows non-duplicate values.

MapSet.new([1, 2, 3])

MapSets ignore duplicate values.

MapSet.new([1, 2, 3, 3])

MapSets are Maps under the hood, so they inherit the same performance properties as Maps.

Operation Time Complexity
Access $O(log(n))$
Search $O(log(n))$
Insertion $O(n)$ for <= 32 elements, otherwise $O(log(n))$
Deletion $O(n)$ for <= 32 elements, otherwise $O(log(n))$

The MapSet module contains functions for working with MapSets.

Here's a few to get you started:

  • new/1 create a new mapset.
  • put/1 add an element into a mapset.
  • delete/2 remove an element from a mapset.

A MapSet can contain any value. Keep in mind that order is not guaranteed.

MapSet.new(["1", 2, :three])

put/2 adds any non-duplicate element to a mapset.

set = MapSet.new([1, 2, 3])
MapSet.put(set, 4)

Duplicates will simply be ignored.

set = MapSet.new([1, 2, 3])
MapSet.put(set, 2)

delete/2 removes an element from a MapSet.

set = MapSet.new([1, 2, 3])
MapSet.delete(set, 2)

MapSet is enumerable. However, any Enum function with a MapSet returns a list.

MapSet.new([1, 2, 3]) |> Enum.map(fn each -> each + 1 end)

Generally, Lists are overused and can often be a MapSet instead. If you have a list where there should never be duplicate elements and order is not important, it's usually more performant to use a MapSet.

Your Turn

Create a MapSet with the elements 1, 2, 3. Use MapSet.member?/2 to check if your MapSet contains the element 2. Your answer should return true.



Commit Your Progress


Run the following in your command line from the beta_curriculum folder to track and save your progress in a Git commit.


$ git add .
$ git commit -m "finish maps mapsets keyword lists section"



Up Next






Previous
Next






Lists Vs Tuples
Fibonacci Challenge