[ théorie ] - L'algorithme le plus balèze que vous connaissez ?

- L'algorithme le plus balèze que vous connaissez ? [ théorie ] - Algo - Programmation

Marsh Posté le 13-02-2003 à 22:42:30    

Quel est l'algorithme qui a vous a épaté par sa puissance, ou qui vous a donné du fil à retordre pour le comprendre, ou tout simplement parce que c'est votre préféré ?

Reply

Marsh Posté le 13-02-2003 à 22:42:30   

Reply

Marsh Posté le 13-02-2003 à 22:43:33    

Joce !

Reply

Marsh Posté le 13-02-2003 à 22:44:27    

Je suis un fan du VQ :D

Reply

Marsh Posté le 13-02-2003 à 23:16:24    

MagicSort m'a laissé sur le c*l :)
 
algo pourtant très simple, mais thérorie derrière à devenir chèvre


Message édité par MagicBuzz le 13-02-2003 à 23:16:47
Reply

Marsh Posté le 13-02-2003 à 23:25:48    

MagicBuzz a écrit :

MagicSort m'a laissé sur le c*l :)
 
algo pourtant très simple, mais thérorie derrière à devenir chèvre


 
c'est kwoaaaaaaaaaaa ?

Reply

Marsh Posté le 13-02-2003 à 23:27:00    

BJOne a écrit :


 
c'est kwoaaaaaaaaaaa ?


 
un algo de tri [:dawa]

Reply

Marsh Posté le 13-02-2003 à 23:27:40    

je m'en doute, mais ça consiste en kwoi comme tri, j'ai boulayé avec google pas trouvé ?


Message édité par bjone le 13-02-2003 à 23:27:49
Reply

Marsh Posté le 13-02-2003 à 23:33:09    

Osama a écrit :

Quel est l'algorithme qui a vous a épaté par sa puissance, ou qui vous a donné du fil à retordre pour le comprendre, ou tout simplement parce que c'est votre préféré ?


puisqu'on en parle, la transformée de fourier justement, même si c'est pas vraiment un algo !  :sweat:


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 13-02-2003 à 23:33:14    

BJOne a écrit :

je m'en doute, mais ça consiste en kwoi comme tri, j'ai boulayé avec google pas trouvé ?


Ben oui c'est MagicBuzz qui l'a pondu un soir de fiesta.
Il a toujours pas réussi à comprendre ce qu'il avait écrit.

Reply

Marsh Posté le 13-02-2003 à 23:34:11    

:lol:

Reply

Marsh Posté le 13-02-2003 à 23:34:11   

Reply

Marsh Posté le 13-02-2003 à 23:45:14    

verdoux a écrit :


Ben oui c'est MagicBuzz qui l'a pondu un soir de fiesta.
Il a toujours pas réussi à comprendre ce qu'il avait écrit.


Ca m'est déjà arrivé :D
 
Sinon, si qq1 pouvait retrouver cet algo justement...
Parceque je sais plus du tous où je l'avais trouvé.
 
 
Sinon, pour résumer, J'avais un tableau de 200 000 lignes en VB *sic* que je devais trier.
 
Avec un algo de tri genre tri à bulle, ct même pas la peine, je pouvais fumer un paquet de cloppe avant que ça termine.
 
Avec QuickSort, ça mettait plus de 15 minutes.
 
Avec MagicSort ben... Même pas une minute. :ouch:
 
En fait, MagicSort, quand on tombe bien dans le bon cas (il faut que le nombre de lignes soit suppérieur à l'intervalle entre la plus petite valeur et la plus grande, pour rentrer dans le cas où ça bombarde) il éclate QuickSort d'une force monstrueuse.
 
En fait, il parcourt 1 fois et demi ton tableau, un point c'est tout (quand on est dans le bon cas, si les valeurs sont trop dispersées, c'est pire que le tri à bulle)
 
J'avais trouvé un site ou l'algo était bien expliqué, mais j'ai relu une dizaine de vois, puis je me suis contenté de transcrire le code C en VB pour mes besoin sans chercher à comprendre plus :D Tout ce que je sais, c'est que comme le tutorial disait "It's like Magic !"


Message édité par MagicBuzz le 13-02-2003 à 23:45:54
Reply

Marsh Posté le 13-02-2003 à 23:55:04    

ton histoire ressemble beaucoup a une vieille legende ... pas de traces sur le web, ni dans les bouquins d'algos, juste quelques rumeurs ..
 
non pas que je sois dubitatif ... mais plutot curieux.

Reply

Marsh Posté le 13-02-2003 à 23:55:47    

Rob Roy a écrit :

ton histoire ressemble beaucoup a une vieille legende ... pas de traces sur le web, ni dans les bouquins d'algos, juste quelques rumeurs ..
 
non pas que je sois dubitatif ... mais plutot curieux.


 
y'a des algos de tri qui n'effectuent aucune comparaison :D

Reply

Marsh Posté le 13-02-2003 à 23:58:38    

genre le tri compteur je croa non ?

Reply

Marsh Posté le 14-02-2003 à 00:01:10    

Reply

Marsh Posté le 14-02-2003 à 00:13:23    

le tri compteur ou par comptage, non, mais le tri a vec l'algo de la "trieuse", aucune comparaison
 
edit: à moi que je confonde compteur et tri par position


Message édité par Taz le 14-02-2003 à 00:15:09
Reply

Marsh Posté le 14-02-2003 à 00:16:00    

le truc c'est que les éléments dans la liste
sont déjà triés (pas besoin de connaitre l'ordre
relatif des élements lorsqu'on connait l'ordre absolu).
 
tri des mécanographes -> la machine n'interprète pas
la valeur des bits mais place les cartes dans le bon  
chemin parce que tout est cablé.
 
LeGreg


---------------
voxel terrain render engine | animation mentor
Reply

Marsh Posté le 14-02-2003 à 00:19:32    

Harkonnen a écrit :


puisqu'on en parle, la transformée de fourier justement, même si c'est pas vraiment un algo !  :sweat:  


 
 :lol:


---------------
[ Canon EOS 30D ] (Grip + Canon 50mm f/1.4 + Canon 18-55mm USM + Tamron 70-300mm Di LD Macro)  [Galerie perso]
Reply

Marsh Posté le 14-02-2003 à 00:22:02    

Une très bonne page pour vois les différents algos de tri :
 
http://www.cs.ubc.ca/spider/harris [...] -demo.html
 
Sinon, ouais, vu la rapidité et la méthode, ce que j'avais trouvé sour le nom de "MagicSort" semble être le "RadixSort"

Reply

Marsh Posté le 14-02-2003 à 00:33:29    

Sinon, pour les tris débiles, j'en avais trouvé un très rapide que j'avais fais qui imposait la même limitation que ce "MagicSort", pour les tris entiers.
 
Il fallait connaître le min et le max de l'intervalle.
Il fallait que ces la diff entre ces deux nombre soit inférieure à la taille du tableau (afin d'éviter des pertes de place mémoire trop importante) et ça n'était pas applicable aux très gros tableaux (sinon, a plus de place en RAM :D)
 
Source en VB du tri ensuite :
 
for i = lbound(tabOri) to ubound(tabTmp)
   tabTmp(tabOri(i)) = tabTmp(tabOri(i)) + 1
next
 
j = lbound(tabTmp)
for i = lbound(tabOri), ubound(tabTmp)
   do while j < ubound(tabTmp) and tabTmp(j) = 0
     j = j + 1
   loop
   tabOri(i) = j
   tabTmp(j) = tabTmp(j) - 1
next
 
Et hop ! Le tableau trié en 1 passage + (min - max) / nblignes


Message édité par MagicBuzz le 14-02-2003 à 00:35:05
Reply

Marsh Posté le 14-02-2003 à 00:37:02    

La possibilite de tout cabler est à la fois une propriété
intéressante des machines électronique et à la fois
une chose dont on s'éloigne sur les machines actuelles
parce que une machine qui fait qu'une seule chose même si elle le fait trés bien est le plus souvent trop coûteuse a mettre en oeuvre. Et les économies que l'on fait le sont sur les grandes échelles.
 
On observe un processus similaire avec le code qui s'automodifie.
Aucun doute qu'on obtiendrait une performance optimale dans tous les cas de figure avec du code qui s'automodifierait pour accélérer les sections critiques (en vitesse).
Pourtant j'observe très peu de code automodifié en regardant autour de moi ou alors ils le sont de façon très codifié, très limité (chargement de librairies dynamiques, choix des optimisations au lancement etc..).
Pourquoi? a mon avis parce qu'ils sont impossibles à maintenir et surtout parce que ces économies d'échelles permettent d'envisager dans le temps qu'il faudrait pour mettre en oeuvre ces techniques et sans la douleur pour les maintenir, un matériel qui rendra obsolète cette recherche de performance (déplacement du goulot d'étranglement).
 
LeGreg


---------------
voxel terrain render engine | animation mentor
Reply

Marsh Posté le 14-02-2003 à 00:38:03    

les algo de cryptage sont assez balez aussi
Chiffrement Vigenàre
Enigma
DES
RSA
PGP
pour ne citer ke ceula...

Reply

Marsh Posté le 14-02-2003 à 00:43:34    

crypto évidememnt (en terme de chiffre dépense dans la recherche d'algorithmes fondamentaux).
 
Je voudrais aussi citer le sequençage des génomes qui etait fut un temps (l'est-il encore?) un moteur pour toute la recherche avançée sur le traîtement des chaînes. (pattern matching, suffix trees).
 
Legreg


---------------
voxel terrain render engine | animation mentor
Reply

Marsh Posté le 14-02-2003 à 01:03:49    

Il ya effectivement de beaux algo dans la recherche et comparaison de sequences biologiques (Blast pour le plus connu). Il s'agit en general de methode heuristiques associant pas mal de techniques entre elles (hash, recherche de scores dans une matrices suivant des processus plus ou moins compliques, chaines de markov, etc...). J'avais aussi ete bluffe par un algo de randomization (merlenne twister si mes souvenirs sont bons).
 
Il y a aussi une classe elegante: les algorithmes genetiques.


---------------
You have the right to remain silent. You are warned that anything you say can will be taken down used as evidence against you///Il n'y a pas de théorie de l'évolution. Juste une liste d'espèces que Chuck Norris autorise à survivre.
Reply

Marsh Posté le 14-02-2003 à 02:58:44    

un qui m'a hachement impressionne c'est le test de primalite en temps polynomial, il est pas tres vieux en plus, je sais plus ou j'avais vu ca... en plus, l'algo tiens en moins de 10 lignes, c'etait monstrueux

Reply

Marsh Posté le 14-02-2003 à 07:22:16    

on a implementer vignenere en cours cette année, alors ou il y ades subtilités que j'ai pas vues, ou c'est l'algo l plus pourri que je connaisse ... ;)

Reply

Marsh Posté le 14-02-2003 à 11:35:58    

Osama a écrit :

Quel est l'algorithme qui a vous a épaté par sa puissance, ou qui vous a donné du fil à retordre pour le comprendre, ou tout simplement parce que c'est votre préféré ?


Il y a un fort joli algorithme de résolution de système linéaire, avec une belle théorie et des résultats de performance bien supérieurs aux autres dans la plupart des cas : le GMRES.
Bon évidement, c'est très mathématques et je doute que la plupart des codeurs fous en ai besoin un jour, mais si vous faites du calcul numérique, vous devez le connaitre.


---------------
Gérez votre collection de BD en ligne ! ---- Electro-jazzy song ---- Dazie Mae - jazzy/bluesy/cabaret et plus si affinité
Reply

Marsh Posté le 14-02-2003 à 12:00:48    

tomlameche a écrit :


Il y a un fort joli algorithme de résolution de système linéaire, avec une belle théorie et des résultats de performance bien supérieurs aux autres dans la plupart des cas : le GMRES.
Bon évidement, c'est très mathématques et je doute que la plupart des codeurs fous en ai besoin un jour, mais si vous faites du calcul numérique, vous devez le connaitre.  


 
je connais mais c est pas le plus baleze :
 
resolution directed un systeme lineaire par une methode multifrontale c est mucho + complique à comprendre
 
Enfin je suis d accord avec toi les algos les plus balezes sont en maths appliquees !!!

Reply

Marsh Posté le 18-02-2003 à 22:29:43    

Hello tout le monde,
 
Etant assez débutant dans le domaine, je suis toujours ébahi devant des mécanismes aussi simples que le parcours largeur ou profondeur d'un graphe à l'aide respectivement une file et une pile, ou des "astuces" du type schéma de Hörner ou méthode de Karatsuba pour la multiplication. Toutes ces "petites" choses me font bien triper =)
 
A+


Message édité par Evadream -jbd- le 18-02-2003 à 22:30:41

---------------
Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live - Martin Golding
Reply

Marsh Posté le 27-02-2003 à 10:30:24    

Pour moi, les algos sont comme les formules en math ou en physique : les plus balèzes sont ceux qui sont à la fois d'une simplicité désarmante et d'une puissance ahurissante (je pense par exemple, en physique, à la célèbre relation entre masse et énergie énoncée par Einstein).

Reply

Marsh Posté le 07-03-2003 à 11:07:01    

Perso, c'etait un algo de verification dans un multi-graphe orienté...
Pour ceux a qui ca dit quelque-chose, c'etait un mélange entre parcours prioritairement en largeur, calcul des composantes fortement connexes, et je sais plus trop quoi...
 
Le genre d'algo qui en maths est déjà assez compliqué, faut penser à tous les cas limites, et quand on veut le transcrire en C là on est vraiment dans la merde. :)
 

Reply

Marsh Posté le 25-03-2003 à 21:26:00    

le tri à bulle :D (2 semaines d'algo inside)
ah si sinon en sup on avait fait avec maple un prog de criptage avec les nombres premiers : c t très sympha :D


Message édité par usa_satriani le 25-03-2003 à 21:26:25

---------------
Ce monde n'est qu'une vaste entreprise à se foutre du monde. Céline
Reply

Marsh Posté le 25-03-2003 à 21:50:07    

Euh... MDR.
 
Un programme qui affiche les puissances de 0 à I d'un nombre X :lol:
 
http://forum.hardware.fr/forum2.ph [...] h=&subcat=

Reply

Marsh Posté le 28-03-2003 à 15:20:02    

la fonction d'ackermann, je pense est une bon exemple d'algo bien relou...
sinon en 3d, ya les algos de Decasteljau, Béziers, voir même bresenheim, qui sont vraiment relou a implémenter ...(genre de casteljau, 4 ou 5 for imbriqué ...)


---------------
coming soon
Reply

Marsh Posté le 28-03-2003 à 16:14:06    

moi j'ai pas d'algo en tete, mais la formule de Gauss qui donne la somme des n premiers entiers, pour rappel n(n+1)/2 m'a bien marqué ! D'après l'histoire, il l'a trouvé a 5 ans quand son prof lui avait donné une addition a la con pour l'occuper parce qu'il s'emmerder en cours  :D  
 
Le petit gauss s'est alors rendu compte qu'en ecrivant la somme deux fois mais en ordre inverse, on obtenait toujours le meme nombre en sommant verticalement :
 


somme a calculer     =   1  +  2  + ... + n-1 + n
somme a calculer     =   n  + n-1 + ... +  2  + 1
somme a calculer * 2 =  n+1   n+1         n+1  n+1

 
 
 :)


---------------
get amaroK plugin
Reply

Marsh Posté le 28-03-2003 à 19:31:56    

ouai c clair :D Gauss powaaaaaaaaaaaaaa.

Reply

Marsh Posté le 28-03-2003 à 19:38:57    

usa_satriani a écrit :

ouai c clair :D Gauss powaaaaaaaaaaaaaa.


 
Ca me rappelle Niels Bohr (physicien). Pendant un oral on lui demande "Comment mesurer la hauteur d'un immeuble avec un barometere ?" Et lui de repondre... On monte en haut de l'immeuble, on laisse tomber le baro et on mesure le temps qu'il met pour arriver en bas [:ddr555]
 
Sinon je suis assez fier de mon algo d'ecriture XML avec gestion des tags ouverts/fermes


---------------
And I looked, and behold a pale horse: and his name that sat on him was Death, and Hell followed with him. Revelations 6:8
Reply

Marsh Posté le 28-03-2003 à 19:40:40    

ciler a écrit :


 
Ca me rappelle Niels Bohr (physicien). Pendant un oral on lui demande "Comment mesurer la hauteur d'un immeuble avec un barometere ?" Et lui de repondre... On monte en haut de l'immeuble, on laisse tomber le baro et on mesure le temps qu'il met pour arriver en bas [:ddr555]
 
Putin trop marant ça  :lol:  
 
Sinon je suis assez fier de mon algo d'ecriture XML avec gestion des tags ouverts/fermes  
 
désolé mais mon nivo me permet pas de piger ca :cry:  

Reply

Marsh Posté le 28-03-2003 à 19:42:50    

MagicBuzz a écrit :


Ca m'est déjà arrivé :D
 
Sinon, si qq1 pouvait retrouver cet algo justement...
Parceque je sais plus du tous où je l'avais trouvé.
 
 
Sinon, pour résumer, J'avais un tableau de 200 000 lignes en VB *sic* que je devais trier.
 
Avec un algo de tri genre tri à bulle, ct même pas la peine, je pouvais fumer un paquet de cloppe avant que ça termine.
 
Avec QuickSort, ça mettait plus de 15 minutes.
 
Avec MagicSort ben... Même pas une minute. :ouch:
 
En fait, MagicSort, quand on tombe bien dans le bon cas (il faut que le nombre de lignes soit suppérieur à l'intervalle entre la plus petite valeur et la plus grande, pour rentrer dans le cas où ça bombarde) il éclate QuickSort d'une force monstrueuse.
 
En fait, il parcourt 1 fois et demi ton tableau, un point c'est tout (quand on est dans le bon cas, si les valeurs sont trop dispersées, c'est pire que le tri à bulle)
 
 


 
il créé un tableau de meme dimension en plus, pour ranger ?

Reply

Marsh Posté le 28-03-2003 à 19:55:22    

les algo de tri normo sont en n*log(n) non?

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed