.. _ch03-python-dictionaries:

===============================================================
Dictionaries
===============================================================

Another useful data type built into Python is the dictionary.
A dictionary is like a list, but it is more general. In a list, the indices have to be integers;
in a dictionary they can be any type.


.. _ch03-python-key-value:

Key:value pair
----------------------------------------------------------------

You can think of a dictionary as a mapping between two things:
 * **keys**: a set of indices,
 * **values**: a set of values corresponding to each key.

Each key maps to a value. The association of a key and a value pair
is called a **key:value pair**.

You can define an empty dictionary in two ways.
One way is to use a built-in function ``dict``

.. code-block:: python

   >>> eng2kor = dict()

or altenatively, use an empty squiggly-brackets, ``{}``

.. code-block:: python

   >>> eng2kor = {}

In both cases you see the following

.. code-block:: python

   >>> type(eng2kor)
   <type 'dict'>
   >>> print eng2kor
   {}

Let's add a new pair to the dictionary, ``eng2kor``. To add one, you can
use square brackets

.. code-block:: python

   >>> eng2kor['one'] = 'hana'

This creates a new key:value pair that maps from the key ``one`` to the value
``hana``. If we print the dictionary again

.. code-block:: python

   >>> print(eng2kor)    # or simply >>> eng2kor
   {'one': 'hana'}

One can add multiple pairs using this output format

.. code-block:: python

   >>> eng2kor={'one':'hana','two':'dool','three':'set','four':'net'}

Unfortunately, ``append`` method cannot be invoked on a dictionary *directly*
(i.e., ``eng2kor.append('five')`` won't work).
Instead, one can keep adding new pairs using

.. code-block:: python

   >>> eng2kor['five'] = 'dasut'

or using ``update`` (try ``help(dict)`` or ``dir(dict)`` to see more options)

.. code-block:: python

   >>> eng2kor.update({'five':'dasut'})

Let's now print to see what we have defined so far

.. code-block:: python

   >>> print eng2kor
   {'four': 'net', 'three': 'set', 'five': 'dasut', 'two': 'dool', 'one': 'hana'}

The order of the key:value pairs does **not** look like what you might have expected.
In fact, they might look different on different computers. Surprisingly, the order of
pairs in a dictionary is unpredictable. This is because the elements
of a dictionary are never indexed with integer indices (they are still iterable though).
Even though it might look confusing, this is not a problem as long as the one-to-one
correspondance between the key:value relationships remain unchanged,
which is the case all the time

.. code-block:: python

   >>> eng2kor['five']
   'dasut'

   >>> eng2kor['two']
   'dool'

or traversing through the dictionary will show

.. code-block:: python

   >>> for i in eng2kor:
   ...     print i
   ...
   four
   three
   five
   two
   one

Here we see that traversing a dictionary is executed among the key lists, not
the value lists.


We can use the iterators that are defined as methods in dictionary
(try ``help(dict)`` and find these), ``items()``, ``keys()``, and ``values()``

.. code-block:: python

   >>> for eng, kor in eng2kor.items():
   ...     print eng, kor
   ...

   one hana
   two dool
   three set
   four net
   five dasut

or, to just get keys

.. code-block:: python

   >>> for eng in eng2kor.keys():
   ...     print eng
   ...

   one
   two
   three
   four
   five

Similarly, to just get values

.. code-block:: python

   >>> for kor in eng2kor.values():
   ...     print kor
   ...
   hana
   dool
   set
   net
   dasut

The method ``items()`` defined in dictionary changes the dictionary to
a list with ``(key,value)`` pairs as tuples

.. code-block:: python

   >>> eng2kor.items()
   dict_items([('one', 'hana'), ('two', 'dool'), ('three', 'set'), ('four', 'net')])

We can apply some of the methods we learned so far to a dictionary

.. code-block:: python

   >>> len(eng2kor)
   5

   >>> 'one' in eng2kor
   True

   >>> 'net' in eng2kor
   False

The second example of the ``in`` operator tells us that Python checks if
the search word appears as a ``key``, but not as a ``value`` in the dictionary.

To see whether something appears as a value instead of a key, is to use the method
``values`` which returns the values as a list

.. code-block:: python

   >>> print(eng2kor.values())
   dict_values(['hana', 'dool', 'set', 'net'])

With this we can now search

.. code-block:: python

   >>> vals = eng2kor.values()
   >>> 'net' in vals
   True

We can also compare between keys or between values

.. code-block:: python

   >>> eng2kor.keys()
   dict_keys(['one', 'two', 'three', 'four'])


.. _ch03-python-counter:

Dictionary as a set of counters
----------------------------------------------------------------

Consider that you are given a string and you wish to count how many times
each character appears. Recall that we did this before using a list :ref:`ch03-python-searching-counting`.
This time let's use a dictionary and see how we can implement a more general algorithm:

.. literalinclude:: ./codes/examples/dictionaries/histogram.py
   :language: python
   :linenos:

Running this in the script mode will give

.. code-block:: console

   $ python3 histogram.py
   (a): {'a': 1, 'p': 2, 'l': 1, 'e': 1}
   (b): {'a': 1, 'p': 2, 'l': 1, 'e': 1}
   (c): False
   (d): 4402933120
   (e): 4402933336
   (f): dict_keys(['a', 'p', 'l', 'e']) 4398279176
   (ff) dict_keys(['a', 'p', 'l', 'e']) 4398278408
   (g): False
   (h): True
   (i): dict_values([1, 2, 1, 1])
   (j): False
   (k): False
   (l): 1
   (m): 159
   (n):--------
   a 1
   p 2
   l 1
   e 1



Dictionaries and lists
----------------------------------------------------------------
Lists can only appear as values in a dictionary, but **not** keys.
For example, if you try

.. code-block:: python

   >>> t=['a','e','l']
   >>> type(t)
   <class 'list'>
   >>> d = dict()
   >>> d[t]
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   TypeError: unhashable type: 'list'

   >>> d['1'] = t
   >>> d
   {'1': ['a', 'e', 'l']}


The above example confirms that lists can only be used as values.
Now, let's consider an application of using lists as values.
Take a look at what we just obtained in the last outcome,
``{'1': ['a','e','l']}``. This looks like an inverse map of the output
``(a)`` or ``(b)``!
This example tells us that we may implement an inverse map routine
which inverts keys and values in a dictionary. Here is a function
that inversts a dictionary:

.. literalinclude:: ./codes/examples/dictionaries/invert_dictionary.py
   :language: python
   :linenos:


The result look like

.. code-block:: console

  $ python3 invert_dictionary.py
  {'a': 1, 'p': 2, 'e': 1, 'l': 1}
  {1: ['a', 'e', 'l'], 2: ['p']}
  {1: 1, 2: 1}
  {1: [1, 2]}

.. note::
   Why are we getting the last two outcomes?


Dictionaries as memos
----------------------------------------------------------------

A dictionary can be used for storing quantities that have been already computed,
and thereby one doesn't need to repeat such previously computed operations.
In computing, this clearly allows a faster performance by efficiently reusing the
stored data.

For example, a straightforward implementation
of `Fibonacci sequence <https://en.wikipedia.org/wiki/Fibonacci_number>`_
can look like:

.. literalinclude:: ./codes/examples/dictionaries/fibonacci.py
   :language: python
   :linenos:

Notice now how many times those terms that appear early in the sequence are
recursively called repeatedly -- very many! A dictionary can be used in this case to
keep track of the terms that have been already evaluated and store them in a dictionary:

.. literalinclude:: ./codes/examples/dictionaries/fibonacci_dict.py
   :language: python
   :linenos:

In the above example, ``known`` is a dictionary that stores the Fibonacci numbers
we already know. It starts with the first two terms in the sequence: ``F0=0`` and ``F1=1``,
or in other words, 0 maps to 0 and 1 maps to 1.

To compare CPU runtimes in seconds, we can do as follow:

.. literalinclude:: ./codes/examples/dictionaries/run_fibonacci.py
   :language: python
   :linenos:


Global variables
----------------------------------------------------------------

In the previous example, ``known`` is initialized *outside* the function. Therefore,
it belongs to the special frame called ``__main__``. Variables in ``__main__``
have their scopes *globally* because they can be accessed from any function.

In order to modify any mutable global variable, especially within a local function,
you need to **declare** it before using it.
The following example illustrates how the global variables behaves and how they
should be modified in a local function:


.. literalinclude:: ./codes/examples/dictionaries/global.py
   :language: python
   :linenos:


The result looks like

.. code-block:: console

   (a): True
   (b): False
   (c): True
   (d): True
   (e): False
   (f): True


An example study
----------------------------------------------------------------

Consider the following example which has been originally adopted from
`Dive Into Python 3 <http://www.diveintopython3.net/index.html>`_
and modified for the class.

This routine takes a computer file size in kilobytes as an input and
converts it approximately to a human-readable form, e.g., 1TB, or 931 GiB, etc.

.. literalinclude:: ./codes/examples/dictionaries/humansize.py
   :language: python
   :linenos:

The output from running the routine looks like

.. code-block:: console

   $ python3 humansize.py
   (a) with the multiple of 1000 bytes:  1 TB
   (b) with the multiple of 1024 bytes:  931 GiB