DICTIONNAIRES

1 - Comparaison avec les listes

a) Rappels sur la construction des listes ; fonction caractéristique

?

def Caractéristique(L) :
    χ = [False] * (max(L) + 1)
    for x in L :
        χ[x] = True
    return χ

b) Listes sans répétitions : deux approches naïves

?

def SansRépétition_1(L) :
    Présents = []
    for x in L :
        if x in Présents :
            return False
    return True

def SansRépétition_2(L) :
    Présent = [False] * (max(L) + 1)
    for x in L :
        if Présent[x] :
            return False
        Présent[x] = True
    return True

c) Utilisation des dictionnaires

?

def SansRépétition_3(L) :
    Présents = {}
    for x in L :
        if x in Présents :
            return False
        Présents[x] = True
    return True

?


2 - Généralités

?


3 - Première application : calcul des effectifs

?

def Effectifs(L) :
    Présents = {}
    for x in L :
        if x in Présents :
            Présents[x] += 1
        else :
            Présents[x] = 1
    return Présents

?


4 - Deuxième application : matrices (très) creuses


Une matrice creuse est une matrice dont la plupart des coefficients sont nuls.

a) Représentation et conversions

?

from numpy import matrix
def Zéros(m, n) :
    return matrix([[0 for j in range(n)] for i in range(m)])
from random import randint as EntAléa
from numpy.random import poisson as Poisson
def MatAléa(m, n) :
    A = Zéros(m, n)
    K = Poisson(max(m, n))
    for _ in range(K) :
        i = EntAléa(0, m - 1)
        j = EntAléa(0, n - 1)
        A[i, j] = EntAléa(-10, 10)
    return A
def Creuse(A) :
    (m, n) = A.shape
    Coefs = {}
    for i in range(m) :
        for j in range(n) :
            if A[i, j] != 0 :
                Coefs[(i, j)] = A[i, j]
    return (m, n, Coefs)
>>> A = MatAléa(4, 4)
>>> print(A)
[[ 0  0  0  0]
 [ 8  0 -7 -3]
 [ 0 -7  0 -7]
 [-8  0  0  0]]
>>> Creuse(A)
(4, 4, {(1, 0): 8, (1, 2): -7, (1, 3): -3, (2, 1): -7, (2, 3): -7, (3, 0): -8})
def Matrice(M) :
    (m, n, cf) = M
    A = Zéros(m, n)
    for (i, j) in cf :
        A[i, j] = cf[(i, j)]
    return A
>>> MA = Creuse(A)
>>> print(Matrice(MA))
[[ 0  0  0  0]
 [ 8  0 -7 -3]
 [ 0 -7  0 -7]
 [-8  0  0  0]]

b) Addition

?

def Add(MA, MB) :
    (mA, nA, cfA) = MA ; (mB, nB, cfB) = MB
    if mA != mB or nA != nB :
        raise Exception("Dimensions incompatibles")
    cfC = {}
    for (i, j) in cfA :
        cfC[(i, j)] = cfA[(i, j)]
    for (i, j) in cfB :
        if (i, j) in cfC :
            cfC[(i, j)] += cfB[(i, j)]
            if cfC[(i, j)] == 0 :
                del cfC[(i, j)]
        else :
            cfC[(i, j)] = cfB[(i, j)]
    return (mA, nA, cfC)
>>> A = MatAléa(8, 12)
>>> B = MatAléa(8, 12)
>>> print(A + B)
[[  0   0   0   0   0   3  -4   1   0   9   2   0]
 [  3   3   0   0  -5   1   0   0   0   0  -4   0]
 [-10   5   0 -10   6   0   0   0   0   0   0   0]
 [  0   0   0   3   0  -8  -9   0   0   0   0  -1]
 [  0   0   0   0   0   3   0   0   7   0   0  -2]
 [  0   0   0   1   0   0   0  -2  -7  -3   0   0]
 [  0   0   0   0   0  -2   0   0   0   4   0   0]
 [  0   0   0   0   0   0   0   4   0   0   9   0]]
>>> MA = Creuse(A) ; MB = Creuse(B)
>>> print(Matrice(Add(MA, MB)))
[[  0   0   0   0   0   3  -4   1   0   9   2   0]
 [  3   3   0   0  -5   1   0   0   0   0  -4   0]
 [-10   5   0 -10   6   0   0   0   0   0   0   0]
 [  0   0   0   3   0  -8  -9   0   0   0   0  -1]
 [  0   0   0   0   0   3   0   0   7   0   0  -2]
 [  0   0   0   1   0   0   0  -2  -7  -3   0   0]
 [  0   0   0   0   0  -2   0   0   0   4   0   0]
 [  0   0   0   0   0   0   0   4   0   0   9   0]]

c) Multiplication

?

# Représentation en ligne def CEL(M) : (m, n, cf) = M LM = {} for (i, j) in cf : if i in LM : LM[i][j] = cf[(i, j)] else : LM[i] = {j : cf[(i, j)]} return (m, n, LM) # Idem en colonnes def CEC(M) : (m, n, cf) = M CM = {} for (i, j) in cf : if j in CM : CM[j][i] = cf[(i, j)] else : CM[j] = {i : cf[(i, j)]} return (m, n, CM) # Multiplication def Mul(MA, MB) : (mA, nA, cfA) = MA ; (mB, nB, cfB) = MB if nA != mB : raise Exception("Dimensions incompatibles") (_, _, LA) = CEL(MA) ; (_, _, CB) = CEC(MB) cfC = {} for i in LA : for j in CB : cfC[(i, j)] = 0 for k in LA[i] : if k in CB[j] : cfC[(i, j)] += LA[i][k] * CB[j][k] if cfC[(i, j)] == 0 : del cfC[(i, j)] return (mA, nB, cfC)
>>> A = MatAléa(8, 12) >>> print(A) [[ 0 0 0 0 -4 0 0 0 0 0 0 -4] [ 4 0 0 0 0 6 0 0 0 0 0 0] [ 0 0 0 0 0 -7 0 0 -5 0 2 -6] [ 0 0 0 0 0 2 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 -1 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 3 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 0]] >>> MA = Creuse(A) >>> MA (8, 12, {(0, 4): -4, (0, 11): -4, (1, 0): 4, (1, 5): 6, (2, 5): -7, (2, 8): -5, (2, 10): 2, (2, 11): -6, (3, 5): 2, (5, 7): -1, (6, 9): 3}) >>> print(A) [[ 0 0 0 0 -4 0 0 0 0 0 0 -4] [ 4 0 0 0 0 6 0 0 0 0 0 0] [ 0 0 0 0 0 -7 0 0 -5 0 2 -6] [ 0 0 0 0 0 2 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 -1 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 3 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 0]] >>> B = MatAléa(12, 5) >>> print(B) [[ 0 -7 0 0 0] [ 0 0 0 0 0] [ 0 0 0 0 6] [ 0 0 0 0 0] [ 0 0 0 0 0] [ -6 0 0 0 0] [ 0 0 -4 -7 0] [ 0 0 0 0 0] [ 0 10 0 0 0] [ 3 -7 0 -1 0] [ 0 0 0 1 -10] [ 0 0 0 0 0]] >>> print(Matrice(Mul(MA, MB))) [[ 0 0 0 0 0] [-36 -28 0 0 0] [ 42 -50 0 2 -20] [-12 0 0 0 0] [ 0 0 0 0 0] [ 0 0 0 0 0] [ 9 -21 0 -3 0] [ 0 0 0 0 0]] >>> print(A * B) [[ 0 0 0 0 0] [-36 -28 0 0 0] [ 42 -50 0 2 -20] [-12 0 0 0 0] [ 0 0 0 0 0] [ 0 0 0 0 0] [ 9 -21 0 -3 0] [ 0 0 0 0 0]]