Problème #3 du project Euler

Copyright : geir tønnessen

« The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ? »

Le troisième problème du projet Euler reprend les notions mathématiques de nombres premiers et de facteurs premiers. Un nombre premier est un nombre entier supérieur à 1 qui n’a pour diviseurs que 1 et lui-même.

Les facteurs premiers d’un nombre entier, quant à eux, sont l’ensemble des nombres premiers qui divisent entièrement cet entier. Par exemple, les facteurs premiers du nombre 70 sont 2, 5 et 7. Comme le décrit l’énoncé de ce problème, les facteurs premiers de 13 195 sont 5, 7, 13 et 29.

La factorisation en nombres premiers d’un entier peut également être exprimée à l’aide de puissances. En guise d’illustration, le nombre 300 peut se décomposer de la manière suivante : 2 x 2 x 3 x 5 x 5. Pour simplifier cette écriture, le carré est souvent utilisé : 2² x 3 x 5².

Algorithme de la solution

Pour trouver le plus grand des facteurs premiers d’un nombre entier x, on considère comme probable diviseur de ce nombre tous les entiers supérieurs à 1, 2 étant le premier des nombres premiers.

Si l’entier considéré divise entièrement x, on divise successivement x par ce nombre, jusqu’à que ce nombre ne soit plus un facteur de x. Cette opération garantit la primalité du nombre considéré car tous les plus petits facteurs de x auront d’ores-et-déjà été traités.

Une première écriture de cet algorithme donnerait le résultat suivant. La fonction obtenue s’exécute en 12.57 millisecondes sur mon ordinateur.

function problem3(){
  var x = 600851475143,
      largest = 1,
      k = 2;
  while(x > 1){
    // If k is a factor of x
    if(x % k == 0){
      largest = k;
      x = x / k;
      while(x % k == 0) x = x / k;
    }
    k++;
  }
  // Give the largest prime factor of x
  return largest;
}

Une première évolution de ce code serait de traiter le nombre 2 à part, car 2 est le seul nombre premier de valeur paire. Cela nous permet par la suite d’utiliser la même boucle, en incrémentant de 2 chaque potentiel candidat à être facteur. On testera donc de manière successive les nombres 3, 5, 7, etc..

Ce nouvel algorithme s’exécute en 3.22 millisecondes sur mon ordinateur.

function problem3(){
  var x = 600851475143,
      largest = 1,
      k = 3;
  // If 2 is a factor of x, we treat it separately...
  if(x % 2 == 0){
    x = x / 2;
    largest = 2;
    while(x % 2 == 0) x = x / 2;
  }
  // ... so we can increase factor with 2 every iteration
  while(x > 1){
    if(x % k == 0){
      largest = k;
      x = x / k;
      while(x % k == 0) x = x / k;
    }
    k += 2;
  }
  // Give the largest prime factor of x
  return largest;
}

Il est encore possible d’améliorer l’efficacité de cette fonction en considérant que chaque entier x ne peut avoir au maximum qu’un seul nombre premier supérieur à sa racine carrée.

Après avoir divisé de manière successive un des nombres premiers trouvés, on calcule la racine carré de la valeur restante de x. Si le facteur considéré est supérieur à la racine carrée de x, alors la valeur restante de x est le plus des grands des nombres premiers de x.

Cette nouvelle version s’exécute cette fois en 1.84 milliseconde chez moi !

function problem3(){
  var x = 600851475143,
      largest = 1,
      k = 3;
  // If 2 is a factor of x, we treat it separately...
  if(x % 2 == 0){
    x = x / 2;
    largest = 2;
    while(x % 2 == 0) x = x / 2;
  }
  // ... so we can increase factor with 2 every iteration
  // This loop runs only if k is not bigger than the square
  // root of the remaining x
  while(x > 1 && k<= Math.sqrt(x)){
    if(x % k == 0){
      largest = k;
      x = x / k;
      while(x % k == 0) x = x / k;
    }
    k += 2;
  }
  // Give the largest prime factor of x
  if(x == 1) return largest;
  else return x;
}

Quand la performance crée de la valeur

Copyright : O'Reilly Conferences

Au cours de la première journée de keynotes de la conférence Velocity qui se tenait à Barcelone, j’ai assisté à la brillante prestation de Monica Pal, venue nous présenter The Impatience Economy, Where Velocity Creates Value. Monica Pal est une ingénieure hautement diplômée. Elle a commencé sa carrière dans le département de recherche et de développement d’Apple et travaille maintenant à la construction d’infrastructures commerciales chez Aerospike.

L’indice de l’impatience

Monica Pal décide très rapidement de mettre l’accent sur l’impatience. La notion d’impatience nous renvoie à l’incapacité de quelqu’un à pouvoir attendre quelque chose de manière calme et posée. Sur un ton enjoué, l’intervenante nous cite des cas d’impatience de la vie courante : celui d’un bébé qui n’obtient pas très rapidement ce qu’il souhaite ou celui d’une personne affamée qui n’arrive plus à garder les idées claires… Ces différentes analogies sont une parfaite introduction à The « Impatience Index », l’étude menée par Kana Software sortie au cours du mois de janvier 2014.

Kana Software est une entreprise proposant des services de monitoring et des solutions de cloud computing. On apprend, grâce à leur analyse, que la patience n’est plus une qualité très répandue de nos jours. En effet, il y a quelques années, les gens étaient capables d’attendre dix jours le facteur pour recevoir des informations de leurs proches. Aujourd’hui, la nouvelle génération considère que 10 minutes d’attente sont amplement suffisantes. Les 18-24 sont d’ailleurs les plus impatients : toutes les 9 minutes 50 secondes en moyenne, ils regardent leurs téléphones à l’affût de nouvelles notifications. Ils regardent leurs smartphones pour tuer le temps, quand ils sont dans une file d’attente, quand ils font du shopping, en regardant la télévision, quand ils étudient… Et, comme le dit si bien Monica Pal, même quand ils attendent, ils détestent attendre ! Cette idée avait d’ores-et-déjà été énoncée par Mike Krieger, le co-fondateur d’Instagram : « Mobile experiences fill gaps while we wait / No one wants to wait while they wait ».

Les attentes du client moyen

Monica Pal nous présente ensuite une vidéo YouTube de Luke Wroblewski, qui nous incite à trouver la meilleure navigation possible pour les utilisateurs d’un site mobile. Luke Wroblewski, auteur par exemple du fameux livre Mobile First pour A Book Apart, explique comment quelque chose de valorisant, quelque chose d’efficace, peut apporter en termes d’expérience utilisateur.

Decoding the new consumer mind : How and why we shop and buy est un livre, écrit par Kit Yarrow, plein de bon sens quant à l’évolution de la société de consommation. L’utilisateur moyen est plus facilement distrait que celui des années 90 et est moins tolérant pour quasi tout ce qui demande de la patience. Ce livre, que nous propose ainsi Monica Pal, est une nouvelle façon d’appréhender comment nos cerveaux, nos esprits et nos perceptions évoluent en parallèle des avancées technologiques. Ce monde de nouvelles plateformes qui émergent nous conditionne à vouloir de la rapidité dans tous nos échanges.

Le consommateur moyen de l’époque avait une approche intellectuelle et réfléchie vis-à-vis des interfaces. Aujourd’hui, les utilisateurs ont une approche bien plus instinctive, liée à l’émotionnel. Quotidiennement, l’utilisateur est dans un environnement digital de couleurs, d’images et de vidéos dans lesquelles il perçoit des gens faire quelque chose qu’il va « aimer », « suivre » et relayer. Il passe son temps à cliquer et à réagir instantanément plutôt qu’à taper sur son clavier. Et donc, selon Monica Pal, cette logique nous mènerait, nous développeurs, à toujours anticiper les comportements de nos utilisateurs. Nous devons sublimer nos interfaces et les rendre intelligibles pour un utilisateur moyen, qui lui, n’aura aucune envie de passer du temps à « comprendre » où se trouvent nos fonctionnalités. Nous devons personnaliser l’expérience utilisateur.

Une étude récente chez Radware démontre qu’une simple seconde de chargement de contenu plus rapide apporte de la valeur significative.

Les impacts d’une bonne structure

De nombreux sites et de nombreux acteurs dans le monde du media ont un système économique lié à la publicité digitale. Aujourd’hui, la publicité est ce qui crée de la valeur fondatrice de certaines expériences sociales, selon Monica Pal. Une des technologies les plus exploitées à l’heure actuelle consiste à allouer en temps réel une impression publicitaire à un annonceur et d’en déterminer le prix en fonction de son format et de son contexte. Cette nouvelle infrastructure, appelée le Real-Time Bidding (RTB), doit donc permettre aux annonceurs en seulement quelques millisecondes d’enchérir sur un emplacement publicitaire, selon les informations connues sur un utilisateur donné. En clair, en un court laps de temps, ils doivent pouvoir extraire des données précises sur cette personne afin de lui proposer un contenu personnalisé, qui va nécessairement modifier son expérience.

Aujourd’hui, quelque soit le site web que vous parcourez, quelle que soit l’application que vous utilisez, votre expérience utilisateur peut être à tout moment bouleversée par ces infrastructures. La rapidité d’exécution apparaît donc un facteur clé de réussite. Monica Pal nous prend l’exemple d’AppNexus, une société américaine spécialisée dans la publicité digitale en temps réel. AppNexus propose un nouveau degré de vitesse : leur base de données leur permet d’effectuer 3 millions de lectures et 1.5 million d’écritures par seconde.

AppLovin, une autre société proposant une technologie RTB orientée applications, traite plus de 20 milliards de requêtes par jour, représentant 100 millions de chiffre d’affaires. Ils utilisent une nouvelle technologie de stockage Flash, au lieu d’utiliser de la RAM, ce qui leur permet de bien répartir leur performance sans ajouter un nombre indécent de serveurs à leur infrastructure.

La mise en cache des données les plus utilisées (dites chaudes) dans une solution de stockage Flash permet de ne plus devoir lire les données à partir des disques durs, d’où une réduction des temps de latence et, de fait, une amélioration des performances des applications.

Christophe Menard, « Optez pour le stockage Flash »

Monica Pal tient donc à démontrer avec toute cette analyse, la nécessité de travailler la partie front-end d’un site web, mais surtout de ne pas négliger la vitesse d’infrastructure qui soutient cette plateforme, qui peut, elle aussi, être gage de performance. You, guys, are focused on the web front end, but there’s a new degree of velocity that is emerging, creating a new kind of value out there.

Améliorer l’échange autour de la performance web

Copyright : O'Reilly Conferences

La première keynote à laquelle j’ai assisté lors de la conférence Velocity est celle d’Aaron Rudger. Aaron Rudger est un technicien possédant une longue expérience en tant que directeur marketing et produit senior chez Keynote Systems en Californie. Son principal objectif, en tant que professionnel référent dans son domaine, est d’établir un univers de développement performant autour des solutions de monitoring de son entreprise sans pour autant déprécier les désirs de ses clients.

Maximize the return of your digital investments est avant tout une prise de connaissance sur le monde dans lequel nous évoluons actuellement, notamment en matière de performance web. La principale question soulevée est celle de la communication entre les équipes marketing et les équipes de développement.

Comme le souligne Aaron Rudger tout au long de son discours, il peut être parfois difficile de faire comprendre aux équipes marketing et commerciales l’enjeu de la performance pour les utilisateurs d’un site internet ou d’une application web. Pourquoi ?  Parce que les clients en veulent toujours plus : plus de publicités digitales, plus de connexions avec les réseaux sociaux, dont le nombre ne cesse d’accroître par ailleurs, plus de pixels captant le comportement des utilisateurs, des images de plus en plus grandes et donc de plus en plus lourdes, etc.. Et bien évidemment, la plupart de ces contenus proviennent de plateformes complètement hors de notre portée, et ne rendent pas nécessairement l’expérience utilisateur satisfaisante.

Selon une étude de la société Forrester réalisée en 2012, près de 32% des acteurs du marketing – directeur marketing, assistant marketing, planner stratégique, media planner, chargé d’études, directeur d’études, manager de la marque, responsable marketing digital, chef de publicité, directeur de clientèle, etc. – pensent que leur département technologique entrave à la réussite budgétaire de leur entreprise. En 2014, Aaron Rudger nous informe que ce nombre est passé à près de 43%. D’après lui, cette croissance souligne simplement que la manière dont le marketing et celle dont les équipes de développement pensent à la performance est de plus en plus divergente.

Parler de temps de connexion inférieur à un certain nombre de secondes pour une page web ne signifie pas grand chose de concret pour tous les « marketeux ». En réalité, c’est toute la notion d’analytics qui n’a pas de grande valeur à leurs yeux. Selon eux, les indicateurs clés de performance d’un bon produit, les Key Performance Indicators, sont l’engagement, la fidélité et la croissance. Il faut donc savoir construire un discours qui dégagera naturellement toutes ces notions dans le contexte de l’entreprise. Parler de l’amélioration du start render en disant par exemple que celui-ci augmentera l’engagement des utilisateurs à terme, et donc aura un impact positif sur les revenus, est une façon de convaincre les équipes marketing de l’intérêt d’un tel projet, qui ne leur semblerait que technique à première vue.

Le principal conseil d’Aaron Rudger serait donc d’élever la conversation pour convaincre les équipes marketing. Il faudrait ainsi, en toutes circonstances, certes mentionner les aspects techniques de nos futurs développements, mais surtout démontrer l’impact final sur la réussite de l’entreprise grâce à la performance technique. Changer sa manière de dialoguer et adopter un discours selon son interlocuteur peut directement jouer en notre faveur. « Create your own sense of ownership around performance that’s driving business impact in your organization. » Aaron Rudger nous propose d’ailleurs un article, Do you speak the same language as your business ?, pour poursuivre les réflexions autour de cette problématique. Vous pouvez également écouter cette keynote grâce à la vidéo ci-dessous.