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

Défis langages fonctionnels Discussion :

Défi N°6 : Les palindromes


Sujet :

Défis langages fonctionnels

  1. #1
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut Défi N°6 : Les palindromes
    Bonjour,

    Pour ce sixième défi proposé par SpiceGuid, l'équipe de developpez.com vous propose un challenge assez court qui peut laisser place à l'optimisation.

    Challenge :



    Il s'agit d'écrire une fonction (s: string) → string qui renvoie un palindrome p tel que:
    • s contient p
    • s ne contient aucun palindrome qui soit strictement plus long que p


    On rappelle qu'un palindrome est une chaîne de caractère dont l'ordre de lettre est identique, selon que la lise par la gauche ou par la droite.
    Formellement, une chaîne s est un palindrome si et seulement si :
    Pour tout i de 0 à taille(s)-1, s[i] = s[taille(s)-1-i]

    Les règles

    Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :
    • la maintenabilité
    • la simplicité
    • le fait qu'il soit optimisé


    Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.

    Pour répondre, il vous suffit de poster à la suite.

    A vos claviers
    de votre participation.

    __________________________
    Sujet proposé par SpiceGuid
    Je ne répondrai à aucune question technique en privé

  2. #2
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    J'avais une petite solution en Haskell, qui utilise un zipper de liste. Je me suis concocté mon propre zipper mais on peut aussi trouver des implémentations sur Hackage :
    MyListZipper.hs :
    Code Haskell : 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
    module MyListZipper (LZ(), toZipper
                        , forward, backward
                        , (<|), (|>)
                        , start, end
                        , next, prev) where
     
    data LZ a = LZ [a] [a]
     
    toZipper xs = LZ [] xs
     
    forward, backward :: LZ a -> LZ a
    forward z@(LZ xs []) = z
    forward (LZ xs (y:ys)) = LZ (y:xs) ys
    backward z@(LZ [] ys) = z
    backward (LZ (x:xs) ys) = LZ xs (x:ys)
     
    (<|) :: a -> LZ a -> LZ a
    y <| (LZ xs ys) = LZ xs (y:ys)
    (|>) :: LZ a -> a -> LZ a
    (LZ xs ys) |> x = LZ (x:xs) ys
     
    start, end :: LZ a -> Bool
    start (LZ xs _) = null xs
    end (LZ _ ys) = null ys
     
    next, prev :: LZ a -> (a, LZ a)
    next (LZ xs (y:ys)) = (y, LZ xs ys)
    prev (LZ (x:xs) ys) = (x, LZ xs ys)

    Et le code principal :
    Code Haskell : 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
    module Main () where
    import Data.List
    import Control.Arrow
    import MyListZipper
     
    data Pal a = Pal [a] [a]
     
    expand (Pal beg seed) = beg ++ seed ++ reverse beg
     
    grow :: (Eq a) => Pal a -> LZ a -> Pal a
    grow pal@(Pal beg seed) z 
        | start z || end z || p /= n = pal
        | otherwise                  = grow (Pal (p:beg) seed) z'
        where (p, temp) = prev z
              (n, z')   = next temp
     
    seeds :: (Eq a) => [a] -> [(Pal a, LZ a)]
    seeds = zSeeds . toZipper 
     
    zSeeds :: (Eq a) => LZ a -> [(Pal a, LZ a)]
    zSeeds z | end z     = []
             | otherwise = (pal, z') : zSeeds z''
             where
               (n, temp)      = next z
               (pal, z', z'') = findSeed [n] temp (forward z)
     
    findSeed :: (Eq a) => [a] -> LZ a -> LZ a -> (Pal a, LZ a, LZ a)
    findSeed s@(x:_) z w
        | end z || n /= x  = (Pal [] s, z, w)
        | otherwise        = findSeed (n:s) z' (forward w)
        where (n, z') = next z
     
    longest = foldl' max (0,"") . map ((length &&& id) . expand . uncurry grow) . seeds
     
    main = print . longest =<< getContents

    L'idée est simple : on commence par isoler les séquences de lettres identiques dans s, puis on essaie de faire "grossir" ces séquences par les deux côtés tant que cela reste un palindrome, enfin on récupère le palindrome le plus long.

    --
    Jedaï

  3. #3
    Expert éminent
    Avatar de djo.mos
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    4 666
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2004
    Messages : 4 666
    Points : 7 679
    Points
    7 679
    Par défaut
    Salut,
    Une solution impérative (code en Java) :
    L'idée est parcourir les lettres de la chaine, en recherchant la lettre courante dans le reste de la chaine. Si on en trouve, on teste si la sous-chaine qui commence à la lettre courante jusqu'à la lettre trouvée est palindrome.

    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
    package defi6;
     
    public class Defi6 {
     
    	private boolean isPalindrome(char[] a, int i, int j) {
    		int l = j - i;
    		for (int x = i; x <= i + l / 2; x++) {
    			if (a[x] != a[j - (x - i)]) {
    				return false;
    			}
    		}
    		return true;
    	}
     
    	private String extractPalyndrome(String s) {
    		char[] a = s.toCharArray();
    		String candidate = null;
    		for (int i = 0; i < a.length; i++) {
    			for (int j = i; j < a.length; j++) {
    				if (a[j] == a[i] && isPalindrome(a, i, j)) {
    					String pal = s.substring(i, j + 1);
    					if (candidate == null
    							|| pal.length() > candidate.length()) {
    						candidate = pal;
    					}
    				}
    			}
    		}
    		return candidate;
    	}
     
    	public static void main(String[] args) {
    		System.out.println(new Defi6().extractPalyndrome("abbbccacc"));
    	}
     
    }

  4. #4
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 58
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Points : 5 753
    Points
    5 753
    Par défaut
    J'espère avoir bien compris qu'il faut réaliser une fonction qui retourne le plus long palindrome d'une chaine de caractère.

    La fonction est réalisée en perl, et est basée sur les expressions régulières :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    sub palindrome {
      return [sort { length $b <=> length $a } $_[0] =~ /((.+).?(??{ reverse "$2" }))/gx]->[0];
    }
    Exemple d'utilisation en uniligne :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    $ perl -e '$aa = "tooiuertreuioot toot azertyuioppoiuytreza";sub palindrome { return [sort { length $b <=> length $a } $aa =~ /((.+
    ).?(??{ reverse "$2" }))/gx]->[0] } print palindrome($aa)'
    Attention cependant, l'opérateur (??{ ... }) des expressions régulières de perl est considéré comme expérimental (version 5.10), mais il est diablement efficace ici.
    L'extraction des palindromes est réalisée grâce à la regexp :
    /((.+).?(??{ reverse "$2" }))/gx
    à savoir un certain nombre de caractère (le plus possible), suivi éventuellement d'un caractère quelconque, suivi de la première partie déjà trouvée, mais à l'envers.
    On extrait de cet expression deux chaines : le palindrome et la première partie du palindrome. La palindrome est toujours plus long que la première partie.
    Ensuite, on trie le résultat par longue décroissante, et on prends le premier élément de cette liste.
    Plus j'apprends, et plus je mesure mon ignorance (philou67430)
    Toute technologie suffisamment avancée est indiscernable d'un script Perl (Llama book)
    Partagez vos problèmes pour que l'on partage ensemble nos solutions : je ne réponds pas aux questions techniques par message privé
    Si c'est utile, say

  5. #5
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    La solution que j'ai donné en premier lieu a une très bonne complexité/efficacité, mais ce n'est évidemment pas le plus simple qu'on puisse faire en Haskell, dans la même optique que la solution Perl, on peut avoir :
    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    isPalindrome s = s == reverse s
    allSubstrings = concatMap (init . tails) . inits
    longest = maximumBy (comparing length) . filter isPalindrome . allSubstrings

    Complexité absolument horrible bien sûr... (ça reste plus rapide que la solution Perl, même en interprété)
    La solution de djo.mos est meilleure de ce point de vue mais tout de même plus complexe que ma première solution Haskell.

    --
    Jedaï

  6. #6
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 58
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Points : 5 753
    Points
    5 753
    Par défaut
    Sauf erreur, Jedaï, je crois que ta fonction isPalindrome ne récupère pas les palindromes de taille impaire.
    Plus j'apprends, et plus je mesure mon ignorance (philou67430)
    Toute technologie suffisamment avancée est indiscernable d'un script Perl (Llama book)
    Partagez vos problèmes pour que l'on partage ensemble nos solutions : je ne réponds pas aux questions techniques par message privé
    Si c'est utile, say

  7. #7
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par Philou67430 Voir le message
    Sauf erreur, Jedaï, je crois que ta fonction isPalindrome ne récupère pas les palindromes de taille impaire.
    Je vois mal comment ce serait possible : en effet ma fonction est une traduction directe de la définition "un palindrome se lit identiquement dans un sens ou dans l'autre"... Peux-tu m'expliquer pourquoi tu croyais cela ?
    En fait dans ce second code, j'ai favorisé à fond la lisibilité et la simplicité du code, il n'y a aucune astuce, la fonction finale :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    longest = maximumBy (comparing length) . filter isPalindrome . allSubstrings
    dit exactement ce qu'elle fait : faire une liste de toutes les sous-chaînes, filtrer celle qui sont des palindromes et récupérer le palindrome de longueur maximale parmi ceux-ci.

    --
    Jedaï

  8. #8
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 58
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Points : 5 753
    Points
    5 753
    Par défaut
    Parce que j'ai mal lu le code
    Plus j'apprends, et plus je mesure mon ignorance (philou67430)
    Toute technologie suffisamment avancée est indiscernable d'un script Perl (Llama book)
    Partagez vos problèmes pour que l'on partage ensemble nos solutions : je ne réponds pas aux questions techniques par message privé
    Si c'est utile, say

  9. #9
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    Une solution identique à ma première mais sur un type de donnée différent, spécifiquement sur une chaîne de caractère disposant d'un accès aléatoire en O(1) (String en Haskell est un synonyme pour [Char] autrement dit une simple liste chaînée de caractères) :
    Code Haskell : 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
    module Main () where
    import Data.List
    import Data.Ord
    import Data.ByteString.Char8 hiding (map)
    import qualified Data.ByteString.Char8 as B
     
    data Pal = P !Int !Int deriving (Show)
     
    expand :: ByteString -> Pal -> ByteString
    expand bs (P start end) = fst . B.splitAt (end - start) . snd . B.splitAt start $ bs
     
    grow :: ByteString -> Pal -> Pal
    grow bs p@(P start end)
        | start == 0 
          || end == B.length bs
          || bs `index` (start-1) /= bs `index` end = p 
        | otherwise                                 = grow bs (P (start - 1) (end + 1))
     
    seeds :: ByteString -> [Pal]
    seeds bs | B.null bs = []
             | otherwise = go (B.head bs) 0 1
        where
          go c start end 
              | end == B.length bs = [P start end]
              | c == nextChar      = go c start (end + 1)
              | otherwise          = P start end : go nextChar end (end + 1)
              where nextChar = bs `index` end
     
    longest :: ByteString -> ByteString
    longest bs = expand bs . maximumBy (comparing lengthPal) . map (grow bs) . seeds $ bs
        where lengthPal (P s e) = e - s
     
    main :: IO ()
    main = print . longest =<< B.getContents

    Cette solution reste complètement fonctionnelle : il n'y a pas le moindre soupçon de mutation ou de code impur dans le tas, simplement il utilise un tableau fonctionnel (immutable) à la place d'une liste chaînée.

    Je doute qu'on fasse beaucoup mieux que ce code par la suite (du point de vue rapidité).

    --
    Jedaï

  10. #10
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    Il est intéressant de noter qu'encore une fois les critères algorithmiques priment sur la question du langage ou de l'efficacité de la structure de donnée choisie : sur un fichier de taille raisonnable (1,5 Mo, un dictionnaire des mots français), ma première version mettait 0.6s environ et ma troisième 0.06s... Je ne sais pas combien de temps mettent les versions Perl et Java : je les ai arrêté après 3/4 d'heure d'exécution !

    La différence tient simplement à la complexité : mes versions 1 et 3 sont en O(np) où p est la longueur du plus grand palindrome), la version Perl est en O(n²) et la version Java également, bien que chacune ait une petite optimisation par rapport à ma version 2 (en O(n²p) pur jus).

    --
    Jedaï

  11. #11
    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 : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Une version impérative (java que j'ai essayé de faire ressemble a du C). Le principe est basé sur l'aspect "miroir" des palindromes: pour chaque caractère de la chaine, on explore simultanément a gauche + a droite jusqu'a rencontrer une différence.

    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
    public class Palindrome {
     
    	private int palindromeLength,palindromeStart;
     
    	private void explore(char[] s, int length, int start) {
    		for(int i=0,j=0;j<=1;j++) {
    			for(i=1;(start - i + j)>=0 && (start + i)<length;i++)
    				if (s[start - i + j] != s[start + i]) break;
    			int plen=1+2*(i-1)-j;
    			if (plen>palindromeLength) {
    				palindromeLength=plen;
    				palindromeStart=start-i+1+j;
    			}
    		}
    	}
     
    	public String getLongestPalindrom(char[] s) {
    		palindromeStart=0;
    		palindromeLength=0;
    		for(int i=0;i<s.length;i++)
    			explore(s,s.length,i);
    		return new String(s,palindromeStart,palindromeLength);
    	}
    }


    EDIT (jeudi à 14h00): Une réecriture de l'algo ci-dessus dans une seule fonction pour avoir une meilleure "maintenabilité" et "simplicité" comme demandé dans l'énoncé. Vive les commentaires.

    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
    String getLongestPalindrom(char[] s, int length) {
    	// pointeurs sur le meilleur palindrome trouvé
    	int palindromeStart=0,palindromeLength=0;
    	// pointeurs gauche/droite sur les caractères
    	int left,right;
    	// pour chaque caractère de la chaine
    	for(int i=0;i<length;i++) {
    		// 1. exploration miroir par rapport a un caractère central
    		for(left=i-1,right=i+1;left>=0 && right<length;left--,right++)
    			if (s[left] != s[right]) break;
    		// sauvegarde du meilleur palindrome
    		if (right-left-1>palindromeLength) {
    			palindromeLength=right-left-1;
    			palindromeStart=left+1;
    		}
    		// 2. exploration miroir par rapport a un axe central
    		for(left=i,right=i+1;left>=0 && right<length;left--,right++)
    			if (s[left] != s[right]) break;
    		// sauvegarde du meilleur palindrome
    		if (right-left-1>palindromeLength) {
    			palindromeLength=right-left-1;
    			palindromeStart=left+1;
    		}
    	}
    	// retourne une copie du meilleur palindrome trouvé
    	return new String(s,palindromeStart,palindromeLength);
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  12. #12
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Une version impérative (java que j'ai essayé de faire ressemble a du C). Le principe est basé sur l'aspect "miroir" des palindromes: pour chaque caractère de la chaine, on explore simultanément a gauche + a droite jusqu'a rencontrer une différence.
    Tu utilise le même algorithme que moi, et ça marche pas mal : sur le fichier /usr/share/dict/words, ton programme mets 0.06s comme ma seconde version (et renvoie la même chose, heureusement).

    --
    Jedaï

  13. #13
    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 : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Tu utilise le même algorithme que moi
    heu... oui. Si tu le dis, je veux bien te croire, vu mon incompétence a déchiffrer du haskell.

    PS: le worst-case pour cet algo c'est lorsqu'on a des grandes séquences de lettres identiques. Cela peut se régler en faisant une première passe pour "compresser" les sequences.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #14
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    heu... oui. Si tu le dis, je veux bien te croire, vu mon incompétence a déchiffrer du haskell.

    PS: le worst-case pour cet algo c'est lorsqu'on a des grandes séquences de lettres identiques. Cela peut se régler en faisant une première passe pour "compresser" les sequences.
    En fait pour être exact, tu utilises la même idée de base, sauf que moi je fais cette première passe dont tu parles (enfin je ne "compresse" pas, je regroupe et fait "grandir" mes palindromes à partir de ces plages de caractères identiques). Néanmoins, le plus important c'est tout de même que ton algorithme, comme le mien est en O(np) et donc capable d'avaler des textes de grande taille, contrairement aux algorithmes en O(n²).

    Si je faisais exactement comme toi dans ma 3ème version, j'écrirais :
    Code Haskell : 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
    module Main () where
    import Data.List
    import Data.Ord
    import Data.ByteString.Char8 hiding (map)
    import qualified Data.ByteString.Char8 as B
     
    data Pal = P !Int !Int deriving (Show)
     
    expand :: ByteString -> Pal -> ByteString
    expand bs (P start end) = fst . B.splitAt (end - start) . snd . B.splitAt start $ bs
     
    grow :: ByteString -> Pal -> Pal
    grow bs p@(P start end)
        | start == 0 
          || end == B.length bs
          || bs `index` (start-1) /= bs `index` end = p 
        | otherwise                                 = grow bs (P (start - 1) (end + 1))
     
    longest :: ByteString -> ByteString
    longest bs = 
      expand bs . maximumBy (comparing lengthPal) . map (grow bs) 
        $ [p | start <- [0..B.length bs - 1], p <- [P start start, P start (start + 1)]]
      where lengthPal (P s e) = e - s
     
    main :: IO ()
    main = print . longest =<< B.getContents

    --
    Jedaï

  15. #15
    Candidat au Club
    Profil pro
    Inscrit en
    Octobre 2007
    Messages
    2
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 2
    Points : 2
    Points
    2
    Par défaut Une methode utilisant des hachages
    Il me semble que ton algo est O( n * p ) , mais ou p se serait la moyenne de la taille des palindromes et non que celle du plus grand ( ce qui est la meme chose qu'en pire cas ... )

    Enfin ...

    je vous propose un algo qui n'est pas mieux que les votre dans le cas moyen parce qu'il a une constante un peu plus grande que les votre et qu'il n'est qu'en O( n * log(Pmax) ) (en pire cas comme en moyenne ) or je crois que Pmoyen ~= log(Pmax) sur une distribution bien aleatoire donc pas bien mieux ... sauf sur le pire cas !

    Le principe de cet algo repose sur le fait que si il n'existe pas de palindrome de taille n ou n+1 (eh oui obliger de distinguer les cas pair et impair ) c'est qu'alors il n'y en a pas de plus grand que n. De la on peut faire une dichotomie.

    La fonction qui regarde si il n'y a pas de palindrome fonctionne avec un hachage ce qui permet ( globalement ) de considerer que la comparaison des cotes gauches et droites se fait en O(1) si elle echoue et O(P) si elle reussit comme elle ne reussit que une fois par appel on a bien du O(N) pour cette fonction donc un total de O( N ln P ).

    Code C++ : 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
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
     
     
    class palindrome
    {
    public:
      int debut , plus_grand ;
    private:
      int * hash_droite  ;
      const char * source ;
      int longueur;
     
      inline bool compare (  int taille , int a  ,int b )
      {
        while ( taille > 0 )
          {
    	if( source[a--] != source[b++] )
    	  return false ;
    	taille--;
          }
        return true ;
      }
     
     
      inline bool possible ( const int taille  )
      {
        plus_grand = -1 ;
     
        int decal = 1 ;
        for ( int i = 0 ; i < taille ; i++ )
          decal *= 5 ;
     
     
        int hash = 0 ;
     
        hash_droite[ longueur-1 ] = source[ longueur - 1 ] ;
        for( int i =  longueur-2 ; i >= 0; i -- )
          if ( (size_t)i+taille < longueur )
    	hash_droite[ i ] = hash_droite[i+1]*5 + source[i] - decal*source[i+taille] ;
          else
    	hash_droite[ i ] = hash_droite[i+1]*5 + source[i] ;
     
        for ( int i = 0 ; i < taille ; i ++ )
          hash = hash * 5 + source[i] ;
     
        for ( size_t i = taille ; i + taille <= longueur ; i++ )
          {
    	if( i+taille < longueur )
    	  if( hash_droite[i+1] == hash )
    	    if ( compare ( taille, i-1 , i+1 ) )
    	      {
    		plus_grand = 2*taille+1 ;
    		debut = i-taille ;
    		return true ;
    	      }
     
    	if( hash_droite[i] == hash )
    	  if ( compare ( taille, i-1 , i ) )
    	    {
    		plus_grand = 2*taille+1 ;
    		debut = i-taille ;
    	    }
    	hash = hash*5+source[i]-decal*source[i-taille] ;       
          }
        return plus_grand != -1 ;
      }
    public:
      palindrome ( const string & chaine )
      {
        plus_grand = -1 ;
        source = chaine.c_str() ;
        longueur = chaine.size () ;
        hash_droite = new int[ longueur ] ;
        int gauche = 1 ;
        int droite =  longueur/2+1 ;
        while( gauche < droite && possible( gauche  )  )
          gauche *= 2 ;
        droite = min( droite , gauche );
        gauche /= 2 ;
        while (  droite-gauche > 1 )
          {
    	const int milieu = (droite+gauche)/2 ;
    	if ( possible ( milieu ) )
    	  gauche = milieu ;
    	else
    	  droite = milieu ;
          }
        possible(gauche);
        delete hash_droite ;
      }
     
    };

    Voila!


    Louis

  16. #16
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 58
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Points : 5 753
    Points
    5 753
    Par défaut
    Jedaï, quand j'utilise ton algorithme 3, avec GHC 6.10.2, sur WinXP Pro, j'obtiens une erreur :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    $ cat french | ./palindrome
    Stack space overflow: current size 8388608 bytes.
    Use `+RTS -Ksize' to increase it.
    J'ai essayer de compiler avec les options +RTS -K100M, mais j'ai le même message d'erreur.
    Je suis dans une fenêtre cygwin pour lancer la commande. J'ai la même erreur depuis une fenêtre de commande windows (en appelant palindrome.exe <french).
    Je vais tenter sous Ubuntu (virtualisé sur mon XP)...
    Plus j'apprends, et plus je mesure mon ignorance (philou67430)
    Toute technologie suffisamment avancée est indiscernable d'un script Perl (Llama book)
    Partagez vos problèmes pour que l'on partage ensemble nos solutions : je ne réponds pas aux questions techniques par message privé
    Si c'est utile, say

  17. #17
    alex_pi
    Invité(e)
    Par défaut
    Voici une version Caml pas mal bidouillesque :

    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
    61
    62
    63
    64
    65
    66
    67
    68
    69
    (* length of an even palindrom, going left from [i] and right from [j] *)
    
    let length_pal_even s i j =
      let l = String.length s in
      let rec aux i' j' acc = 
        if i' < 0 || j' >= l || s.[i'] <> s.[j'] then 2 * acc
        else aux (pred i') (succ j') (succ acc) in
      aux i j 0
    
    
    (* number of equal chars from [i] *)
    let length_rep s i = 
      let l = String.length s in
      let c = s.[i] in
      let rec aux i' acc = 
        if i' >= l || s.[i'] <> c then acc
        else aux (succ i') (succ acc) in
      aux (succ i) 1
    
    
    (* starting position and length of the first longest pal *)
    let longest_pal s = 
      if s = "" then (0, 0) else
      let l = String.length s in
    
      (* bp = best position
         bl = best length
         i = current position
      *)
      let rec aux bp bl i =
        (* if we reached the end of the string *)
        if i >= l then (bp, bl) else
        let lr = length_rep s i in
    
        (* external lenth: lenght of the palindrome outside the current
        repetition *)
        let el = length_pal_even s (pred i) (i + lr) in
    
        (* palindrom length*)
        let pl = el + lr in
        if pl > bl then 
          aux (i - (el / 2)) pl (i + lr)
        else
          aux bp bl (i + lr)
      in
        aux (-1) (-1) 0
    
    
    
    (* two helpers to get the content of a file *)
    let with_input_file ?(bin=false) x f =
      let ic = (if bin then open_in_bin else open_in) x in
      try let res = f ic in close_in ic; res with e -> (close_in ic; raise e)
    
    let read_file x =
      with_input_file ~bin:true x begin fun ic ->
        let len = in_channel_length ic in
        let buf = String.create len in
        let () = really_input ic buf 0 len in
        buf
      end
    
    
    (* the main function *)
    let _ = 
      let s = read_file Sys.argv.(1) in
      let p, l = longest_pal s in
        Printf.printf "The longest pal has length %i and is [[%s]]" l (String.sub s p l)
    De l'ordre de dix fois plus rapide que la première version de Jedai sur la bible (4,3 MO), et deux fois plus rapide que la 3eme version, mais je ne suis pas sûr d'avoir employé les bonnes options de compilation, donc à voir !

  18. #18
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par alex_pi Voir le message
    De l'ordre de dix fois plus rapide que la première version de Jedai sur la bible (4,3 MO), et deux fois plus rapide que la 3eme version, mais je ne suis pas sûr d'avoir employé les bonnes options de compilation, donc à voir !
    Sur un fichier avec de *nombreuses* et *longues* répétition, la 3ème version de Jedai me rattrape, mais la première devient 50 fois plus lente.

  19. #19
    Expert éminent
    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
    Points : 8 586
    Points
    8 586
    Par défaut
    Je précise que je compile avec optimisation (-O2 -funbox-strict-fields) rien de plus compliqué.

    @Philou : Tu as bien compilé avec optimisation ? Pour ma part je n'ai pas eu de stack overflow et je ne pense pas que tu ais le problème avec les optimisations (ça pourrait venir du maximumBy, mais avec optimisation, il est normalement strict et donc non sujet à ce problème).

    @AlexPi : Il est relativement normal que la première version soit bien plus lente sur de gros fichiers vu qu'elle utilise String, qui n'est autre qu'un synonyme pour [Char]... Ta version comme ma 3ème utilise des tableaux de caractères pour les chaînes et est donc nettement plus efficace. Par ailleurs si la seule différence entre ma 3ème version et ton code est un facteur 2, je m'avoue plutôt content puisqu'a priori tu as employé une technique relativement plus bas niveau que la mienne.

  20. #20
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Par ailleurs si la seule différence entre ma 3ème version et ton code est un facteur 2, je m'avoue plutôt content puisqu'a priori tu as employé une technique relativement plus bas niveau que la mienne.
    Oh oui !! Mais quand même du fonctionnel pur hein

Discussions similaires

  1. Défi : Toutes les semaines un peu de code pour aller plus loin avec Windows 7
    Par Jérôme Lambert dans le forum Développement Windows
    Réponses: 41
    Dernier message: 05/01/2012, 13h00
  2. les palindromes et chaines de caractères
    Par olivier1209 dans le forum C
    Réponses: 75
    Dernier message: 07/01/2007, 13h40

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