Je ne vois pas du tout en quoi j'oublie ça. J'essaie d'expliquer que le fonctionnement d'un logiciel d'échecs est très différent du raisonnement d'un débutant, ce qui rend la tâche demandée très difficile.
Je vois difficilement comment ça pourrait donner quelque chose de pertinent. À titre d'exemple, considère le début de partie suivant (Spielmann - Walter, 1928) : 1.e4 c6 2.Cc3 d5 3.Cf3 Cf6 4.e5 Ce4 5.De2 Cxc3 6.dxc3 b6 7.Cd4 c5?
À ce stade, un programme qui cherche à expliquer l'erreur des noirs avec les critères habituels des débutants va probablement critiquer le fait d'avoir joué un coup de pion alors que les pièces ne sont pas développées ; en revanche, il ne dira rien sur le centre puisque 7…c5 prend le contrôle de la case centrale d4, ni sur l'initiative puisque le pion menace un cavalier. Le même débutant sera donc bien surpris d'apprendre que le bon coup était 7…d6, encore un coup de pion, et qui plus est, qui ne menace rien – on lui avait pourtant dit de prendre l'initiative, non ? L'explication est tout simplement qu'il fallait absolument empêcher les blancs de jouer 8.e5!, un coup qui ne développe aucune pièce et qui laisse le cavalier en prise… C'est pourtant un exemple typique de partie que l'on montre aux débutants, un programme qui se respecte devrait donc le traiter correctement.
Non, c'est nettement plus difficile que ça. Expliquer pourquoi un coup est fort est relativement simple. Ce qui est évoqué ici, c'est expliquer pourquoi un coup qu'un débutant envisagerait est faible, en lien avec son processus de prise de décision (celui de l'humain). C'est beaucoup plus complexe, parce qu'en général, pour l'ordinateur, un coup est faible parce qu'il permet une variante qui conduit l'adversaire à une bonne position, rarement parce qu'il néglige un critère humainement compréhensible en particulier. Ce genre d'explication (écrire un coup suivi d'un point d'interrogation et commenter « néglige le centre », « perd l'initiative », ou quelque chose dans le genre) est typiquement du travail d'humain, et généralement simplifié pour que le lecteur ait l'impression de suivre le commentaire. D'ailleurs, les meilleurs commentateurs pour le grand public sont les bons pédagogues, pas forcément les plus forts joueurs.
Commenter un coup faible nécessite donc de comprendre, dans une certaine mesure, comment l'humain réfléchit. Or il y en a difficilement deux qui réfléchissent de la même façon. Il y a ceux qui envisagent tout le temps des coups qui tendent des pièges grossiers sans faire progresser leur position, ceux qui ne pensent qu'à capturer tout le matériel adverse, ceux qui jettent toutes leurs pièces dans des attaques imaginaires… Il me parait nécessaire, pour expliquer pourquoi un coup est mauvais, de demander au joueur pourquoi il l'a choisi. C'est d'ailleurs l'approche de Jeremy Silman dans The amateur's mind. Et dès lors qu'on parle de comprendre, on est dans l'IA, et bien loin du minimax.
Facile à partir de l'ECO. Certaines transpositions ne seront pas résolues, mais de toutes façons on n'y peut rien.
conseiller de garder le centre
Mmmmmmh. Déjà, dans l'ouverture, il faut choisir entre l'occuper ou le contrôler à distance, voire passer de l'un à l'autre, et c'est très compliqué. Le choix entre garder ou liquider la tension centrale est souvent très difficile, et parfois plus une affaire de goût qu'autre chose. Ensuite, il arrive qu'on relâche volontairement le contrôle du centre, ne serait-ce que temporairement, pour redéployer une pièce. Prends par exemple la variante Breyer de l'espagnole : 1. e4 e5 2. Cf3 Cc6 3. Fb5 a6 4. Fa4 Cf6 5. o-o Fe7 6. Te1 b5 7. Fb3 d6 8. c3 o-o 9. h3 Cb8 (le cavalier perd le contrôle des cases centrales e5 et d4) et par exemple, 10.d4 Cbd7 (le cavalier se redéploie). Note que le coup 9 … Cb8, non content de lâcher le centre, remet une pièce sur sa case de départ (un coup de dé-développement, en quelque sorte), ce qui contrevient d'un coup à deux conseils donnés aux débutants.
la structure de pions
Vaste sujet. Il est important de connaitre les principaux éléments de structure de pions et les conseils généralement applicables, mais ce qui est encore plus important, c'est de savoir accepter une structure de pions abîmée en échange d'un autre déséquilibre. Et les pions doublés ou pendants, par exemple, sont parfois bien plus forts qu'on ne pourrait le penser. D'autre part, la structure de pions à un moment donné peut être trompeuse : on peut permettre à l'adversaire de « réparer » sa structure de pions si on sait qu'on est en mesure de la casser à nouveau plus tard. Le sujet du pion dame isolé mérite un livre à lui seul, et d'ailleurs il l'a (Winning pawn structures, de Baburin).
annoncer à l'avance des pièges possibles
Le problème que je vois ici est que se laisser avoir par une simple fourchette est difficile à distinguer d'une autre grosse bourde, du genre déplacer sa dame vers une case où elle est en prise (sans compensation).
parler des coups qui paraissent évidents mais qui sont mauvais
Qu'est-ce qu'un coup qui parait évident ? La réponse dépend totalement de celui à qui on pose la question, et pas seulement de son niveau, ça dépend aussi de sa façon de voir le jeu. Les agressifs voudront qu'on réfute leurs sacrifices bidons, les placides ne verront pas l'attaque qui les supplie d'être jouée, etc. Je ne vois vraiment pas comment formaliser le critère « coup paraissant évident ».
À mon avis, le problème est que tu cherches à faire évaluer par un ordinateur des critères que l'on donne aux humains pour les guider dans leur réflexion. Mais ces critères ne sont que cela, des guides. En réalité, ce qui compte vraiment, c'est de calculer des variantes, vite et bien. La centralisation, la structure de pions, l'espace, l'initiative, le contrôle d'un complexe de cases, la recherche d'une bonne case pour une pièce mineure, etc., peuvent — et doivent — guider dans le calcul des variantes, mais le cœur du jeu, c'est la tactique.
Effectivement, c'est beaucoup. Je propose d'en faire les briques de bases du futur palais des congres, ce qui fera du boulot pour l'entreprise de maconnerie.
It was from the RAND study that the false rumor started claiming that the ARPANET was somehow related to building a network resistant to nuclear war. This was never true of the ARPANET, only the unrelated RAND study on secure voice considered nuclear war. However, the later work on Internetting did emphasize robustness and survivability, including the capability to withstand losses of large portions of the underlying networks.
L'article de "bug brother" vient de faire disjoncter mon foutaisomètre. Tout ça pour ça : leboncoin utilise un serveur Apache. S'ils avaient eu IIS ou n'importe quoi d'autre, le résultat aurait été exactement le même.
À ne pas confondre avec les sports de combat, c'est justement ce qui m'a poussé vers l'aïkido. Pratiquer avec un partenaire me convient beaucoup mieux que contre un adversaire.
En attendant, ch et c'h s'écrivent toujours sous forme de deux et trois caractères, respectivement, ce qui complique le traitement des langues qui les considèrent comme un seul caractère. C'est le cas au moins du breton pour les deux, du tchèque pour ch. Et ce, alors même qu'il existe des caractères pour certaines ligatures, comme ff (ff). Mais voyons le bon côté des choses : avec un peu de chance, à force d'ajouter des hiéroglyphes et des kikoolols, on finira par en trouver des ressemblants.
C'est gentil de la part des modérateurs de corriger l'orthographe. Je voudrais tout de même profiter de cette dépêche pour demander une nouvelle fonctionnalité : ne pas corriger ce qui n'est pas faux. J'avais écrit ma dépêche sur la vulnérabilité des tables de hachage à une attaque basée sur la complexité algorithmique en appliquant les rectifications orthographiques de 1990. Un modérateur a « corrigé » vers l'orthographe pré-1990 sur une partie seulement du texte. Le résultat est un mélange des deux, ce qui est autorisé mais moche. Tout ça n'est évidemment pas grave et j'encourage vivement les modérateurs à continuer de corriger les énormités qui piquent les yeux.
Tiens, étrangement, Alternatives Économiques et ses forks publications sœurs (Alternatives Internationales, etc.) ne se meurent pas du tout à ma connaissance. Leur recette : vivre essentiellement des abonnements, avec un modèle mixte papier + Internet, des articles écrits par des journalistes et des chercheurs qui parlent de leur spécialité. Comme quoi, ça existe.
lorsque les expressions régulières utilisées sont de vraies expressions régulières il existe une implémentation beaucoup plus efficace que celle de Perl
Oui, du moins si d'autres conditions sont remplies. Par exemple, sa façon d'évacuer le problème d'Unicode est une plaisanterie.
Cela permettrait donc d'accélérer grandement le traitement des expressions régulière dans de nombreux cas sans ralentir les cas où on a vraiment besoin de l'implémentation actuelle.
Ça, c'est beaucoup moins sûr. Pour que cette solution ait un intérêt, il faudrait être sûr que la construction de l'automate ne coute pas plus cher que l'exécution du code actuel. Or, tout comme il existe des cas limites pour la méthode utilisée par Perl, il existe des cas limites pour les automates, avec la différence que l'explosion ne concerne pas seulement le temps d'exécution (facile à contrôler avec un chien de garde), mais une combinaison de temps et de mémoire, et, selon le type d'automate, à la construction et/ou à l'exécution. Voilà qui devient amusant à surveiller…
Par exemple, classiquement, les grosses répétitions et les grandes classes de caractères posent problème. Est-il vraiment une bonne idée d'avoir une implémentation pour ga?bu et une autre pour \w{2,3000}ga?bu : c'est douteux, surtout s'il faut entrer dans le cas pathologique pour s'apercevoir qu'on aurait mieux fait de ne pas y aller. Mais tout ça, et bien plus, est couvert dans la discussion ci-dessus.
Attention : l'article parle des expressions régulières au sens académique du terme, pas au sens « Perl » du terme. Voir par exemple cette discussion à laquelle participent des développeurs de Perl et l'auteur de l'article en question. En particulier, il a fallu un article paru plus tard pour avoir des NFA / DFA prenant en charge les références arrière, et ce n'est que l'un des aspects qui rendent l'article inapplicable en l'état.
La bonne solution est plutôt de s'assurer que l'algo de tri ne peut facilement dégénérer, sans être d'emblée non plus en O(n**2)
Voir introsort pour ceux que ça intéresse. Au passage, de nombreux environnements d’exécution utilisent « quicksort » pour trier, sans plus de précision dans leur doc (je n’ai pas regardé le code source). Si ce n’est pas une version de quicksort intégrant une astuce pour éviter le cas pathologique, ça peut donner des idées pour la prochaine fois…
En principe oui, mais avec une probabilité extrêmement faible. Si un risque aussi faible n’est pas acceptable, il vaut mieux laisser tomber directement les tables de hachage et utiliser une structure de données (l’un des nombreux types d’arbres…) qui garantit un pire cas en n log n (voire utiliser des tables de hachage que l'on remplace à la volée par des arbres si on détecte un scénario pathologique). Et toujours si on refuse un risque aussi faible, il faut tellement tout contrôler qu'il est pratiquement impensable d’utiliser un langage de haut niveau (haut comme Perl, C étant considéré comme bas).
Aucune fonction de hachage utilisées en pratique en cryptographie sont issues de travaux de Bernstein
En crypto, non, mais ce n'est pas le sujet. Les fonctions de hachage pour tables de hachage dans les environnements visés sont issues de ses travaux. Je n’ai cité la crypto que pour situer le personnage, l'apposition ne devait pas être comprise comme un rapport logique. J’aurais d’ailleurs peut-être mieux fait de parler de sécurité, terme plus général, puisqu'il ne fait pas que de la crypto.
[^] # Re: ordinateur vs humain
Posté par ɹǝıʌıʃO . En réponse au journal projet : commentaires didactiques d'une partie d'échecs. Évalué à 2.
Je ne vois pas du tout en quoi j'oublie ça. J'essaie d'expliquer que le fonctionnement d'un logiciel d'échecs est très différent du raisonnement d'un débutant, ce qui rend la tâche demandée très difficile.
[^] # Re: ordinateur vs humain
Posté par ɹǝıʌıʃO . En réponse au journal projet : commentaires didactiques d'une partie d'échecs. Évalué à 1.
Je vois difficilement comment ça pourrait donner quelque chose de pertinent. À titre d'exemple, considère le début de partie suivant (Spielmann - Walter, 1928) : 1.e4 c6 2.Cc3 d5 3.Cf3 Cf6 4.e5 Ce4 5.De2 Cxc3 6.dxc3 b6 7.Cd4 c5?
À ce stade, un programme qui cherche à expliquer l'erreur des noirs avec les critères habituels des débutants va probablement critiquer le fait d'avoir joué un coup de pion alors que les pièces ne sont pas développées ; en revanche, il ne dira rien sur le centre puisque 7…c5 prend le contrôle de la case centrale d4, ni sur l'initiative puisque le pion menace un cavalier. Le même débutant sera donc bien surpris d'apprendre que le bon coup était 7…d6, encore un coup de pion, et qui plus est, qui ne menace rien – on lui avait pourtant dit de prendre l'initiative, non ? L'explication est tout simplement qu'il fallait absolument empêcher les blancs de jouer 8.e5!, un coup qui ne développe aucune pièce et qui laisse le cavalier en prise… C'est pourtant un exemple typique de partie que l'on montre aux débutants, un programme qui se respecte devrait donc le traiter correctement.
[^] # Re: ordinateur vs humain
Posté par ɹǝıʌıʃO . En réponse au journal projet : commentaires didactiques d'une partie d'échecs. Évalué à 3.
Non, c'est nettement plus difficile que ça. Expliquer pourquoi un coup est fort est relativement simple. Ce qui est évoqué ici, c'est expliquer pourquoi un coup qu'un débutant envisagerait est faible, en lien avec son processus de prise de décision (celui de l'humain). C'est beaucoup plus complexe, parce qu'en général, pour l'ordinateur, un coup est faible parce qu'il permet une variante qui conduit l'adversaire à une bonne position, rarement parce qu'il néglige un critère humainement compréhensible en particulier. Ce genre d'explication (écrire un coup suivi d'un point d'interrogation et commenter « néglige le centre », « perd l'initiative », ou quelque chose dans le genre) est typiquement du travail d'humain, et généralement simplifié pour que le lecteur ait l'impression de suivre le commentaire. D'ailleurs, les meilleurs commentateurs pour le grand public sont les bons pédagogues, pas forcément les plus forts joueurs.
Commenter un coup faible nécessite donc de comprendre, dans une certaine mesure, comment l'humain réfléchit. Or il y en a difficilement deux qui réfléchissent de la même façon. Il y a ceux qui envisagent tout le temps des coups qui tendent des pièges grossiers sans faire progresser leur position, ceux qui ne pensent qu'à capturer tout le matériel adverse, ceux qui jettent toutes leurs pièces dans des attaques imaginaires… Il me parait nécessaire, pour expliquer pourquoi un coup est mauvais, de demander au joueur pourquoi il l'a choisi. C'est d'ailleurs l'approche de Jeremy Silman dans The amateur's mind. Et dès lors qu'on parle de comprendre, on est dans l'IA, et bien loin du minimax.
# ordinateur vs humain
Posté par ɹǝıʌıʃO . En réponse au journal projet : commentaires didactiques d'une partie d'échecs. Évalué à 10.
Facile à partir de l'ECO. Certaines transpositions ne seront pas résolues, mais de toutes façons on n'y peut rien.
Mmmmmmh. Déjà, dans l'ouverture, il faut choisir entre l'occuper ou le contrôler à distance, voire passer de l'un à l'autre, et c'est très compliqué. Le choix entre garder ou liquider la tension centrale est souvent très difficile, et parfois plus une affaire de goût qu'autre chose. Ensuite, il arrive qu'on relâche volontairement le contrôle du centre, ne serait-ce que temporairement, pour redéployer une pièce. Prends par exemple la variante Breyer de l'espagnole : 1. e4 e5 2. Cf3 Cc6 3. Fb5 a6 4. Fa4 Cf6 5. o-o Fe7 6. Te1 b5 7. Fb3 d6 8. c3 o-o 9. h3 Cb8 (le cavalier perd le contrôle des cases centrales e5 et d4) et par exemple, 10.d4 Cbd7 (le cavalier se redéploie). Note que le coup 9 … Cb8, non content de lâcher le centre, remet une pièce sur sa case de départ (un coup de dé-développement, en quelque sorte), ce qui contrevient d'un coup à deux conseils donnés aux débutants.
Vaste sujet. Il est important de connaitre les principaux éléments de structure de pions et les conseils généralement applicables, mais ce qui est encore plus important, c'est de savoir accepter une structure de pions abîmée en échange d'un autre déséquilibre. Et les pions doublés ou pendants, par exemple, sont parfois bien plus forts qu'on ne pourrait le penser. D'autre part, la structure de pions à un moment donné peut être trompeuse : on peut permettre à l'adversaire de « réparer » sa structure de pions si on sait qu'on est en mesure de la casser à nouveau plus tard. Le sujet du pion dame isolé mérite un livre à lui seul, et d'ailleurs il l'a (Winning pawn structures, de Baburin).
Le problème que je vois ici est que se laisser avoir par une simple fourchette est difficile à distinguer d'une autre grosse bourde, du genre déplacer sa dame vers une case où elle est en prise (sans compensation).
Qu'est-ce qu'un coup qui parait évident ? La réponse dépend totalement de celui à qui on pose la question, et pas seulement de son niveau, ça dépend aussi de sa façon de voir le jeu. Les agressifs voudront qu'on réfute leurs sacrifices bidons, les placides ne verront pas l'attaque qui les supplie d'être jouée, etc. Je ne vois vraiment pas comment formaliser le critère « coup paraissant évident ».
À mon avis, le problème est que tu cherches à faire évaluer par un ordinateur des critères que l'on donne aux humains pour les guider dans leur réflexion. Mais ces critères ne sont que cela, des guides. En réalité, ce qui compte vraiment, c'est de calculer des variantes, vite et bien. La centralisation, la structure de pions, l'espace, l'initiative, le contrôle d'un complexe de cases, la recherche d'une bonne case pour une pièce mineure, etc., peuvent — et doivent — guider dans le calcul des variantes, mais le cœur du jeu, c'est la tactique.
[^] # Re: J'ai acheté récemment
Posté par ɹǝıʌıʃO . En réponse au message quelle carte graphique pour Debian Wheezy ?. Évalué à 1.
Merci, voilà le genre de retours que je cherchais. Donc je suppose que n'importe quelle carte basée sur de G210 va fonctionner.
[^] # Re: Série 6000.
Posté par ɹǝıʌıʃO . En réponse au message quelle carte graphique pour Debian Wheezy ?. Évalué à 1.
OK, merci. On trouve dans le commerce des 6450 avec sorties DVI et VGA, donc à privilégier pour ceux qui ont encore appareils en VGA.
[^] # Re: Intel ou Nvidia
Posté par ɹǝıʌıʃO . En réponse au message quelle carte graphique pour Debian Wheezy ?. Évalué à 1.
Bon eh bien ça ne m'arrange pas : elle ne se vend plus, si ce n'est d'occasion. Merci quand même, celle de ta machine pro est peut-être plus récente…
[^] # Re: Intel ou Nvidia
Posté par ɹǝıʌıʃO . En réponse au message quelle carte graphique pour Debian Wheezy ?. Évalué à 2.
D'autre part, je ne trouve pas de trace d'une Nvidia GT 460. Je trouve une GTX 460 et une GT 640, ce ne serait pas l'une des deux ?
[^] # Re: Intel HD
Posté par ɹǝıʌıʃO . En réponse au message quelle carte graphique pour Debian Wheezy ?. Évalué à 2.
Merci, mais c'est pour ajouter à une tour existante, et je ne me vois vraiment pas changer le CPU et/ou la carte mère pour ça.
[^] # Re: Intel ou Nvidia
Posté par ɹǝıʌıʃO . En réponse au message quelle carte graphique pour Debian Wheezy ?. Évalué à 2.
OK mais peux-tu être plus précis sur le modèle ? Quels GPU ont tes cartes Nvidia ?
[^] # Re: nb
Posté par ɹǝıʌıʃO . En réponse au journal Un cours en français sur la compilation : ne boudons pas notre plaisir !. Évalué à 3.
Xavier a sans doute voulu dire détonne (avec deux n, pour ne pas mettre le feu aux poudres).
[^] # Re: Avant de commencer
Posté par ɹǝıʌıʃO . En réponse au journal Conseils aux libristes, 1ere partie: eviter de sous-estimer la competition sur le plan technique. Évalué à 6.
Effectivement, c'est beaucoup. Je propose d'en faire les briques de bases du futur palais des congres, ce qui fera du boulot pour l'entreprise de maconnerie.
[^] # Légende urbaine détectée
Posté par ɹǝıʌıʃO . En réponse au journal Rapport sur la résilience de l'Internet en France. Évalué à 3.
Pas du tout. Voir la Brève histoire d'Internet de l'Internet Society :
It was from the RAND study that the false rumor started claiming that the ARPANET was somehow related to building a network resistant to nuclear war. This was never true of the ARPANET, only the unrelated RAND study on secure voice considered nuclear war. However, the later work on Internetting did emphasize robustness and survivability, including the capability to withstand losses of large portions of the underlying networks.
# cherchez l'intrus
Posté par ɹǝıʌıʃO . En réponse à la dépêche Revue de presse de l'April pour la semaine 13 de l'année 2012. Évalué à 4.
L'article de "bug brother" vient de faire disjoncter mon foutaisomètre. Tout ça pour ça : leboncoin utilise un serveur Apache. S'ils avaient eu IIS ou n'importe quoi d'autre, le résultat aurait été exactement le même.
# Il manque les arts martiaux
Posté par ɹǝıʌıʃO . En réponse au sondage Et toi, lecteur de LinuxFr.org, quel sport pratiques-tu ?. Évalué à 4.
À ne pas confondre avec les sports de combat, c'est justement ce qui m'a poussé vers l'aïkido. Pratiquer avec un partenaire me convient beaucoup mieux que contre un adversaire.
# ch c'h
Posté par ɹǝıʌıʃO . En réponse à la dépêche Nouvelle version d'Unicode : la 6.1.0. Évalué à 2.
En attendant, ch et c'h s'écrivent toujours sous forme de deux et trois caractères, respectivement, ce qui complique le traitement des langues qui les considèrent comme un seul caractère. C'est le cas au moins du breton pour les deux, du tchèque pour ch. Et ce, alors même qu'il existe des caractères pour certaines ligatures, comme ff (ff). Mais voyons le bon côté des choses : avec un peu de chance, à force d'ajouter des hiéroglyphes et des kikoolols, on finira par en trouver des ressemblants.
# correction d'orthographe
Posté par ɹǝıʌıʃO . En réponse à la dépêche Appels à rédacteurs sur LinuxFr.org !. Évalué à 10.
C'est gentil de la part des modérateurs de corriger l'orthographe. Je voudrais tout de même profiter de cette dépêche pour demander une nouvelle fonctionnalité : ne pas corriger ce qui n'est pas faux. J'avais écrit ma dépêche sur la vulnérabilité des tables de hachage à une attaque basée sur la complexité algorithmique en appliquant les rectifications orthographiques de 1990. Un modérateur a « corrigé » vers l'orthographe pré-1990 sur une partie seulement du texte. Le résultat est un mélange des deux, ce qui est autorisé mais moche. Tout ça n'est évidemment pas grave et j'encourage vivement les modérateurs à continuer de corriger les énormités qui piquent les yeux.
[^] # Re: Correction
Posté par ɹǝıʌıʃO . En réponse au journal Fermeture de la tribune. Évalué à 9.
Tiens, étrangement, Alternatives Économiques et ses
forkspublications sœurs (Alternatives Internationales, etc.) ne se meurent pas du tout à ma connaissance. Leur recette : vivre essentiellement des abonnements, avec un modèle mixte papier + Internet, des articles écrits par des journalistes et des chercheurs qui parlent de leur spécialité. Comme quoi, ça existe.[^] # Re: Turing-incomplétude
Posté par ɹǝıʌıʃO . En réponse à la dépêche UEFI Secure Boot et les tablettes/téléphones Windows 8 - conclusion ?. Évalué à 2.
Quel rapport avec quoi que ce soit ? On peut évidemment écrire une machine de Turing (limitée par la RAM) sous Windows 8.
[^] # Re: Merci à linuxfr.org
Posté par ɹǝıʌıʃO . En réponse à la dépêche Meilleurs contributeurs LinuxFr.org : les gagnants de décembre 2011. Évalué à 2.
Merci de même, on ne s'attend pas à recevoir un livre en écrivant une dépêche et ça fait très plaisir. Et merci aux partenaires, bien sûr.
[^] # Re: Perl et la complexité
Posté par ɹǝıʌıʃO . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 3.
Oui, du moins si d'autres conditions sont remplies. Par exemple, sa façon d'évacuer le problème d'Unicode est une plaisanterie.
Ça, c'est beaucoup moins sûr. Pour que cette solution ait un intérêt, il faudrait être sûr que la construction de l'automate ne coute pas plus cher que l'exécution du code actuel. Or, tout comme il existe des cas limites pour la méthode utilisée par Perl, il existe des cas limites pour les automates, avec la différence que l'explosion ne concerne pas seulement le temps d'exécution (facile à contrôler avec un chien de garde), mais une combinaison de temps et de mémoire, et, selon le type d'automate, à la construction et/ou à l'exécution. Voilà qui devient amusant à surveiller…
Par exemple, classiquement, les grosses répétitions et les grandes classes de caractères posent problème. Est-il vraiment une bonne idée d'avoir une implémentation pour ga?bu et une autre pour \w{2,3000}ga?bu : c'est douteux, surtout s'il faut entrer dans le cas pathologique pour s'apercevoir qu'on aurait mieux fait de ne pas y aller. Mais tout ça, et bien plus, est couvert dans la discussion ci-dessus.
[^] # Re: Perl et la complexité
Posté par ɹǝıʌıʃO . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 3.
Attention : l'article parle des expressions régulières au sens académique du terme, pas au sens « Perl » du terme. Voir par exemple cette discussion à laquelle participent des développeurs de Perl et l'auteur de l'article en question. En particulier, il a fallu un article paru plus tard pour avoir des NFA / DFA prenant en charge les références arrière, et ce n'est que l'un des aspects qui rendent l'article inapplicable en l'état.
[^] # Re: N'optimiser que si nécessaire
Posté par ɹǝıʌıʃO . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 1.
Voir introsort pour ceux que ça intéresse. Au passage, de nombreux environnements d’exécution utilisent « quicksort » pour trier, sans plus de précision dans leur doc (je n’ai pas regardé le code source). Si ce n’est pas une version de quicksort intégrant une astuce pour éviter le cas pathologique, ça peut donner des idées pour la prochaine fois…
[^] # Re: "et paf l'attaque"
Posté par ɹǝıʌıʃO . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 3.
En principe oui, mais avec une probabilité extrêmement faible. Si un risque aussi faible n’est pas acceptable, il vaut mieux laisser tomber directement les tables de hachage et utiliser une structure de données (l’un des nombreux types d’arbres…) qui garantit un pire cas en n log n (voire utiliser des tables de hachage que l'on remplace à la volée par des arbres si on détecte un scénario pathologique). Et toujours si on refuse un risque aussi faible, il faut tellement tout contrôler qu'il est pratiquement impensable d’utiliser un langage de haut niveau (haut comme Perl, C étant considéré comme bas).
[^] # Re: Bernstein ???
Posté par ɹǝıʌıʃO . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 8.
En crypto, non, mais ce n'est pas le sujet. Les fonctions de hachage pour tables de hachage dans les environnements visés sont issues de ses travaux. Je n’ai cité la crypto que pour situer le personnage, l'apposition ne devait pas être comprise comme un rapport logique. J’aurais d’ailleurs peut-être mieux fait de parler de sécurité, terme plus général, puisqu'il ne fait pas que de la crypto.