Recherches autour de la fonction sort() (1/2)

Si vous êtes développeur PHP vous utilisez à coup sûr régulièrement la fonction sort(). Vous l’aurez sans doute remarqué, cette fonction est très efficace, tellement que personnellement je n’ai jamais eu besoin d’écrire une fonction de tri spécifique (en utilisant l’un des algorithmes de tri connus) là où j’aurais pu l’utiliser.

Mais comment est implémentée cette fonction ? Quel algorithme y est mis en oeuvre ? Peut être même que plusieurs sont utilisés en fonction des conditions initiales comme le nombre d’éléments à trier ou encore le nombre d’éléments différents à trier ? Pour comprendre cela, nous allons dans un premier temps essayer de trouver quels algorithmes correspondent aux performances de sort() par l’expérience puis nous fouillerons le code source la fonction pour trouver les vraies réponses.

Intéressons-nous à l’implémentation de cette fonction et en particulier à l’algorithme mis en oeuvre dans celle-ci. En premier lieu, j’ai décidé d’implémenter les principaux algorithmes de tris connus, de les expérimenter en faisant varier les paramètres de départ et de comparer leurs performances à celles de sort().

(Vous pouvez retrouver l’implémentation de ces algorithmes sur github)

Commençons par les algorithmes suivants :

  • Bulle
  • Comb
  • Insertion
  • Fusion
  • Rapide
  • Selection (avec et sans mémorisation)

Le graphique ci-dessous représente le temps de tri de chaque algorithme en fonction du nombre d’éléments à trier :

Capture d’écran 2015-02-10 à 22.36.14Première constatation : sort() est le grand vainqueur ! Sur le graphique il semble même constant. Pour y voir plus clair, regardons le même graphique en se concentrant sur les algorithmes les plus efficaces et pour un nombre d’éléments à trier plus important :

Capture d’écran 2015-02-10 à 23.27.12

On constate que :

  • L’algorithme le plus efficace est toujours celui de sort(), même sur des volumes importants ;
  • l’algorithme le plus proche des performances de sort() est le tri par insertion (étonnant non ?), réputé comme étant un tri naïf ;
  • sort() est très peu sensible à l’état du tableau à trier au départ, tout comme le tri fusion.

A ce stade (et sans tricher) on ne peut pas vraiment dire si on tient ou non le bon algorithme. En effet, sort() est très certainement implémenté en C et non en PHP, ce qui peut avoir de grands impacts sur ses performances. A contrario, peut-être que tout simplement nous ne tenons pas encore le bon algorithme de tri…

Dans le prochain article, nous testerons d’autres algorithmes de tri plus efficaces puis nous chercheront des réponses directement dans le code source de PHP.

Petite précision : ces tests ont étés effectués sous PHP 5.6.5.

plume-httpd

L’autre jour je me suis levé avec une idée en tête : « Et si j’écrivais mon propre serveur HTTP qui implémenterait la SAPI PHP ? ». En plus de l’envie qui me taraude depuis quelques temps d’écrire un compilateur, ça commence à faire beaucoup ! Mais pourquoi pas après tout ?

Voilà donc pourquoi je vais le faire :

  • Cela va me permettre de renouer avec un langage que je n’avais plus pratiqué pratiquement depuis la fin de mes études. Le choix est évident, je veux, entre autres, implémenter la SAPI PHP donc quoi de plus naturel que d’écrire ce serveur HTTP en C/C++ ? Après presque 2 ans de développement exclusivement en environnement LAMP, prendre du recul avec un langage bas niveau est idéal.
  • C’est un défi ! Pour le coup je pars vraiment de zéro, je vais devoir me débrouiller en environnement hostile, là où je n’ai plus mes habitudes. Je doute fortement que les problèmes que je pourrais rencontrer auront une solution à « copier, coller » toute prête sur Stack Overflow !
  • Lorsque le projet sera plus ou moins abouti, j’espère que d’autres développeurs auront l’envie de participer au projet, plus dans un but d’expérimenter et de geeker que par la volonté de produire un véritable produit utilisable en production.
  • Mieux comprendre le fonctionnement interne d’un serveur HTTP et par la même, aller voir « sous le capot » de PHP.
  • Enfin, cela va me forcer à mettre mon nez dans la RFC du protocole HTTP, ce qui est un de mes objectifs cette année !

Je me suis déjà lancé dans l’écriture de quelques lignes de code et mais je ne publierais les sources que lorsque j’aurais implémenté de manière primitive la méthode GET pour des fichiers statiques.

Pour ce qui est du nom du projet, je pensais à quelque chose qui pourrait symboliser l’aspect « léger » de l’application. Je me suis donc laissé inspirer par le logo du serveur HTTP apache. Ce sera donc plume-httpd. Ce nom n’est pas forcément définitif mais j’avoue que je l’aime bien :-).

Coder proprement

Livre: Coder proprement

Coder proprementIl y a quelques mois, lors d’un passage au rayon « littérature informatique » de la FNAC, je suis tombé sur un livre qui a attiré mon attention. Son titre, « Coder proprement » m’a interpellé. Je ne suis vraiment pas déçu d’avoir dépensé quelques euros pour ce livre qui depuis est devenu ma référence en terme de bonnes pratiques.

L’auteur est un « vrai » développeur qui a beaucoup de recul et a tiré de nombreux enseignements de ses années d’expérience dans l’informatique. Tout ce qu’il décrit est construit sur de vraies problématiques qu’il a rencontré au cours de sa carrière et que tout développeur rencontrera également.

De nombreux sujets sont traités, on y retrouve entre autres :

  • les conséquences d’un code sale;
  • le nommage de variables, fonctions, classes, …;
  • le découpage des fonctions;
  • la rédaction de commentaires;
  • le formatage du code;
  • la gestion des erreurs;
  • la conception des tests.

Bien que les exemples soient écrits en Java, n’importe quel développeur avec un minimum d’expérience est apte à aborder ce livre. Certaines parties 100% Java pourront toutefois être passées si besoin.

D’un point de vue général, je conseille ce livre parce que :

  • L’auteur a de la bouteille, il transpire l’expérience.
  • Les sujets abordés sont profonds et modernes (TDD, agile, …).
  • De nombreuses références à d’autres ouvrages de référence sont présentes.
  • Un chapitre entier résume toutes les bonnes pratiques présentes dans le livre ce qui permet de se rafraichir la mémoire régulièrement.

En conclusion, ce livre est pour moi une référence absolue que je conseillerais à tout développeur.

Livre disponible ici.

Objectifs 2014

Je profite de ce premier article depuis le « reset » de mon blog pour fixer mes objectifs pour 2014.

(Au fur et à mesure, je mettrait en vert les objectifs atteints)

Compétences

Ce que je veux maitriser :
– Le framework PHP Laravel
– Mise en place d’un serveur nginx.
– Configuration apache 2.2 et 2.4.
– Tous les codes HTTP
– HTTP 1.1 en profondeur
– TCP/IP en profondeur
– Savoir monter une architecture de serveurs pour un site web à forte audience
– Le fonctionnement interne de PHP
– Le fonctionnement interne de MySQL
– Les différents types d’enregistrements pour un nom de domaine
– Configurer iptables
– Angular.js
– Capuccino
– KCachegrind
– Tous les design patterns du GoF
HHVM
– Shell scripts avancés

Articles à écrire

– Les tris
– Mon avis sur prestashop
– Comment se prémunir contre les principales attaques en PHP ?
– Les principales directives de php.ini
– La précision des floats
– Un point sur le multithreading en PHP
– Être un bon développeur
– Quelques articles sur les design patterns

Lecture

Voici les livres que j’aimerais avoir le temps de lire :
Coder proprement ✓
– MySQL 5.6 – Administration et optimisation ✓
– Design Patterns pour Java
– Performances PHP
– Javascript: The Good Parts
– Understanding MySQL Internals

Ça fait un livre tous les 2 mois, j’espère pouvoir faire mieux :-).

Projets / Divers

Concevoir un langage de programmation (rien que ça !) pour :
– entretenir mes connaissances en compilation
– faire de la R&D
– refaire du C ou du JAVA
– le fun 🙂

Côté web :
– Enrichir, améliorer, optimiser www.annuaireanimaux.fr (PHP, Silex).
– Mettre en production www.infosanimaux.com (PHP, Laravel).

Participer à un projet open source.

Développer une application pour Karotz.

Changer le thème de ce blog !

Ecrire au moins 1 article tous les 15 jours.

Venir à bout du dossier « à lire » de mes marques pages !

 

Bref, j’espère pourvoir tenir tous mes objectif, je ferais le bilan l’année prochaine !