Introduction

Sleep sort is a very curious and original algorithm. It brings several interesting questions. Such as, how to measure its complexity or in what cases does it perform the best.

Principle

In a nutshell: for each element to sort, start a thread or a process which sleeps a time proportional to the element and then pushes it back to the main thread.

Trivial Bash implementation:

1
2
3
4
5
6
7
8
9
10
11
12

#!/bin/bash
 
function f {
        sleep $1
        echo $1
}
 
while [ -n "$1" ] ; do 
        f $1 &
        shift
done
wait

Test suite

In order to study it and measure its performance we (me and Hartok) decided to implement the Sleep Sort in Python and gevent.

Our program generates a set of random numbers and sorts it with Sleep sort then with the Python built-in Quick sort and records timings. It works with three parameters:

• set size
• maximum value in the set
• the ratio between sleep time and values in the set (for example with 10 the thread for 42 sleeps for 42/10 seconds)

This last parameter is pretty tricky: the higher it is, the faster the Sleep sort works. But if it is too high, the time to start a new thread (or greenlet) will be more important than the sleep time for low values and the result will be incorrect. It seems to be strongly hardware dependent and a little tied to the other parameters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#!/usr/bin/python
 
import sys
import random
import time
import copy
import gevent
 
divisor = 900000
 
def sort(numbers):
        """ Sorts a list with Sleep Sort algorithm and measures time
        """
        begin = time.time()
 
        def f(n, result):
                gevent.sleep(float(n)/divisor)
                result.append(n)
        
        result = []
        greenlets = []
        # spawn a sleep greenlet for each value
        for n in numbers:
                greenlets.append(gevent.Greenlet.spawn(f, n, result))
 
        # wait for all greenlets to end
        gevent.joinall(greenlets)
        return (time.time()-begin, result)
 
def systemsort(numbers):
        """ Sorts a list with system sort function and measures time
        """
        begin = time.time()
        result = copy.copy(numbers)
        result.sort()
        return (time.time()-begin, result)
 
def generate(n, m): 
        """ Generates a list of n random numbers, each being less than m
        """
        numbers = []
        for i in range(n):
                numbers.append(random.randint(1, m))
        return numbers
 
if __name__ == '__main__':
        # read params
        try:
                n = int(sys.argv[1])
                m = int(sys.argv[2])
        except BaseException:
                print "usage: %s n m [d]" % sys.argv[0]
                print " - n number of random numbers"
                print " - m maximum random value"
                print " - d time divisor (optionnal), default is %d" % divisor
                sys.exit(1)
 
        try:
                divisor = int(sys.argv[3])
        except:
                pass
 
        # generate random values
        numbers = generate(n, m)
        # sleep sort them
        (sleep_time, sleep_result) = sort(numbers)
        # system sort them
        (system_time, system_result) = systemsort(numbers)
 
        if system_result == sleep_result:
                print "sleep sort succeed"
                print "sleep: %f" % sleep_time
                print "system: %f" % system_time
        else:
                print "sleep sort failed (time divisor too ambitious ?)"
                print "sleep: (%d elements)" % len(sleep_result)
                #print sleep_result.__str__()
                print "system: (%d elements)" % len(system_result)
                #print system_result.__str__()
                errors = 0
                for n in range(n):
                        if system_result[n] != sleep_result[n]:
                                errors = errors + 1
                print "%d errors" % errors

Test results

The overall performance of the Sleep sort is awful, but it has interesting performance when it comes to sets with few different values.

Avant-propos

Tout d'abord je voudrais remercier tous ceux qui ont promu mon billet précédent sur Twitter ou dans leurs blogs : en deux jours, je suis passé de 50 à 1000 visiteurs journaliers, avec une pointe à 3500 hier. Ça me donne vraiment envie d'écrire plus souvent.

Mon blog a d'ailleurs eu une petite coupure causée par cette affluence soudaine. Il est actuellement hébergé à la maison avec une machine à la retraite et une connexion ADSL. Je fais ça plus par conviction que par manque de moyens. Ce système marchait parfaitement pour 50 visiteurs journaliers mais il est évident que ça ne peut plus marcher avec 1000 et au-delà. Je vais donc le déplacer sur un serveur dédié plus traditionnel dans les jours qui viennent et il n'y aura plus de problèmes de ce côté.

Des personnes ont mentionné le tethering employé pour faire mes tests comme un non respect des conditions d'utilisation. Oui c'est vrai, mais techniquement, la provenance d'un paquet n'a aucune espèce d'importance et je me suis servi d'un PC pour une raison purement pratique, pour avoir accès à des outils comme tcpdump, wireshark, wget, nmap ou netcat. On pourrait refaire les mêmes tests depuis le terminal du téléphone et l'on trouvera rigoureusement la même chose. D'ailleurs la raison qui m'a poussé à faire ces tests est que je n'arrivais regarder presqu'aucune vidéo proposée par un site web depuis mon téléphone. D'autres personnes se plaignent de ne pas pouvoir consulter des documents tels que des journaux ou des BD depuis leur téléphone. Ceci démontre bien que ce n'est pas un problème de tethering, mais une véritable limitation pour ceux qui utilisent légitiment le service.

N'hésitez pas à me contacter si vous avez des questions techniques concernant le test de votre connexion. Je pourrai même vous aider si vous me donnez un accès SSH.

Introduction

De nombreuses personnes (et trolls) ont commenté mon billet précédent dans lequel je dénonçais la coupure des sessions TCP dépassant 10 Mo et l'interdiction, par un proxy transparent, de l'accès aux fichiers dépassant 10 Mo. Plusieurs personnes ont dit que ces limites étaient annoncées dans les conditions générales de service de l'opérateur. À ma grande surprise c'est vrai ! Mais pourtant, je me rappelle, en janvier 2011, avoir épluché ces conditions, avant de souscrire à mon forfait Internet et il n'y avait rien qui parlait de ce genre de limites.

Pratiques douteuses avec les CGS

Je ne suis pas du tout juriste, mais je sais que lorsqu'on souscrit à un service, surtout avec de l'engagement de durée, on signe un très long contrat décrivant très scrupuleusement le service souscrit et les conditions de son utilisation. Lorsque l'opérateur ne respecte pas ces conditions, ou lorsqu'il décide de changer de manière unilatérale ces conditions, le client n'est plus tenu à respecter son engagement. C'est exactement ce qui était arrivée avec l'augmentation de la TVA sur les services multimédias en février 2011.

Chez Bouygues Télécom on a une vision très particulière du contrat avec le client. Après des heures de recherche, la seule page qui contient des informations à valeur légale (et non pas des brochures ou des informations indicatives) est la suivante : http://www.laboutique.bouyguestelec...

La première chose qui m'a frappée, c'est que ces documents ne sont pas versionnés : il sont régulièrement mis à jour et toute trace des versions précédentes est effacée. Or c'est les conditions de service à la date où l'on a souscrit au service qui doivent être appliquées à un client. Le moindre changement doit être explicitement accepté par le client. C'est quelque chose que l'on voit régulièrement chez Free, sur la page d'accueil de l'espace client on nous propose d'accepter ou non des modifications apportées au contrat (souvent pour profiter de nouveaux tarifs ou services). Chez Bouygues, il est donc quasi impossible d'obtenir le texte des conditions de services à la date où l'on s'est abonné au service.

Deuxième point noir : "Conditions Générales de Service" est tout sauf un document légal, c'est encore une brochure de 4 pages qui prend la forme d'une FAQ et où on vous dit en gros deux choses :

• Les seules raisons valables pour résilier avant la fin de l'engagement c'est le décès ou l'emprisonnement à longue durée du client.
• Tous les tarifs et les services sont définis dans le "Guide des tarifs".

Alors là c'est très fort : pour la description et les tarifs des services souscrits on vous renvoie à une brochure !

Changement des CGS en douce

Je tombe alors sur le fameux "Guide des tarifs" version "mai/août 2011" qui prend la forme d'une brochure explicative des prix et des services avec, à la page 74, "les informations contractuelles". Cette dernière partie se contente de reprendre le texte des "Conditions Générales de Service" sous forme de FAQ.

Dans la partie non contractuelle on trouve effectivement la phrase suivante :

INTERNET
Correspond à la navigation sur tous les sites Internet ou wap. Cette navigation s'effectue soit :
sur votre mobile ou sur votre ordinateur/tablette grâce à l'option modem 24/24. Chaque télé-
chargement ou accès en streaming est de 10Mo maximum.

Première remarque : on est en train de nous dire que Internet c'est naviguer sur des sites Internet ou WAP. On m'a appris à l'école, que Internet est un réseau qui interconnecte des millions de réseaux et leur permet d'échanger des données au moyen du protocole IP. Chez Bouygues Internet c'est la consultation d'un seul service, le web, au moyen du protocole HTTP. Soit.

Deuxième remarque : toutes les limites d'utilisation du service Internet sont répertoriées dans la partie contractuelle de la brochure, mais pas celle-là ! Ça sent l'ajout à la va-vite, sans avoir consulté le juriste pour inclure cette condition dans les véritables CGS...

J'avais vraiment le sentiment que cette phrase ne figurait pas dans le "Guide des tarifs" en janvier 2011. Heureusement que le web conserve et archive des documents : j'ai pu retrouver les PDF des versions précédentes du "Guide des tarifs", effacées du site officiel :

guide des tarifs bouygues "Offres mobile" filetype:pdf

Résultats :

• 12729PHR novembre/janvier 2010 : pas de paragraphe "INTERNET", mais un modeste paragraphe "SURF" qui donne des exemples d'utilisation
• 12755PHR mars/mai 2010 : +"L’Internet depuis un mobile correspond à l’échange de données (dont les e-mails) sur les sites Internet ou WAP."
• 12783PHR août/novembre 2010 : "Correspond à la navigation sur tous les sites Internet ou wap. Cette navigation s’effectue exclusivement sur votre mobile non relié à un ordinateur ou avec une clé 3G+ relié à un seul ordinateur."
• 12820PHR janvier/mars 2011 : pas de changement
• 12830PHR mars/mai 2011 : pas de changement
• 12846PHR mai/août 2011 (version actuelle) : bingo ! +"Chaque télé-chargement ou accès en streaming est de 10Mo maximum."

Je ne veux pas soutenir une quelconque théorie du complot, ou me donner de l'importance : mais mon billet précédent a été publié le 19 avril 2011 et à l'époque je l'avais twitté à @bouyguestelecom et il avait fait déjà un peu de bruit.

Conclusion

Les Conditions Générales de Service de Bouygues ont été modifiées en douce en mai 2011 pour rendre contractuelles des limitations techniques intolérables. Les versions précédentes des documents contractuels sont effacées pour faire comme si tous les clients acceptaient tacitement n'importe quel changement.

Le contrat que j'ai signé en janvier 2011 ne mentionne pas ces limitations, pourtant je les subis et je n'ai jamais accepté les nouvelles conditions. Dans la mesure où ce changement est une régression du service proposé, ceci constitue une modification unilatérale de mon contrat. Je suis actuellement en stage à l'étranger et ma ligne est temporairement suspendue. À mon retour je compte envoyer une lettre de résiliation.

Je voudrais vraiment entendre des vrais avis juridiques sur la question. L'idéal serait de faire étudier la problématique à quelqu'un comme Maître Éolas... Il y a peut-être aussi du matériel pour une action de l'UFC Que choisir ?

Edit

J'ai retrouvé plusieurs autres PDF 12***PHR, surtout le "mars/mai 2011" qui était la pièce manquante pour avoir la preuve que le changement a été introduit en mai 2011. J'ai aussi ajouté une évolution plus détaillé du paragraphe problématique : on s'aperçoit qu'il a été remanié plus d'une fois !

Remarquez le passage de "SURF" à "INTERNET" après janvier 2010. Bizarrement ce changement n'a pas entraîné l'ouverture d'autres services que le web ou l'attribution d'adresses IP Internet aux clients...