# Programming in JuliaSets and Dictionaries

## Sets

**Sets** are unordered collections of unique values. The main advantage of having a special type for sets is that the design of the data structure can be optimized for membership checking. Figuring out whether a given value is in an array requires going through each element in the array, so the amount of time it takes increases with the length of the array. By contrast, checking membership in a set can be done very quickly even if the set is large.

A = [1,2,3] S = Set(A) 2 in S # evaluates to true pop!(S, 2) # removes 2 push!(S, 11) # puts 11 in the set 2 in S # evaluates to false now

**Exercise**

Make a set which contains the first 10,000 prime numbers.

*Hint*: It suffices to look for primes among the first 110,000 integers. Compare how long it takes to check whether a given number is in that set to the time it takes to compute whether the number is prime using `Primes.isprime`

.

using Primes: isprime primes = # add code here primes_set = Set(primes) @time 98779 in primes @time 98779 in primes_set @time isprime(98779)

*Solution.* To get exactly 10,000 primes, we index the list obtained by filtering out the composite numbers:

using Primes: isprime primes = [k for k in 2:110_000 if isprime(k)][1:10000] primes_set = Set(primes) @time 98779 in primes @time 98779 in primes_set @time isprime(98779)

Put the three methods in order from fastest to slowest:

## Dictionaries

The internal mechanism that sets use to check membership extremely fast is also useful when the information you want to retrieve is more complex than just `true`

or `false`

.

For example, suppose you want to store a collection of color names together with the RGB values for each one. We'll store the names as

It's possible to do this by putting the names in an array and the values in a list of the same length:

```
names = ["fuchsia", "firebrick", "goldenrod"]
rgbs = [(256, 0, 256), (178, 34, 34), (218, 165, 32)]
```

However, this solution gets very tedious quickly. For example, modifying this structure requires

The Julia data structure tailored to the problem of encoding a map from one finite set to another is called a **dictionary**. Dictionaries are created by supplying pairs to the `Dict`

function. For example, the dictionary encoding the map described above looks like this:

rgb = Dict( "fuchsia" => (256, 0, 256), "firebrick" => (178, 34, 34), "goldenrod" => (218, 165, 32) )

The domain elements `"fuchsia"`

, `"firebrick"`

and `"goldenrod"`

are called the **keys** of the dictionary, and the codomain elements `(256,0,256)`

, `(178,34,34)`

, and `(218,165,32)`

are called the **values**.

We can also form new dictionaries from lists of pairs using the `dict`

function:

```
Dict([
("fuchsia", (256, 0, 256)),
("firebrick", (178, 34, 34)),
("goldenrod", (218, 165, 32))
])
```

We can perform a dictionary lookup using indexing `rgb["fuchsia"]`

returns `(256,0,256)`

. We can also change the value associated with a given key or introduce a new key-value pair using indexing and assignment:

rgb = Dict( "fuchsia" => (256, 0, 256), "firebrick" => (178, 34, 34), "goldenrod" => (218, 165, 32) ) rgb["crimson"] = (220, 20, 60) rgb

`keys`

and `values`

functions may be used to obtain the keys and values.

rgb = Dict( "fuchsia" => (256, 0, 256), "firebrick" => (178, 34, 34), "goldenrod" => (218, 165, 32) ) collect(keys(rgb))

**Exercise**

Consider a dictionary which encodes flight arrival times:

```
import Dates
arrival_times = Dict(
"JetBlue 924" => Dates.Time(7,9),
"United 1282" => Dates.Time(7,42),
"Southwest 196" => Dates.Time(7,3)
)
```

You can most easily use this dictionary to

Suppose you want to reverse the lookup direction: for any given time, you want to see which flight arrives at that time. One problem is that

Assuming that the codomain values are distinct, however, you can form a new dictionary that allows you to look up keys for values by using an array comprehension that iterates over the key-value pairs of the dictionary (obtainable using the `pairs`

function).

Implement this idea in the block below. Check that your dictionary works by indexing it with `Dates.time(7,9)`

.

import Dates arrival_times = Dict( "JetBlue 924" => Dates.Time(7,9), "United 1282" => Dates.Time(7,42), "Southwest 196" => Dates.Time(7,3) )

*Solution.* We use the `Dict`

function to convert the list of pairs back into a dictionary: `Dict([(b,a) for (a,b) in pairs(arrival_times)])`

.

## Exercises

**Exercise**

You can construct dictionaries using a comprehension in Julia. For example, here's a dictionary that maps each one-digit positive integer to its square:

`square_dict = Dict(k => k*k for k in 1:9)`

Use a dictionary comprehension to make a dictionary which maps each of the first 100 powers of 2 to its units digit. Note: you'll need to use `big(2)`

instead of `2`

to calculate its 100th power, because is larger than the largest 64-bit integer.

*Solution.* We convert to a string, get the last character, and convert back to an integer:

Dict([big(2)^k => parse(Int64, string(big(2)^k)[end]) for k in 1:100])

**Exercise**

Suppose you want to store student IDs in a part of a web application where the main thing you need to do is check whether an ID input by a student is a valid student ID (so you can flag it if it has been mistyped). Among the given options, the best data structure for this purpose would be a

*Solution.* This is an ideal use case for sets. Lists and tuples will be slower for checking membership, and dictionaries aren't quite appropriate because it isn't clear what the values would be.