vendredi 30 septembre 2011

Un client lourd Médoc

Mon projet de documentation Médoc continue de fonctionner impeccablement, du moins du côté de la base de données et du client Web. Par contre, le client lourd en OCaml et LablGTK, chargé de charger les documents dans la base à partir du scanner ou d'un fichier, commence à tomber en ruines.

Pas très ergonomique d'une part, et pas très intégré d'autre part (la plupart des commandes, telles le chargement de fichier ou le scan en lui-même, sont faites à partir de lignes de commandes lancées par le programme). Je me suis donc mis à écrire un client lourd en C++ avec WxWidgets qui soit un peu plus pratique à utiliser. La libsane se chargera de piloter le scanner, libmagick++ sait apparemment transformer un pdf en image, et la libharu sait transformer une image en pdf.

Y'a plus qu'à coller les morceaux.

mercredi 28 septembre 2011

Courir après sa base de données

Julien me parlait de systèmes de suivi de courses type marathon ou trail à base de RFID, et il n'en a pas fallu plus pour enflammer mon imagination. Je pensais à ce à quoi ressemblerait un schéma de base de données enregistrant le passage des coureurs à des points donnés, afin de permettre le suivi par les commissaires de courses, le public, et la publication des résultats et des statistiques pour les coureurs. Et on dirait bien qu'un tel système présente une sacrée dose de défis.

L'on s'intéressera plutôt aux courses de type ultramarathon ou trail, sur chemins ou en pleine nature, où les coureurs doivent s'enregistrer auprès des commissaires de courses à des points de passages déterminés. Le coureur passe donc son RFID au dessus de l'appareil du commissaire de course, et repart.

Voyons donc ce schéma. Les faits sont assez simples: une table contenant chaque détection d'un coureur à un point de passage. Mais qu'est-ce qu'un coureur, et qu'est-ce que c'est qu'un point de passage? Redéfinissons: notre table contient chaque détection d'un RFID par un appareil. Et il ne doit pas être possible de modifier ou d'enlever une ligne: une détection est une détection. Elle s'est effectuée à une certaine heure déterminée par l'appareil, et reçue à une autre heure (parfois beaucoup plus tard s'il y a des soucis de connectivité) par la base de données.

(device_id, rfid, device_timestamp, local_timestamp)

L'on pensera bien sûr aux pannes: si un rfid ou un appareil ne fonctionne plus, le commissaire pourrait se retrouver forcé d'enregistrer les coureurs manuellement via un autre type d'identification, comme un dossard.

(marshal_id, runner_id, marshal_timestamp, local_timestamp)

Ce sont les faits: irréfutables.

Maintenant, tout le problème est de rajouter les tables qui permettront d'associer les appareils aux points de passages, et les RFID aux coureurs.

- Un coureur découvre en milieu de course que son RFID est défectueux, et un commissaire de course lui en fournit un autre
- N'ayant cependant pas rendu son premier RFID, qui s'est tout à coup mis à remarcher, il passe parfois l'un, parfois l'autre aux points de passages
- Deux coureurs échangent un sac, et oublient que leur RFID était dedans

- Un commissaire change de point de passage, et garde avec lui son appareil
- Les commissaires découvrent que l'appareil pour la détection à l'arrivée est en panne, et décident de rapatrier un autre appareil pour l'arrivée, où une détection précise est plus importante

Toute la difficulté est donc de maintenir l'état le plus fréquent (un coureur ayant correctement été enregistré par son RFID par les bon appareils aux bons endroits), tout en permettant un réglage fin de toutes les petites déviations qui surviennent lorsque la réalité débarque avec ses gros sabots dans la théorie.

Peut-on rajouter la positien GPS de chaque appareil à chaque enregistrement pour tenter de les associer automatiquement à un point de passage?
Peut-être des tables se basant sur des plages horaires ou géographiques: de telle heure à telle heure, ou de tel point de passage à tel point de passage, le coureur A avait le RFID f, puis il est passé au RFID g?
Ou tout simplement des tables d'override: tel enregistrement doit être ignoré, tel autre doit être considéré comme ayant détecté le RFID g et non f?

Pas évident.

mardi 27 septembre 2011

Github

J'ai enfin fait le saut, et me voici sur github. Ayant depuis longtemps eu l'envie de m'essayer à git, le logiciel de contrôle de version décentralisé crée par Linus Torvalds, je me suis ouvert un compte sur github, et j'ai commencé à commiter.

Github est particulièrement bien: guidant pas à pas la création du dépôt et la configuration de git, réactif et ergonomique, c'est un petit bijou d'interface. Les performances ont également l'air d'être au rendez-vous.

Utilisant git de manière mono-utilisateur et mono-branche, mon utilisation est très proche de Subversion (en beaucoup plus rapide cependant, mais les dépôts Subversion de tortue de chez Sourceforge n'aident pas non plus), j'espère cependant au moins m'y initier suffisamment pour ne plus être complètement perdu lorsque certains collègues plus dégourdis jonglent avec git-svn sur les dépôts du boulot.

Déjà quelques trucs qui m'ont un petit peu bloqué: il n'est pas possible d'avoir des répertoires vides. La solution standard est de créer un .gitignore vide dans le répertoire, et d'ajouter ce fichier. Également, ajouter un répertoire est récursif, ce qui est souvent bien, mais parfois lourd lorsque ce répertoire contient déjà un build, par exemple. Le plus simple est de commencer par nettoyer tous les fichiers non voulus avant d'ajouter.

jeudi 22 septembre 2011

Le crible en détail, partie 2

Continuons donc à décortiquer le programme.

La fonction principale de notre crible contient la sous-fonction do_sieve, qui permet une fois de plus de devenir tail recursive, ou à récursion terminale en bon français.

Elle prend comme paramètres l'entier courant à tester, l'ensemble des multiples des nombres premiers précédents, et la liste courante des nombres premiers. À partir de là, c'est tout bête: l'on retire le premier élément de nos multiples, et on le compare à l'entier à tester. S'ils sont égaux, notre entier courant est un multiple, donc non premier, l'on ré-appelle donc notre fonction récursive avec l'entier suivant. Si ce n'est pas l'entier à tester, on a trouvé un nombre premier! L'on ajoute tous ses multiples à la liste des multiples, l'on rajoute l'entier à la liste de nos nombres premiers, et l'on appelle la fonction récursivement. Et bien sûr, puisqu'il faut bien sortir un jour de la récursion, n'oublions pas notre condition de sortie: lorsque l'entier courant atteint le maximum passé en paramètre de la fonction principale, l'on retourne nos nombres premiers.

Notez l'optimisation qui consiste à zapper les multiples de 2: l'on démarre à 3, et l'on passe de 2 en 2 pour l'entier courant et pour le calcul des multiples.

Voici une indication des performances. Loin des meilleurs résultats impératifs, mais tout à fait utilisables.




LimiteTemps
100 000140ms
1 000 0002.7s
10 000 00041s

samedi 17 septembre 2011

Le crible en détail, partie 1

Mon post précédent était un poil laconique, je vais donc reprendre quelques détails d'implémentation, et en profiter pour vous convaincre que OCaml, ça roxe.

Les premières lignes sont simplement la définition d'un set sur les entiers. Les sets en OCaml fonctionnent via des modules paramétrés par d'autres modules suivant une certaine signature. L'on créé donc un module définissant un type t et sa comparaison, avec lequel on paramétrise le module Set.Make.


module OrderedInt =
struct
type t = int
let compare = compare
end

module IntSet = Set.Make(OrderedInt)

Ceci va donc définir un module tout neuf, que j'appelle IntSet, et qui fournit des fonctions pour travailler sur des sets fonctionnels, c'est à dire sans effets de bords. Ainsi, ajouter un élément au set retourne en fait un nouveau set contenant l'élément. C'est plus efficace qu'il n'y parait, et surtout, cela permet de raisonner à plus haut niveau, d'une manière plus mathématique.

Ensuite, définissons une fonction qui nous sera utile plus tard, qui retourne une liste d'entiers entre deux entiers définis, avec un pas.

let seq_step a b t =
let rec do_seq_step a acc =
if a > b then
acc
else
do_seq_step (a + t) (a::acc)
in
List.rev (do_seq_step a [])

La fonction définit une sous-fonction do_seq_step, prenant l'entier courant a, et la liste d'entiers accumulés jusque là acc. La récursion est triviale: si mon entier courant a atteint ma borne supérieure, retournons la liste accumulée jusque là. Sinon, appelons récursivement la fonction, avec mon entier courant incrémenté du pas, et ma liste à laquelle j'aurais ajouté mon entier courant.

Depuis la fonction externe, l'on appelle la sous-fonction en passant la borne inférieure, et une liste vide. Enfin, parce que l'on a accumulé les entiers à l'envers (en partant de 3 de 2 en 2: [3], puis [5; 3], puis [7; 5; 3]...), l'on inverse la liste avec List.rev. Le résultat:

# seq_step 3 10 2;;
- : int list = [3; 5; 7; 9]

Notez que l'on aurait pu implémenter la fonction d'un coup, de cette façon:

let rec seq_step2 a b t =
if a > b then
[]
else
a::(seq_step2 (a + t) b t)

Le résultat semble strictement le même, et pourtant:

# seq_step 1 1000000 1;;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; ...]

# seq_step2 1 1000000 1;;
Stack overflow during evaluation (looping recursion?).

La deuxième version est arrêtée nette par un dépassement de pile. C'est que la première version est une récursion terminale (ou tail-recursion en anglais), c'est à dire qu'elle peut être trivialement transformée en une fonction itérative, ce que fait le compilateur. La deuxième, elle, utilise la pile comme accumulateur implicite, et provoque donc un dépassement de pile lorsque le nombre de récursions devient trop important.

Pour des raisons de performances et d'extensibilité, il est donc recommandé d'implémenter ses fonctions de manière récursive terminale à chaque fois que cela est possible.

Voilà, suivant l'approche ascendante qui sied bien à OCaml et aux langages fonctionnels, c'est à dire la construction de fonctions de base, puis de fonctions plus haut niveau utilisant ces briques, les utilitaires utilisés pour le crible. Dans la deuxième partie, je reprendrait plus en détails l'algorithme du crible lui-même.

Implémentation fonctionnelle d'un crible d'Ératosthène

Voilà l'engin:


module OrderedInt =
struct
type t = int
let compare = compare
end

module IntSet = Set.Make(OrderedInt)

let seq_step a b t =
let rec do_seq_step a acc =
if a > b then
acc
else
do_seq_step (a + t) (a::acc)
in
List.rev (do_seq_step a [])

let sieve n =
let rec do_sieve current multiples primes =
if current > n then
primes
else if IntSet.is_empty multiples || IntSet.min_elt multiples <> current then
do_sieve
(current + 2)
(List.fold_left
(fun acc e -> IntSet.add e acc)
multiples
(seq_step (current * 3) n (current * 2)))
(current::primes)
else
do_sieve (current + 2) (IntSet.remove current multiples) primes
in
do_sieve 3 IntSet.empty [2]

Sur ma machine, compilé en natif, trouver les nombres premiers en dessous du million prend 2,7 secondes.

mercredi 14 septembre 2011

Un peu de fonctionel

Je me suis remis à Project Euler, et résolu quelques problèmes supplémentaires. Je continue à tenter d'apporter des solutions aussi fonctionnelles pures que possible, ce qui m'a amener à réfléchir à un crible d’Ératosthène fonctionnel pur. Jusqu'ici, j'utilisais les fonctionnalités impératives d'OCaml pour m'en tirer un avec un gros tableau de booléens, mais en fait, si l'on considère un set d'entiers pour les multiplies, il est facile de faire quelque chose de plutôt efficace. Je dois mettre un peu d'ordre dans mon code, et je le posterai ici.