Skip to content

Latest commit

 

History

History
261 lines (181 loc) · 8.7 KB

maps_mapsets_keyword_lists.livemd

File metadata and controls

261 lines (181 loc) · 8.7 KB
Raw

Maps, Mapsets, And Keyword Lists

Mix.install([
  {:jason, "~> 1.4"},
  {:kino, "~> 0.9", override: true},
  {:youtube, github: "brooklinjazz/youtube"},
  {:hidden_cell, github: "brooklinjazz/hidden_cell"}
])

Navigation

Review Questions

Upon completing this lesson, a student should be able to answer the following questions.

  • When should you use a MapSet vs a list?
  • What are the performance impacts of MapSets, Maps, and Keyword Lists?

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/2 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


DockYard Academy now recommends you use the latest Release rather than forking or cloning our repository.


Run git status to ensure there are no undesirable changes.
Then run the following in your command line from the curriculum folder to commit your progress.


$ git add .
$ git commit -m "finish Maps, Mapsets, And Keyword Lists reading"
$ git push



We're proud to offer our open-source curriculum free of charge for anyone to learn from at their own pace.


We also offer a paid course where you can learn from an instructor alongside a cohort of your peers.
We will accept applications for the June-August 2023 cohort soon.


Navigation