IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Toutes les sous-séquences croissantes et maximales d'une séquence des entiers


Sujet :

Algorithmes et structures de données

  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2008
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2008
    Messages : 61
    Par défaut Toutes les sous-séquences croissantes et maximales d'une séquence des entiers
    Bonjour,
    Je suis en trains de développer une application et pour une partie de ca j'ai besoin de trouver toutes les sous-séquences croissantes d'une séquence des entiers qui sont aux-même maximales .

    Je m'explique:

    Imaginons la séquences des entiers S={1,5,6,9,2,3,4,7,8}
    une sous-séquence croissantes est une sous-séquences de S dont les items sont dans l'ordre croissantes. Une sous-séquence est maximale si elle n'est pas la sous-séquence des autres sous-séquences.

    Par ex :
    S1={1,5,6,9} ou S2={1,5,6,7,8} sont sous-sequences croissantes et maximales de S. Mais S3={1,5,6,2} n'est pas croissante ou la sous-sequence S4={6,7,8} n'est pas maximale comme il y a une autre sous-sequence S5={1,5,6,7,8} qui contiens S4.

    Alors le problématique est de chercher toutes les sous-séquences croissantes et maximales de S.

    A dire qu'il y a pleins de travailles sur "LIS" (Longest Increasing Subsequence) (la sous-sequence croissante la plus longue) même des algos avec complexité O(n log n) mais j'ai pas trouvé une solution qui rend toutes les sous-sequences croissantes et maximales de n'importe quelle tille.

    Par exemple sur seq S, j'aimrais de trouver les sous-séquences croissantes et maximales ci-dessous :
    {1,5,6,9} {1,5,6,7,8} {1,2,3,4,7,8}
    je remarque que c'est possible d'avoir plusieurs sous-sequences croissantes maximales exactement de la même taille. donc on s'intéresser d'avoir toutes pas juste une parmi toutes.

    Je vous remercie bien de fournir un pesudo code si vous donner un algo pour mieux faire inspirer le structure de données utilisé.

    En vous remerciant j'attends vos réponses.

  2. #2
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Bonjour,

    à part une recherche exhaustive, je n'ai pas d'idée...
    Ca peut paraître très lourd, mais on peut largement élagué les branches de l'arbre de recherche :
    - il faut essayer de commencer avec tous les éléments de la liste (ça c'est lourd), mais dès qu'un chiffre est utilisé dans une liste solution, on sait qu'il ne faut plus démarrer par lui car toutes les listes qu'il engendrerait ne serait pas maximales. Ce qui réduit considérablement les possibilités.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  3. #3
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    on peut aussi construire les listes en partant de la fin.

    Le dernier element Z d'une liste maximale est tel qu'il n'y a pas d'element supérieur à Z dans le reste de S.


    1. On cherche les elements Z qui peuvent être les derniers elements d'une liste maximale:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    S = 1,5,6,9,2,3,4,7,8
              ^         ^
    => Les listes maximales de L finissent par Z=9 ou Z=8

    2. Split récursif: on a 2 cas à traiter. Les listes qui finissent par 9, et celles qui finissent par 8.

    Pour chaque cas, on réduit S aux choix possibles = la liste des éléments de S precedents Z et dont la valeur est inferieure à Z.

    cas "Z=9": --> S = 1,5,6
    cas "Z=8": --> S = 1,5,6,2,3,4,7

    3. retour à l'étape 1, pour chaque Z.


    En esperant ne pas avoir dit trop de bétises.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Expert confirmé Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Par défaut
    Bonjour,

    Etape 1 : Après avoir inséré en début de liste un nombre égal au minimum absolu (exemple : -2**31), on stoke pour chaque nombre de la liste tous les nombres situés derrière et supérieurs à ce nombre.

    Etape 2 : en démarrant du premier élément (le minimum absolu), parcourir toutes les possibiltés de chainages en allant jusqu'au dernier élément sans chainage.

  5. #5
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Une petite implémentation de l'idée de Pseudocode (sauf que moi je part du début, quelle drôle d'idée de vouloir partir de la fin !) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    import Data.List
     
    sscm [] = [[]]
    sscm xs@(x:_) = concatMap (\(y:ys) -> map (y:) $ sscm $ 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
    Et l'idée de Graffito n'est pas tout à fait correcte (à priori sans la phase d'élimination de candidats proposé par Pseudocode, on tombe sur des sous-séquences non maximales).

    Une solution en partant de la fin, comme proposé par Pseudocode (avec partage des queues de liste, on pourrait faire pareil en partant du début) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    sscmR [] t = [t]
    sscmR rxs@(x:xs) t = concatMap (\(y:ys) -> sscmR (filter (<=y) ys) (y:t)) cs
        where
          cs = snd . foldl' isEnd (x,[rxs]) . init . tails $ xs
          isEnd p@(maxi,cs) c@(y:_) 
              | y > maxi = (y,c:cs)
              | otherwise = p
     
    sscm' xs = sscmR (reverse xs) []
    --
    Jedaï

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Jedai Voir le message
    (sauf que moi je part du début, quelle drôle d'idée de vouloir partir de la fin !)
    C'est parce que je suis un rebelle.

    Et sinon, je suppose que ça marche ? (sinon tu m'aurais lynché)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    C'est parce que je suis un rebelle.

    Et sinon, je suppose que ça marche ? (sinon tu m'aurais lynché)
    Ca marche très bien, tu as eu l'intuition décisive avec ton histoire de "dernier élément" (ou premier, comme on veut).

    Il n'est pas exclu qu'il y ait mieux toutefois.

    --
    Jedaï

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    c'est parceque j'ai enfin fait le tuto Haskell. Je commence à penser en fonctionnel. Arg! Ca fait 2 réponses de suite que j'ai pensé en fonctionnel !

    Heureusement je code encore en Java.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Expert confirmé Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Par défaut
    Et l'idée de Graffito n'est pas tout à fait correcte (à priori sans la phase d'élimination de candidats proposé par Pseudocode, on tombe sur des sous-séquences non maximales).
    Exact, il faut effectivement ajouter une contrainte dans l'étape 1 recherche des "suivants", à savoir qu'une fois qu'un suivant a été trouvé, tous les candidats situés derrière ce suivant dans une séquence croissante ne doivent pas être retenus.

  10. #10
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 78
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    Ce truc me parait simple à comprendre.
    Question perfs je ne sais pas ce que ça vaut.
    Je compte sur Jedai pour nous le dire bientôt.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    # -*- coding: cp1252 -*-
     
    S=[1,5,6,9,2,3,4,7,8]
     
    # sous suite de S correspondant à une suite binaire 1 on prend 0 on laisse
    def sequ(L):
        return [S[i] for i in range(0,len(S)) if L[i]!=0]
     
    #teste si deux suites binaires sont incluses l'une dans l'autre
    def incluse (L1,L2):
        if L1==[] and L2==[]:
            return True
        if L1[0]>L2[0]:
            return False
        else:
            return incluse (L1[1:],L2[1:])
     
    #teste si suite croissante
    def croissante (S1):
        if len(S1)<=1:
            return True
        if S1[0]>S1[1]:
            return False
        else:
            return croissante(S1[1:])
     
    # retourne les suites  de n éléments de F
    def puissance(n,F):
        G=[[x] for x in F]
        for i in range (0,n-1):
            G= [y+[x] for y in G for x in F]
        return G
     
    #élimine les éléments non maximaux
    def traite (Poss):
        if Poss==[]:
            return Poss
        else:
            Q=Poss[1:]
        for L in Q:
            if incluse(Poss[0],L):
                return traite(Q)
        return [Poss[0]]+traite(Q)
     
    #fonction principale
    def main():
        R=puissance(len(S),[0,1])
        G=[L for L in R if croissante(sequ(L))]
        print [sequ(L) for L in traite(G)]
     
    if __name__ == '__main__':
        main()
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  11. #11
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Citation Envoyé par Zavonen Voir le message
    Ce truc me parait simple à comprendre.
    Question perfs je ne sais pas ce que ça vaut.
    Je compte sur Jedai pour nous le dire bientôt.
    Ce truc est simple à comprendre et évidemment extrêmement mauvais... Par acquis de conscience j'ai essayé, mais même sur la séquence de départ x 5 il peine à mort. Bien sûr, j'avais abandonné tout espoir à partir du moment où j'ai vu que tu calculais l'ensemble des listes de 0 ou 1 de la taille de la séquence de départ...
    Ta méthode procède par génération et filtrage, mais vu que la génération est purement exponentielle, les performances ne peuvent pas être bonnes. Il faut entremêler génération et filtrage afin d'éliminer des sous-arbres complets de possibilités, sinon l'algo est en O(2^n), ingérable.

    Ton programme devient très lent dès 17 éléments dans la séquence et absolument inutilisable un peu après la vingtaine alors que ma fonction sscm' en Haskell reste utilisable avec des centaines d'éléments (200 éléments au hasard dans [-10000,10000], 9_470_532 sous-séquences trouvés, 12s (rien que ton traite() en O(n^2) prendrait des heures pour vérifier ça). Pour les séquences de 140 éléments ou moins, le temps de calcul reste en dessous de la seconde (0.5s de moyenne sur ma machine) ).

    Je ne sais pas si on peut faire beaucoup mieux que la proposition de Pseudocode, mais au moins elle apparaît relativement efficace pour une classe de problême de taille raisonnable.

    (EDIT : En fait, en supposant que ton incluse prenne une microseconde, le traite() sur 9_470_532 sous-séquences maximales prendrait environ 1 an et demi...)
    --
    Jedaï

  12. #12
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 78
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    Ce truc est simple à comprendre et évidemment extrêmement mauvais...
    Je ne suis pas surpris, mon algo est naïf, c'est pourquoi il est simple à comprendre.
    En voici un autre, à mon avis encore très lisible et qui à l'air de carburer un peu plus:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    # -*- coding: cp1252 -*-
     
    S=[1,5,6,9,2,3,4,7,8]*5
     
    # liste des indices correspondant à des éléments plus grands que l'élément d'indice i
    def After(i):
        return [j for j in range(i,len(S)) if S[j]>S[i]]
     
    # teste si on ne peut rien intercaler entre les éléments d'indices k et i
    def JustAfter(k,i):
        for j in range (k+1,i+1):
            if S[k]<S[j]<S[i]:
                return False
        return True
     
    # tous les indices des éléments pouvant suivre l'élément d'indice i dans une suite croissante maximale
    def CanFollow(i):
        L=After(i)
        return [k for k in L if JustAfter(i,k)]
     
    # teste si l'élément d'indice i peut commencer une suite maximale
    def CanBegin(i):
        for j in range (0,i):
            if S[j]<S[i]:
                return False
        return True
     
    # Toutes les suites maximales commençant par l'indice i (sous forme d'indices)
    def Beg(i):
        L=CanFollow(i)
        if L==[]:
            return [[i]]
        else:
            T=[]
            for j in L:
                T=T+Beg(j)
            return [[i]+ x for x in T]
     
    # Toutes les suites maximales sous forme de suites d'indices
    def All():
        R=[]
        for i in range(0,len(S)):
            if CanBegin(i):
                R+=Beg(i)
        return R
     
    # transforme les indices en éléments de S
    def desindexe(L):
        return [S[i] for i in L]
     
    # Toutes les solutions
    def Solutions():
        return [desindexe(L) for L in All()]
     
     
    def main():
        print Solutions()
     
    if __name__ == '__main__':
        main()
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  13. #13
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2008
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2008
    Messages : 61
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    on peut aussi construire les listes en partant de la fin.

    Le dernier element Z d'une liste maximale est tel qu'il n'y a pas d'element supérieur à Z dans le reste de S.


    1. On cherche les elements Z qui peuvent être les derniers elements d'une liste maximale:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    S = 1,5,6,9,2,3,4,7,8
              ^         ^
    => Les listes maximales de L finissent par Z=9 ou Z=8
    En fait j'ai pas compris comment on peut determiner que les sous-seq maximales d'une seq finissent par quoi? Si j'ai bien compris tu veut dire qu'elle finissent soit par le dernier entier de la seq soit par l'entier le plus grand dans la seq. si c'est le cas, c'est pas tout à fait juste.
    Par ex. S={1,5,6,9,2,3,7,8,4}
    la, les sous-seq maximales finissent par le 4 ou le 8 ou le 9....

    merci d'expliquer.


    En plsu j'ai une question peut-etre un êut bête. mais qu'est-ce qu c'est le meilleur implementation d'un arbre n-aire sous java vu la performance surtout quand on parcours l'arbre plusieurs fois.

    Merci de tous.

  14. #14
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Citation Envoyé par hassanJava Voir le message
    En fait j'ai pas compris comment on peut determiner que les sous-seq maximales d'une seq finissent par quoi? Si j'ai bien compris tu veut dire qu'elle finissent soit par le dernier entier de la seq soit par l'entier le plus grand dans la seq.
    Non c'est pas ce qu'il dit : il dit que les sous-seq maximales ne peuvent se finir que par un nombre plus grand que tous ceux qui le suivent dans la séquence (sinon on pourrait rajouter ce nombre à la sous-séquence croissante, qui ne serait donc pas maximale), ça correspond bien à 4, 8 et 9 dans ton exemple.

    Bon alors ma version finale, j'ai pris comme définition d'une séquence croissante une séquence S tel que si i et j sont des indices, i < j => S(i) < S(j). (strictement croissante pourrait-on dire)
    Par ailleurs pour l'inclusion, je ne prend en compte que les indices, pas les valeurs, autrement dit je peux renvoyer plusieurs fois la même sous-séquence si elle est présente à plusieurs endroits dans la séquence d'origine.

    Ca me donne :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    sscmR :: (Ord a) => [a] -> [a] -> [[a]]
    sscmR [] t = [t]
    sscmR rxs@(x:xs) t = concatMap (\(y:ys) -> sscmR (filter (<y) ys) (y:t)) cs
        where
          cs = snd . foldl' isEnd (x,[rxs]) . init . tails $ xs
          isEnd p@(maxi,cs) c@(y:_) 
              | y >= maxi = (y,c:cs)
              | otherwise = p
     
    sscm :: (Ord a) => [a] -> [[a]]
    sscm xs = sscmR (reverse xs) []
    La solution de Zavonen a la même sémantique et est infiniment meilleure que sa première proposition mais fait beaucoup trop de vérifications inutiles (par exemple le JustAfter() vérifie trop d'indices, il ne devrait vérifier que ceux dans le After(), de plus il y a pas mal de travail gaché par rapport à mon fold qui transporte le "maximum jusqu'ici"), au final pour S=[1,5,6,9,2,3,4,7,8,10]*14 elle met 37s, là où ma solution met 0,5s.

    --
    Jedaï

  15. #15
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par hassanJava Voir le message
    merci d'expliquer.
    Le dernier élement d'une sous-seq MAXIMALE est tel qu'il n'y a pas d'élement plus grands après lui dans S. Sinon, la sous-seq ne serait pas maximale car on pourrait y ajouter un element au bout.

    Donc, pour savoir si un élement de S sera le dernier élement d'une sous-seq maximale, il suffit de regarder s'il y en a d'autres plus grands que lui dans la fin de S.

    S={1,5,6,9,2,3,7,8,4}

    1 --> après il y a 5,6,9,7,8 => pas un dernier element
    5 --> après il y a 6,9,7,8 => pas un dernier element
    6 --> après il y a 9,7,8 => pas un dernier element
    9 --> pas d'element plus grands dans le reste de S => c'est un dernier element
    (...)
    7 --> après il y a 8 => pas un dernier element
    8 --> pas d'element plus grands dans le reste de S => c'est un dernier element
    4 --> pas d'element plus grands dans le reste de S => c'est un dernier element

    => les sous-seq maximales finissent par 9, 8 et 4
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #16
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2008
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2008
    Messages : 61
    Par défaut
    Je vous remercie beaucoup pour les réponses rapides.

    En fait comme chercher des sous-seq il fait partie d'un projet de clustering et je l'ai developpé jusqu'à la sous Java, je ne peut donc pas switch sous haskell bien que je le sais pas bien.

    alors j'ai mal pour implementer vos idées sous java. En fait comme la performance est l'un des prioritaire dans ce projet alors je ne peut pas le faire avec n'importe quelle structure de code et de données.

    Je ne sais pas comment faire pour le meilleur performance sous java surtout comment à la fin récuperer les sous-seq trouvées.

    Merci encore.

  17. #17
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    A priori, si tu veux essayer de copier ma solution en Java, il faut que tu utilises des LinkedList. Ce ne sera pas parfait (Linked-List est doublement lié, de plus il faudra que tu fasses des clone() puis addFirst() là où je me contente de faire des cons,etc), mais ce sera assez proche.

    Peut-être y aurait-il une façon plus propre de le faire en Java, qui est après tout un langage très différent de Haskell, qu'en pense notre expert Java local Pseudocode ?

    --
    Jedaï

  18. #18
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Peut-être y aurait-il une façon plus propre de le faire en Java, qui est après tout un langage très différent de Haskell, qu'en pense notre expert Java local Pseudocode ?
    Tiens, j'ai un nouveau titre.

    Bon, alors en Java, j'ai la sale habitude de remplir des piles par récursion. Comme ca je gère ma pile (les subseq) et je laisse le compilateur gerer la sienne (les parcours des sous listes)

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
     
    /**
     * @param S La liste de référence
     * @param start Offset de départ dans la liste de référence
     * @param subseq La SubSeq maximale en cours de remplissage 
     * @param subseqlen La taille actuelle de la SubSeq maximale
     */
    static void findSubSeq(int[] S, int start, int[] subseq, int subseqlen) {
     
    	int min=Integer.MAX_VALUE;
    	for(int i=start;i<S.length;i++) {
     
    		// ignore les elements qui ne forment pas une subseq strictement croissante
    		if (subseqlen>0 && S[i]<=subseq[subseqlen-1]) continue;
     
    		// detection d'un element minimal
    		if (S[i]<min) {
    			min=S[i];
     
    			// empilement dans la subseq
    			subseq[subseqlen++]=S[i];
     
    			// traitement de la liste restante
    			findSubSeq(S,i+1,subseq,subseqlen);
     
    			// depilement de la subseq
    			subseqlen--;
    		}
     
    	}
     
    	// la subseq ne grossit plus -> fini : on affiche
    	if (min==Integer.MAX_VALUE) {
    		for(int i=0;i<subseqlen;i++)
    			System.out.print(subseq[i]+" ");
    		System.out.print("\n");
    	}
     
    }
     
    public static void main(String[] args) {
    	int[] S = new int[] {1,5,6,9,2,3,4,7,8}; 
     
    	long t0 = System.currentTimeMillis();
    	findSubSeq(S,0,new int[S.length],0);
    	long t1 = System.currentTimeMillis();
     
    	System.out.println("duration: "+(t1-t0)+"ms");
    }

    On peut alléger la récursion en transformant les variables locales de la méthode en variables de classe/instance. Cet exercice est laissé au lecteur.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  19. #19
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Tu as une petite erreur de sémantique (que j'avais également dans ma première version), à cette ligne :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    // detection d'un element minimal
                    if (S[i]<min) {
    Ceci devrait plutôt être :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    // detection d'un element minimal
                    if (S[i]<=min) {
    en accord avec ta proposition.
    En effet, si tu n'agis pas ainsi, tu manque potentiellement un certain nombre de sscm (j'en ai marre de dire sous-séquence croissante maximale). Du moins du point de vue des indices... Si le posteur initial pouvait nous éclairer sur son besoin ?

    En tout cas, je ne sais pas pourquoi exactement, mais ta solution est moins rapide que ma fonction Haskell, mettant dans les 13s pour 140 éléments. En fait, j'ai une idée, c'est parce que tu ne filtres pas comme moi les éléments trop petits pour être inclus dans la sous-séquence en construction, tu retestes tous les éléments de la séquence.

    --
    Jedaï

  20. #20
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Jedai Voir le message
    En effet, si tu n'agis pas ainsi, tu manque potentiellement un certain nombre de sscm (j'en ai marre de dire sous-séquence croissante maximale). Du moins du point de vue des indices... Si le posteur initial pouvait nous éclairer sur son besoin ?
    Effectivement, ca dépend si le PO veut des sscm distinctes par "valeur" ou par "indice".

    En tout cas, je ne sais pas pourquoi exactement, mais ta solution est moins rapide que ma fonction Haskell, mettant dans les 13s pour 140 éléments.
    ? Ca serait pas plutot l'affichage des sscm qui ralentit le test ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Lister toutes les sous-classes d'un classe mère
    Par Kerod dans le forum Langage
    Réponses: 10
    Dernier message: 09/02/2009, 19h21
  2. Réponses: 2
    Dernier message: 22/04/2008, 13h45
  3. Réponses: 10
    Dernier message: 10/12/2006, 16h26
  4. [MS-DOS] Supprimer tout les sous répertoires contenu dans un
    Par Furius dans le forum Scripts/Batch
    Réponses: 7
    Dernier message: 30/11/2005, 12h24

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo