L3 MIASHS, Algorithme et Programmation 3, année 2022

Réductions algorithmiques

Lorsqu’on étudie les structures de données (au sens le plus général, pas celui vu nécessaire dans Python), on s’intéresse à la notion de réduction:

Ce qui nous intéresse, c’est les problèmes du genre:

Quelle complexité pour simuler la structure de données A avec une structure de donnée B.

Quand on se focalise sur Python, cela revient à définir des classes surchargeant la structure de données de votre choix en supposant en input une ou plusieurs classes implémentants des structures de données supports.

On parle de la complexité de la réduction pour la complexité de réaliser les opérations de bases de la structure de données implémentée en fonction de la complexité des opérations sur les classes supports.

Exemples: Implémenter une MutableSequence avec un MutableMapping

import collections
def MutableSequenceReduction(class_support):
    if not issubclass(class_support, collections.abc.MutableMapping):
        raise ValueError("La classe en entrée doit être un MutableMapping")

    class MutSeq(collections.abc.MutableSequence):
        _datastructure = None
        def __init_datastructure(self):
            if self._datastructure is None:
                self._datastructure = class_support()

        def __getitem__(self, index):
            self.__init_datastructure()
            if index not in self._datastructure:
                raise IndexError("list index out of range")
            return self._datastructure[index]

        def __len__(self):
            self.__init_datastructure()
            return len(self._datastructure)

        def __setitem__(self, key, value):
            self.__init_datastructure()
            if key not in self._datastructure:
                raise IndexError("list assignment index out of range")
            self._datastructure[key] = value

        def __delitem__(self, index):
            self.__init_datastructure()
            x = self[index]
            for i in range(index, len(self)-1):
                self[i] = self[i+1]
            del self._datastructure[len(self)-1]

        def insert(self, index, value):
            self.__init_datastructure()
            if index >= len(self):
                self._datastructure[len(self)] = value
            if index < 0:
                index = len(self) + index
            for i in range(index, len(self)):
                self._datastructure[i], value = value, self._datastructure.get(i+1)
    return MutSeq

Ainsi en faisant:

list_from_dict = MutableSequenceReduction(dict)

On obtient une nouvelle classe list_dict qui est une implémentation des séquence avec les dictionnaires classique. On peut vérifier que ça marche bien:

L = list_from_dict()
L.append(1)
L.append(2)
L.append(3)
del L[2]

for x in L:
    print(x)

1
2

Ce qui nous intéresse le plus ici, c’est la complexité des opérations surchargée:

__getitem__, __len__ et __setitem__ se réduise en \(O(1)\) aux opérations de MutableMapping.
__delitem__ et insert nécessite par contre une complexité en \(O(n)\) en les opérations __getitem__ et __setitem__ des MutableMapping.

Exemples2: Implémenter des MutableMapping avec des MutableSequence

On peut faire une réduction similaire dans l’autre sens. Pour ce faire, on va stocker dans la liste les pairs (key, value).

import collections
def MutableMappingeReduction(class_support):
    if not issubclass(class_support, collections.abc.MutableSequence):
        raise ValueError("La classe en entrée doit hériter de MutableSequence")

    class MutDict(collections.abc.MutableMapping):
        _datastructure = None

        def __init_datastructure(self):
            if self._datastructure is None:
                self._datastructure = class_support()

        def __getitem__(self, index):
            self.__init_datastructure()
            for (key, value) in self._datastructure:
                if key == index:
                    return value
            raise KeyError(index)
        
        def __len__(self):
            self.__init_datastructure()
            return len(self._datastructure)

        def __setitem__(self, key, value):
            self.__init_datastructure()
            for i, (k, value) in enumerate(self._datastructure):
                if k == key:
                    self._datastructure[i] = (key, value)
                    return
            self._datastructure.append((key, value))

        def __delitem__(self, key):
            self.__init_datastructure()
            for i, (k, value) in enumerate(self):
                if k == key:
                    del self._datastructure[i]
                    return
            raise KeyError(key)

        def __iter__(self):
            self.__init_datastructure()
            return map(lambda e:e[0], self._datastructure)            
    return MutDict

dict_from_list= MutableMappingeReduction(list)

On obtient une nouvelle classe dict_list qui est une implémentation des dictionnaires avec les listes classique. On peut vérifier que ça marche bien:

d = dict_from_list()
d.update(tomate="farcie", chouquette="garnie", poulet="roti")
print(len(d))
for x in d:
    print(x, d[x])

3
tomate farcie
chouquette farcie
poulet farcie

Voire le code fait en cours ici

Réductions et complexité

Nous avons vu trois abstractions de structures de données pour l’instant:

Les ensembles (MutableSet). Leur opération de bases sont:
- Le test d’appartenance à l’ensemble __contains__
- L’ajout: add
- La supression sans erreur: discard
- L’itérabilité: __iter__
- La longueur: __len__
Les listes (MutableSequence).
- La modification d’un élément de la liste: __setitem__
- La suppression d’un élément de la liste: __delitem__
- L’accès à un élément de la liste: __getitem__
- La logueur: __len__
- Insertion à une position dans la liste: insert

En particulier, faire une passe sur une liste (__iter__) est réalisé en faisant des appels successif à __getitem__. Il s’agit donc d’une opération de complexité linéaire.

def __iter__(L):
    def generator():
        for i in range(len(L)):
            yield L[i]
    return generator()

On pourrait également réalisé ça de manière plus fonctionnel:

def __iter__(L):
    return map(L.__getitem__, range(len(L)))

De même, l’appartenance est réalisé par une passe séquentiel dans la liste. Voici des implémentations simple:

def __contains__(L, key):
    for i in range(len(L)):
        if L[i] == key:
            return True
    return False

Et une version plus fonctionelle

def __contains__(L, key):
    return any(map(lambda i:L[i]==key, range(len(L))))

Les dictionnaires (MutableMapping)
- Définir une paire de clef/valeur: __setitem__
- Supprimer une paire de clef/valeur: __delitem__
- Accédérer à la valeur d’une clef: __getitem__
- Itérer sur toutes les clefs: __iter__
- Le nombre de paire de clef/valeur: __len__

On a vu qu’il était possible d’implémenter un dictionnaire avec une liste et réciproquement. Il est également possible d’implémenter un ensemble avec une liste (et réciproquement) ainsi qu’un dictionnaire avec un ensemble (et réciproquement).

Ces réductions ont un coût qui est évaluable: on parle alors de la complexité de la réduction: Pour cela, on doit évaluer le nombre d’appels à une méthode de base de la structure de données abstraites.

Implémentation d’un ensemble
Opérations	Liste	Dictionnaire
`__contains__`	O(n)	O(1)
`add`	O(1)	O(1)
`discard`	O(n)	O(1)
`__iter__`	O(1)	O(1)
`__len__`	O(1)	O(1)

On peut faire le même type de tableau pour les implémentations d’une liste:

Implémentation d’une Liste
Opérations	Ensemble	Dictionnaire
`__setitem__`	O(n)	O(1)
`__delitem__`	O(n)	O(n)
`__getitem__`	O(n)	O(1)
`__len__`	O(1)	O(1)
`insert`	O(n)	O(n)

L’implémentation d’un dictionnaire ne peut pas être efficace quelque soit la notion de complexité considérée. Pour ça, on se retrouve avec un tableau de complexité pas très pertinent.

Implémentation d’un Dictionnaire
Opérations	Ensemble	Liste
`__setitem__`	O(n)	O(n)
`__delitem__`	O(n)	O(n)
`__getitem__`	O(n)	O(n)
`__iter__`	O(1)	O(1)
`__len__`	O(1)	O(1)

Les listes ordonnées

Il est possible d’améliorer grandement la complexité de la réduction d’un ensemble (et dictionnaire) à partir d’une liste en stockeant les informations dans la liste de manière ordonnées. Pour cela on utilise l’ordre des hash des valeurs.

Il devient alors possible de trouver un élément en réalisant une recherche dichotomique. La liste sous-jacente doit être maintenue ordonnée néanmoins.

def SetFromOrdoredList(class_support):
    if not issubclass(class_support, collections.abc.MutableSequence):
        raise ValueError("La classe en entrée doit hériter de MutableSequence")

    class MutSet(collections.abc.MutableSet):
        def __init__(self):
            self._datastructure = class_support()
        def _contains_helper(self, key, i, j):
            if j + 1 <= i:
                return i

            mid = (i + j)//2
            if hash(key) < hash(self[mid]):
                return self._contains_helper(key, i, mid)
            return self._contains_helper(key, mid, j)
               

        def __contains__(self, key):
            return self._contains_helper(key, 0, len(self))
            
        def add(self, key):
            
        def discard(self, key):
            pass
        def __iter__(self):
            return iter(self._datastructure)
        def __len__(self):
            return len(self._datastructure)
    return MutSet

Traceback (most recent call last):
  File "/var/www/cha/check_py_md", line 77, in repl
    exec(code, env)
  File "<string>", line 18
        def __contains__(self, key):
TabError: inconsistent use of tabs and spaces in indentation

dict_from_list= MutableMappingeReduction(list)

On obtient une nouvelle classe dict_list qui est une implémentation des dictionnaires avec les listes classique. On peut vérifier que ça marche bien:

d = dict_from_list()
d.update(tomate="farcie", chouquette="garnie", poulet="roti")
print(len(d))
for x in d:
    print(x, d[x])

3
tomate farcie
chouquette farcie
poulet farcie

Compiled the: dim. 07 janv. 2024 23:19:05 CET