.. _adv_python-dictset:

**************************
Dictionnaires et ensembles
**************************

Après les séquences, nous abordons ici deux autres structures de données fondamentales en Python, les dictionnaires (:class:`dict`) et les ensembles (:class:`set`). Elles ont en commun de reposer sur des `tables de hachage <https://en.wikipedia.org/wiki/Hash_table>`_ conduisant à des performances algorithmiques en :math:`\Theta(1)` pour les opérations de recherche, d'insertion et de suppression. Au détriment d'une occupation mémoire plus importante que pour les séquences.

Les objets "hashables"
======================

Seuls les objets immutables sont "hashables" car leur valeur de hachage est constante tout au long de la durée de vie. Une valeur de hachage différente pour chaque objet différent est retournée par la fonction :func:`hash`::

    >>> hash("a string")
    -7948514637191243730
    >>> hash("another string")
    -722956108645606665
    >>> hash("one more")
    7230730472324293320

la fonction :func:`hash` est un wrapper autour de la méthode :meth:`__hash__` de l'objet concerné. Cette méthode doit être redéfinie lorsqu'on écrit sa propre classe::

    >>> "a string".__hash__()
    -7948514637191243730
    >>> "another string".__hash__()
    -722956108645606665
    >>> "one more".__hash__()
    7230730472324293320

Lorsque l'objet est *mutable*, tenter d'obtenir sa valeur de hachage lève une exception::

    >>> hash([1, 2, 3])
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unhashable type: 'list'

Pour les containers, non seulement le container lui même doit être *immutable*, mais également l'ensemble des objets qu'il contient, sinon une exception est levée::

    >>> t1 = (1, 2, 3)
    >>> hash(t1)
    2528502973977326415

    >>> t2 = (1, 2, [1, 2, 3])
    >>> hash(t2)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unhashable type: 'list'

Le :class:`set` est un cas particulier de container. Dans sa version classique, il est mutable et ne peut donc pas être utilisé comme clé de hachage::

    >>> hash(set([1, 2, 3]))
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unhashable type: 'set'

Mais il dispose également d'une version "frozen" *imutable* (:class:`frozenset`), ce qui le rend éligible::

    >>> hash(frozenset([1, 2, 3]))
    -7699079583225461316

    
Les dictionnaires
=================

Le dictionnaire est une structure fondamentale dans laquelle l'interpréteur Python stocke par exemple son environnement. Par exemple::

    >>> type(__builtins__.__dict__)
    <class 'dict'>
    >>> len(__builtins__.__dict__)
    153
    >>> __builtins__.__dict__['__doc__']
    "Built-in functions, exceptions, and other objects.\n\nNoteworthy: None is the `nil' object; Ellipsis represents `...' in slices."

Explorons quelques notions relatives aux dictionnaires.

Les dictcomp
------------

Comme pour les listes et les générateurs, Python dispose d'une syntaxe concise et lisible pour créer des dictionnaires. Le principe est de produire une paire clé-valeur à partir de séquences::

    >>> d = { chr(c):c for c in range(91,97) }
    >>> d
    {'[': 91, '\\': 92, ']': 93, '^': 94, '_': 95, '`': 96}

Comme pour les listcomp on peut insérer un prédicat simple::

    >>> d = { chr(c):c for c in range(32,127) if not chr(c).isalnum() }
    >>> d
    {' ': 32, '!': 33, '"': 34, '#': 35, '$': 36, '%': 37, '&': 38, "'": 39, '(': 40, ')': 41, '*': 42, '+': 43, ',': 44, '-': 45, '.': 46, '/': 47, ':': 58, ';': 59, '<': 60, '=': 61, '>': 62, '?': 63, '@': 64, '[': 91, '\\': 92, ']': 93, '^': 94, '_': 95, '`': 96, '{': 123, '|': 124, '}': 125, '~': 126}

.. admonition:: Exercice

    Construire un dictionnaire d'un million d'éléments avec une boucle classique puis avec un *dictcomp*. Comparer les temps d'exécution. Conclusions ?  


..
    Contrairement aux listes, pour l'efficacité algorithmique, il n'y a pas d'avantage significatif à utiliser un dictcomp.
    
    import timeit, sys

    print('dict with dictcomp : ', end = '')
    print(timeit.timeit('{ str(i):i for i in range(int(1e6))}', number=10))

    LOOP = '''
    d = {}
    for i in range(int(1e6)):
        d[str(i)] = i
    '''

    print('dict with loop/__getitem__ : ', end = '')
    print(timeit.timeit(LOOP, number=10))

    Les résultats sont tout à fait comparables::
    
    dict with dictcomp : 4.840082066268801
    dict with loop/__getitem__ : 4.917832062420141
    
Taille en mémoire
-----------------

Pour la gestion des collisions, l'utilisation d'une table de hachage pour implémenter le dictionnaire est plus gourmande en mémoire que la :class:`list`. Une liste de 1 million d'éléments occupe environ 9 Mb::

    >>> import sys
    >>> l = [i for i in range(int(1e6))]
    >>> print('size of list : ', sys.getsizeof(l))
    size of list : 8697464

Pour une taille équivalente, le dictionnaire nécessite environ 5 fois plus de mémoire (42 Mb)::
    
    >>> d = { str(i):i for i in range(int(1e6))}
    >>> print('size of dict : ', sys.getsizeof(d))
    size of dict :  41943144

C'est le prix à payer pour conserver un temps d'accès aux éléments en :math:`\Theta(1)`.

Clés et valeurs
---------------

Les méthodes :meth:`dict.keys` et :meth:`dict.values` retournent respectivement les clés et les valeurs du dictionnaire sous forme de vue dynamique et non pas de structure de donnée statique (une liste par exemple)::

    >>> d = { 'ENGIE':14.580, 'BNP PARIBAS':63.64, 'CARREFOUR':16.695, 'DANONE':70.17 }

    >>> k = d.keys()
    >>> type(k)
    <class 'dict_keys'>
    >>> k
    dict_keys(['ENGIE', 'BNP PARIBAS', 'CARREFOUR', 'DANONE'])

    >>> v = d.values()
    >>> type(v)
    <class 'dict_values'>
    >>> v
    dict_values([14.58, 63.64, 16.695, 70.17])

Une fois créées, ces vues sont une représentation dynamiques des clés et des valeurs du dictionnaire. Si on retire un élément du dictionnaire::

    >>> d.pop('ENGIE')
    14.58

Les vues dynamiques déjà créées reflètent les modifications intervenues sur le dictionnaire::

    >>> k
    dict_keys(['BNP PARIBAS', 'CARREFOUR', 'DANONE'])
    >>> v
    dict_values([63.64, 16.695, 70.17])
    
Performances
------------

L'utilisation d'une table de hachage dans les dictionnaires a pour conséquence que le test d'appartenance est indépendant de la taille, contrairement à ce qui se passe pour une séquence, pour laquelle la totalité de la collection doit être parcourue dans le cas où l'élément testé n'est pas présent.

.. code-block:: python
    :linenos:

    import timeit

    # 1e6 paires clé:valeur dans un dictionnaire 
    d = { i:str(i) for i in range(1000000) }

    setup = 'from __main__ import d' # setup for timeit measurement

    # 'in' test 

    stmt = '{} in d'

    for i in [9, 99, 999, 9999, 99999, 999999, 9999999]:
        s = stmt.format(i)
        b = eval(s)
        res = timeit.timeit(s, number=10, setup=setup)
        print('{:>12} : {:>5s} : {:>6.2f} µs'.format(s, str(b), res/1e-6))

D'autre part, le temps de recherche est du même ordre de grandeur, que la clé recherchée soit présente ou pas::

          9 in d :  True :   0.96 µs
         99 in d :  True :   0.96 µs
        999 in d :  True :   0.96 µs
       9999 in d :  True :   1.28 µs
      99999 in d :  True :   1.28 µs
     999999 in d :  True :   1.28 µs
    9999999 in d : False :   0.96 µs

Il en est de même pour les accés en lecture.

.. code-block:: python
    :linenos:

    import timeit

    # 1e6 paires clé:valeur dans un dictionnaire 
    d = { i:str(i) for i in range(1000000) }

    setup = 'from __main__ import d' # setup for timeit measurement

    # 'get' test 

    stmt = 'd.get({}, -1)'

    for i in [9, 99, 999, 9999, 99999, 999999, 9999999]:
        s = stmt.format(i)
        b = eval(s)
        res = timeit.timeit(s, number=10, setup=setup)
        print('{:>20} : {:>6} : {:>6.2f} µs'.format(s, b, res/1e-6))

Les temps d'accès sont supérieurs à une simple recherche de clé, parce qu'il y a une opération en plus (la récupération de la valeur)::

        d.get(9, -1) :      9 :   1.60 µs
       d.get(99, -1) :     99 :   1.60 µs
      d.get(999, -1) :    999 :   1.92 µs
     d.get(9999, -1) :   9999 :   1.60 µs
    d.get(99999, -1) :  99999 :   1.92 µs
   d.get(999999, -1) : 999999 :   1.92 µs
  d.get(9999999, -1) :     -1 :   1.60 µs

:meth:`~dict.popitem` est un peu plus rapide car l'élément retourné n'est pas choisi

.. code-block:: python
    :linenos:

    import timeit

    # 1e6 paires clé:valeur dans un dictionnaire 
    d = { i:str(i) for i in range(1000000) }

    setup = 'from __main__ import d' # setup for timeit measurement

    # 'popitem()' test 

    stmt = 'd.popitem()'

    for i in range(5):
        b = eval(stmt)
        res = timeit.timeit(stmt, number=10, setup=setup)
        print('{:>20} : ({},{}) : {:>6.2f} µs'.format(stmt, *b, res/1e-6))

Les temps sont donc inférieurs à ceux rencontrés pour :meth:`~dict.get`::

         d.popitem() : (999999,999999) :   1.28 µs
         d.popitem() : (999988,999988) :   1.28 µs
         d.popitem() : (999977,999977) :   1.28 µs
         d.popitem() : (999966,999966) :   1.28 µs
         d.popitem() : (999955,999955) :   1.28 µs



Gérer l'absence de clé
----------------------

Tenter d'accéder sans précaution à une clé de dictionnaire non existante, lève une exception::

    >>> d = { 'ENGIE':14.580, 'BNP PARIBAS':63.64, 'CARREFOUR':16.695, 'DANONE':70.17 }
    >>> d['LVMH']
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    KeyError: 'LVMH'

On peut traiter ce cas particulier de plusieurs façons. 

Une première façon pythonique de le faire est d'encapsuler la tentative d'accès dans un bloc :keyword:`try` - :keyword:`except`::

    >>> try:
    ...     d['LVMH']
    ... except:
    ...     print('Key is missing')
    ...
    Key is missing

Mais plutôt que de l'interrompre avec une exception, on peut souhaiter continuer le traitement, auquel cas on peut utiliser une valeur par défaut retournée par la méthode :meth:`dict.get`. Cette valeur par défaut est le second argument s'il est présent, :class:`None` sinon::

    >>> print(d.get('LVMH', 'NA'))
    'NA'
    >>> print(d.get('LVMH'))
    None

Mais si :meth:`dict.get` permet de fournir une valeur et de ne pas interrompre le traitement, la structure du dictionnaire n'est pas modifiée::

    >>> k
    dict_keys(['BNP PARIBAS', 'CARREFOUR', 'DANONE'])
    >>> v
    dict_values([63.64, 16.695, 70.17])

Si le dictionnaire doit être mis à jour, il faudrait une instruction d'affectation supplémentaire, ce qui est coûteux. La méthode :meth:`setdefault` est une réponse intéressante à ce problème puisqu'elle retourne la clé si elle est présente, ou l'initialise sinon::

    >>> d.setdefault('LVMH', 249.75)
    249.75
    
et le dictionnaire est bien modifié::

    >>> d.keys()
    dict_keys(['BNP PARIBAS', 'CARREFOUR', 'DANONE', 'LVMH'])
    >>> d.values()
    dict_values([63.64, 16.695, 70.17, 249.75])

:class:`~collections.defaultdict`: une alternative
--------------------------------------------------

Une autre façon de gérer l'absence de clé dans un dictionnaire est d'utiliser le :class:`~collections.defaultdict` qui permet de créer des valeurs à la volée lorsqu'on tente d'y accéder et qu'elles n'existent pas.

L'idée est de fournir à la construction une *factory* utilisée pour produire une valeur par défaut lorsqu'on passe une clé non existante à la méthode :meth:`~dict.__getitem__` (appelée chaque fois que l'on tente d'accéder à un élément du dictionnaire avec la syntaxe ``d[key]`` ).

:class:`~collections.defaultdict` fait partie du module :mod:`collections`::

    >>> from collections import defaultdict

Ici la *factory* est le constructeur de la classe :class:`list`::

    >>> dd = defaultdict(list)

A la création, le dictionnaire est bien entendu vide::

    >>> dd
    defaultdict(<class 'list'>, {})

    >>> k = dd.keys()
    >>> k
    dict_keys([])
    >>> v = dd.values()
    >>> v
    dict_values([])

Tenter d'accéder à une clé non existante ne lève pas d'exception mais crée une liste vide comme valeur::
    
    >>> dd['a']
    []
    
Le dictionnaire est bien modifié::
    
    >>> dd
    defaultdict(<class 'list'>, {'a': []})

La *factory* retourne une référence vers la valeur créée, qui peut alors être utilisée directement::
    
    >>> dd['b'].append(2)
    >>> dd
    defaultdict(<class 'list'>, {'a': [], 'b': [2]})

Par contre, la *factory* n'est appelée que lorsqu'on cherche à accéder à l'élément du dictionnaire avec la syntaxe ``dd[key]`` qui appelle la méthode :meth:`~dict.__getitem__`. Les autres méthodes d'accès ne déclenchent pas l'exécution de la *factory*.
    
    >>> dd.get('c')
    >>> dd
    defaultdict(<class 'list'>, {'a': [], 'b': [2]})

Un :class:`~collections.defaultdict` multi dimensionnel
-------------------------------------------------------

Pour organiser des données multidimensionnelles, on peut utiliser des dictionnaires de dictionnaires, des dictionnaires de dictionnaires de dictionnaires, etc... C'est la notion de dictionnaire multidimensionnel.

Une fonction récursive est utilisée :

.. code-block:: python

    # Utility function to create multi dim dictionary
    def multi_dict(K, type):
        if K == 1:
            return defaultdict(type)
        else:
            return defaultdict(lambda: multi_dict(K-1, type))

Son utilisation est directe, et l'utilisation d'un :class:`~collections.defaultdict` autorise à ne prendre aucune précaution sur l'existence des clés:

    >>> d = multi_dict(3, int)
    >>> d[sexe][age][dpt] = 17 # donnée fantaisiste
    
Un dictionnaire 'user defined'
------------------------------

Il peut arriver que les classes concrètes fournies par Python ne conviennent pas parfaitement à l'usage qu'on souhaite. Il est alors possible d'utiliser les `Abstract Base Class (ABC) <https://docs.python.org/3/library/collections.abc.html>`_ pour développer ses propres implémentations. Ces ABC fournissent un certain nombre de méthodes abstraites qu'il faut alors redéfinir dans la classe concrète qui en hérite.

On trouvera des informations complémentaires sur les objets Python dans la section `Emulating container types <https://docs.python.org/3/reference/datamodel.html#emulating-container-types>`_.

..
    Ce qui va suivre est inspiré de `How to “perfectly” override a dict? <https://stackoverflow.com/questions/3387691/how-to-perfectly-override-a-dict>`_. 

La première étape est d'hériter de la collection :class:`~collections.UserDict` et de redéfinir les méthodes abstraites :meth:`~object.__getitem__` (lecture), :meth:`~object.__setitem__` (écriture), :meth:`~object.__delitem__` (suppression), :meth:`~object.__iter__` (itération)et :meth:`~object.__len__` (taille).

Observer attentivement la redéfinition des méthodes ci dessous:

.. code-block:: python
    :linenos:

    # transformed_dict.py

    import collections

    class TransformedDict(collections.UserDict):
        """A dictionary that applies an arbitrary key-altering
        function before accessing the keys"""

        # Constructeur
        def __init__(self, *args, **kwargs):
            self.store = dict() # un dictionnaire est utilisé pour le stockage interne
            self.update(dict(*args, **kwargs))  # alimenté par les paramètres du constructeur

        # look up with transformed key
        def __getitem__(self, key):
            return self.store[key]

        # storage with transformed key
        def __setitem__(self, key, value):
            self.store[key] = value

        # delete internal dict entry
        def __delitem__(self, key):
            del self.store[key]

        # return an iterator over the internal dict
        def __iter__(self):
            return iter(self.store)

        # return len() of internal dict
        def __len__(self):
            return len(self.store)

Vérifions maintenant que les méthodes redéfinies fonctionnent correctement et confèrent à notre :class:`TransformedDict` toutes les propriétés d'un dictionnaire classique. 

On commence par importer :class:`TransformedDict`::

    >>> from transformed_dict import TransformedDict

Le constructeur fonctionne::

    >>> d = TransformedDict( { i:ord(i) for i in 'abcdef' } )
    >>> type(d)
    <class 'transformed_dict.TransformedDict'>

La redéfinition de :meth:`__getitem__` fait que l'accesseur ``[ ]`` fonctionne également::

    >>> d['a'] # __getitem__()
    97
    >>> len(d) # __len__()
    6

La redéfinition de :meth:`__setitem__` permet d'utiliser également la syntaxe ``[ ]`` en écriture::

    >>> d['g'] = 103 # __setitem__()
    >>> len(d)
    7

La redéfinition de :meth:`__delitem__` rend opérationnelle la fonction :func:`del`::

    >>> del d['a'] # __delitem__()
    >>> d['a']
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    File "C:\Users\User\Documents\ESIEE\AdvancedPython\transformed_dict.py", line 16, in __getitem__
        return self.store[key]
    KeyError: 'a'

La redéfinition de :meth:`__len__` rend opérationnelle la fonction :func:`len`::

    >>> len(d)
    6

La redéfinition de :meth:`__iter__` dote notre :class:`TransformedDict` d'un itérateur::

    >>> i = iter(d) # __iter__()
    >>> i
    <dict_keyiterator object at 0x00000130A6BA8408>
    >>> i.__next__()
    'e'
    >>> i.__next__()
    'f'

Les méthodes de base ayant été redéfinies, par héritage, les méthodes :meth:`~dict.pop`, :meth:`~dict.popitem`, :meth:`~dict.clear`, :meth:`~dict.update`, et :meth:`~dict.setdefault` sont également disponibles::

    >>> d.pop('b')
    98
    >>> len(d)
    5
    >>> d.popitem()
    ('e', 101)
    >>> len(d)
    4
    >>> d.update( { i:ord(i) for i in 'abc' } )
    >>> len(d)
    6
    >>> c = 'a'
    >>> d.setdefault(c, ord(c))
    97
    >>> len(d)
    6
    >>> c = 'h'
    >>> d.setdefault(c, ord(c))
    104
    >>> len(d)
    7

Il en est de même pour les méthodes :meth:`~object.__contains__`, :meth:`~dict.keys`, :meth:`~dict.items`, :meth:`~dict.values`, :meth:`~dict.get`, :meth:`~object.__eq__`, and :meth:`~object.__ne__`::

    >>> 'a' in d
    True
    >>> 'z' in d
    False
    >>> d.keys()
    KeysView(<transformed_dict.TransformedDict object at 0x00000000022F9A58>)
    >>> d.items()
    ItemsView(<transformed_dict.TransformedDict object at 0x00000000022F9A58>)
    >>> d.values()
    ValuesView(<transformed_dict.TransformedDict object at 0x00000000022F9A58>)
    >>> d.get('a', -1)
    97
    >>> d.get('z', -1)
    -1
    >>> dd = d
    >>> dd == d
    True
    >>> dd != d
    False

A cette étape le dictionnaire est presque fonctionnel, mais son affichage n'est pas encore opérationnel::

    >>> d
    <transformed_dict.TransformedDict object at 0x00000000022F9A58>

Il faut redéfinir la méthode :meth:`~object.__repr__` (et éventuellement :meth:`~object.__str__`). Lire `Difference between __str__ and __repr__ in Python <https://stackoverflow.com/questions/1436703/difference-between-str-and-repr-in-python>`_ pour comprendre la différence entre les deux. 

.. code-block:: python
    :linenos:

    def __repr__(self):
            return '{}({})'.format(self.__class__.__name__, repr(self.store))

Maintenant l'affichage du dictionnaire produit une chaîne de caractères informative, qui peut éventuellement être réutilisée pour la construction d'un autre objet::

    >>> d
    TransformedDict({'b': 98, 'a': 97, 'h': 104, 'f': 102, 'e': 101, 'd': 100, 'c': 99})    

La représentation textuelle fournie par la méthode :meth:`~object.__repr__` permettre de (re)créer l'objet:: 

    >>> a = eval(repr(d))
    >>> a
    TransformedDict({'b': 98, 'a': 97, 'h': 104, 'f': 102, 'e': 101, 'd': 100, 'c': 99})

A cette étape, nous avons donc ré implémenté un dictionnaire parfaitement fonctionnel. Cependant, il n'apporte aucune valeur ajoutée par rapport au :class:`dict` de base. C'est l'objectif de l'exercice qui suit.

.. admonition:: Exercice

    Modifier la classe :class:`TransformedDict` pour implémenter un dictionnaire dont les clés sont insensibles à la casse. Pour cela, il faut utiliser le dictionnaire interne pour le stockage et transformer les clés avant insertion dans ce dictionnaire. La transformation utilisée ici sera la mise en minuscules de la clé. Cela devra conduire au comportement suivant::

        >>> d['ABC'] = 1
        >>> d['ABC']
        1
        >>> d['abc']
        1
        >>> d['AbC']
        1

..
    # transformed_dict_sol.py

    import collections

    class TransformedDict(collections.UserDict):
        """A dictionary that applies an arbitrary key-altering
        function before accessing the keys"""

        # Constructeur
        def __init__(self, *args, **kwargs):
            self.store = dict()  # un dictionnaire est utilisé pour le stockage interne
            # alimenté par les paramètres du constructeur
            self.update(dict(*args, **kwargs))

        # look up with transformed key
        def __getitem__(self, key):
            return self.store[self.__keytransform__(key)]

        # storage with transformed key
        def __setitem__(self, key, value):
            self.store[self.__keytransform__(key)] = value

        # delete internal dict entry
        def __delitem__(self, key):
            del self.store[self.__keytransform__(key)]

        # return an iterator over the internal dict
        def __iter__(self):
            return iter(self.store)

        # return len() of internal dict
        def __len__(self):
            return len(self.store)

        # transform function set to identity()
        def __keytransform__(self, key):
            return str(key).lower()

        def __repr__(self):
                return '{}({})'.format(self.__class__.__name__, repr(self.store))

    if __name__ == '__main__':
        d = TransformedDict()
        d['ABC'] = 1
        print(d['ABC']) # 1
        print(d['abc']) # 1
        print(d['AbC']) # 1


Le :class:`~collections.Counter`
--------------------------------

Le :class:`~collections.Counter` est une classe fille de :class:`dict` qui possède des méthodes optimisées pour le comptage. Son constructeur accepte une séquence ou un dictionnaire. 

.. admonition:: Exercice

    Compter les occurrences de chacun des caractères présents dans le texte de `Victor Hugo <https://fr.wikipedia.org/wiki/Victor_Hugo>`_, :download:`Notre Dame de Paris<../data/NotreDameDeParis.txt>`. En extraire les 10 plus fréquents et les 10 moins fréquents. Avec les structures de données traditionnelles. Puis avec le :class:`~collections.Counter`. Vous mesurerez les performances algorithmiques des 2 solutions avec la fonction :func:`~time.perf_counter`.


    L'oeuvre est lue puis stockée dans une chaîne de caractères avec le code suivant::

        with open('NotreDameDeParis.txt', encoding='utf8', mode='r') as f:
            s = f.read()

..
    from collections import Counter
    from time import perf_counter

    with open('NotreDameDeParis.txt', encoding='utf8', mode='r') as f:
        s = f.read()

    print("text length : ", len(s))
    # text length :  1065831

    # build counter from text
    t0 = perf_counter()
    c = Counter(s)
    t1 = perf_counter()

    # extract ten most common signs
    l1 = c.most_common(10)
    t2 = perf_counter()

    # extract ten less common signs
    l2 = c.most_common()[:-10:-1]
    t3 = perf_counter()

    print("Counter built in {:8.6f} s".format(t1-t0))
    # Counter built in 0.098381 s
    print("10 most common : ", l1)
    # 10 most common :  [(' ', 159111), ('e', 123539), ('a', 64054), ('s', 61411), ('t', 59890), ('i', 59245), ('r', 54159), ('u', 53296), ('n', 52443), ('l', 47896)]
    print("    found in {:8.6f} s".format(t2-t1))
    #    found in 0.000058 s
    print("10 less common : ", l2)
    # 10 less common :  [('%', 1), ('Æ', 1), ('á', 1), ('ñ', 1), ('#', 1), ('\ufeff', 1), ('$', 2), ('@', 2), ('Ù', 2)]
    print("    found in {:8.6f} s".format(t3-t2))
    #    found in 0.000036 s


Les ensembles (:class:`set`)
============================

Les ensembles (:class:`set`) sont des structures de données qui reposent sur le même principe que les clés des dictionnaires (table de hachage). En conséquence, chaque élément qu'ils contiennent doit être *hashable* et est unique par construction. Les :class:`set` ne sont pas des séquences et ne supportent donc pas les opérations de *slicing*. Ils fournissent par contre de puissantes opérations ensemblistes que l'on peut mettre à profit pour la recherche.

On considère le problème suivant : on dispose d'un premier ensemble E de n nombres rééls uniques et d'un second ensemble V de k ( :math:`k << n` ) nombre réels uniques. On s'assurera par construction de l'ensemble V que :math:`k/2` valeurs sont incluses dans E et que :math:`k/2` valeurs ne le sont pas. On se propose de compter le nombre d'éléments de V contenus dans E et de mesurer les performances de cette opération lorsque E et V sont implémentés avec différentes structures de données. On s'intéressera ici aux containers :class:`list`, :class:`~array.array` et :class:`set`. Pour fixer les idées on prendra n = :math:`10^6` et  k = :math:`10^3`.

.. admonition:: Exercice

    Ecrire le code permettant de comparer les performances de l'opération de comptage pour les 3 structures de données ci dessus et en tirer les conclusions. Par construction de chacune, vous devez pouvoir inférer la hiérarchie entre elles avant d'écrire le code.

..
    import random
    import array
    import timeit

    n = 10**6  # taille de la meule de foin
    k = 10**3  # nombre d'aiguilles
    m = n + k // 2  # taille de l'échantillon

    # Build extended collection of unique random numbers

    EE = {1 / random.random() for i in range(m)}  # n + k//2 unique values
    while len(EE) < m:
        EE.add(1 / random.random())  # fill if any duplicates at previous step

    EE = list(EE)
    random.shuffle(EE)
    print("len(EE) = ", len(EE))
    print(EE[:10])

    # Build collection to search in

    E = EE[:n]
    print("len(E) = ", len(E))

    # Build collection of values to search for

    V = EE[n:] + random.choices(E, k=k // 2)  # keys out + keys in
    print("len(V) = ", len(V))


    def search_in_sequence(E, V):
        count = 0
        for i in V:
            if i in E:
                count += 1
        return(count)

    # Search in list

    # 198.05418721423695
    print(timeit.timeit("search_in_sequence(E, V)",
                            setup="from __main__ import search_in_sequence, E, V",
                            number=5))

    # Search in array

    E = array.array('d', E)
    V = array.array('d', V)
    # 62.11385011007169
    print(timeit.timeit("search_in_sequence(E, V)",
                            setup="from __main__ import search_in_sequence, E, V",
                            number=5))

    # Search in set

    E = set(E)
    V = set(V)
    def search_in_set(E, V):
        return len(E & V)
    # 0.0008646657053574813
    print(timeit.timeit("search_in_set(E, V)", 
                            setup="from __main__ import search_in_set, E, V",
                            number=5))