Discussion :

[cvanaret]

Bonsoir,

j'ai codé un algo de SVM (http://fr.wikipedia.org/wiki/Machine...urs_de_support), dont l'entraînement requiert la résolution d'un problème quadratique.
De nombreux multiplicateurs de Lagrange étant nuls, on peut utiliser une structure de vecteur creux pour les représenter.

Seulement, les différentes structures de données implémentées en OCaml ne me satisfont pas. J'aimerais pouvoir :
- accéder efficacement au ième élément du vecteur.
- modifier le vecteur durant la résolution QP : passer à 0 un élément non nul, ou donner une valeur non-nulle à un élément nul.
- parcourir, éventuellement partiellement, les éléments (avec la possibilité de s'arrêter en route, pas comme un fold).

Une Hashtbl m'aurait paru appropriée s'il n'y avait pas eu le 3e point...
Des idées ?

[SpiceGuid]

Ça me fait penser à un arbre Patricia.
(sans oublier de lire le petit guide du bouturage qui donne plusieurs méthodes pour rendre mutable ton arbre Patricia)

parcourir, éventuellement partiellement, les éléments (avec la possibilité de s'arrêter en route, pas comme un fold)

Tu peux éventuellement quitter un fold (l'avorter, sans valeur de retour) à l'aide de l'exception Exit.
Sinon tu ne vas pas trouver ça tout-prêt à l'emploi.
Tu vas devoir implanter ton propre itérateur/récurseur qui progresse selon ton motif de parcours.

EDIT: Éventuellement la bibliothèque OCaml Batteries included contient une structure de données prête à ton emploi. Si gasche passe par ici il pourra t'en dire davantage à ce sujet. Sinon je t'invite à consulter la documentation.

[cvanaret]

Merci pour ta réponse !

Pour le moment, j'implémente mon vecteur creux avec 3 structures (un élément x du vecteur appartient à [0, C]) :
- une hashtable pour 0 < x < C
- un set pour = 0
- un set pour = C

J'ai déjà mesuré un gain en temps sur l'entraînement du SVM
Je vais regarder du côté des arbres Patricia.