SFEIR

SFEIR

1 Fév, 2022

Comment résoudre l’algo geohash ?

Rubrique

Playoffs

Introduction

 

Suite à notre évènement Test d’algo, mode d’emploi du 25 janvier, nous avons voulu faire un focus sur le talk de Gérôme Grignon, comment présenter l’algo geohash dans un cas concret.

Pour plus d’informations, nous vous invitons à consulter le replay.

Suite à une reconversion professionnelle, Gérôme Grignon, développeur Front-End chez SFEIR Nantes, nous partage ses connaissances à travers la vulgarisation de l’algo geohash.

 

Lorsque l’on créé un algorithme, il y a plusieurs étapes d’itération : 

  1. s’assurer qu’il fonctionne correctement
  2. s’assurer qu’il fonctionne par rapport à nos cas d’usage
  3. s’assurer que son exécution soit la plus rapide possible 

 

Nous allons prendre le cas concret d’un avertisseur de radar pour montrer comment utiliser l’algorithme geohash.

Un utilisateur en déplacement dans l’espace se retrouve dans différentes positions géographiques. L’objectif de l’avertisseur de radar est de fournir rapidement la localisation des radars à proximité de sa position géographique.

Quand on pense à un accès très rapide à une base de données, on pense directement aux bases de données de type colonne comme Cassandra.

Avec ces bases de données, nous ne pouvons pas comparer plusieurs colonnes, or dans notre cas, nous avons une longitude et une latitude.

 

Nous devons donc passer d’une représentation de l’espace en 2 dimensions (longitude/ latitude) à 1 dimension.

L’algorithme geohash est un système d’encodage de localisation géographique, il permet de passer d’une longitude et latitude à une chaîne de caractère par exemple. 

Pour plus d’informations, vous pouvez retrouver la définition sur wikipédia.  

 

Comment coder un geohash ? 

  1. partir de latitude et notre longitude
  2. faire l’étape de dichotomie pour arriver à un code binaire
  3. convertir en base 32 pour arriver à notre chaîne de caractère

 

 

 

Plus que des mots, voici la réalisation

 

const DECODING_TRANSLATION_MAP = new Map(

   [['0', [0]], ['1', [1]], /* ... */ ]);

 

exports.decode = function(geohash) {

   let [minLat, maxLat, minLong, maxLong] = [-90.0, 90.0, -180.0, 180.0];

   let computeLong = true;

   for (let char of geohash) {

       const hashChunk = DECODING_TRANSLATION_MAP.get(char);

       for (let bit of hashChunk) {

           if (computeLong) {

               const midLong = (maxLong + minLong) / 2.0;

               if (bit) {

                   // on garde la partie droite

                   minLong = midLong;

               } else {

                   // on garde la partie gauche

                   maxLong = midLong;

               }

           } else {

               const midLat = (maxLat + minLat) / 2.0;

               if (bit) {

                   // on garde la partie inférieure

                   minLat = midLat;

               } else {

                   // on garde la partie supérieure

                   maxLat = midLat;

               }

           }

           computeLong = !computeLong;

       }

   }

   return [minLat, maxLat, minLong, maxLong];

}

Restez informés

Recevez chaque mois nos dernières actus techs et événements à venir.

Social

Un peu de lecture

accelerate sfeir institute

Accelerate, le programme de formations gratuites de SFEIR Institute

Actualités

SFEIR Institute lance un nouveau programme de formations gratuites : Accelerate. En partenariat avec des géants du secteur comme AWS, Google Cloud, et Confluent, SFEIR Institute propose des formations gratuites et sans engagement sur l'essentiel des évolutions technologiques afin de vous aider à...

Lire la suite

SFEIR JDN didier girard

[Presse] Innovation technologique : quand vient l'heure d'inclure les DSI dans les comités de direction

Actualités, SFEIR dans la presse

Didier Girard, Co-CEO de SFEIR, a publié une tribune dans le Journal du Net (JDN) : "Innovation technologique : quand vient l'heure d'inclure les DSI dans les comités de direction" Dans cet article, Didier explique qu'il faut décloisonner le business et l'IT...

Lire la suite

SFEIR lance un nouveau blog : sfeir.dev

Actualités

🚀 It’s the Towel Day !  Un jour très spécial pour la communauté SFEIR : 1) -> La journée de la serviette a une signification importante car c’est de là que vient l’histoire du chiffre  42 ! Si vous souhaitez...

Lire la suite

Parlez à un expert

Social

Contact