PHP tableaux et data-structures

Cela fait plusieurs projets que je mène en PHP dans lesquels l’impact de mes choix de conteneur de données sont très importants. Basiquement, en php, en utilise les tableaux qui sont très intuitifs et très… puissants.  Pourtant pour des raisons d’occupation mémoire ou bien pour une utilisation très précise, eh bien ils sont gourmand. Petit tour d’horizon des tableaux et de leurs alternatives en php.

Les tableaux php : caisse omnipotents?

Conception

Soyons clairs : un tableau PHP, ce n’est pas un tableau C ou Java. Ce n’est pas une liste python, c’est… un tableau PHP. A la source, c’est une “ordered map”. Cela permet d’utiliser ces tableaux comme tableau, dictionnaire, liste, file, pile… Mais surtout, de manière sous-jacente cela signifie qu’en PHP tout ce qui sera rangé dans un conteneur de donnée (que ça soit un array ou autre chose), il y aura une association clé=>valeur.

Cela est extrêmement important car en PHP, cela signifie qu’avec un peu d’effort de conception, vous pouvez organiser vos tableaux pour qu’à l’usage tout soit en O(1). Vous sacrifiez un peu (beaucoup) de mémoire, mais ça va vite.
SI je prend le temps de dire cela, c’est qu’il arrive souvent qu’un développeur, habitué à des langages comme Java ou C construise son tableau comme un tableau indicé. Puis, comme il veut que ses données n’aient pas de duplicata, il fait une fonction du type :

[cc lang=”php”]
function insert($value,$collection){
if(array_search($value)!==false){
$array[] = $value;
}
}

[/cc]

Et ça c’est du O(n), donc le temps pour insérer un élément, au lieu d’être constant comme il l’est habituellement avec les tableaux php, sera croissant avec le nombre de données. Puisque nous sommes en php, rien ne nous interdisait pourtant de faire

[cc lang=”php”]
$array[$value]=isset($array[$value])?:true;
[/cc]

API

L’autre avantage des arrays PHP est l’API qui les accompagne. C’est cette API qui vous permettra d’utiliser les tableaux comme des piles/files (pop,push,shift), qui vous permettra aussi de voir les tableaux comme des ensembles (diff, merge, surcharge de l’opérateur + et -). Ces fonctions sont très nombreuses, et vous permettent d’économiser du temps de développement sur tout ce qui concerne les algorithmes de tri, de filtrage…

Les fonctions sur les arrays sont nommées de cette manière : array_nom_de_la_fonction. Et si la méthode a une variante qui accepte une callback, il suffira d’ajouter un “u” pour faire array_unom_de_la_fonction.

Les alternatives

Les alternatives que je présentes sont celles proposées par la SPL (Standard PHP Library). Je n’en présente volontairement que deux que j’ai utilisés récemment, mais un grand nombres de structures de données vous sont proposées. Vous aurez ainsi la possibilité d’utiliser une liste chaînée, une implémentation objet des tableaux, une pile et une file déjà codées. Mais place à deux structures que j’apprécie beaucoup.

Pour faire comme Java

Il faut faire plaisir aux fan de Java, il faut leur donner un tableau indicé à taille fixe qui ne se soucie pas des clés string des arrays.
C’est ainsi que fut créé SPLFixedArray. Son utilisation? comme un tableau java :
[cc lang=”php”]$array = new SPLFixedArray($size);[/cc] Contrairement à un tableau php habituel, il y aura d’emblée 5 cases de créées, et la taille sera de $size et non de 0. Un json_encode vous en assurera en imprimant :

{“0″:null,”1″:null,”2″:null,”3″:null,”4”:null}

Si, théoriquement un FixedArray est plus rapide (pas de hashmap) (5% sur la version 5.4, je ne sais pas pour la 5.5), son implémentation dans la 5.3 est légèrement plus lente qu’un array normal. Néanmoins, des progrès sont sans cesse faits et la conception en soit de la SPL évolue donc il faudra être patient. En fait la principale optimisation de la SPLFixedArray c’est l’utilisation mémoire. Ces derniers temps, j’ai migré un code qui se servait de matrice 10×10 de array vers SPLFixedArray. Auparavant, pour m’assurer du gain réel, j’avais été vérifier avec quelques benchmark le gain que je faisais et pour la mémoire, voici la différence :

  • Array : 225952 octets pour une matrice d’entiers 5×5
  • SPLFixedArray : 225632 octets pour une matrice d’entiers 5×5

gain : 320 octets pour 25 entiers stockés, ces entiers étant sur 64bits : nous faisons une économie de 320 octets pour 200 octets de données pures.

Cette tendance est réelle et confirmée par un gain de 1024 octets sur une matrice d’entiers 10×10.

SPLHeap

Se déclinant en MinHeap, MaxHeap et PriorityQueue, le tas est une structure de données que j’ai pu utiliser dans deux cas très précis, à savoir l’algorithme de Dijkstra et une insertion de données dans une collection de manière à ce que les nouvelles données ne cassent pas l’ordre désiré.

Ici il s’agit surtout d’éviter absolument des opérations de tri en O(nlog(n)) à chaque fois qu’on doit insérer une donnée. En effet même si les processeurs actuels sont rapides, c’est quand même assez long comme complexité. Consommer un “log(n)” à l’insertion permet d’éviter un tri complet à chaque fois. En plus cela permet de contrôler l’endroit où l’objet est inséré grâce à plusieurs paramètres pondérés.

Conclusion

Même si elle a certaines failles de conception la SPL vous offre des alternatives intéressantes pour ranger vos données de manière optimisée. Néanmoins les tableaux php restent sa plus grande force et permettent une optimisation temporelle des algorithmes qui est immense ! N’hésitez pas à réfléchir à la manière dont vous utilisez vos tableaux !

Compte rendu du world forum 2/3

Nous voici donc au début de la seconde partie de mon compte rendu du 6ème world forum de lille sur l’économie responsable. Je m’intéresserai aujourd’hui à la conférence donnée par M.Didier LEROY, CEO de TOYOTA Europe intitulée Troisième révolution industrielle : les transports.

La technologie hybride : économie, modularité, performance

M.Leroy commence sa conférence sur un constat : les constructeurs automobile sont des pures produits de la seconde révolution industrielle, pas de la troisième, encore à venir. Leur business model n’en est que plus impacté.

Pourtant, avec le programmePrius,voiture hybride sortie en 1997 pour le premier modèle, Toyota (et les constructeurs concurrents, PSA en particulier) voit s’ouvrir devant elle la porte de la troisième révolution industrielle.

Au départ, la technologie hybride devait être un hommage aux accords de Kyoto en 1997 et surtout -alors que la courbe du prix du pétrole de cessait de monter- une promesse de consommer moitié moins d’essence.

A l’aune des nouveaux moteurs, à la fois plus petits, plus perfectionnés, mieux construits peut être et qui produisent bien moins qu’avant, ces 50% semblent être surtout marketting. Mais à l’époque c’était une révolution, tant et si bien qu’avec la troisième version de la Prius peu importe qu’elle soit rechargeable ou non, en comparant aux moteurs actuels, le véhicule consomme 66% de moins. Je ne connais pas les chiffres de l’hybride diesel de Peugeot, mais ils ne doivent pas être loin du compte.

La technologie hybride ne se résume pas à un moteur essence et un moteur électrique qui ont des régimes d’utilisation différents. Elle se compose d’un grand nombre de modules : batterie, récupération d’énergie au freinage, calculateurs embarqués pour optimiser le tout… Ces modules peuvent être ajoutés à des voitures essence, électrique, à pile à combustible ou même à des installations domestique – c’est dire le potentiel économique !

Malheureusement, je parlais de l’ancrage fort des constructeurs automobiles dans la seconde révolution industrielle, et si l’hybride -aujourd’hui rentable chez tous les constructeurs- a pu réussir, c’est surtout grâce aux aides des différents états. Au Japon cela a permis d’avoir une population conduisant 40% de voitures hybrides.

La voiture : au sein du réseau

Au delà de la technique et de la technologie, l’avenir de la voiture semble être un usage alternatif et surtout spontané. Ce mot est important car ce sont deux catastrophes naturelles qui ont mis ces utilisations en exergue : le tsunami qui a mené à la catastrophe de Fukushima et l’ouragan Sandy.

Durant ces deux catastrophe, fondations, états, entreprises fournirent (autant par philanthropie que pour la communication) du matériel et entre autre des voitures. Rapidement, une pratique a émergé : utiliser la batterie des voitures hybrides comme générateur d’appoint pour les besoin de base en électricité d’une maison : réfrigérateurs, chauffe-eau, plaque à induction. Une voiture hybride peut fournir 1.5 kW pendant 4 jours avec un réservoir plein !

Ces utilisations alternatives ont permis de remettre en question la place de la voiture dans le réseau énergétique (pas que électrique !) et Toyota (ainsi que d’autres) travaille désormais à intégrer ses Prius rechargeables dans les smart-grid, utilise un réseau social d’utilisateurs pour optimiser la mobilité des utilisateurs ainsi que la qualité de leur service de maintenance ! Par exemple votre smartphone peut recevoir l’état actuel de votre voiture et l’envoyer à votre garagiste qui décidera s’il y a besoin de réparation et vous donnera immédiatement ses plages horaires.

Constructeurs de la troisième révolution industrielle = constructeur de mobilité?

M.LEROY a aussi ouvert la discussion à propos de ce que pourrait être la place d’un constructeur automobile dans la troisième révolution industrielle. Sa position était qu’il fallait être un constructeur de mobilité : s’assurer de transporter l’utilisateur d’un point A à un point B que ça soit par voiture, transport en commun, vélo… Il nous a proposé le schéma Voiture->gare train->ville d’arrivée véhicule électrique (scooter, voiture, vélo) -> destination.

Ce schéma me plait et me fait penser aux installations collectives qui ont généré tant de revenu aux villes de Paris et Lille (Vel’lib, Vel’lille, Autolib…) et qui ont permis d’intégrer des voitures électriques sur un business model différent des constructeurs habituels. C’est une expérience qui semble avoir marché. Par contre, à l’opposé, M.LEROY ne croit pas en la stratégie de Renault de miser sur le véhicule électrique comme véhicule pour particulier. Il manque d’autonomie, de performance et il fait peur aux utilisateurs. Il dit que TOYOTA n’a pas trouvé le business model adéquat à l’intégration du véhicule électrique dans sa gamme européenne. Soit, le future nous en dira plus.

Le véhicule du future : le véhicule à pile à combustible

Le véhicule à pile à combustible a plusieurs avantages sur le papier :

  • recharge instantanée
  • efficience énergétique de 83%
  • grande autonomie
  • pas de CO2

Ce véhicule devrait être développé en 2015, mais avant ça à peu près tous les constructeurs cherchent à s’approcher de cette excellence théorique. Peut être, un jour. J’aimerai bien voir les semi-remorque tracté à l’hydrogène, ça, ça ferait des économies.

Le nucléaire au thorium

Présent dans presque tous les débats depuis la catastrophe de Fukoshima la production d’électricité via l’énergie nucléaire est souvent critiquée, décriée.

Souvent on pense qu’il faut absolument sortir de cette source d’énergie ? cause de son danger et des déchets qu’elle laisse derrière elle. Pourtant il est souvent on oublie de préciser quelque chose : notre source d’énergie nucléaire est l’uranium 235 et 238.

La réaction se passe ainsi :

message picture

Parmi les déchets on trouve donc de l’Uranium 235 (non consumé ou produit de la réaction) et du Plutonium. C’est ce dernier qui pose problème : il est très radioactif et très long ? se désintégrer.

La France a choisi de donner sa chance au Plutonium 239 via la création de MOX, la Chine, elle a décidé, en 2010, d’expérimenter une autre alternative : le thorium.

Une différence fondamentale : matériaux fissiles, matériaux fertiles

Il y a plus d’un siècle désormais deux scientifiques, Pierre et Marie Curie mettaient en avant la radioactivité du Thorium, découvert ? la fin du XIXème siècle. La radioactivité c’est la capacité ? perdre de l’énergie (rayonnement alpha, beta + ou-, ou gamma) pour créer un nouveau noyau plus stable (qui rayonnera moins). C’est différent de la possibilité de fissionner un noyau comme c’est le cas pour l’Uranium 235 ou 238.

Le thorium ne fait pas partie des matériaux fissiles, il serait très difficile de le fracturer en le bombardant de neutron. Cependant, ce dernier, une fois qu’il a capté un neutron se met ? être fortement radioactif. Et le résultat de cette radioactivité sera de l’Uranium 233, qui lui, est fissile.

Cette capacité ? donner naissance ? un noyau fissile fait que le Thorium est appelé fertile.

Cela a une conséquence importante : il faut amorcer la réaction. C’est ? dire qu’il faut quand même mélanger le Thorium ? de l’Uranium (souvent 235) pour que la réaction fonctionne.

Mais la grande force (ou la grande faiblesse selon qu’on soit pour ou contre la bombe atomique…) c’est que cette réaction ne produira que très peu de Plutonium (uniquement les résidus de l’amorçage).

Une autre conséquence non négligeable qui a largement ralenti le développement des réacteurs ? Thorium c’est que celui-ci devient très fortement radioactif au cours de la réaction et que des très puissants rayons gamma sont relâchés. Cependant qui dit amélioration des matériaux et de la robotique dit possibilité d’envisager la construction des réacteurs ? Thorium.

Un fonctionnement à part

Une grande force du Thorium est qu’il permet très facilement d’être exploité ? l’état liquide plutôt que solide à l’intérieur de réacteurs portant l’acronyme LFTR.

Les premiers prototypes de ce type de réacteurs date des années 40. Ce qui explique leur abandon : la filière du thorium n’était pas créé mais en plus le thorium ne créait pas de Plutonium dont on avait besoin pour les bombes atomiques de l’époque.

Depuis le forum Génération IV de nouveaux prototype comme SuperPhoenix ou le Rubbiatron

Dans tous les cas on remarque que le danger, jusque l? inhérent au nucléaire, d’emballement de la réaction peut être supprimé. En effet ces réacteurs peuvent fonctionner de manière viable en régime dit “sous-critique” durant lesquels la réaction peut s’arrêter toute seule si on la prive de combustible ou de neutrons.

Le traitement des déchets

Bien que les déchets soient moins radioactifs et pour moins longtemps, ils existent et leur demie-vie reste très élevée (un millénaire), pour autant différents projets ont été mis au point, notamment les ADS : Systèmes pilotés par accélérateurs qui permettent la transmutation des déchets vers d’autres qui se dégradent plus rapidement. Ces projets semblent prometteurs :

Les études de faisabilité des ADS sont maintenant bien avancées. Des travaux ont été effectués au plan national, au CEA et en collaboration CEA-CNRS ; au plan européen, sous l?égide du « Technical Working Group » (TWG) et dans le cadre de projets européens du 5e et, maintenant, du 6e PCRD. Des industriels ont pris une part importante ? ces travaux. En collaboration CEA-CNRS, des expériences ? puissance zéro ont été effectuées ? Cadarache sur la maquette critique « Masurca » (CEA-Cadarache) et un injecteur de protons de haute intensité est en construction au CEA Saclay.

Chiffres en vrac

  • 200 fois plus de Thorium que d’Uranium dans la nature, on trouve de très bons gisements partout dans le monde, notamment, pour nous, en Bretagne
  • 3,5 millions de fois la capacité du charbon
  • 14.5 milliards d’année : c’est la demie vie du Thorium 232, plus importante que l’âge de la terre
  • 10 000$ : c’est le coût annuel estimé d’un réacteur de type LFTR d’une puissance de 1GW, soit 40 fois moins qu’un réacteur ? Uranium 235/238.
  • 3000m² : la taille estimée pour une centrale de type LFTR soit 100 fois moins qu’une centrale ? l’Uranium 235/238