Discussion :

[millie]

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

[Jedai]

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�

[djo.mos]

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"));
	}
 
}

[Philou67430]

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.

[Jedai]

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�

[Philou67430]

Sauf erreur, Jeda�, je crois que ta fonction isPalindrome ne r�cup�re pas les palindromes de taille impaire.

[Jedai]

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�

[Philou67430]

Parce que j'ai mal lu le code

[Jedai]

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�

[Jedai]

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�

[pseudocode]

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);
}

[Jedai]

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�

[pseudocode]

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.

[Jedai]

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�

[rrk275]

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

[Philou67430]

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)...

[alex_pi]

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 !

[alex_pi]

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.

[Jedai]

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.

[alex_pi]

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