Code of duty

Cela faisait longtemps que je n'avais plus écrit ici...

Ce billet est consacré à un évènement en cours au moment ou j'écrit: code of duty (http://codeofduty.criteo.com/)

Petit récapitulatif: c'est un concours de programmation ou il y a des lots à gagner (assez intéressants: iPad2, 10.000€!!).

Alors que j'essayais de produire une solution, j'ai été confronté à un problème de compréhension relative à la phrase suivante: "l’élément ni ne peut « transférer » qu’une unité à un seul de ses voisins". Je comprends cette phrase comme: "Un élément A ne peut se voir décrémenter que d'une seule unité par itération". Mais quid de l'incrémentation? Est-ce possible d'incrémenter deux fois un élément? Prenons par exemple la configuration (3 0 3). S'il on peut incrémenter plus d'une fois par itération, alors une seule itération suffit. Sinon, deux itérations sont nécessaires.

Du coup, j'ai râlé tout seul dans mon coin et j'ai passé en revue l'énoncé et différentes questions me sont venues à l'esprit:
* Dans un de leurs point de la FAQ, ils parlent de deux points en moins toutes les deux heures. Je suppose que cette règle est présente pour favoriser ceux qui ont été réactifs. Mais les plus réactifs sont déjà favorisé par la règle "A réponse identique entre deux ou plusieurs participants, c’est la première reçue qui aura l’avantage." Identique c-a-d, algorithme identique? Ou cotation identique?
* Pourquoi ne pas avoir choisi de publier toutes les soumissions? Cela aurait été très
instructif.
* Le matériel utilisé n'a pas été très défini. Je ne demande pas savoir la quantité de cache L2 des processeurs, mais il a été dit que les machines pouvaient être single ou dual core. Or, il me semble que cela fait une très grande différence si l'on veut utiliser le multi-thread.
* Lors des soumissions, il est demandé de n'envoyer qu'un seul fichier. Je comprends l'aspect pratique pour ceux qui vont recevoir toutes les soumissions. Mais le java pousse les utilisateurs à avoir qu'une classe par fichier tandis que pour le C et C++, tout le monde a tendance à séparer les définitions des implémentations. Du coup, je trouve ce choix curieux.
* Une seule soumission est permise. Je trouve cela dommage et presque en contradiction avec la règle favorisant les personnes réactives. La première idée n'est pas toujours la bonne. Donc, si je veux attendre d'avoir une nouvelle idée pour les comparer, je suis obligé d'attendre et donc, perdre des points.
* Pourquoi ne pas pouvoir poser de questions pendant le concours? A partir du moment ou toutes les questions/réponses seraient accessibles à tous, il n'y aurait pas d'avantage donné à celui qui pose la question.


Après avoir lu ces différentes réflexions, vous pourriez penser que tout est noir, mais je tiens à relativiser. Ce sont des points que j'aimerai voir amélioré lors de la prochaine édition et j'espère réellement qu'une prochaine édition aura lieu. Car je tient à féliciter les organisateurs de ce concours car cela demande un réel travail de leur part. Et je tiens également à prendre mes responsabilités: je n'ai pas pris le temps de lire toute la documentation avant le début du concours auquel cas j'aurai pu poser certaines de ces questions et j'y aurai eu des réponses.


Sinon, note personnelle: utiliser ce blog lorsque je veux faire part d'une réflexion, twitter c'est juste bon pour publier des faits et c'est vraiment pas pratique pour avoir une discussion avec quelqu'un...

Quadtree - partie 5

Un tout petit billet pour expliquer une petite modification possible relative aux quadtree dont les éléments sont contenus dans des feuilles. Plutôt que de contenir qu'un seul élément, une feuille pourrait contenir plusieurs éléments. Quel en serait l'avantage? Le plus évident est celui de la limitation de consommation de mémoire. En effet, si une feuille peut contenir N éléments, ce sont autant de feuilles qu'il ne faut pas créer.

Et comme souvent, il est également nécessaire de se poser la question: quel est le coût de ceci? Et bien, lors de la recherche, lorsque l'on arrive à une feuille, il faudra rechercher l'élément souhaité parmi N. Cette recherche peut être soit logarithmique (mais alors il faut maintenir le tableau trié), soit linéaire ( ce qui ne nécessite pas de garder le tableau trié lorsque l'on ajoute un élément). Toutes les opérations (consultation, ajout, suppression) s'en trouveront ralenties en fonction de N ce qui rend le choix de cette valeur assez crucial.

Quadtree - partie 4

Bon, pour ce billet, on va changer un peu les règles. Adieu la sauvegarde des éléments dans chacun des noeuds. On sauvegardera les éléments dans les feuilles. Quel est l'avantage me demanderez-vous? Et bien, cela dépend des applications. Si vous utilisez des langages assez modulaire, il y a moyen de créer deux structures de noeuds. La première sert la création l'arbre tandis que la seconde sert de feuille.
À quoi servirait la distinction? Simplement l'économie de mémoire. Et ce soucis d'économie n'est pas superflu. En effet, tous les noeuds servant à la création de l'arbre sont autant de données qui ne sont pas directement liée aux éléments.

Qu'est-ce que ça change? Et bien, un peu tout.

Retrait d'un élément

Le retrait est un peu plus compliqué que la version précédente. Nous devons nous assurer que si un noeud existe, il référence au minimum un élément, et s'il ne référence qu'un seul élément alors ce noeud ne possède pas de fils et il contient lui-même l'élément. Ensuite, si le noeud n'est pas une feuille et qu'il référence deux éléments, alors celui-ci deviendra une feuille lorsque l'on aura enlevé un des fils.
Dès lors, une question se pose. Comment connaitre le nombre de noeud référencés? Un parcours de l'arbre peut être effectué, mais ce n'est pas efficace. Une manière de connaitre ce nombre serait de maintenir un compteur dans chaque noeud. De ce fait, la structure deviendrait la suivante:

definition of Node{
  x, y, w, h, s : Integer;
  ne, nw, se, sw : Node;
  element : Element;
}

Un entier s est ajouté afin de retenir le nombre d'éléments référencés par ce noeud.

function removeElement( n : Node, e : Element) : Node{
  centerX, centerY : Integer;
  if( n.s = 1) {
    destroy( n);
    removeElement = null;
  }else{
    centerX = n.x + n.w / 2;
    centerY = n.y + n.h / 2;
    if( e.x > centerX){
     if( e.y > centerY){
       n.ne = removeElement(n.ne, e);
     }else{
       n.se = removeElement(n.se, e);
     }
    } else {
     if( e.y > centerY){
       n.nw = removeElement(n.nw, e);
     }else{
       n.sw = removeElement(n.sw, e);
     }
    }
    if(n.s = 2){
      if(n.ne != null){
        n.element = n.ne.element;
        destroy( n.ne);
      }else if (n.nw != null){
        n.element = n.nw.element;
        destroy( n.nw);
      }else if (n.se != null){
        n.element = n.se.element;
        destroy( n.se);
      }else if (n.sw != null){
        n.element = n.sw.element;
        destroy( n.sw);
      }
    }
    n.s = n.s - 1;
    removeElement = n;
  }
}

Pour ce code, on suppose que l'élément que l'on veut enlever existe bel et bien au sein de l'arbre.

Ajout d'un élément

Il y a plusieurs cas à distinguer. Soit le noeud courant est une feuille, alors il contient un élément. Soit ce n'est pas une feuille, alors on peut atteindre au moins deux éléments à partir de lui. Donc au moment d'ajouter un élément dans un noeud, il faut regarder si celui ci possède un fils.

procedure addElement( n: Node, e: Element){
  tmp : Element;
  centerX, centerY : Integer;
  n.s = n.s + 1;
  if( n.element == null){
    centerX = n.x + n.w / 2;
    centerY = n.y + n.h / 2;
    if( e.x > centerX){
     if( e.y > centerY){
       if( n.ne == null){
         create( n.ne);
         n.ne.element = e;
         n.ne.x = centerX;
         n.ne.y = centerY;
         n.ne.w = n.w / 2;
         n.ne.h = n.h / 2;
         n.ne.s = 1;
       }else{
         addElement( n.ne, e)
       }
     }else{
       if( n.se == null){
         create( n.se);
         n.se.element = e;
         n.se.x = centerX;
         n.se.y = n.y;
         n.se.w = n.w / 2;
         n.se.h = n.h / 2;
         n.se.s = 1;
       }else{
         addElement( n.se, e)
       }
     }
    } else {
     if( e.y > centerY){
       if( n.nw == null){
         create( n.nw);
         n.nw.element = e;
         n.nw.x = n.x;
         n.nw.y = centerY;
         n.nw.w = n.w / 2;
         n.nw.h = n.h / 2;
         n.nw.s = 1;
       }else{
         addElement( n.nw, e)
       }
     }else{
       if( n.sw == null){
         create( n.sw);
         n.sw.x = n.x;
         n.sw.y = n.y;
         n.sw.w = n.w / 2;
         n.sw.h = n.h / 2;
         n.sw.element = e;
         n.sw.s = 1;
       }else{
         addElement( n.sw, e)
       }
     }
    }
  }else{
    tmp = n.element;
    n.element = null;
    addElement( n, tmp);
    addElement( n, e);
  }
}

Un petit mot d'explication lors d'ajout d'un élément dans une feuille. On peut facilement savoir si un noeud est une feuille. En effet, s'il l'est, alors il contient un élément. S'il n'en contient pas, c'est qu'il n'est pas une feuille.
Une fois que l'on sait qu'un élément est une feuille, il va falloir enlever l'élément de la feuille pour le mettre dans une nouvelle feuille, puis ajouter l'élément que l'on devait ajouter.

Recherche d'un élément

Il est assez facile d'effectuer la recherche d'un élément au sein d'un arbre quaternaire dont seules les feuilles contiennent des éléments. Le code parle de lui-même:

function lookAt( n : Node, x : Integer, y : Integer) : Element {
  if( n.s = 1) {
    if( n.element.x == x && n.element.y == y){
      lookAt = n.element;
    }else{
      lookAt = null;
    }
  }else{
    centerX = n.x + n.w / 2;
    centerY = n.y + n.h / 2;
    if( e.x > centerX){
     if( e.y > centerY){
       lookAt = lookAt(n.ne, x, y);
     }else{
       lookAt = lookAt(n.se, x, y);
     }
    } else {
     if( e.y > centerY){
       lookAt = lookAt(n.nw, x, y);
     }else{
       lookAt = lookAt(n.sw, x, y);
     }
    }
  }
}

Quadtree - partie 3

Pour ce billet, une petite question: comment initialiser le noeud racine?

Soit on le définit comme représentant tout l'espace possible. Mais cela pose deux problèmes. Certains langages n'ont pas de limite sur la taille des nombre représentés, il n'y a pas donc pas moyen de borner l'espace possible. Le deuxième problème est plus vicieux. Supposons que les nombres entiers soient codés sur n bits. Il y a donc 2^n nombres différents. Généralement, le premier bit est utilisé pour le signe du chiffre. Ceci étant connu, quelle valeur doit-on mettre pour initialiser x, y, w, et h? Si l'on veut représenter tout l'espace w et h devraient valoir 2^n. Et il n'est pas toujours possible d'assigner une telle valeur à une variable.

Une autre solution est de spécifier un sous-domaine du domaine complet. Mais alors, que ce passe t'il lorsque l'on veut ajouter des éléments en dehors de ce sous-domaine?
Il existe une solution: agrandir l'arbre. L'idée est simple: avant d'ajouter un élément dans l'arbre, on regarde si le domaine représenté contient l'élément. Sinon, on crée un nouveau noeud A qui aura pour fils la racine de l'arbre. Et A devient donc la nouvelle racine.

Voici un petit extrait de code permettant de faire cette deuxième option.

function extend( r : Node, e : Element) : Node {
tmp : Node;
create( tmp);
tmp.w = r.w * 2;
tmp.h = r.h * 2;
if( e.x < r.x){
  if( e.y < r.y){
    tmp.ne = r;
  } else{
    tmp.se = r;
  }
} else{
  if( e.y < r.y){
    tmp.nw = r;
  } else{
    tmp.sw = r;
  }
}

Cependant, il faut faire attention: cela ne règle pas le problème de limitation des entiers. Et lorsque l'on augmente la taille de la nouvelle racine il se peut que l'on dépasse les limites pour les entiers...