Tri plus rapide que prévu

Links: notebook, html ., PDF, python, slides ., GitHub

Dans le cas général, le coût d’un algorithme de tri est en O(n \ln n). Mais il existe des cas particuliers pour lesquels on peut faire plus court. Par exemple, on suppose que l’ensemble à trier contient plein de fois le même élément.

from jyquickhelper import add_notebook_menu
add_notebook_menu()
run previous cell, wait for 2 seconds
%matplotlib inline

trier un plus petit ensemble

import random
ens = [random.randint(0,99) for i in range(10000)]

On peut calculer la distribution de ces éléments.

def histogram(ens):
    hist = {}
    for e in ens:
        hist[e] = hist.get(e, 0) + 1
    return hist

hist = histogram(ens)
list(hist.items())[:5]
[(0, 91), (1, 97), (2, 101), (3, 99), (4, 87)]

Plutôt que de trier le tableau initial, on peut trier l’histogramme qui contient moins d’élément.

sorted_hist = list(hist.items())
sorted_hist.sort()

Puis on recontruit le tableau initial mais trié :

def tableau(sorted_hist):
    res = []
    for k, v in sorted_hist:
        for i in range(v):
            res.append(k)
    return res

sorted_ens = tableau(sorted_hist)
sorted_ens[:5]
[0, 0, 0, 0, 0]

On crée une fonction qui assemble toutes les opérations. Le coût du nivrau tri est en O(d \ln d + n)d est le nombre d’éléments distincts de l’ensemble initial.

def sort_with_hist(ens):
    hist = histogram(ens)
    sorted_hist = list(hist.items())
    sorted_hist.sort()
    return tableau(sorted_hist)

from random import shuffle
shuffle(ens)
%timeit sort_with_hist(ens)
100 loops, best of 3: 3.23 ms per loop
def sort_with_nohist(ens):
    return list(sorted(ens))
shuffle(ens)
%timeit sort_with_nohist(ens)
100 loops, best of 3: 2.9 ms per loop

Les temps d’exécution ne sont pas très probants car la fonction sort est immplémentée en C et qu’elle utilise l’algorithme timsort. Cet algorithme est un algorithme adaptatif tel que smoothsort. Le coût varie en fonction des données à trier. Il identifie d’abord les séquences déjà triées, trie les autres parties et fusionne l’ensemble. Trier un tableau déjà trié revient à détecter qu’il est déjà trié. Le coût est alors linéaire O(n). Cela explique le commentaire The slowest run took 19.47 times longer than the fastest. ci-dessous où le premier tri est beaucoup plus long que les suivant qui s’appliquent à un tableau déjà trié. Quoiqu’il en soit, il n’est pas facile de comparer les deux implémentations en terme de temps.

def sort_with_nohist_nocopy(ens):
    ens.sort()
    return ens
shuffle(ens)
%timeit sort_with_nohist_nocopy(ens)
The slowest run took 21.88 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 164 µs per loop

évolution en fonction de n

Pour réussir à valider l’idée de départ. On regarde l’évolution des deux algorithmes en fonction du nombre d’observations.

def tableaux_aleatoires(ns, d):
    for n in ns:
        yield [random.randint(0,d-1) for i in range(n)]

import pandas
import time
def mesure(enss, fonc):
    res = []
    for ens in enss:
        cl = time.clock()
        fonc(ens)
        diff = time.clock() - cl
        res.append(dict(n=len(ens), time=diff))
    return pandas.DataFrame(res)

df = mesure(tableaux_aleatoires(range(100, 30000, 100), 100), sort_with_nohist)
df.plot(x="n", y="time")
<matplotlib.axes._subplots.AxesSubplot at 0x219ef99ebe0>
../_images/tri_nlnd_18_1.png
df = mesure(tableaux_aleatoires(range(100, 30000, 100), 100), sort_with_hist)
df.plot(x="n", y="time")
<matplotlib.axes._subplots.AxesSubplot at 0x219eb2ea2b0>
../_images/tri_nlnd_19_1.png

L’algorithme de tri de Python est plutôt efficace puisque son coût paraît linéaire en apparence.

df = mesure(tableaux_aleatoires(range(100, 30000, 200), int(1e10)), sort_with_nohist)
df.plot(x="n", y="time")
<matplotlib.axes._subplots.AxesSubplot at 0x219efdadf98>
../_images/tri_nlnd_21_1.png

On ajoute un logarithme.

from math import log
df["nlnn"] = df["n"] * df["n"].apply(log) * 4.6e-8
df.plot(x="n", y=["time", "nlnn"])
<matplotlib.axes._subplots.AxesSubplot at 0x219f00cefd0>
../_images/tri_nlnd_23_1.png

Il faut grossier le trait.

from math import exp
list(map(int, map(exp, range(5, 14))))
[148, 403, 1096, 2980, 8103, 22026, 59874, 162754, 442413]
df100 = mesure(tableaux_aleatoires(map(int, map(exp, range(5, 14))), 100), sort_with_nohist)
dfM = mesure(tableaux_aleatoires(map(int, map(exp, range(5, 14))), 1e9), sort_with_nohist)
df = df100.copy()
df.columns = ["n", "d=100"]
df["d=1e9"] = dfM["time"]
df.plot(x="n", y=["d=100", "d=1e9"])
<matplotlib.axes._subplots.AxesSubplot at 0x219f147dfd0>
../_images/tri_nlnd_26_1.png

L’algorithme de tri timsort est optimisé pour le cas où le nombre de valeurs distinctes est faible par rapport à la taille du tableau à trier.