Archives de catégorie : snippet

c++, snippet

Anagrammes

Laisser un commentaire

En passant par une page de documentation, je me suis attardé sur std::next_permutation. Ça m’a tout de suite donné des idées d’anagrammes. En effet, de pouvoir aussi facilement boucler irréfragablement sur toutes les permutations des lettres d’un mot m’a  suscité l’irrépressible envie de créer un petit détecteur d’anagrammes.

Évidemment, pour détecter un anagramme, il faut d’abord et avant tout avoir une base de données de mots valides pour une langue donnée. Il se trouve que j’ai une telle base de données.  En effet, il y a déjà une vingtaine d’années, j’avais réalisé une petite page web d’aide aux mots-croisés. Pour ce faire j’avais contacté, via un forum, un cruciverbiste-internaute qui avait eu la grande gentillesse de me faire parvenir ce fichier par courriel. C’était un gros fichier à l’époque: presque 3 Mo. En fait, à l’origine c’était même 26 fichiers allant de A.txt à Z.txt. Cruciverbiste-internaute des années ’90 qui se reconnait dans cette histoire, je te remercie encore une fois!

Le corpus en tant que tel date un peu: le mot courriel, par exemple, n’y apparaît même pas. Quoi qu’il en soit, avec ses 280000 entrées composées de noms propres, de substantifs et d’adjectif au singulier comme au  pluriel, de verbes conjugués à toutes les formes, c’est suffisant pour tenter quelques expériences significatives.

En tout cas, c’est amplement suffisant pour tester une première version d’un détecteur d’anagramme. Une version pas très robuste mais qui a le mérite de tester l’utilisation de std::next_permutation.

La première version lit la base de données en insérant dans un std::vector> tous les mots rencontrées. Le vecteur est triée pour permettre une recherche rapide avec std::binary_search

Une fonction ressemblant à ça pourrait par exemple faire l’affaire (j’assume un compilateur C++11 ou plus qui garantit que les objets comme la base de données ne sont pas retournés par copie sur la pile mais bien en utilisant le mécanisme de Copy Elision).

[pastacode lang= »cpp » manual= »typedef%20vector%3Cstd%3A%3Astring%3E%20AnagramDB%20%3B%0A%0AAnagramDB%20GetAnagramDB(const%20std%3A%3Astring%26%20filename)%20%0A%7B%0A%09std%3A%3Avector%3Cstd%3A%3Astring%3E%20words%3B%0A%09std%3A%3Aifstream%20datafile(filename)%3B%0A%0A%20%20%20%20std%3A%3Astring%20str%3B%0A%20%20%20%20while%20(datafile%20%3E%3E%20str%20)%0A%09%7B%0A%09%09words.push_back(str)%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20std%3A%3Asort(words.begin()%2C%20words.end())%3B%0A%09return%20words%3B%0A%7D » message= »Lecture de la base de données et insertion dans un vecteur trié » highlight= » » provider= »manual »/]

Avec un vecteur ainsi trié, on peut rechercher un mot avec grosso-modo la même efficacité que dans un arbre binaire. En imaginant qu’on boucle sur les différentes permutations des lettres d’un mot, on voudra tester pour chaque combinaison si le mot est présent  ou pas dans la base de données. Quelque chose comme ça.

[pastacode lang= »cpp » manual= »bool%20isInDatabase(const%20AnagramDB%26%20database%2C%20const%20std%3A%3Astring%26%20str)%0A%7B%0A%09return%20std%3A%3Abinary_search(database.cbegin()%2C%20database.cend()%2C%20str)%3B%0A%7D » message= »Utilisation de binary_search pour trouver un mot dans une liste triée » highlight= » » provider= »manual »/]

Une fois qu’on a une base de données chargée et un mécanisme pour tester si un mot (une combinaison de lettres) est valide (donc présent dans le base de données), il ne reste plus qu’à obtenir un mot à tester, boucler sur toutes ses permutations et vérifier pour chaque anagramme si il correspond à un mot valide dans la langue française (ici représentée par notre fichier de base de données).

On pourrait par exemple lire en boucle sur stdin pour obtenir des mots, qu’on testerait un à la fois. Pour chacun des mots, la liste des anagrammes valides serait envoyée sur stdout, et ainsi de suite. On remarque que pour initier les permutations, le mot est tout d’abord trié en ordre lexicographique, de manière à commencer par le « premier » anagramme.

Ça ressemblerait donc à ça.

[pastacode lang= »cpp » manual= »int%20main(int%20argc%2C%20char**%20argv)%0A%7B%0A%09if(argc%3C%3D1)%20%0A%09%09return%200%3B%0A%09std%3A%3Astring%20str%20%3D%20argv%5B1%5D%3B%0A%20%20%20%20auto%20db%20%3D%20GetAnagramDB(str)%3B%0A%09std%3A%3Acout%20%3C%3C%20%22Word%20to%20look%20for%3A%20%22%3B%20%0A%09while(std%3A%3Acin%20%3E%3E%20str%20)%20%0A%09%7B%0A%09%09std%3A%3Asort(str.begin()%2C%20str.end())%3B%0A%09%09int%20num%20%3D%200%3B%0A%09%09while(std%3A%3Anext_permutation(str.begin()%2C%20str.end())%20)%0A%09%09%7B%0A%09%09%09if(%20isInDatabase(str)%20)%20%0A%09%09%09%7B%0A%09%09%09%09std%3A%3Acout%20%3C%3C%20str%20%3C%3C%20std%3A%3Aendl%3B%3B%20%0A%09%09%09%09num%2B%2B%3B%0A%09%09%09%7D%0A%09%09%7D%0A%09%09%09%0A%09%09std%3A%3Acout%20%3C%3C%20%22Found%20%3A%20%22%20%3C%3C%20num%20%3C%3C%20std%3A%3Aendl%3B%20%0A%09%09std%3A%3Acout%20%3C%3C%20%22Word%20to%20look%20for%3A%20%22%3B%20%0A%09%20%7D%0A%0A%09return%200%3B%0A%7D » message= »Boucle naïve pour la recherche d’anagrammes valides basé sur std::next_permutation » highlight= »12″ provider= »manual »/]

Cette boucle et ce programme fonctionne parfaitement comme il se doit. Par contre il souffre de quelques faiblesses:

  • Le nombre de permutations est N! ; pour un mot de 10 lettres, on a déjà plus de 3,5 millions de combinaisons à tester (3628800)
  • Les casses minuscule et majuscules sont considérées comme étant des lettres différentes
  • Les accents et autres diacritiques génèrent des lettres différentes

Dans le prochain épisode sur les anagrammes, on améliorera tout ça en repensant la base de données et en évitant les multiples permutations. On s’affranchira aussi des problèmes de casse et de diacritiques.

c++, snippet

Comment enlever les accents des caractères en C++

Laisser un commentaire

Souvent lorsqu’on manipule du texte, on cherche à retrouver la forme de base des caractères, c’est-à-dire sans les signes diacritiques. Ce peut être utile pour générer une liste en ordre alphabétique de mots par exemple (on notera que dans l’ordre lexicographique des dictionnaires français, le E, et le É ont la même valeur).

Cet exercice peut être assez complexe car fortement dépendant de l’encodage des caractères (UTF-8, ASCII étendu, etc.) et de la définition donnée à « forme de base« . En effet, d’une langue à l’autre, cette notion peut varier et les diacritiques dans certaines langues donne une lettre à part entière. Par exemple en espagnol, la lettre ñ est une lettre à part qui est classée après le n.

Le remplacement des accents dans une application multi-langues est une tâche complexe et pour se faire, le mieux est d’être aidé par des bibliothèques comme ICU.

En revanche, pour tous les cas relativement fréquents où les caractères sont simplement codés sur un octet en utilisant l’ASCII étendu avec l’encodage ISO-Latin-1, on pourrait utiliser le petit bout de code suivant (inspiré d’une réponse sur Stack Overflow).

[pastacode lang= »cpp » manual= »char%20RemoveAccent(char%20ch)%20%0A%7B%0A%09static%20const%20std%3A%3Amap%3Cchar%2C%20char%3E%20tr%20%3D%0A%09%7B%0A%09%09%7B%20’%C3%80’%2C%20’A’%20%7D%2C%0A%09%09%7B%20’%C3%81’%2C%20’A’%20%7D%2C%0A%09%09%7B%20’%C3%82’%2C%20’A’%20%7D%2C%0A%09%09%7B%20’%C3%83’%2C%20’A’%20%7D%2C%0A%09%09%7B%20’%C3%84’%2C%20’A’%20%7D%2C%0A%09%09%7B%20’%C3%85’%2C%20’A’%20%7D%2C%0A%09%09%0A%09%09%7B%20’%C3%86’%2C%20’E’%20%7D%2C%0A%0A%09%09%7B%20’%C3%87’%2C%20’C’%20%7D%2C%0A%0A%09%09%7B%20’%C3%88’%2C%20’E’%20%7D%2C%0A%09%09%7B%20’%C3%89’%2C%20’E’%20%7D%2C%0A%09%09%7B%20’%C3%8A’%2C%20’E’%20%7D%2C%0A%09%09%7B%20’%C3%8B’%2C%20’E’%20%7D%2C%0A%0A%09%09%7B%20’%C3%8C’%2C%20’I’%20%7D%2C%0A%09%09%7B%20’%C3%8D’%2C%20’I’%20%7D%2C%0A%09%09%7B%20’%C3%8E’%2C%20’I’%20%7D%2C%0A%09%09%7B%20’%C3%8F’%2C%20’I’%20%7D%2C%0A%0A%09%09%7B%20’%C3%90’%2C%20’D’%20%7D%2C%0A%0A%09%09%7B%20’%C3%91’%2C%20’N’%20%7D%2C%0A%0A%09%09%7B%20’%C3%92’%2C%20’O’%20%7D%2C%0A%09%09%7B%20’%C3%93’%2C%20’O’%20%7D%2C%0A%09%09%7B%20’%C3%94’%2C%20’O’%20%7D%2C%0A%09%09%7B%20’%C3%95’%2C%20’O’%20%7D%2C%0A%09%09%7B%20’%C3%96’%2C%20’O’%20%7D%2C%0A%0A%09%09%7B%20’%C3%97’%2C%20’x’%20%7D%2C%0A%0A%09%09%7B%20’%C3%98’%2C%20’0’%20%7D%2C%0A%0A%09%09%7B%20’%C3%99’%2C%20’U’%20%7D%2C%0A%09%09%7B%20’%C3%9A’%2C%20’U’%20%7D%2C%0A%09%09%7B%20’%C3%9B’%2C%20’U’%20%7D%2C%0A%09%09%7B%20’%C3%9C’%2C%20’U’%20%7D%2C%0A%0A%09%09%7B%20’%C3%9D’%2C%20’Y’%20%7D%2C%0A%09%09%7B%20’%C3%9E’%2C%20’P’%20%7D%2C%0A%09%09%7B%20’%C3%9F’%2C%20’S’%20%7D%2C%0A%0A%09%09%7B%20’%C3%A0’%2C%20’a’%20%7D%2C%0A%09%09%7B%20’%C3%A1’%2C%20’a’%20%7D%2C%0A%09%09%7B%20’%C3%A2’%2C%20’a’%20%7D%2C%0A%09%09%7B%20’%C3%A3’%2C%20’a’%20%7D%2C%0A%09%09%7B%20’%C3%A4’%2C%20’a’%20%7D%2C%0A%09%09%7B%20’%C3%A5’%2C%20’a’%20%7D%2C%0A%0A%09%09%7B%20’%C3%A6’%2C%20’e’%20%7D%2C%0A%0A%09%09%7B%20’%C3%A7’%2C%20’c’%20%7D%2C%0A%0A%09%09%7B%20’%C3%A8’%2C%20’e’%20%7D%2C%0A%09%09%7B%20’%C3%A9’%2C%20’e’%20%7D%2C%0A%09%09%7B%20’%C3%AA’%2C%20’e’%20%7D%2C%0A%09%09%7B%20’%C3%AB’%2C%20’e’%20%7D%2C%0A%0A%09%09%7B%20’%C3%AC’%2C%20’i’%20%7D%2C%0A%09%09%7B%20’%C3%AD’%2C%20’i’%20%7D%2C%0A%09%09%7B%20’%C3%AE’%2C%20’i’%20%7D%2C%0A%09%09%7B%20’%C3%AF’%2C%20’i’%20%7D%2C%0A%0A%09%09%7B%20’%C3%B0’%2C%20’d’%20%7D%2C%0A%0A%09%09%7B%20’%C3%B1’%2C%20’n’%20%7D%2C%0A%0A%09%09%7B%20’%C3%B2’%2C%20’o’%20%7D%2C%0A%09%09%7B%20’%C3%B3’%2C%20’o’%20%7D%2C%0A%09%09%7B%20’%C3%B4’%2C%20’o’%20%7D%2C%0A%09%09%7B%20’%C3%B5’%2C%20’o’%20%7D%2C%0A%09%09%7B%20’%C3%B6’%2C%20’o’%20%7D%2C%0A%0A%09%09%7B%20’%C3%B7’%2C%20’%2F’%20%7D%2C%0A%0A%09%09%7B%20’%C3%B8’%2C%20’0’%20%7D%2C%0A%0A%09%09%7B%20’%C3%B9’%2C%20’u’%20%7D%2C%0A%09%09%7B%20’%C3%BA’%2C%20’u’%20%7D%2C%0A%09%09%7B%20’%C3%BB’%2C%20’u’%20%7D%2C%0A%09%09%7B%20’%C3%BC’%2C%20’u’%20%7D%2C%0A%0A%09%09%7B%20’%C3%BD’%2C%20’y’%20%7D%2C%0A%09%09%7B%20’%C3%BE’%2C%20’p’%20%7D%2C%0A%09%09%7B%20’%C3%9F’%2C%20’s’%20%7D%0A%09%7D%3B%0A%09%0A%09auto%20it%20%3D%20tr.find(ch)%3B%0A%09if%20(it%20!%3D%20tr.end())%0A%09%09return%20it-%3Esecond%3B%0A%09return%20ch%3B%0A%7D » message= »RemoveAccent() » highlight= » » provider= »manual »/]

c++, Informatique, snippet

Chronomètre basique

En passant Laisser un commentaire

On a souvent besoin d’un chronomètre multiplateforme. Celle-ci est 100% inline et ne dépend que de ctime (aka time.h). Un simple #include suffit à l’utiliser un peu partout. La classe étant basée sur clock(), la précision n’est pas garantie. Mais c’est souvent amplement suffisant.

Le fichier est disponible ici: chrono.h

[pastacode provider= »manual » lang= »c++ » message= »Contenu du fichier chrono.cpp »]

#ifndef __CHRONO_H__
#define __CHRONO_H__

#include <ctime>

/**
 * \namespace	Chrono 
 *
 * \brief	A small set of utilities encapsulating timing functions 
**/
namespace Chrono 
{

/**
* \class	Stopwatch
*
* \brief	A stopwatch
*
* \details	Allows to create a stopwatch, start, stop and getting time in various formats.
**/
class Stopwatch
{
public:
 /**
 * \fn	Stopwatch::Stopwatch();
 *
 * \brief	Default constructor. 
 *
**/
inline
Stopwatch();

 /**
 * \fn	void Stopwatch::Start();
 *
 * \brief	Starts the time counter. 
 *
**/
inline
void Start();

  /**
 * \fn	void Stopwatch::Stop();
 *
 * \brief	Stops the time counter. 
 *
**/
inline
void Stop();

  /**
 * \fn	void Stopwatch::Reset();
 *
 * \brief	Resets the time counter to 0 sec.
 *
**/
inline
void Reset();

  /**
 * \fn	double  Stopwatch::GetTimeInMilliseconds();
 *
 * \brief	Gets the time in milliseconds. 
 *
 * \return	The time in milliseconds. 
 *
**/
inline
double  GetTimeInMilliseconds();

 /**
 * \fn	double Stopwatch::GetTimeInSeconds();
 *
 * \brief	Gets the time in seconds. 
 *
 * \return	The time in seconds. 
 *
**/
inline
double  GetTimeInSeconds();

  /**
 * \fn	double Stopwatch::GetTimeInMinutes();
 *
 * \brief	Gets the time in minutes. 
 *
 * \return	The time in minutes. 
 *
**/
inline
double  GetTimeInMinutes();

  /**
 * \fn	double Stopwatch::GetTimeInHours();
 *
 * \brief	Gets the time in hours. 
 *
 * \return	The time in hours. 
 *
**/
inline
double  GetTimeInHours();

  /**
 * \fn	void Stopwatch::GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds);
 *
 * \brief	Gets a time in a formated way
 *
 * \param [in,out]	aHours			a in hours. 
 * \param [in,out]	aMinutes		a in minutes. 
 * \param [in,out]	aSeconds		a in seconds. 
 * \param [in,out]	aMilliseconds	a in milliseconds. 
 *
**/

inline
void    GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds);

private :
  unsigned int mStart;
  unsigned int mAccumulator;
  bool mStopped;
  };
}

inline
Chrono::Stopwatch::Stopwatch() : mAccumulator(0), mStopped(true)
{
}

inline
void Chrono::Stopwatch::Start()
{
  if(!mStopped)
   return;

  mStart = clock() - mAccumulator;
 mStopped = false;
}

inline
void Chrono::Stopwatch::Stop()
{
  if(mStopped)
   return;

  mAccumulator = clock() - mStart;
  mStopped = true;
}

inline
void Chrono::Stopwatch::Reset()
{
  Stop();
  mAccumulator = 0;
}

inline
double Chrono::Stopwatch::GetTimeInMilliseconds()
{
  return GetTimeInSeconds() * 1000.0;
}

inline
double Chrono::Stopwatch::GetTimeInSeconds()
{
  unsigned int lTime;
  if(mStopped)
   lTime = mAccumulator;
  else
   lTime = clock() - mStart;

  return lTime / (double)CLOCKS_PER_SEC;
}

inline
double Chrono::Stopwatch::GetTimeInMinutes()
{
  return GetTimeInSeconds() / 60.0;
}

inline
double Chrono::Stopwatch::GetTimeInHours()
{
  return GetTimeInSeconds() / 3600.0;
}

inline
void Chrono::Stopwatch::GetTime(int &aHours, int &aMinutes, int &aSeconds, int &aMilliseconds)
{
  double lRemainder = GetTimeInSeconds();

  aHours = (int)(lRemainder / 3600.0);
  lRemainder -= aHours;

  aMinutes = (int)(lRemainder / 60.0);
  lRemainder -= aMinutes;

  aSeconds = (int)lRemainder;
  lRemainder -= aSeconds;

  aMilliseconds = (int)lRemainder;
}

#endif // __CHRONO_H__

[/pastacode]

c++, Informatique, snippet

Écart type en une passe

Laisser un commentaire

On a souvent besoin de calculer quelques statistiques sur un ensemble de données. Si calculer la moyenne en une passe est trivial, le calcul de l’écart type demande un peu d’attention. Ci-dessous, une solution que je poste comme pense-bête.

Le snippet calcule aussi les valeurs min et max.

Code snippet :

[pastacode provider= »manual » lang= »c++ » message= »Écart type en une passe » manual= »std%3A%3Avector%3Cint%3E%20vec%3B%20%20%20%2F%2F%20Container%20with%20values%0Auint64_t%20count%20%20%3D%200%20%3B%20%20%20%20%20%0Auint64_t%20accu%20%20%20%3D%200%20%3B%20%20%20%20%20%0Auint64_t%20accu2%20%20%3D%200%20%3B%0Auint64_t%20min%20%20%20%20%3D%20-1%3B%0Auint64_t%20max%20%20%20%20%3D%200%20%3B%0A%0Afor_each(begin(vec)%2C%20end(vec)%20%5B%26%5D(int%20x)%0A%7B%0A%20%20%20%20accu%20%2B%3D%20x%3B%0A%20%20%20%20accu2%20%2B%3D%20%20x%20*%20x%3B%0A%20%20%20%20min%20%3D%20(std%3A%3Amin)(min%2C%20x)%3B%0A%20%20%20%20max%20%3D%20(std%3A%3Amax)(max%2C%20x)%3B%0A%20%20%20%20%2B%2Bcount%3B%0A%7D)%3B%0A%0Afloat%20average%20%3D%20accu%2Ffloat(count)%3B%0Afloat%20stdev%20%3D%20sqrt(accu2*count%20-%20accu*accu)%2Fcount%3B »/]