Donc je bosse dans un collège, et la saison des subvention permet
d'acheter des poste. Et ceux de PS étant intéressant niveau prix/config,
ce sont ceux qu'on a acheté.
Résultat : Le Mandrake linux Discovery annoncé est en fait un Linpus
Linux, distribution basée Mdk, sur laquelle je n'ai pas réussit à faire
un chti urpmi, ni même à trouver un outil graphique pour maj.
Bref, moi qui espérait un peu là-dessus pour convaincre de faire migrer
la salle info sous linux, pas de pot avec cette config à 2 sous...
Ouais, je sais, on en a pour son argent. Mais quand même...
La fin de l'aventure, totalement HS ici, mais bon, c'est que j'ai tout
viré pour refoutre win98 dessus (et ouais, je sais :-(). Ai pour ça
utilisé une knoppix, et QTParted, en 2 fois (obligation de redémarrer au
milieu), pour pouvoir supprimer les partitions et préparer/formater en
fat32. Et le fin du fin, aucun pilote fourni. Heureusement qu'il y a un
site.
En bref, le prix, 350 l'UC pour 80Go, Celeron D et 512 Mo Ram se justifie.
In article <4283923e$0$297$, Jean-Francois BILLAUD wrote:
scripsit Michel Billaud :
C'est mal programmé surtout. Un quicksort quadratique à cause de la concaténation. Bouuuuh !
Suffit d'acheter une machine plus puissante, ça revient moins cher que d'embaucher un bon programmeur.
Pis, bon, je ne sais pas si c'est bien judicieux d'évoquer la complexité des algorithmes à ce niveau-là... (en parler, certes, le détailler, ça amènerait un peu loin...).
Ah oui mais bon alors pourquoi s'emmerder à faire un quicksort ? Et à quoi bon d'ailleurs faire un tri, alors qu'il suffit d'aller chercher le plus grand (ou le plus petit) quand on a besoin, par un parcours tout simple ?
PS: pour transformer le quicksort inefficace, 1. poser q(a,b) = quicksort(a) @ b 2. en déduire une définition récursive de q 3. et comme quicksort(x) = q(x,[]), voili voila.
C'est bien le vrai intérêt de la programmation fonctionnelle : on peut raisonner sur les transformations de programmes avec les outils algébriques de la classe de quatrieme.
-- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Eric Jacoboni <jaco@teaser.fr> writes:
In article <4283923e$0$297$636a15ce@news.free.fr>,
Jean-Francois BILLAUD <billaud@interpc.fr> wrote:
scripsit Michel Billaud :
C'est mal programmé surtout. Un quicksort quadratique à cause de la
concaténation. Bouuuuh !
Suffit d'acheter une machine plus puissante, ça revient moins cher que
d'embaucher un bon programmeur.
Pis, bon, je ne sais pas si c'est bien judicieux d'évoquer la complexité
des algorithmes à ce niveau-là... (en parler, certes, le détailler, ça
amènerait un peu loin...).
Ah oui mais bon alors pourquoi s'emmerder à faire un quicksort ? Et à
quoi bon d'ailleurs faire un tri, alors qu'il suffit d'aller chercher
le plus grand (ou le plus petit) quand on a besoin, par un parcours
tout simple ?
PS: pour transformer le quicksort inefficace,
1. poser q(a,b) = quicksort(a) @ b
2. en déduire une définition récursive de q
3. et comme quicksort(x) = q(x,[]), voili voila.
C'est bien le vrai intérêt de la programmation fonctionnelle : on peut
raisonner sur les transformations de programmes avec les outils
algébriques de la classe de quatrieme.
--
Michel BILLAUD billaud@labri.fr
LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792
351, cours de la Libération http://www.labri.fr/~billaud
33405 Talence (FRANCE)
In article <4283923e$0$297$, Jean-Francois BILLAUD wrote:
scripsit Michel Billaud :
C'est mal programmé surtout. Un quicksort quadratique à cause de la concaténation. Bouuuuh !
Suffit d'acheter une machine plus puissante, ça revient moins cher que d'embaucher un bon programmeur.
Pis, bon, je ne sais pas si c'est bien judicieux d'évoquer la complexité des algorithmes à ce niveau-là... (en parler, certes, le détailler, ça amènerait un peu loin...).
Ah oui mais bon alors pourquoi s'emmerder à faire un quicksort ? Et à quoi bon d'ailleurs faire un tri, alors qu'il suffit d'aller chercher le plus grand (ou le plus petit) quand on a besoin, par un parcours tout simple ?
PS: pour transformer le quicksort inefficace, 1. poser q(a,b) = quicksort(a) @ b 2. en déduire une définition récursive de q 3. et comme quicksort(x) = q(x,[]), voili voila.
C'est bien le vrai intérêt de la programmation fonctionnelle : on peut raisonner sur les transformations de programmes avec les outils algébriques de la classe de quatrieme.
-- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Michel Billaud
Richard Delorme writes:
Richard Delorme writes:
Moi j'aurais bien dit Ocaml, qui respecte sans problème toutes ces conditions, et a en plus une syntaxe très agréable,
Personnellement, je ne trouve pas la syntaxe d'Ocaml très lisible. Par exemple, dans ce tri rapide :
(* Tri rapide (quicksort ou tri de Hoare) d'une liste *) let rec qsort = function | [] -> [] | x :: l -> let rec coupelist = function | [] -> [], [] | y :: m -> let a, b = coupelist m in if y < x then y :: a, b else a, y :: b in let debut, fin = coupelist l in (qsort debut) @ [x] @ (qsort fin);;
Il y a plein de symboles assez abscons : '->' '::', '|', '@', et j'ai du mal à lire le code.
C'est mal indenté.
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
la technique pour extraire les sous-listes n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les mêmes dans les deux exemples.
Il s'agit de deux programme de quicksort piqués sur le web et relativement court, mais que je trouve assez démonstratif sur la lisibilité.
pas moi.
C'est mal programmé surtout. Un quicksort quadratique à cause de la concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au langage, on est bien d'accord. Cela dit, la concaténation de listes ce fait généralement en temps constant,
C'est nouveau ça.
ce qui rend la complexité plus grande est la création de variables intermédiaires avec des copies cachées.
MB
-- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Richard Delorme <abulmo@nospam.fr> writes:
Richard Delorme <abulmo@nospam.fr> writes:
Moi j'aurais bien dit Ocaml, qui respecte sans problème toutes ces
conditions, et a en plus une syntaxe très agréable,
Personnellement, je ne trouve pas la syntaxe d'Ocaml très lisible. Par
exemple, dans ce tri rapide :
(* Tri rapide (quicksort ou tri de Hoare) d'une liste *)
let rec qsort = function
| [] -> []
| x :: l ->
let rec coupelist = function
| [] -> [], []
| y :: m -> let a, b = coupelist m in
if y < x then y :: a, b else a, y :: b
in let debut, fin = coupelist l
in (qsort debut) @ [x] @ (qsort fin);;
Il y a plein de symboles assez abscons : '->' '::', '|', '@', et j'ai du
mal à lire le code.
C'est mal indenté.
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
la technique pour extraire les sous-listes
n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les
mêmes dans les deux exemples.
Il
s'agit de deux programme de quicksort piqués sur le web et relativement
court, mais que je trouve assez démonstratif sur la lisibilité.
pas moi.
C'est mal programmé surtout. Un quicksort quadratique à cause de la
concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au
langage, on est bien d'accord. Cela dit, la concaténation de listes ce
fait généralement en temps constant,
C'est nouveau ça.
ce qui rend la complexité plus
grande est la création de variables intermédiaires avec des copies cachées.
MB
--
Michel BILLAUD billaud@labri.fr
LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792
351, cours de la Libération http://www.labri.fr/~billaud
33405 Talence (FRANCE)
Moi j'aurais bien dit Ocaml, qui respecte sans problème toutes ces conditions, et a en plus une syntaxe très agréable,
Personnellement, je ne trouve pas la syntaxe d'Ocaml très lisible. Par exemple, dans ce tri rapide :
(* Tri rapide (quicksort ou tri de Hoare) d'une liste *) let rec qsort = function | [] -> [] | x :: l -> let rec coupelist = function | [] -> [], [] | y :: m -> let a, b = coupelist m in if y < x then y :: a, b else a, y :: b in let debut, fin = coupelist l in (qsort debut) @ [x] @ (qsort fin);;
Il y a plein de symboles assez abscons : '->' '::', '|', '@', et j'ai du mal à lire le code.
C'est mal indenté.
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
la technique pour extraire les sous-listes n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les mêmes dans les deux exemples.
Il s'agit de deux programme de quicksort piqués sur le web et relativement court, mais que je trouve assez démonstratif sur la lisibilité.
pas moi.
C'est mal programmé surtout. Un quicksort quadratique à cause de la concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au langage, on est bien d'accord. Cela dit, la concaténation de listes ce fait généralement en temps constant,
C'est nouveau ça.
ce qui rend la complexité plus grande est la création de variables intermédiaires avec des copies cachées.
MB
-- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
remy
"Stephane Zuckerman" a écrit dans le message de news:
ah j'ai eu le meme type de prof et a la fin il finissait par
tout le reste ce ne sont que des abstractions parce que l'on est pas tres doue ou faienant dans le meilleur des cas
mais parler de complement a 1 ou 2 pour faire une soustraction qd l'on a 15 ans ils risquent de s'en foutre et ils auront peut etre raison J'ai fait TSA en 2nde (qui mène à la section S tronc commun TI, maintenant
appelé SI), et le complément à {1,2} était abordé dans nos cours.
mon parcours scolaire est atypique en gros a pleurer ou a mourir de rire
pour revenir au debat vaut il mieux aborder l'obg via ""l'uml "" heritage direct indirect polymorfisme ou simplement dire que c'est un espace d'adressage protege par le type de l'obj
-- des conneries j'en ai dites oui oui je vous assure... mais elles n'engagent que votre perception remy
"Stephane Zuckerman" <szuckerm@etu.utc.fr> a écrit dans le message de
news:Pine.OSF.4.58.0505131226240.37582@vega.utc.fr...
ah j'ai eu le meme type de prof
et a la fin il finissait par
tout le reste ce ne sont que des abstractions
parce que l'on est pas tres doue ou faienant dans le meilleur des cas
mais parler de complement a 1 ou 2 pour faire une soustraction
qd l'on a 15 ans ils risquent de s'en foutre et ils auront peut etre
raison
J'ai fait TSA en 2nde (qui mène à la section S tronc commun TI, maintenant
appelé SI), et le complément à {1,2} était abordé dans nos cours.
mon parcours scolaire est atypique
en gros a pleurer ou a mourir de rire
pour revenir au debat vaut il mieux aborder l'obg
via ""l'uml "" heritage direct indirect polymorfisme
ou simplement dire que c'est un espace d'adressage
protege par le type de l'obj
--
des conneries j'en ai dites oui oui je vous assure...
mais elles n'engagent que votre perception
remy
"Stephane Zuckerman" a écrit dans le message de news:
ah j'ai eu le meme type de prof et a la fin il finissait par
tout le reste ce ne sont que des abstractions parce que l'on est pas tres doue ou faienant dans le meilleur des cas
mais parler de complement a 1 ou 2 pour faire une soustraction qd l'on a 15 ans ils risquent de s'en foutre et ils auront peut etre raison J'ai fait TSA en 2nde (qui mène à la section S tronc commun TI, maintenant
appelé SI), et le complément à {1,2} était abordé dans nos cours.
mon parcours scolaire est atypique en gros a pleurer ou a mourir de rire
pour revenir au debat vaut il mieux aborder l'obg via ""l'uml "" heritage direct indirect polymorfisme ou simplement dire que c'est un espace d'adressage protege par le type de l'obj
-- des conneries j'en ai dites oui oui je vous assure... mais elles n'engagent que votre perception remy
Michel Billaud
Jean-Francois BILLAUD writes:
Pour une initiation à la programmation, aucun langage ne convient. On peut aussi dire que n'importe lequel convient.
Ça me rassure.
Certes c'est rassurant de savoir qu'on peut dire absolument n'importe quoi.
Mais je me demande si quelqu'un est vraiment prêt à défendre GAP, RPG, PL/I, ...
Ah oui, j'ai une idée, on pourrait inventer un pseudo-langage que l'on traduirait ensuite dans le langage de son choix. En plus ça fera un chouette exercice de passer d'un pseudo-langage récursif à un vrai langage qui ne l'est pas.
Ensuite pour les travaux pratiques éventuels, n'importe quel langage convient.
J'hésite entre APL et COBOL objet.
et LSE, on n'en parle pas ?
MB -- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Pour une initiation à la programmation, aucun langage ne convient. On peut
aussi dire que n'importe lequel convient.
Ça me rassure.
Certes c'est rassurant de savoir qu'on peut dire absolument n'importe quoi.
Mais je me demande si quelqu'un est vraiment prêt à défendre GAP, RPG,
PL/I, ...
Ah oui, j'ai une idée, on pourrait inventer un pseudo-langage que l'on traduirait
ensuite dans le langage de son choix. En plus ça fera un chouette exercice de
passer d'un pseudo-langage récursif à un vrai langage qui ne l'est pas.
Ensuite pour les travaux pratiques éventuels, n'importe quel langage convient.
J'hésite entre APL et COBOL objet.
et LSE, on n'en parle pas ?
MB
--
Michel BILLAUD billaud@labri.fr
LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792
351, cours de la Libération http://www.labri.fr/~billaud
33405 Talence (FRANCE)
Pour une initiation à la programmation, aucun langage ne convient. On peut aussi dire que n'importe lequel convient.
Ça me rassure.
Certes c'est rassurant de savoir qu'on peut dire absolument n'importe quoi.
Mais je me demande si quelqu'un est vraiment prêt à défendre GAP, RPG, PL/I, ...
Ah oui, j'ai une idée, on pourrait inventer un pseudo-langage que l'on traduirait ensuite dans le langage de son choix. En plus ça fera un chouette exercice de passer d'un pseudo-langage récursif à un vrai langage qui ne l'est pas.
Ensuite pour les travaux pratiques éventuels, n'importe quel langage convient.
J'hésite entre APL et COBOL objet.
et LSE, on n'en parle pas ?
MB -- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Michel Billaud
Eric Jacoboni writes:
In article <4284721e$0$314$, Jean-Francois BILLAUD wrote:
Je voudrais inventer le mien.
Ça existe déja : ça s'appelle l'algorithmique... (à moins que tu ne préfères dire "blurp", à la place de "tant que").
Alors disons "algorythmique ?
MB
-- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Eric Jacoboni <jaco@neottia.net> writes:
In article <4284721e$0$314$636a15ce@news.free.fr>,
Jean-Francois BILLAUD <billaud@interpc.fr> wrote:
Je voudrais inventer le mien.
Ça existe déja : ça s'appelle l'algorithmique... (à moins que tu ne
préfères dire "blurp", à la place de "tant que").
Alors disons "algorythmique ?
MB
--
Michel BILLAUD billaud@labri.fr
LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792
351, cours de la Libération http://www.labri.fr/~billaud
33405 Talence (FRANCE)
In article <4284721e$0$314$, Jean-Francois BILLAUD wrote:
Je voudrais inventer le mien.
Ça existe déja : ça s'appelle l'algorithmique... (à moins que tu ne préfères dire "blurp", à la place de "tant que").
Alors disons "algorythmique ?
MB
-- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Jean-Francois BILLAUD
Michel Billaud écrivait :
et LSE, on n'en parle pas ?
J'y avais pensé.. Quelqu'un aurait une dizaine de Logabax dans un placard ? Ou un Mitra 15 ?
JFB
-- "Not only is this incomprehensible, but the ink is ugly and the paper is from the wrong kind of tree." -- Professor W.
Michel Billaud écrivait :
et LSE, on n'en parle pas ?
J'y avais pensé..
Quelqu'un aurait une dizaine de Logabax dans un placard ?
Ou un Mitra 15 ?
JFB
--
"Not only is this incomprehensible, but the ink is ugly and the paper
is from the wrong kind of tree."
-- Professor W.
J'y avais pensé.. Quelqu'un aurait une dizaine de Logabax dans un placard ? Ou un Mitra 15 ?
JFB
-- "Not only is this incomprehensible, but the ink is ugly and the paper is from the wrong kind of tree." -- Professor W.
Richard Delorme
C'est mal indenté.
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
La différence est que le Python mal programmé est malgré tout bien indenté.
la technique pour extraire les sous-listes n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les mêmes dans les deux exemples.
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles abscons". le détail de l'algo je m'en fichais ici.
Il s'agit de deux programme de quicksort piqués sur le web et relativement court, mais que je trouve assez démonstratif sur la lisibilité.
pas moi.
Oui, c'est subjectif. Cela dit je ne sais pas ce que fait la version en OCaml, pour dire comme c'est lisible... tandis que la version en Python, ou celle en Haskell d'Eric Jacoboni, j'arrive à les lire.
C'est mal programmé surtout. Un quicksort quadratique à cause de la concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au langage, on est bien d'accord. Cela dit, la concaténation de listes ce fait généralement en temps constant,
C'est nouveau ça.
Non, mais c'est sans doute uniquement vrai dans mes implémentations personnelles de liste en C.
Cela dit, un chronométrage de la version python me fait sérieusement douté de sa complexité quadratique.
-- Richard
C'est mal indenté.
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
La différence est que le Python mal programmé est malgré tout bien indenté.
la technique pour extraire les sous-listes
n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les
mêmes dans les deux exemples.
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles
abscons". le détail de l'algo je m'en fichais ici.
Il
s'agit de deux programme de quicksort piqués sur le web et relativement
court, mais que je trouve assez démonstratif sur la lisibilité.
pas moi.
Oui, c'est subjectif. Cela dit je ne sais pas ce que fait la version en
OCaml, pour dire comme c'est lisible... tandis que la version en Python,
ou celle en Haskell d'Eric Jacoboni, j'arrive à les lire.
C'est mal programmé surtout. Un quicksort quadratique à cause de la
concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au
langage, on est bien d'accord. Cela dit, la concaténation de listes ce
fait généralement en temps constant,
C'est nouveau ça.
Non, mais c'est sans doute uniquement vrai dans mes implémentations
personnelles de liste en C.
Cela dit, un chronométrage de la version python me fait sérieusement
douté de sa complexité quadratique.
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
La différence est que le Python mal programmé est malgré tout bien indenté.
la technique pour extraire les sous-listes n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les mêmes dans les deux exemples.
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles abscons". le détail de l'algo je m'en fichais ici.
Il s'agit de deux programme de quicksort piqués sur le web et relativement court, mais que je trouve assez démonstratif sur la lisibilité.
pas moi.
Oui, c'est subjectif. Cela dit je ne sais pas ce que fait la version en OCaml, pour dire comme c'est lisible... tandis que la version en Python, ou celle en Haskell d'Eric Jacoboni, j'arrive à les lire.
C'est mal programmé surtout. Un quicksort quadratique à cause de la concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au langage, on est bien d'accord. Cela dit, la concaténation de listes ce fait généralement en temps constant,
C'est nouveau ça.
Non, mais c'est sans doute uniquement vrai dans mes implémentations personnelles de liste en C.
Cela dit, un chronométrage de la version python me fait sérieusement douté de sa complexité quadratique.
-- Richard
Michel Billaud
Richard Delorme writes:
C'est mal indenté.
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
La différence est que le Python mal programmé est malgré tout bien indenté.
Ca me rassure.
la technique pour extraire les sous-listes n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les mêmes dans les deux exemples.
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles abscons". le détail de l'algo je m'en fichais ici.
Ouais enfin [ ] pour définir un ensemble, c'est pas top. Un minimum de cohérence avec les notations habituelles aurait été { x | p(x) }
Oui, c'est subjectif. Cela dit je ne sais pas ce que fait la version en OCaml, pour dire comme c'est lisible... tandis que la version en Python, ou celle en Haskell d'Eric Jacoboni, j'arrive à les lire.
En Haskell
-module(quicksort). -export([qsort/1]).
qsort([]) -> []; qsort([Pivot|Rest]) -> qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).
Désole mais tout ça c'est du pareil au même. On peut même comparer avec une version Hope (la même version débile non optimisée)
dec TriPartition : list(num) -> list(num) ; --- TriPartition ( [ ] ) <= [ ] ; --- TriPartition ( p :: r ) <= let pp == PlusPetits(p, r) in let pg == PlusGrands(p, r) in TriPartition(pp) <>( p :: TriPartition(pg) ) ;
Avec dec PlusPetits : num X list(num) -> list(num); --- PlusPetits ( n , [ ] ) <= []; --- PlusPetits ( n , p :: r ) <= if (p < n) then p :: PlusPetits(n,r) else PlusPetits(n,r); L'autre étant laissé en exercice.
C'est mal programmé surtout. Un quicksort quadratique à cause de la concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au langage, on est bien d'accord. Cela dit, la concaténation de listes ce fait généralement en temps constant,
C'est nouveau ça.
Non, mais c'est sans doute uniquement vrai dans mes implémentations personnelles de liste en C.
Cela dit, un chronométrage de la version python me fait sérieusement douté de sa complexité quadratique.
Dans le pire des cas (liste déjà ordonnée dans un sens), bien ou mal implémenté, c'est déjà foncierement quadratique, concatenation en temps constant ou lineaire.
(A chaque etape, pour une liste de longueur n, cout linéaire pour isoler les deux sous-listes, et si on n'a pas de bol on recursionne sur une des sous-listes qui est de taille n-1, et rebelotte, somme des entiers de 1 à n => quadratique)
MB
-- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Richard Delorme <abulmo@nospam.fr> writes:
C'est mal indenté.
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
La différence est que le Python mal programmé est malgré tout bien indenté.
Ca me rassure.
la technique pour extraire les sous-listes
n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les
mêmes dans les deux exemples.
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles
abscons". le détail de l'algo je m'en fichais ici.
Ouais enfin [ ] pour définir un ensemble, c'est pas top. Un minimum de
cohérence avec les notations habituelles aurait été { x | p(x) }
Oui, c'est subjectif. Cela dit je ne sais pas ce que fait la version en
OCaml, pour dire comme c'est lisible... tandis que la version en Python,
ou celle en Haskell d'Eric Jacoboni, j'arrive à les lire.
En Haskell
-module(quicksort).
-export([qsort/1]).
qsort([]) -> [];
qsort([Pivot|Rest]) ->
qsort([ X || X <- Rest, X < Pivot])
++ [Pivot]
++ qsort([ Y || Y <- Rest, Y >= Pivot]).
Désole mais tout ça c'est du pareil au même. On peut même comparer
avec une version Hope (la même version débile non optimisée)
dec TriPartition : list(num) -> list(num) ;
--- TriPartition ( [ ] ) <= [ ] ;
--- TriPartition ( p :: r ) <=
let pp == PlusPetits(p, r)
in let pg == PlusGrands(p, r)
in TriPartition(pp) <>( p :: TriPartition(pg) ) ;
Avec
dec PlusPetits : num X list(num) -> list(num);
--- PlusPetits ( n , [ ] ) <= [];
--- PlusPetits ( n , p :: r ) <= if (p < n)
then p :: PlusPetits(n,r)
else PlusPetits(n,r);
L'autre étant laissé en exercice.
C'est mal programmé surtout. Un quicksort quadratique à cause de la
concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au
langage, on est bien d'accord. Cela dit, la concaténation de listes ce
fait généralement en temps constant,
C'est nouveau ça.
Non, mais c'est sans doute uniquement vrai dans mes implémentations
personnelles de liste en C.
Cela dit, un chronométrage de la version python me fait sérieusement
douté de sa complexité quadratique.
Dans le pire des cas (liste déjà ordonnée dans un sens), bien ou mal
implémenté, c'est déjà foncierement quadratique, concatenation en
temps constant ou lineaire.
(A chaque etape, pour une liste de longueur n, cout linéaire pour
isoler les deux sous-listes, et si on n'a pas de bol on recursionne
sur une des sous-listes qui est de taille n-1, et rebelotte, somme des
entiers de 1 à n => quadratique)
MB
--
Michel BILLAUD billaud@labri.fr
LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792
351, cours de la Libération http://www.labri.fr/~billaud
33405 Talence (FRANCE)
Oui, aussi. Tandis que le Python est nécessairement bien indenté.
N'importe quel langage bien programmé est bien indenté aussi.
La différence est que le Python mal programmé est malgré tout bien indenté.
Ca me rassure.
la technique pour extraire les sous-listes n'est pas la même. Le spommes et les oranges.
La question n'est pas dans ce détail là, mais sur la lisibilité.
qui dépend aussi du choix des étapes intermédiaires, qui ne sont pas les mêmes dans les deux exemples.
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles abscons". le détail de l'algo je m'en fichais ici.
Ouais enfin [ ] pour définir un ensemble, c'est pas top. Un minimum de cohérence avec les notations habituelles aurait été { x | p(x) }
Oui, c'est subjectif. Cela dit je ne sais pas ce que fait la version en OCaml, pour dire comme c'est lisible... tandis que la version en Python, ou celle en Haskell d'Eric Jacoboni, j'arrive à les lire.
En Haskell
-module(quicksort). -export([qsort/1]).
qsort([]) -> []; qsort([Pivot|Rest]) -> qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).
Désole mais tout ça c'est du pareil au même. On peut même comparer avec une version Hope (la même version débile non optimisée)
dec TriPartition : list(num) -> list(num) ; --- TriPartition ( [ ] ) <= [ ] ; --- TriPartition ( p :: r ) <= let pp == PlusPetits(p, r) in let pg == PlusGrands(p, r) in TriPartition(pp) <>( p :: TriPartition(pg) ) ;
Avec dec PlusPetits : num X list(num) -> list(num); --- PlusPetits ( n , [ ] ) <= []; --- PlusPetits ( n , p :: r ) <= if (p < n) then p :: PlusPetits(n,r) else PlusPetits(n,r); L'autre étant laissé en exercice.
C'est mal programmé surtout. Un quicksort quadratique à cause de la concaténation. Bouuuuh !
La bonne programmation consiste à utiliser la fonction sort() intégré au langage, on est bien d'accord. Cela dit, la concaténation de listes ce fait généralement en temps constant,
C'est nouveau ça.
Non, mais c'est sans doute uniquement vrai dans mes implémentations personnelles de liste en C.
Cela dit, un chronométrage de la version python me fait sérieusement douté de sa complexité quadratique.
Dans le pire des cas (liste déjà ordonnée dans un sens), bien ou mal implémenté, c'est déjà foncierement quadratique, concatenation en temps constant ou lineaire.
(A chaque etape, pour une liste de longueur n, cout linéaire pour isoler les deux sous-listes, et si on n'a pas de bol on recursionne sur une des sous-listes qui est de taille n-1, et rebelotte, somme des entiers de 1 à n => quadratique)
MB
-- Michel BILLAUD LABRI-Université Bordeaux I tel 05 4000 6922 / 05 5684 5792 351, cours de la Libération http://www.labri.fr/~billaud 33405 Talence (FRANCE)
Eric Jacoboni
In article , Michel Billaud wrote:
Désole mais tout ça c'est du pareil au même. On peut même comparer avec une version Hope (la même version débile non optimisée)
Moi, je dirai qu'on s'en branle un peu.
Il n'est pas question de cours de programmation pour des licences d'Info, là, il était question de gamins de 15 ans à qui on veut donner des rudiments de programmation, et je ne suis pas sûr qu'il soit judicieux de leur pourrir le citron avec les problèmes de complexité.
Dire que certains algos sont meilleurs que d'autres : montrer en quoi une implémentation stupide est moins efficace qu'une implémentation un peu plus rusée, ok. Le reste, c'est juste bon à vider la salle de cours, à cet âge-là.
De toutes façons, si besoin en était, je choisirai plutôt Fibonnacci que les concaténations comme exemple de ce qu'il ne faut pas faire en récursivité : ça me semble plus immédiat à faire comprendre.
Bon, cela-dit, je méjuge peut-être les gamins de 15 ans (j'en ai pas sous la main pour me rendre compte).
-- Jaco
In article <7zsm0r6rfx.fsf@serveur5.labri.fr>,
Michel Billaud <billaud@labri.u-bordeaux.fr> wrote:
Désole mais tout ça c'est du pareil au même. On peut même comparer
avec une version Hope (la même version débile non optimisée)
Moi, je dirai qu'on s'en branle un peu.
Il n'est pas question de cours de programmation pour des licences
d'Info, là, il était question de gamins de 15 ans à qui on veut donner
des rudiments de programmation, et je ne suis pas sûr qu'il soit
judicieux de leur pourrir le citron avec les problèmes de complexité.
Dire que certains algos sont meilleurs que d'autres : montrer en quoi
une implémentation stupide est moins efficace qu'une implémentation un
peu plus rusée, ok. Le reste, c'est juste bon à vider la salle de
cours, à cet âge-là.
De toutes façons, si besoin en était, je choisirai plutôt Fibonnacci que
les concaténations comme exemple de ce qu'il ne faut pas faire en
récursivité : ça me semble plus immédiat à faire comprendre.
Bon, cela-dit, je méjuge peut-être les gamins de 15 ans (j'en ai pas
sous la main pour me rendre compte).
Désole mais tout ça c'est du pareil au même. On peut même comparer avec une version Hope (la même version débile non optimisée)
Moi, je dirai qu'on s'en branle un peu.
Il n'est pas question de cours de programmation pour des licences d'Info, là, il était question de gamins de 15 ans à qui on veut donner des rudiments de programmation, et je ne suis pas sûr qu'il soit judicieux de leur pourrir le citron avec les problèmes de complexité.
Dire que certains algos sont meilleurs que d'autres : montrer en quoi une implémentation stupide est moins efficace qu'une implémentation un peu plus rusée, ok. Le reste, c'est juste bon à vider la salle de cours, à cet âge-là.
De toutes façons, si besoin en était, je choisirai plutôt Fibonnacci que les concaténations comme exemple de ce qu'il ne faut pas faire en récursivité : ça me semble plus immédiat à faire comprendre.
Bon, cela-dit, je méjuge peut-être les gamins de 15 ans (j'en ai pas sous la main pour me rendre compte).
-- Jaco
Richard Delorme
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles abscons". le détail de l'algo je m'en fichais ici.
Ouais enfin [ ] pour définir un ensemble, c'est pas top. Un minimum de cohérence avec les notations habituelles aurait été { x | p(x) }
Ça j'arrive à le concevoir. Les [] servent à définir des listes et non des ensembles. Programmer, ce n'est pas nécessairement faire des mathématiques, et de toute manière l'ASCII manque de caractères pour permettre une notation mathématique exacte.
Désole mais tout ça c'est du pareil au même. On peut même comparer avec une version Hope (la même version débile non optimisée)
[...]
A part montrer que Hope est plus verbeux et moins lisible que Haskell, je ne vois pas l'intérêt de cet exemple.
Cela dit, un chronométrage de la version python me fait sérieusement douté de sa complexité quadratique.
Dans le pire des cas (liste déjà ordonnée dans un sens), bien ou mal implémenté, c'est déjà foncierement quadratique, concatenation en temps constant ou lineaire.
(A chaque etape, pour une liste de longueur n, cout linéaire pour isoler les deux sous-listes, et si on n'a pas de bol on recursionne sur une des sous-listes qui est de taille n-1, et rebelotte, somme des entiers de 1 à n => quadratique)
Que le quicksort soit de complexité quadratique dans le pire des cas n'est pas lié à la concaténation. J'avoue ne pas comprendre le problème.
-- Richard
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles
abscons". le détail de l'algo je m'en fichais ici.
Ouais enfin [ ] pour définir un ensemble, c'est pas top. Un minimum de
cohérence avec les notations habituelles aurait été { x | p(x) }
Ça j'arrive à le concevoir. Les [] servent à définir des listes et non
des ensembles. Programmer, ce n'est pas nécessairement faire des
mathématiques, et de toute manière l'ASCII manque de caractères pour
permettre une notation mathématique exacte.
Désole mais tout ça c'est du pareil au même. On peut même comparer
avec une version Hope (la même version débile non optimisée)
[...]
A part montrer que Hope est plus verbeux et moins lisible que Haskell,
je ne vois pas l'intérêt de cet exemple.
Cela dit, un chronométrage de la version python me fait sérieusement
douté de sa complexité quadratique.
Dans le pire des cas (liste déjà ordonnée dans un sens), bien ou mal
implémenté, c'est déjà foncierement quadratique, concatenation en
temps constant ou lineaire.
(A chaque etape, pour une liste de longueur n, cout linéaire pour
isoler les deux sous-listes, et si on n'a pas de bol on recursionne
sur une des sous-listes qui est de taille n-1, et rebelotte, somme des
entiers de 1 à n => quadratique)
Que le quicksort soit de complexité quadratique dans le pire des cas
n'est pas lié à la concaténation. J'avoue ne pas comprendre le problème.
Ce que je reprochais à OCaml était surtout l'utilisation de "symboles abscons". le détail de l'algo je m'en fichais ici.
Ouais enfin [ ] pour définir un ensemble, c'est pas top. Un minimum de cohérence avec les notations habituelles aurait été { x | p(x) }
Ça j'arrive à le concevoir. Les [] servent à définir des listes et non des ensembles. Programmer, ce n'est pas nécessairement faire des mathématiques, et de toute manière l'ASCII manque de caractères pour permettre une notation mathématique exacte.
Désole mais tout ça c'est du pareil au même. On peut même comparer avec une version Hope (la même version débile non optimisée)
[...]
A part montrer que Hope est plus verbeux et moins lisible que Haskell, je ne vois pas l'intérêt de cet exemple.
Cela dit, un chronométrage de la version python me fait sérieusement douté de sa complexité quadratique.
Dans le pire des cas (liste déjà ordonnée dans un sens), bien ou mal implémenté, c'est déjà foncierement quadratique, concatenation en temps constant ou lineaire.
(A chaque etape, pour une liste de longueur n, cout linéaire pour isoler les deux sous-listes, et si on n'a pas de bol on recursionne sur une des sous-listes qui est de taille n-1, et rebelotte, somme des entiers de 1 à n => quadratique)
Que le quicksort soit de complexité quadratique dans le pire des cas n'est pas lié à la concaténation. J'avoue ne pas comprendre le problème.
