Ch 11 - Dictionaries

Question 1

Think Julia

What is a dictionary?

Answer 1

**A Dictionary Is a Mapping **

A dictionary is like an array, but more general. In an array, the indices have to be integers; in a dictionary they can be (almost) any type.

A dictionary contains a collection of indices, which are called keys, and a collection of values. Each key is associated with a single value. The association of a key and a value is called a key-value pair, or sometimes an item.

In mathematical language, a dictionary represents a mapping from keys to values, so you can also say that each key “maps to” a value. As an example, we’ll build a dictionary that maps from English to Spanish words, so the keys and the values are all strings.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4140-4149). Kindle Edition.

Question 2

Think Julia

How can you create a new empty dictionary?

Answer 2

The function Dict creates a new dictionary with no items (because Dict is the name of a built-in function, you should avoid using it as a variable name):

julia > eng2sp = Dict()
Dict{ Any, Any} with 0 entries

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4149-4154). Kindle Edition.

Question 3

Think Julia

How can you add an item to a dictionary?

Answer 3

julia > eng2sp = Dict()
Dict{ Any, Any} with 0 entries

The types of the keys and values in the dictionary are specified in curly braces: here, both are of type Any. The dictionary is empty. To add items to the dictionary, you can use square brackets:

julia > eng2sp[” one”] = “uno”;

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4152-4165). Kindle Edition.

Question 4

Think Julia

How can you create a new dictionary with items in it?

Answer 4

you can create a new dictionary with three items as follows:

julia > eng2sp = Dict(“ one” = > “uno”, “two” = > “dos”, “three” = > “tres”)
Dict{ String, String} with 3 entries:
“two” = > “dos”
“one” = > “uno”
“three” = > “tres”

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4172-4178). Kindle Edition.

Question 5

Think Julia

How are dictionaries ordered?

Answer 5

The order of the items in a dictionary is unpredictable. If you type the same example on your computer, you might get a different result.

But that’s not a problem because the elements of a dictionary are never indexed with integer indices. Instead, you use the keys to look up the corresponding values:

julia > eng2sp[” two”]
“dos”

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4180-4187). Kindle Edition.

Question 6

Think Julia

How can you check if something is a key in a dictionary?

Answer 6

Now you can use the ∈ operator to see whether something appears as a key in the dictionary:

julia > “one” ∈ ks ………# ks is a dictionary
true
julia > “uno” ∈ ks
alse

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4205-4210). Kindle Edition.

Question 7

Think Julia

How can you find the number of keys in a dictionary?

Answer 7

The length function works on dictionaries; it returns the number of key-value pairs:

julia > length( eng2sp)
3

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4194-4198). Kindle Edition.

Question 8

Think Julia

How can you return an array of all the keys in a dictionary.

Answer 8

The function keys returns a collection with the keys of the dictionary:

julia > ks = keys( eng2sp);
julia > print( ks)
[” two”, “one”, “three”]

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4198-4204). Kindle Edition.

Question 9

Think Julia

How can you check if something is a value in a dictionary?

Answer 9

To see whether something appears as a value in a dictionary, you can use the function values, which returns a collection of values, and then use the ∈ operator:

julia > vs = values( eng2sp);
julia > “uno” ∈ vs
true

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4211-4218). Kindle Edition.

Question 10

Think Julia

How can you have a function throw an exception?

Answer 10

function reverselookup( d, v)
….for k in keys( d)
……..if d[ k] = = v
…………return k
……..end
….end
….error(“ LookupError”)
end

This function is yet another example of the search pattern, but it uses a function we haven’t seen before: error. The error function is used to produce an ErrorException that interrupts the normal flow of control. In this case it has the message “LookupError”, indicating that a key does not exist.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4313-4328). Kindle Edition.

Question 11

Think Julia

How can dictionaries and arrays cooperate with each other?

Answer 11

Dictionaries and Arrays

Arrays can appear as values in a dictionary. For example, if you are given a dictionary that maps from letters to frequencies, you might want to invert it— that is, create a dictionary that maps from frequencies to letters. Since there might be several letters with the same frequency, each value in the inverted dictionary should be an array of letters.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4343-4349). Kindle Edition.

Question 12

Think Julia

What quality must a dictionary key have?

Answer 12

I mentioned earlier that a dictionary is implemented using a hash table. That means that the keys have to be hashable.

A hash is a function that takes a value (of any kind) and returns an integer. Dictionaries use these integers, called hash values, to store and look up key-value pairs.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4378-4383). Kindle Edition.

Question 13

Think Julia

What is a: hash

Answer 13

I mentioned earlier that a dictionary is implemented using a hash table. That means that the keys have to be hashable.

A hash is a function that takes a value (of any kind) and returns an integer. Dictionaries use these integers, called hash values, to store and look up key-value pairs.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4378-4383). Kindle Edition.

Question 14

Think Julia

What is a: memo

Answer 14

One solution is to keep track of values that have already been computed by storing them in a dictionary. A previously computed value that is stored for later use is called a memo. Here is a “memoized” version of fibonacci:

known = Dict( 0 = > 0, 1 = > 1)
function fibonacci( n)
….if n ∈ keys( known)
……..return known[ n]
….end
….res = fibonacci( n-1) + fibonacci( n-2)
….known[ n] = res
….res
end

known is a dictionary that keeps track of the Fibonacci numbers we already know. It starts with two items: 0 maps to 0 and 1 maps to 1.

Whenever fibonacci is called, it checks known. If the result is already there, it can return immediately. Otherwise, it has to compute the new value, add it to the dictionary, and return it.

If you run this version of fibonacci and compare it with the original, you will find that it is much faster.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4414-4418). Kindle Edition.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4397-4413). Kindle Edition.

Question 15

Think Julia

What is a: main

Answer 15

Global Variables

In the previous example, known is created outside the function, so it belongs to the special frame called Main. Variables in Main are sometimes called global because they can be accessed from any function. Unlike local variables, which disappear when their function ends, global variables persist from one function call to the next.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4419-4424). Kindle Edition.

Question 16

Think Julia

What is a: global variables

Answer 16

Global Variables

In the previous example, known is created outside the function, so it belongs to the special frame called Main. Variables in Main are sometimes called global because they can be accessed from any function. Unlike local variables, which disappear when their function ends, global variables persist from one function call to the next.

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4419-4424). Kindle Edition.

Question 17

Think Julia

Can a global variable be changed inside a function?

Answer 17

If you try to reassign a global variable, you might be surprised. The following example is supposed to keep track of whether the function has been called:

been_called = false
function example2()
….been_called = true # WRONG
end

But if you run it you will see that the value of been_called doesn’t change. The problem is that example2 creates a new local variable named been_called. The local variable goes away when the function ends, and has no effect on the global variable.

To reassign a global variable inside a function you have to declare the variable global before you use it:

been_called = false
….function example2()
….global been_called
been_called = true end

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4431-4445). Kindle Edition.

Question 18

Think Julia

How can a global variable be changed inside a function.

Answer 18

If you try to reassign a global variable, you might be surprised. The following example is supposed to keep track of whether the function has been called:

been_called = false
function example2()
….been_called = true # WRONG
end

But if you run it you will see that the value of been_called doesn’t change. The problem is that example2 creates a new local variable named been_called. The local variable goes away when the function ends, and has no effect on the global variable.

To reassign a global variable inside a function you have to declare the variable global before you use it:

been_called = false
….function example2()
….global been_called
been_called = true end

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4431-4445). Kindle Edition.

Question 19

Think Julia

What should you do to a global variable to make it more performant?

Answer 19

For performance reasons, you should declare a global variable constant. You can no longer reassign the variable, but if it refers to a mutable value, you can modify the value:

const known = Dict( 0 = > 0, 1 = > 1)
function example4()
….known[ 2] = 1
end

Ben Lauwens and Allen B. Downey. thinkjulia (Kindle Locations 4477-4487). Kindle Edition.