Implémentation originale
Le blog https://wjmn.github.io/posts/j-can-look-like-apl.html propose une version "naïve" (selon l'auteur) de k-means :
init =. ([ ? #@:]) { ]
alloc =. {.@:I.@:(= <./)@:(+/@:*:@:-"1)
step =. (+/ % #)&>@:(alloc"1 2 </. [)
kmc =. ] step^:_ init
En ce qui me concerne, je ne suis pas assez compétent pour décider de la naïveté de cette implémentation. Toutefois, plusieurs choses me dérangent dans cette version :
- @: est utilisé partout, y compris quand ce n'est pas obligatoire
- ~ n'est pas utilisé quand il est utile
- même si ça fonctionne, il serait bon de simplifier la manière d'adresser le rang du verbe alloc
- Le verbe alloc est bizarrement implémenté.
Résultat, c'est lent et cette version est difficile a lire et comprendre.
Version améliorée
On commence par supprimer les parenthèses dans le verbe init :
init2 =: ]{~[?#@]
Cela se fait facilement en utilisant ~ .
Ensuite, le calcul de la distance euclidienne :
L'auteur propose (+/@:*:@:-"1) pour calculer la distance euclidienne. Une variante robuste au rang, que j'utilise par ailleurs, serait +/&.:*:@:-"1 .
Il y a un problème avec la sélection de l'indice du plus petit élément : on peut très bien faire comme l'auteur propose, mais il existe une forme dédiée en J. On remplace donc {.@:I.@:(= <./)@: par (i. <./)"1 .
Enfin, on arrange le berne step car il est écrit à l'envers (à mon sens). Je suspecte cette manière de l'écrire comme étant une des causes principale de ralentissement de la version de l'auteur.
Une fois nettoyé et réarrangée, ça donne :
init2 =: ]{~[?#@]
alloc2=: [: (i. <./)"1 +/&.:*:@:-"1 / ~
mean =: +/ % #
kmc2 =: init2 (alloc2 mean/. ])^:_ ]
Et en supplément une version one-liner :
kmc2OneLiner =: (]{~[?#@]) (([: (i. <./)"1 +/&.:*:@:-"1 / ~) (+/ % #)/. ])^:_ ]
Speed Test
On va comparer la vitesse d’exécution des différentes version (l'originale, ma version, et la version oneliner) sur un ensemble de 5000 points situés dans un espace à trois dimensions :
dt =: 5000 3 ?@$ 0
(,[:<"0[:(,:(%~{.))timex&>)'40 kmc dt';'40 kmc2 dt';'40 kmc2OneLiner dt
Ce qui donne :
Le gain de temps est notable!
Tout le code
NB. ---------------------------------------------------------
NB. implementation from https://wjmn.github.io/posts/j-can-look-like-apl.html
NB. ---------------------------------------------------------
init =. ([ ? #@:]) { ]
alloc =. {.@:I.@:(= <./)@:(+/@:*:@:-"1)
step =. (+/ % #)&>@:(alloc"1 2 </. [)
kmc =. ] step^:_ init
NB. ---------------------------------------------------------
NB. faster version
NB. ---------------------------------------------------------
init2 =: ]{~[?#@]
alloc2=: [: (i. <./)"1 +/&.:*:@:-"1 / ~
mean =: +/ % #
kmc2 =: init2 (alloc2 mean/. ])^:_ ]
kmc2OneLiner =: (]{~[?#@]) (([: (i. <./)"1 +/&.:*:@:-"1 / ~) (+/ % #)/. ])^:_ ]
NB. ---------------------------------------------------------
NB. speed test
NB. ---------------------------------------------------------
dt =: 500 3 ?@$ 0
(,[:<"0[:(,:(%~{.))timex&>)'40 kmc dt';'40 kmc2 dt';'40 kmc2OneLiner dt'
NB. Line1 : what is executed, line2 : execution speed, line3 : xtimes faster than first column
NB. ┌─────────┬──────────┬──────────────────┐
NB. │40 kmc dt│40 kmc2 dt│40 kmc2OneLiner dt│
NB. ├─────────┼──────────┼──────────────────┤
NB. │32.2017 │0.803435 │0.701243 │
NB. ├─────────┼──────────┼──────────────────┤
NB. │1 │40.08 │45.9208 │
NB. └─────────┴──────────┴──────────────────┘
Commentaires
Enregistrer un commentaire