Saturday, November 29, 2014

Sleep Sort

Je suis en train d’expérimenter avec les nouvelles fonctionnalités de C++11, en particulier les manières de gérer la concurrence. Dans ce post je propose une implémentation de sleep sort.

Qu’est ce que sleep sort ? Un algorithme de tri basé sur la mise en attente de thread. Cet algorithme n’a pas à ma connaissance d’application autre qu’être une plaisanterie populaire sur le board /prog/ de 4chan. L’idée de l’algorithme est de lancer en parallèle pour chaque entier x à trier sleep(x); print x;. Dans un monde parfait cet algorithme à comme complexité O(max(x)), en pratique c’est plutôt O(n^2 + max(x)) car l’ordonnanceur du noyau doit maintenir les n threads. Il y a également un point sur lequel il faut faire attention, si les éléments à trier ne sont pas garantis sans doublon si print n’est pas thread-safe il y des accès concurrents. C’est pourquoi j’utilise un mutex.

#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <thread>
#include <vector>

using namespace std;
using namespace std::chrono;

auto die = bind(uniform_int_distribution<>{1, 64}, default_random_engine{});

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& t) {
    bool first = true;
    for (auto& x : t) {
        if (!first)
            os << ' ';
        first = false;
        os << x;
    }
    return os;
}

template <typename Iterator>
void sleep_sort(Iterator first, Iterator last) {
    vector<thread> tasks;
    mutex m;
    for (auto it = first; it != last; ++it) {
        typename Iterator::value_type x = *it;
        tasks.push_back(thread{[&first, x, &m]() {
            this_thread::sleep_for(milliseconds{10 * x});
            unique_lock<mutex> lck{m};
            *first = x;
            ++first;
        }});
    }

    for (auto& th : tasks)
        th.join();
}

int main() {
    vector<int> t(128);
    for (int& x : t)
        x = die();

    cout << t << '\n';

    sleep_sort(begin(t), end(t));
    assert(is_sorted(begin(t), end(t)));
    
    cout << t << '\n';
}

Friday, October 24, 2014

Vitesse d'insertion: Vector vs List

J’ai récemment vu un débat sur la vitesse d’insertion dans une liste par rapport à un vector. Il semblait que grâce au préfetcheur, comme un vector occupe une zone contiguë de mémoire l’insertion pouvait être plus rapide que dans une liste.

Ceci est surprenant, car l’insertion dans un vector nécessite de recopier tous les éléments suivant la position d’insertion. On a donc une complexité en moyenne linéaire. Alors qu’une insertion dans une liste ne demande que de mettre à jour un nombre constant de pointeurs et a donc une complexité constante.

Voyons en pratique ce qu’il en est.

Effectuons un benchmark simple: on va remplir un conteneur (une liste ou un vector) d’entiers pris dans un ordre aléatoire, mais en les insérant de manière triée, afin de simuler une série d’insertions à des positions aléatoires. Bien entendu si l’on ne se préoccupe que d’insérer de manière triée des entiers, de nombreuses optimisations sont possibles. Par exemple, on peut trouver la position d’insertion par dichotomie, on peut aussi tout insérer puis trier à la fin, ou simplement utiliser un set, mais le but ici est de simuler des insertions à des positions aléatoires dans un conteneur.

Voici le code utilisé:


#include <algorithm>
#include <chrono>
#include <iostream>
#include <list>
#include <vector>

using namespace std;
using namespace std::chrono;

class bench{
    high_resolution_clock::time_point start;
public:
    bench():start(high_resolution_clock::now()){};
    ~bench(){
        auto end = high_resolution_clock::now();
        cout << duration_cast<duration<double,milli>>(end-start).count();
    }
};

template<typename T>
void insert_all(const vector<int>& t, T& collection){
    for(int n:t){
        auto it = find_if(begin(collection), end(collection), [n](int x){return x>n;});
        collection.insert(it, n);
    }
}

const vector<int> values{1000,2000,4000,8000,16000};

int main(){
    cout << "SIZE,Vector Time(ms),List Time(ms)\n";
    for(int N:values)
        for(int again=0;again<3;++again){
        vector<int> t(N);
        for(int i=0;i<N;++i)
            t[i] = i;
        random_shuffle(begin(t), end(t));
        cout << N << ',';
        vector<int> t_vector;
        {bench b;insert_all(t, t_vector);}
        cout << ',';
        list<int> t_list;
        {bench b;insert_all(t, t_list);}
        cout << '\n';
    }
}

Et les résultats obtenus sur ma machine (j’ai pris la moyenne de plusieurs essais).

SIZE Vector Time(ms) List Time(ms)
1k 0.164817 0.49307
2k 0.697207 4.74188
4k 3.80992 26.7169
8k 7.23118 106.516
16k 39.1317 746.279
32k 138.673 6167.51
64k 570.2 16853.9
128k 2403.38 152090

J’ai aussi testé sur une machine ayant une architecture différente (ARMv6l c’est à dire sur un raspberryPi) les résultats sont du même ordre de grandeur: le vector est largement plus rapide.

Est-ce que cela montre que les insertions sur un vector sont plus rapides que sur une liste ? Non, cela montre uniquement que construire un conteneur par insertions en position aléatoire est plus rapide sur un vector que sur une liste, mais cela ne nous dit rien sur la vitesse d’insertion.

En profilant le code, on voit qu’une portion significative du temps est passée dans la fonction find_if. En fait, on doit parcourir linéairement le conteneur pour trouver la position d’insertion puis effectuer l’insertion. Que le conteneur soit un vector ou une liste la complexité d’une insertion est donc linéaire.

Il est tout de même intéressant de noter que parcourir des éléments stockés sur une zone mémoire contiguë est significativement plus rapide. Comme il est possible en C++ d’avoir du contrôle sur le layout de la mémoire c’est un point qui peut être utile.

Cependant en pratique, je ne connais pas beaucoup d’exemples sur lesquels l’utilisation d’une liste est supérieure à celle d’un vector. En effet si la liste est plus rapide pour l’insertion ou la suppression en position arbitraire d’un élément. Dès qu’il faut parcourir le conteneur pour trouver cette position d’insertion, le vector redevient plus rapide. Un cas possible est celui de l’implémentation d’un cache LRU. En stockant dans la table de hachage l’itérateur vers la position de l’élément dans la liste on peut effectuer toutes les opérations en temps constant.

Friday, April 25, 2014

Coursera

La suite de mes impressions sur plusieurs cours en-ligne (MOOC) à la fois sur Udacity et sur Coursera.

Udacity va arrêter de donner des certificats pour ceux n’étant pas inscrit à la partie payante du cours, c’est dommage c’était une motivation supplémentaire pour finir le cours.

J’ai donc suivi 5 nouveaux cours depuis le dernier post, à savoir: Startup Engineering, Computational Investing, Part I, Algorithms: Design and Analysis, Part 2, Intro to Hadoop and MapReduce et Web Development. Voici ce que j’ai pensé de chacun de ces cours.

  • Startup Engineering Le but de ce cours été de voir comment utiliser les outils modernes (bitcoin, cloud…) pour lancer une startup orientée web. Ce cours était très bien parti, les poly étaient vraiment travaillés et contenaient de nombreuses informations. Malheureusement les enseignants ont sans doute mal évalué la charge de travail que cela allait leur demander et le cours à été abandonné au bout de quelques semaines. Cela dit les poly sur la mise en place d’un environnement de développement et l’utilisation du cloud (amazon web service et heroku) est très bonne, et c’est une très bonne lecture si vous avez un projet web mais que vous ne savez pas vraiment comment mettre en place l’infrastructure.

  • Computational Investing, Part I Pas grand chose à dire sur ce cours. En utilisant Python et une librairie fournie (QSTK) on a analysé des tas de valeurs boursières. Par exemple on peut trouver des événements (une valeur chute alors que celles du même secteur augmentent par exemple) puis voir la tendance historique après un tel événement (la valeur remonte alors significativement 2 semaines plus tard). On peut alors en déduire quelle valeur acheter automatiquement en fonction des événements actuels. L’idée étant de faire de nombreuses transactions pour être en moyenne gagnant. Je pense que le cours était très bien fait, mais il faudrait prendre plus de temps pour pouvoir plus expérimenter. Les statiques sur les avis des étudiants pour ce cours sont disponibles ici.

  • Algorithms: Design and Analysis, Part 2 Un très bon cours d’algo. Le plan annoncé a parfaitement été suivi et les exercices (tant théoriques que de programmation) permettaient vraiment d’approfondir le cours. En revanche les algorithmes étudiés sont tous très classiques, si vous connaissez bien les algorithmes du Cormen vous n’apprendrez sans doute pas grand chose de plus avec ce cours. Celui de [structures avancées](http://ocw.mit.edu/courses /electrical-engineering-and-computer-science/6-851-advanced-data-structures- spring-2012/lecture-videos/) du MIT est sans doute bien plus intéressant pour ceux ayant déjà des bases solides d’algo.

  • Intro to Hadoop and MapReduce Une introduction à Hadoop le framework open-source de référence pour mapReduce. Je suis un peu déçu sur le contenu de ce cours. Je l’ai fini en une après-midi ce qui est exceptionnellement court. Au final j’ai vu la mise en place d’Hadoop avec la distribution de cloudera et le principe des algorithmes (une phase de mapping puis une de reduce). Notez qu’Hadoop peut aussi exécuter des programmes en Python. C’est ce qui était proposé ici. Il suffisait d’écrire une fonction map et une fonction reduce en Python. Au fond c’est un bon tuto sur Hadoop et mapReduce mais vous en aurez fait le tour très rapidement. Et la question centrale de comment installer Hadoop sur un tas de machines n’est pas abordée alors que c’est à mon avis le point difficile, le paradigme MapReduce étant finalement très simple.

  • Web Development Peut-être le meilleur cours en ligne que j’ai suivi jusqu’à maintenant. Le but était de construire des applis web (blog, wiki) en Python en utilisant Google app Engine (dont le quota gratuit est suffisant pour toutes sortes d’essais). J’avais déjà fait un site en Python sur Google app Engine mais j’ai vu de nombreuses techniques pour simplifier mon code et si j’avais suivi ce cours avant j’aurais définitivement gagné un temps fou.

Wednesday, January 29, 2014

Top 5 des erreurs stupides

Dans les problèmes de programmation du type CodinGame, ACM, Google Code Jam, etc., certaines erreurs reviennent fréquemment. C’est d’autant plus rageant qu’elles sont difficiles déboguer (sur les exemples ça marche) et qu’une fois trouvées, on se rend compte que ce sont des erreurs triviales déjà faites plusieurs fois.
Voyons donc ce que je considère comme mon top 5 d’erreurs stupides.

Les int overflow


En C++ la norme demande qu’un int soit codé sur au moins 16 bits, il peut donc contenir au moins des entiers de -32767 à 32767. En pratique je n’ai jamais vu (en 2014) de système où un int n’est pas codé sur au moins 32 bits, il peut alors contenir des entiers de -2147483647 à 2147483647. Il est donc raisonnable d’utiliser des int lorsque les nombres considérés sont inférieurs à 10^9.
Le problème étant que de nombreux problèmes demandent le résultat modulo un grand nombre. Et là même si le modulo est inférieur à 10^9 et donc que le résultat final tient bien dans un int, ce n’est pas le cas des résultats intermédiaires.
Dans ce code récursif (pour info la version itérative est sensiblement plus rapide) de l’exponentiation rapide modulaire:
int expMod(int a, int b, int MOD){
    if(b==0) return 1;
    long long tmp = expMod(a, b/2, MOD);
    tmp = (tmp*tmp)%MOD;
    if(b%2==0)
        return tmp;
    return (a*tmp)%MOD;
}
Si on défini tmp comme un int et non comme un long long le code devient complètement faux. Attention également à bien prendre le modulo à chaque multiplication est à ne pas faire plusieurs multiplications en une seule étape. Typiquement faire (tmp*tmp*a)%MOD produit également un code faux même avec des long long.
La meilleure manière d’éviter ces problèmes d’int overflow est bien sûr d’y penser avant de coder. Voici cependant plusieurs indicateurs:
  • Vous utilisez des int, le résultat devrait être positif et il est négatif
  • En remplaçant brutalement tous les int par des long long le résultat change
C’est que vraisemblablement vous avez un problème d’int overflow. Si la solution de tous les remplacer par des long long ne suffit pas. Il est aussi très simple d’utiliser gmp (les bindings c++ font que les grands entiers se comportent comme des types de base, vous pouvez alors simplement faire un typedef mpz_class bigInt et utiliser les bigInt comme des int). Le problème de GMP est qu’il est difficile de l’inclure dans votre fichier afin de respecter les contraintes imposées par les sites de programmation. Dans ce cas j’ai récemment trouvé cette librairie qui fourni des infInt avec les bons binding et qui est suffisamment petite pour être inclue dans votre code source.

Les modulo négatifs


Pas grand chose à dire, sur ce problème, mais lorsqu’on ne le sait pas il peut être difficile à trouver. L’opérateur modulo % renvoie un nombre entre -MOD et MOD suivant le signe de votre nombre de départ. Par exemple -5%2==-1, ce qui est plutôt perturbant. Si vous voulez un modulo plus classique, c’est à dire avec un résultat entre 0 est MOD-1, il faut faire ((n%MOD)+MOD)%MOD.

Ne pas réinitialiser ses données


Probablement la pire des erreurs, mais elle n’apparait que lorsqu’il y a plusieurs testcases dans le même fichier. Typiquement lors du second testcase, votre code utilise encore des données liées au premier testcase. C’est souvent compliqué à déboguer, car sur un unique testcase tout semble correct. De plus, si les testcases sont donné par taille croissante il est possible qu’ils se réécrivent dessus, il qu’il n’y ait donc aucun problème.
Je vous conseille donc d’une part de toujours tester votre code sur un fichier de plusieurs testcases, et de rajouter le premier testcase à la fin (dans le but de casser ce problème de testcase de taille croissante).
Une autre solution est de n’avoir aucune structure globale et de définir vos structures de données exactement là où elles sont initialisées. De cette manière les données du testcase précédent n’existent plus lors du testcase suivant. Cela implique souvent de devoir passer en paramètre toutes les données à vos fonctions annexes. Vu qu’il est possible (et souhaitable) de les passer par référence le surcout est négligeable mais c’est vrai que parfois (dans le cas de code très simple) c’est pénible à faire. L’avantage étant qu’il est plus facile de modifier significativement de larges portions de votre algorithme sans casser tout le reste. Par défaut je trouve que c’est la meilleure solution.

Laisser le code de débogue


La vérification étant généralement basée sur un simple diff, laisser un cout de débogue est la meilleure manière d’obtenir un WRONG ANSWER. Dans certains cas, il n’est pas évident de voir le problème, par exemple si l’affichage n’a lieu que dans un cas très précis qui n’a pas lieu sur vos exemples. Ou plus bêtement, si après avoir passé beaucoup de temps à déboguer, vous ne faite plus attention aux messages de débogue corrects.
Le plus simple pour éviter ce problème est de ne pas utiliser la sortie standard pour afficher vos messages de débogue mais plutôt le canal d’erreur par exemple (cerr). Pour éviter le TIME LIMIT si vous avez beaucoup de messages de débogue (il est donc possible que votre programme passe un temps non négligeable à les afficher), vous pouvez les afficher uniquement en mode débogue en utilisant la directive de préprocesseur #ifdef et en compilant en local avec l’option -DDEBUG.
    #ifdef DEBUG
    cerr << "à la ligne 17 t contient:" << endl;
    for(int x:t)
        cerr << x << ' ';
    cerr << endl;
    #endif

Lire les cartes en sautant les espaces

Cette erreur n’est pas si courante, mais vu qu’elle m’a déjà pas mal pénalisé je la mets ici.
Par défaut cin saute les caractères blancs (espace, tabulation, retour de ligne). Si vous devez lire un plan en ASCII et que les cases vides sont représentées par des espaces vous allez donc lire n’importe quoi. De même si vous devez lire une phrase. Vous pouvez alors soit passer noskipws à cin afin qu’il ne saute plus les caractères blancs (attention il faut alors lui passer skipws pour qu’il retrouve son comportement usuel), ou bien simplement utiliser getline.

Thursday, December 12, 2013

Codingame novembre 2013

Neuvième post de la série, comme toujours mes algos et codes en C++ pour les CodinGames. La page d’entrainement est toujours ici.

Le premier exercice demande de répartir le prix d’un cadeau entre différentes personnes. Chaque personne a un budget maximal, mais on veut faire en sorte que le partage soit le plus équitable possible. Ici équitable veut dire que l’on cherche à minimiser la somme de celui qui paye le plus, puis du second qui paye le plus, etc.

Intuitivement, on cherche à privilégier la solution ou tout le monde paye le même prix. Un algorithme possible est de calculer cette somme, faire payer au maximum ceux qui ont un budget inférieur et recommencer avec le prix mis à jour et les personnes restantes. Dans ce cas, il faut faire attention, si le prix n’est pas divisible par le nombre de personnes sur comment gérer les nombres non entiers (certains vont payer un euro de plus que les autres).

Ma solution se base sur cette idée, on trie les budgets par ordre croissant, et pour chacun on paye le minimum entre le budget et le prix divisé par le nombre de personnes restantes. On met alors à jour le nouveau prix et le nombre de personnes restantes. On a alors un algorithme de complexité O(n ln(n)) à cause du tri. Je ne pense pas que ce soit possible de faire plus rapide vu que si les budgets sont exactement les entiers de 1 à n donné dans un ordre quelconque, que le prix du cadeau est exactement la somme (n(n+1)/2), la seule solution est de faire payer chacun au maximum et comme la sortie demande d’être trié, ce problème généralise le tri.

Voici mon code:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long ll;

int main(){
  ll n, c;
  cin >> n >> c;
  vector<ll> t(n);

  for(int i=0;i<n;++i)
    cin >> t[i];

  ll sum=0;
  for(ll x:t)
    sum+=x;

  if(sum<c)
    cout << "IMPOSSIBLE\n";
  
  else{
    sort(begin(t), end(t));
    for(int i=0;i<n;++i){
      ll paye=min(t[i], c/(n-i));
      cout << paye << '\n';
      c-=paye;
    }
  }
}

Le deuxième exo est bien plus long (le premier a été résolu en moins de 10 min alors que le plus rapide à passé 1h15 sur le second). Cependant même s’il est complexe (dans le sens il faut être capable de mettre bout à bout beaucoup de choses) il peut se décomposer en plusieurs problèmes simples. Là ou se problème est intéressant c’est qu’il ne demande pas de connaitre un algo précis ou d’avoir une idée géniale (ceux qui auront passé du temps sur Project Euler comprendront), mais d’être capable d’avoir les idées claires avant de se lancer dans le code et savoir coder juste, vu que la moindre erreur sur un problème intermédiaire sera compliqué à trouver. Pour toutes ces raisons je trouve que c’est un très bon exo pour évaluer la capacité à coder d’un candidat (bon après c’est assez long et probablement trop difficile, mais du coup c’est un excellent entrainement).

Quel est le but de cet exercice ? Faire de la reconnaissance d’image pour décoder une partition. Rien que ça ! C’est un peu pompeux de dire ça, vu que lorsqu’on parle de reconnaissance d’image on pense plutôt à la partie Machine Learning pour classifier les lettres, alors qu’ici on a plutôt besoin de la partie détection, afin de savoir précisément où est chaque note.

Je pense qu’il y a beaucoup de manières de résoudre ce problème voici donc ma solution (qui est loin d’être parfaite, elle marche, mais je ne là pense pas très robuste). Je ne suis pas très content d’avoir autant de variables globales, dans l’idéal il faudrait une classe qui préprocesse le fichier et qui ensuite lit note par note.

La première étape est de transformer le fichier encodé en quelque chose de plus facilement utilisable, vu qu’il n’y a pas vraiment de problème de mémoire, le plus simple est de tout décoder et d’avoir une matrice de pixel. Pour obtenir cette matrice je passe par deux étapes, dans un premier temps readStraight décode le fichier et me donne un tableau en une dimension avec les pixels. Les lignes 85 à 87 mettent ensuite ce tableau en forme pour avoir une vraie matrice. Encore une fois, on pourrait se passer de ce tableau et utiliser uniquement t_straight mais le but est de coder juste et la milliseconde économisée ne vaut pas les 20 min (et encore je suis optimiste) perdues en cas de bug. Une fois la lecture faite il est judicieux de la tester, on peut par exemple utiliser quelque chose comme mes lignes 91 à 95. Ceci permet de trouver immédiatement les bugs idiots (par exemple, je sais que je confonds souvent largeur et hauteur) et aussi (si vous n’êtes pas sujets aux bugs) de voir à quoi ressemble vraiment le fichier. Par exemple on notera que les lignes de portées ne commencent pas au début du fichier.

Ma seconde étape est de savoir où sont les lignes de portées (et je prends aussi en compte la pseudo ligne qui apparait uniquement en bas pour le Do). Pour cela j’ai uniquement besoin de savoir quelle est la première ligne de portés la largeur de chaque porté et l’espacement entre deux portées. Tout ceci est calculé dans la fonction findLine.

L’étape suivante est de détecter les notes. La seule partie qui nous intéresse est les pixels noirs qui ne sont pas ceux des portées ni ceux de queue de note. Une remarque importante est que si je sais éliminer ceux des portées et que je parcours mon fichier pixel par pixel de gauche à droite puis de haut en bas je tombe toujours sur un pixel de note qui n’est pas de queue. En effet lorsque la queue est à gauche elle va toujours vers le bas. Reste uniquement le problème de savoir si le pixel est un pixel de portée ou de note. Connaissant le début de la première portée, sa largeur et l’espacement entre deux portées on peut facilement savoir si un pixel est un pixel de portée. Ceci est fait par la fonction isUsefull.

Connaissant un pixel de la note je fais ensuite un parcours afin de trouver le pixel le plus à gauche et celui le plus à droite de la note (fonction DFS). Dans le cas des notes sur une portée on parcourt uniquement la demi-note, il faut aussi être vigilant pour avoir des pixels de notes qui ne sont pas sur la queue, dans mon cas ça marche, mais le code n’est pas explicite.

On peut alors regarder le pixel au milieu, il détermine si la note est une noire ou une blanche. Finalement en regardant la position de ce pixel par rapport aux lignes de portées on peut connaitre la note. Il faut alors penser à chercher le prochain pixel de note après la fin de la note que l’on vient de traiter.

Voici mon code:

#include<iostream>
#include<vector>

using namespace std;

typedef pair<int, int> pi;

int w, h;
int firstLine, widthBlack, widthNext;
vector<vector<bool> > t;
vector<vector<bool> > visited;

vector<pi> dir{pi{1,0}, pi{-1,0}, pi{0,1}, pi{0,-1}, pi{1,1}, pi{1,-1}, pi{-1, 1}, pi{-1,-1}};
vector<char> note{'G', 'F', 'E', 'D', 'C', 'B', 'A', 'G', 'F', 'E', 'D', 'C'};

void readStraight(vector<bool>& t){
  char c;
  int n;
  int curr=0;
  while(cin >> c >> n)
    while(n--)
      t[curr++]=(c=='B');
}

void findLine(){
  for(int j=0;j<w;++j)
    for(int i=0;i<h;++i)
      if(t[i][j]){
    firstLine=i;
    widthBlack=i;
    while(t[widthBlack][j]) ++widthBlack;
    widthNext=widthBlack;
    while(!t[widthNext][j]) ++widthNext;
    
    widthBlack = widthBlack-firstLine;
    widthNext = widthNext-firstLine;    
    return;
      }
}

bool isUsefull(int x, int y){
  //return true iff t[x][y] is not a line.
  if(!t[x][y])
    return false;
  
  for(int i=0;i<6;++i)
    if(x>=firstLine+i*widthNext && x<firstLine+i*widthNext+widthBlack)
      return false;

  return true;
}

void dfs(int i, int j, pi& p1, pi& p2){
  if(j<p1.second){
    p1.first=i;
    p1.second=j;
  }
  if(j>p2.second){
    p2.first=i;
    p2.second=j;
  }

  visited[i][j]=true;
  for(const auto& d: dir)
    if(!visited[i+d.first][j+d.second] && isUsefull(i+d.first, j+d.second))
      dfs(i+d.first, j+d.second, p1, p2);
}

int main(){
  cin >> w >> h;
  vector<bool> t_straight(w * h);
  readStraight(t_straight);
  
  t.resize(h);
  for(int i=0;i<h;++i)
    t[i].resize(w);

  visited.resize(h);
  for(int i=0;i<h;++i)
    visited[i].resize(w);
  for(int i=0;i<h;++i)
    for(int j=0;j<w;++j)
      visited[i][j]=false;
      
  for(int i=0;i<h;++i)
    for(int j=0;j<w;++j)
      t[i][j]=t_straight[i*w+j];

  findLine();

  //for(int i=0;i<h;++i){
  //  for(int j=0;j<w;++j)
  //    cerr << (isUsefull(i,j)?'#':(t[i][j]?'x':' '));
  //  cerr << '\n';
  //}

  bool first=true;

  for(int j=0;j<w;++j)
    for(int i=0;i<h;++i)
      if(isUsefull(i,j)){
    pi start{w,w};
    pi final{-1,-1};
    dfs(i,j,start, final);

    bool isBlack = t[(start.first+final.first)/2][(start.second+final.second)/2];

    char value='Z';
    for(int i=-1;i<12;++i)
      if(start.first<firstLine+i*widthNext/2){
        value=note[i+1];
        break;
      }

    if(!first)
      cout << ' ';
    first=false;
    cout << value << (isBlack?'Q':'H');

    j=final.second;
    break;
      }
  cout << '\n';
}

Saturday, November 23, 2013

Fast Cin

On dit souvent que les lectures d’entrées sont lentes en C++ et qu’il est préférable d’utiliser scanf/printf à cin/cout. En particulier sur certains sites de problèmes, il serait impossible d’éviter le TIME_LIMIT en utilisant cin/cout. Voyons les faits et comment améliorer les input/output.

Je vais considérer le problème suivant: on doit lire une liste d’entiers (plus petit que 10^9) et tous les dix entiers lus afficher la somme globale modulo 10^9+7.

Voici le code avec cin/cout

#include<iostream>
using namespace std;

const int MOD=1000000007;

int main(){
  //ios::sync_with_stdio(false);
  //cin.tie(nullptr);
  int sum=0;
  int cmt=0;
  int tmp;
  while(cin >> tmp){
    sum+=tmp;
    sum%=MOD;
    ++cmt;
    if(cmt%10==0){
      cmt=0;
      cout << sum << '\n';
    }
  }
}

et avec printf/scanf

#include<cstdio>
using namespace std;

const int MOD=1000000007;

int main(){
  int sum=0;
  int cmt=0;
  int tmp;
  while(scanf("%d",&tmp) != EOF){
    sum+=tmp;
    sum%=MOD;
    ++cmt;
    if(cmt%10==0){
      cmt=0;
      printf("%d\n",sum);
    }
  }
}

J’ai effectué le test avec 50 millions d’entiers générés via ce code (ce qui donne un fichier d’input de 50Mo):

#!/usr/bin/env python
import random
for i in xrange(5000000):
    print random.randint(0,1000000000)

Les résultats montrent clairement que scanf/printf est bien plus rapide. Avec gcc4.8.2 on passe de 12 secondes à 1,5 secondes (dans tous les cas je compile avec -O2).

Une raison de la lenteur de cin/cout est que les flux standards sont synchronisés sur ceux de C. On peut stopper cette synchronisation avec io::sync_with_stdio(false) à placer juste en dessous du main. On passe alors à 2s. Le nouveau code est à peine plus lent que le code utilisant scanf/printf. Mais on peut encore améliorer les choses, ici l’entrée est synchronisée avec la sortie, c’est à dire que cout est flushé avant de pouvoir lire sur cin. Dans le cas d’un programme non interactif cette synchronisation est inutile. On peut la supprimer en ajoutant cin.tie(nullptr), ou sans utiliser nullptr de C++11, cin.tie(0). On obtient alors un code qui s’exécute en 0,8s. Notre code est devenu plus rapide que le code scanf/printf.

On peut tester sur d’autres types que les entiers, les résultats sont toujours les mêmes. Avec io::sync_with_stdio(false) et cin.tie(nullptr) il n’y a pas de perte de performance à utiliser cin/cout. Dans ce cas attention à ne pas mélanger cin/scanf vu qu’ils ne sont maintenant plus synchronisés. Notez bien que ceci n’est pas une méthode miracle, et n’a une chance de vous sauver du TIME_LIMIT que dans le cas d’un algo linéaire (à la limite O(n ln(n))). Sinon le temps de lecture d’entrées est de toute façon négligeable devant le temps d’exécution de votre algo.

méthode temps
cin/cout 12s
cin/cout + sync_with_stdio(false) 2s
cin/cout + sync_with_stdio(false) + cin.tie(nullptr) 0,8s
scanf/printf 1,5s

Tuesday, October 15, 2013

Codingame septembre 2013

Huitième post de la série cette fois avec pas mal de retard, comme toujours mes algos et codes en C++ pour les CodinGames. La page d’entrainement est toujours ici.

Le premier exo demande de simuler les déplacements d’un robot. Algorithmiquement rien de très compliqué pour cet exo, en revanche il faut être organisé pour produire rapidement un code sans bug.

J’ai choisi de coder le robot par un objet contenant les variables pour décrire son état (sa position, vers où regarde-t-il, a-t-il été “inversé”, est-il en mode casseur, est-il vivant). Je stocke également tous ses déplacements précédents, vu que si le robot boucle, il faut simplement afficher “LOOP”. Cet objet contient également une méthode avance qui simule un déplacement.

Pour détecter si le robot boucle, on peut soit utiliser l’algorithme du lièvre et de la tortue où vu qu’ici la mémoire n’est pas critique simplement marqué chaque case vue avec l’état du robot. S’il repasse par la même case avec le même état, c’est qu’il boucle. Attention dans ce cas il ne faut pas seulement avoir l’état du robot, mais également celui du plateau. Vu que la seule modification du plateau possible est les obstacles destructibles, et que cette modification est irréversible, on peut simplement se souvenir du nombre de murs détruits.

Enfin une bonne factorisation, consiste à utiliser un vecteur contenant les déplacements possibles (ici mon vector<pi> D) plutôt que de copier coller le code correspondant à un déplacement dans chaque direction possible. Ceci est encore plus pratique lorsque les déplacements sont plus compliqués (par exemple un cavalier aux échecs).

Attention également à la lecture caractère par caractère avec des espaces, il faut penser à utiliser cin << noskipws.

Pour le reste des détails d’implémentation, voici mon code:

#include<iostream>
#include<vector>
#include<string>

using namespace std;

typedef pair<int, int> pi;

vector<string> carte;
vector<pi> teleport;
int l,c;

struct etat{
  int dir=0;
  bool prio=false;
  bool casseur=false;
  int destroy=0;
  etat(int a=-1, bool b=true, bool c=true, int d=0):
    dir(a), prio(b), casseur(c), destroy(d){};

  bool operator==(const etat& e) const{
    return dir==e.dir &&
        prio==e.prio &&
        casseur==e.casseur &&
        destroy==e.destroy;
  }
};

vector<vector<etat> > state;

struct Bender{
  int x,y;
  int dir=0;
  bool prio=false;
  bool casseur=false;
  int destroy=0;
  bool alive=true;

  vector<pi> D{pi(1,0), pi(0,1), pi(-1,0), pi(0,-1)};

  vector<string> past_dir;

  bool avance(){
    etat et(dir,prio,casseur,destroy);
    if(state[x][y]==et)
      return false;
    state[x][y]=et;

   int nx=x+D[dir].first, ny=y+D[dir].second;
   if(nx<0 || nx>=l || ny<0 || ny>=c || carte[nx][ny]=='#' ||
       (carte[nx][ny]=='X' && !casseur)){
     for(int i=0;i<4;++i){
       int ndir=prio?3-i:i;
       int nx=x+D[ndir].first, ny=y+D[ndir].second;
       if(nx<0 || nx>l || ny<0 || ny>c || carte[nx][ny]=='#')
     continue;
       if(carte[nx][ny]=='X' && !casseur)
     continue;
       
       dir=ndir;
       x=nx;
       y=ny;
      break;
     }
   }
   else{
     x=nx;
     y=ny;
   }

   if(dir==0)
     past_dir.push_back("SOUTH");
   else if(dir==1)
     past_dir.push_back("EAST");
   else if(dir==2)
     past_dir.push_back("NORTH");
   else
     past_dir.push_back("WEST");

    if(carte[x][y]=='X'){
      carte[x][y]=' ';
      destroy++;
    }
    else if(carte[x][y]=='$'){
      alive=false;
      return false;
    }
    else if(carte[x][y]=='S')
      dir=0;
    else if(carte[x][y]=='E')
      dir=1;
    else if(carte[x][y]=='N')
      dir=2;
    else if(carte[x][y]=='W')
      dir=3;
    else if(carte[x][y]=='B')
      casseur=!casseur;
    else if(carte[x][y]=='I')
      prio=!prio;
    else if(carte[x][y]=='T'){
      if(x==teleport[0].first && y==teleport[0].second){
    x=teleport[1].first;
    y=teleport[1].second;
      }
      else{
    x=teleport[0].first;
    y=teleport[0].second;
      }
    }
    
    return true;
  }
};


int main(){
  cin >> l >> c;
  cin.ignore();
  
  Bender b;
  state.assign(l,vector<etat>(c));

  for(int i=0;i<l;++i){
    string tmp;
    getline(cin, tmp);
    carte.push_back(tmp);
  }
  
  for(int i=0;i<l;++i)
    for(int j=0;j<c;++j){
      char tmp=carte[i][j];
      if(tmp=='@'){
    b.x=i;
    b.y=j;
    tmp=' ';
      }
      else if(tmp=='T')
    teleport.push_back(pi(i,j));
    }

   while(b.avance());

  if(!b.alive)
    for(auto s:b.past_dir)
      cout << s << '\n';
  else{
    cout << "LOOP\n";
  }

}

Le deuxième exo est assez classique et ressemble à “Dwarfs standing on the shoulders of giants”. Étant donné un graphe orienté sans cycle (un DAG) il faut trouver le plus long chemin. Cette fois les arêtes ont des poids, mais cela ne change pas vraiment le problème. Pour résoudre efficacement ce problème, il faut utiliser la programmation dynamique. Comme souvent je préfère écrire simplement ma fonction récursive et utiliser la mémoïzation afin de ne pas refaire des calculs. L’idée est simple, dès qu’un sous problème est résolu je stocke la solution dans une table. Si ce sous-problème apparait de nouveau il suffit de vérifier s’il n’est pas déjà dans la table, et dans ce cas renvoyer directement le résultat, sinon il faut faire le calcul.

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<limits>

using namespace std;

const int NEG_INF=numeric_limits<int>::min();

int aux(const string& start, map<string, vector<string> >& from,
    map<string, int >& money, map<string, int>& mem){
  if(mem[start]!=0) return mem[start];
  
  int res=(start=="0")?0:NEG_INF;
  for(auto pred:from[start])
    res=max(res, aux(pred, from, money, mem)+money[pred]);

  return mem[start]=res;
}

int main(){
  int n;
  cin >> n;
  map<string, int> mem;
  map<string, vector<string> > from;
  map<string, int > money;
  for(int i=0;i<n;++i){
    string in, out1, out2;
    int found;
    cin >> in >> found >> out1 >> out2;
    from[out1].push_back(in);
    from[out2].push_back(in);
    money[in]=found;
  }
  cout << aux("E", from, money, mem) << '\n';
}

Le dernier problème est plutôt original, étant donné des mesures de performance d’un algorithme, i.e. son temps d’exécution sur une entrée de taille donnée il faut prédire sa complexité.

Ma première idée était d’appliquer une transformation “inverse”, calculer le coefficient de corrélation linéaire, et prendre la transformation donnant le plus grand coefficient. Cela avait deux problèmes, calculer l’inverse de (n log(n)) n’est pas évident même si on peut toujours le faire numériquement. D’autre part, je ne sais pas comment distinguer une complexité constante d’une complexité linéaire.

La solution que j’ai retenue, est la suivante: je calcule les valeurs de référence xi pour chaque fonction possible, je prends ensuite un coefficient multiplicateur comme étant la moyenne des rapports xi/ti où ti est la valeur fournie par l’entré et xi la valeur théorique pour la taille de l’entrée. Je calculer ensuite la somme des carrés des écarts et je prends la fonction minimisant cette valeur. Du point de vue pratique, utiliser des valarray rend le code vraiment simple et concis.

Maintenant ma solution n’est pas vraiment bonne puisque pour valider ce problème j’ai du éliminer les données avec un temps d’exécution trop faible. Dans la vraie vie, ce serait justifié. En efet timer un programme s’exécutant instantanément n’a pas de sens dans la mesure où la moindre perturbation de la machine (un accès disque…) provoque des écarts de mesure significatifs.

#include<iostream>
#include<valarray>
#include<vector>

using namespace std;

double comp_diff(valarray<double>& x, const valarray<double>& t){
  x*=(t/x).sum()/t.size();
  valarray<double> tmp = (t-x)*(t-x);
  return abs(((t-x)*(t-x)).sum());
}

int main(){
  int N;
  cin >> N;

  vector<double> nn, tt;
  for(int i=0;i<N;++i){
    double n1, t1;
    cin >> n1 >> t1;
    if(t1>100){
      nn.push_back(n1);
      tt.push_back(t1);
    }
  }

  valarray<double> n(nn.data(), nn.size()), t(tt.data(), tt.size());

  valarray<double> x(1,t.size());

  double mini = comp_diff(x,t);
  string res = "O(1)";
  double tmp;

  //log
  x = log(n);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(log n)";
  }

  //n
  x = n;
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n)";
  }

  //nlog
  x = n*log(n);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n log n)";
  }

  //n2
  x = pow(n,2.);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n^2)";
  }

  //n2 log
  x = pow(n,2.)*log(n);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n^2 log n)";
  }

  //n3
  x = pow(n,3.);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(n^3)";
  }

  //2^n
  x = pow(2.,n);
  tmp = comp_diff(x, t);
  if(tmp<mini){
    mini=tmp;
    res="O(2^n)";
  }

  cout << res << endl;
}

Et vous, comment avez-vous résolu ce dernier problème ?