Exos sympas MP(*)

[Arky]

En pratique, c'est l'idée mais c'est vrai que fondamentalement on peut se dire que c'est du gachis. En fait le gachis serait en realité d'allouer une taille de memoire et un algorithme d'exploitation adapté à chaque int. Vouloir en faire moins nous prendrait alors plus de temps, ce qui n'est pas viable dans la plupart des utilisations de l'informatique, ou l'efficacité est ce qu'il y a de plus important (apres le fait d'avoir qqch de correct).
Du coup V@J est dans le vrai si on etait dans une situation ideale et generale. Mais 99% des cas entrent dans un meme modele, qu'on peut donc "constantiser", comme l'a fait Fakbill, mais peut-etre en precisant où l'on a fait des abus.
Maintenant que ce point est eclairci, on peut retourner a notre jeu de "qui aura la permutation la plus uniforme en O(n) ?".

[fakbill]

Maintenant que ce point est eclairci, on peut retourner a notre jeu de "qui aura la permutation la plus uniforme en O(n) ?".

Gni??? Tu veux un shuffle uniforme? Certains algo le sont parfaitement et d'autres pas.

[Arky]

Désolé j'avais pas vu qu'on s'était arrêté là.
Bah en fait après coup je me suis mal exprimé. Je me disais qu'une petite analyse de l'uniformité de ton shuffle pourrait être cool. Du coup je peux la faire histoire de conclure. Pour ça on va supposer que ton tableau est initialement trié.

Pourquoi toutes les permutations sont générées ?

Prenons une permutation arbitraire. Appliquons lui l'algorithme-type de tri par insertion : on a évidemment un tableau trié. Or, appliquer le principe en sens inverse reviens à un cas de ton shuffle. Donc toute les permutations sont générées.

Pourquoi le suffle est-il uniforme ?

Sachant qu'on a bien une proba $ 1/n $ pour la première itération, il nous suffit - si on veut pouvoir récurer proprement - de montrer que chaque permutation n'est générée que d'une unique façon.
Imaginons deux procédés différents. On se place à la première étape (qu'on notera l'étape n° $ k $) où ils diffèrent. Alors il est évident que dans les deux tableaux, les valeurs indexées par $ n-k $ sont différentes à l'étape $ k $, puis ne bougent plus. Donc les permutations sont différentes.

[fakbill]

oui et le gag c'est qu'il est facile de se tromper et de code un shuffle qui n'est pas uniforme...c'est piégeux.

[Artix]

Tentative de réanimation du topic :

Un barman aveugle joue au jeu suivant avec un client : il a devant lui un plateau sur lequel sont disposés quatre verres formant un carré. Chacun de ces verres peut être retourné ou non, sans que le barman ne le sache. Le but de ce dernier est de s’arranger pour que tous les verres soient tournés dans le même sens. Pour ce faire, il peut à chaque tour choisir l’une des trois actions suivantes :
–
tourner l’un des verres ;
–
tourner deux verres voisins ;
–
tourner deux verres opposés ;

mais pour corser la difficulté, le client peut tourner le plateau d’un nombre quelconque de quart de tours entre chacune des actions du barman. Le jeu s’arrête dès qu’une des deux positions gagnantes est atteinte.

1. Montrer qu’on peut restreindre à quatre le nombre de configurations différentes, puis représenter les actions possibles du jeu par un automate non déterministe.
2. Déterminiser cet automate et en déduire une stratégie gagnante pour le barman

N'hésitez pas à poster des exercices !

[LeCaRiBoU]

Ciel mon topic

Dans un genre totalement différent, j'ai un truc cool qui n'est pas vraiment un exercice:

Ecrire le code suivant:

Code : Tout sélectionner

let id x = x in
     (id 1, id 1.);;

Jusque là pas de problème, (id 1, id 1.) est de type int * float, et ça compile.
Maintenant, tapez ça:

Code : Tout sélectionner

let id x = x in
let id_composee = id id in
     (id_composee 1, id_composee 1.);;

Et là c'est le drame, ça ne compile pas:

Code : Tout sélectionner

Error: This expression has type float but an expression was expected of type
         int

Essayez d'expliquer pourquoi.

Bon c'est évidemment clairement hors-programme je demande pas forcément d'explication très poussée, mais le but c'est surtout de montrer en quoi il faut arrêter de se toucher sur Python, et de voir à quel point OCaml c'est cool.

[fakbill]

mais le but c'est surtout de montrer en quoi il faut arrêter de se toucher sur Python, et de voir à quel point OCaml c'est cool.

N'importe quoi
Ca dépend de ce qu'on veut en faire. Si on veut faire de l'analyse de données python est un très bon outil. Python est un langage très très pragmatique. Le duck typing en est une preuve. On ne fiche du type en tant que type, on regarde juste si l'objet a une méthode qui permet de faire ce qui est demandé. Si cette méthode existe alors le langage est content et l'utilise. Si on écrit def f(a,b): return a+b alors ca marchera avec n'importe quoi du moment que "ca sait s'ajouter".

OCaml c'est cool du point de vue de l'informatique théorique et par ex du typage. En dehors de ce monde, c'est utilisable mais pas beaucoup utilisé. Un langage c'est surtout une communauté. Celle de python dans le monde du traitement de données est immense. Celle de OCaml en dehors de l'info ""théorique"" est petite.

[-L-C-]

Ciel mon topic

Dans un genre totalement différent, j'ai un truc cool qui n'est pas vraiment un exercice:

Ecrire le code suivant:

Code : Tout sélectionner

let id x = x in
     (id 1, id 1.);;

Jusque là pas de problème, (id 1, id 1.) est de type int * float, et ça compile.
Maintenant, tapez ça:

Code : Tout sélectionner

let id x = x in
let id_composee = id id in
     (id_composee 1, id_composee 1.);;

Et là c'est le drame, ça ne compile pas:

Code : Tout sélectionner

Error: This expression has type float but an expression was expected of type
         int

Essayez d'expliquer pourquoi.

Bon c'est évidemment clairement hors-programme je demande pas forcément d'explication très poussée, mais le but c'est surtout de montrer en quoi il faut arrêter de se toucher sur Python, et de voir à quel point OCaml c'est cool.

C'est un exemple intéressant, du coup j'ai essayé de m'intéresser à la "value restriction" de Ocaml (il y a un bon gros pavé http://caml.inria.fr/pub/papers/garrigu ... wflp04.pdf) et d'autres articles plus sommaires sur le web. Ben je trouve finalement que ton exemple montre les limites de Ocaml qui essaye de mélanger de l'impératif et du fonctionnel très poussé (et j'adore le fonctionnel, mais ce n'est pas adapté à tout).

Même si j'ai un temps adoré Ocaml, python me plaît encore plus. Pour moi, il est loin d'être réservé à l'analyse des données. Petit lien qui résume assez bien ma pensée sur ce langage : http://sametmax.com/python-meilleur-nul ... t-partout/
Le gros soucis de python, c'est la perf (et le parallélisme qui est un beau bordel avec le GIL). Au travail, je n'utilise pas que python parce que j'ai parfois besoin d'un programme très performant (en mémoire et en temps). Chez moi, c'est python parce que c'est hyper productif.

Je me suis remis à OCaml récemment, et finalement, j'ai trouvé le code peu lisible, et une certaine frustration à n'utiliser que du fonctionnel.

[fakbill]

Pour moi, il est loin d'être réservé à l'analyse des données

heu en fait un programme ca fait toujours de l'Analyse de données donc python sait tout faire

Au travail, je n'utilise pas que python parce que j'ai parfois besoin d'un programme très performant (en mémoire et en temps).

Ca dépend. python est lent c'est certain. Cependant, si c'est pour aller lire une valeur dans fichier txt, ce n'est pas la lenteur de python qui va limiter. Si ca prend 1ms ou 2ms ca ne change rien. Par contre, tu vas mettres 5min à écire le code en python et 1h en C++
Si tu as besoin de faire des calculs numériques, tu as scipy et numpy (et matplotlib pour faire les graphs)....et là...ce n'est PAS lent car justement c'est en fait appels à des lib en C ou en fortran hyper optimisées (blas, atlas et autres). Ces libs sont multi proc (si elles ont été compliées avec les bonnes options).
Le GIL n'est pas le problème. Tu as des module python pour faire du processing en // (encore une fois, on parle là le processing de fichiers par exemple, PAS de calculs...pour les calculs il y a numpy et scipy).
Si vraiment tu as un bout en pur pyhton qui est trop lent pour toi, tu peux toujours taper dans cython, numba et autres...mais c'est rare.

Quel est ton usecase? qu'est ce qui fait que c'est trop lent?

[LeCaRiBoU]

Bon j'aurais peut-être du argumenter ma pensée.

C'est clair que si tu veux exécuter un petit script à la con, python est très bien; Mais à vrai dire, OCaml aussi, et pas mal d'autres langages.
De même c'est pas forcément de la vitesse que je parle, puisque scipy fait ça très bien.

Ce dont je parle, c'est d'une mode qui consiste à toujours conseiller python pour tout (dans mon cas, il s'agit essentiellement de concours de prog), sous prétexte que:
- Les biblis python sont énormes. Sauf que à vrai dire, même en OCaml tu as pas mal de bibliothèques sur tout et n'importe quoi sur internet. Bon après je dis peut-être ça parce que mes préoccupations sont loin du monde de l'entreprise, mais même sur des trucs un peu pointus genre diagramme de Voronoï ou listes dansantes, j'ai trouvé des implémentations en OCaml (attention, je suis bien conscient que la communauté OCaml est très loin d'être aussi importante que celle de Python et elle est probablement très déficiente pour un ingé lambda, mais mon coté utopiste me fait dire qu'il appartient à tout un chacun de proposer de quoi améliorer son langage favori....)
[supprimé après vérification]
- Et surtout, en Python tout compile. Alors, en Python, certes tout compile, mais ça n'a juste aucun intérêt si ça ne fait pas exactement ce que tu veux, et si c'est pour qu'on te signale une erreur 23 lignes plus bas. Typiquement, pour reprendre l'exemple de mes concours de prog, je sais qu'à partir du moment où je fais gaffe aux dépassement de tableau et que je découpe bien mon code, 99.999% des erreurs que je pourrais faire me seront signalées clairement, et de fait je n'aurai qu'à me concentrer sur le fonctionnement général de mon programme; ce qui n'était clairement pas le cas quand je programmais en python.

Bon après, je me rend compte en les écrivant que modulo le dernier, mes arguments s'appliquent beaucoup moins à un ingé lambda qui a besoin de pisser 2 lignes de codes vite fait pour vérifier une intuition. Mais pour des secteurs type finance/aéronautiques/etc... où il peut y avoir besoin de calculs à la fois super lourds et importants et où on s'attache au moindre détail (l'exemple classique étant Google qui vu la taille de ses bases de données est obligé d'envisager la probabilité qu'un bit soit modifié par un rayon cosmique), je trouve dommage qu'OCaml n'ait pas plus la côte. D'ailleurs, Jane Street, une "entreprise de trading" (je n'ai aucune idée de comment ça s'appelle dans le milieu ), utilise OCaml principalement pour ces questions de sécurité.