Discussion :

[Jedai]

? Ca serait pas plutot l'affichage des sscm qui ralentit le test ?

Effectivement (bon j'avais redirigé vers /dev/null, mais même ainsi...) si je me contente de faire compter le nombre de sscm par ton code, alors tu descend à 130ms, contre 420ms pour ma fonction (d'un autre côté, ma fonction renvoie la liste de toutes les sscm, alors que du coup la tienne ne fait plus rien que compter, peut-être serait-il plus équitable de comparer avec une fonction en Java qui renvoie la liste de toutes les sscm ?)

[EDIT] Je descend à 180ms avec une fonction qui ne fait que compter :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
nsscm [] = 1
nsscm xs@(x:_) = sum . map (\(y:ys) -> nsscm $ filter (>y) ys) $ cs
    where 
      cs = snd . foldl' isStart (x,[xs]) . init . tails . tail $ xs
      isStart p@(mini,cs) c@(y:_) 
          | y < mini = (y,c:cs)
          | otherwise = p

--
Jedaï

[pseudocode]

peut-être serait-il plus équitable de comparer avec une fonction en Java qui renvoie la liste de toutes les sscm ?

En stockant les résultats dans un ArrayList, je passe de 141ms à 1250ms.

Cool, un facteur 10.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
static List<int[]> sscm = new ArrayList<int[]>();

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
(...)
	// la subseq ne grossit plus -> fini
	if (min==Integer.MAX_VALUE) {
		sscm.add(Arrays.copyOf(subseq, subseqlen));
	}
(...)

[hassanJava]

Bonjour,
D'abord je vous remercie beaucoup. vous etes formidable

L'algo que vous avez donné est très bien et marche en un complexité bien.


Merci encore.