Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6

Posté par  . Modéré par Benoît Sibaud.
Étiquettes :
0
22
sept.
2002
Noyau
Alors que le noyau de développement entrera en phase de « feature freeze » le 31 octobre, on peut déjà voir à quel point nos joyeux hackers ont fait du super boulot.
En effet, avec la récente intégration de ordonnanceur O(1) de Ingo Molnar, associée à la toute nouvelle bibliothèque sponsorisée par Red Hat de support natif des threads POSIX (Native POSIX Thread Library), le noyau se montre capable de créer et détruire sur un « vieux » IA-32 dual 450MHz PII Xeon 100 000 threads en 2,3 secs (avec jusqu'à 50 threads à tourner en même temps).
Même si concrètement aucune application n'utilise pour le moment autant de threads en parallèle, ce test montre surtout que ce nouveau design supporte bien mieux des changements d'échelle et est bien plus efficace (le même test prend 15 minutes sur un noyau non modifié).
La NPTL est appelée à être incluse à la bibliothèque GNU C quand elle sera jugée suffisamment stable.

NdM: Merci à MadCoder qui nous a proposé aussi cette nouvelle en indiquant également que des architectures powerPC récentes, il a même été réussi de lancer près d'un million de threads avec 200 qui tournaient en parallèle.

Aller plus loin

  • # Bravo les gars

    Posté par  . Évalué à 10.

    On n'a qu'a se rejouir d'une aussi bonne nouvelle, parce que les threads natifs posix, c'etait jusqu'a présent une 'non conformité' de linux... (on pouvait leur envoyer des signaux) Si, et la c'est une cerise sur l'iceberg, tout cela s'accompagne de performances qui déchirent... it's amazing!!! Ben y'a plus qu'a faire des benchmarks de comparaison avec Solaris (qui brille dans ce domaine). ps: bon ok faut pas s'affoler, la route est encore longue avant de trouver un Linux 2.6 chez l'epicier du coin.

    • [^] # Re: Bravo les gars

      Posté par  . Évalué à 10.

      ps: bon ok faut pas s'affoler, la route est encore longue avant de trouver un Linux 2.6 chez l'epicier du coin. Je rappelle à ce propos que le "feature freeze" est prévu pour Halloween, après il n'y aura plus que des bug fixes ou des ajouts mineurs, le noyau 2.6 devrait donc arriver dans un délai raisonnable (quelques mois après le feature freeze je pense). Mais comme tous les noyaux, il sera préférable d'attendre un peu avant d'upgrader là où c'est sensible... les 2.x.0 n'ont pas toujours été parfaits ;p

      • [^] # Re: Bravo les gars

        Posté par  . Évalué à 10.

        > le noyau 2.6 devrait donc arriver dans un délai raisonnable Il me semble qu'entre le "feature freeze" et la sortie officiel du 2.4 il y a eu près de 12 mois.

        • [^] # Re: Bravo les gars

          Posté par  . Évalué à -10.

          <humour>
          Ca devrait donc être disponible sur debian en 2012...
          </humour>

  • # Ordonnanceur?

    Posté par  . Évalué à 10.

    Si quelqu'un savait exactement à quoi ça sert, parceque je n'ai trouvé nul part d'explication de l'utilité de l'ordonnanceur. Tout ce que l'on peut faire avec, c'est utiliser le programme setbatch <pid> qui fait... ben on sait pas en fait, y'a rien dans les sources, sauf mettre le PID en SCHED_BATCH, mais savoir à quoi ça sert...

    • [^] # Re: Ordonnanceur?

      Posté par  . Évalué à 10.

      L'ordonnanceur(=scheduler) c'est ce qui decide de quel thread va tourner sur quel processeur. C'est lui qui regarde quels sont les threads qui sont prets a tourner, quels sont ceux qui sont les plus prioritaires, quel CPU est libre,... et qui decide que c'est au tour de xbill plutot que StarOffice de tourner.

    • [^] # Re: Ordonnanceur?

      Posté par  . Évalué à 10.

      c'est ce qui permet de faire du multitache, et de passer d'un thread a l'autre, en fonction des priorites, etc... Gérer tout les processus, koi, imagine un chef qui dit : toi tu bosses ! toi je t'aime pas tu t'arretes ! visiblement celui la est en O(1), donc une complexité constante (nbre d'operations) en fonction du nombre de thread/process surement ...

      • [^] # Re: Ordonnanceur?

        Posté par  . Évalué à 6.

        T'aurais pas un lien, parceque là je comprends rien du tout. Enfin, je comprends un peu, c'est le "batch" que je comprends pas. Sur Solaris, on a la possibilité de mettre des "priorités" à des processus (ça c'est un process temps réel, ça un process Interface graphique (avec un peu plus de priorités)). C'est ça ou pas?

        • [^] # Re: Ordonnanceur?

          Posté par  . Évalué à 10.

          Ingo va te l'expliquer lui-meme: http://lwn.net/Articles/3866/

        • [^] # Re: Ordonnanceur?

          Posté par  . Évalué à 10.

          Sur Solaris, on a la possibilité de mettre des "priorités" à des processus Avec l'ordonnanceur de Linux aussi, il y a deux choses différents: la "classe" du programme (temps-réel ou timesharing, seul un process tournant en root peut demander à être "temps-réel") et la "gentillesse", une valeur de -20 à 20 (0 à 20 pour les utilisateurs non privilégiés) (man nice, man renice, man setpriority)

        • [^] # Re: Ordonnanceur?

          Posté par  . Évalué à 10.

          Je vais essayer de t'expliquer en gros. Si jamais je fais des erreurs, les autres me reprendront ! ;-) Alors, un sytème d'exploitation multi-tâches est un logiciel qui gère plusieurs programmes en même temps. Que ce soit sur un ou plusieurs processeurs. De façon schématique on dit qu'un programme se présente potentiellement sous deux formes: 1) Son binaire. Qui est stocké sur le disque-dur ou en mémoire vive pendant son execution. 2) Un processus. Qui correspond à l'execution du binaire. Il est important de noter que chaque processus a son propre espace mémoire à lui. La plupart des systèmes d'exploitations partagent le processeur entre les différents processus, mais Linux, lui, utilise une granularité plus fine car il gère le partage du/des processeur(s) entre des threads. Un thread est un 'sous-processus' qui partage le même espace mémoire que les autres threads que gère le processus principal. Finalement, le scheduleur est le programme qui va donner la main à chacun des threads chacun leur tour suivant certaines données (comme leur priorité, leur age, etc). Le problème, c'est que ce scheduleur doit essayer d'éviter les deadlocks entre les threads (typiquement, un thread doit s'executer avant un autre ou alors ils tentent tous les deux d'acceder à une ressource critique). Et résoudre tout ces problèmes de dépendance est compliqué. L'algorithme proposé par Ingo, lui reste de complexité constante quelque soit le nombre de threads (O(1)). Et il semble marcher plutôt bien. Évidemment, lorsqu'on utilise des threads comme brique de base, il faut pouvoir commuter rapidement d'un processus à un autre (on appelle cela plutôt un 'environnement' car on charge en mémoire l'endroit où en était le processus que l'on redémarre). Il se trouve que la nouvelle implémentation des processus s'adapte particulièrement bien à la commutation de processus (et donc de threads). Voila, j'ai surement dit plein de bétise, mais au moins c'est un début d'explication.

          • [^] # Re: Ordonnanceur?

            Posté par  . Évalué à 10.

            Le problème, c'est que ce scheduleur doit essayer d'éviter les deadlocks entre les threads heuuu, pas vraiment non. Les dead lock entre threads c'est au programmeur de les prevoir (c'est d'ailleur le principal probleme de la programmation multi-thread et l'apparition des lock, semaphores, ...). le scheduleur a une tache simple :-) , decider qui tourne sur quel processeur. Quand un thread a besoin d'une ressource non disponible, il n'est plus elligible et n'aura donc pas le cpu. quand tu utilises "top", seuls les process/threads marqué d'un "R" sont "runnable". Seul ceux-ci font l'objet d'un arbitrage ...

          • [^] # Re: Ordonnanceur?

            Posté par  . Évalué à 10.

            mwais, bon, pour la notion de processus (je préfère dire tâche) et de thread, je vous conseille les défintions données dans le Mach Kernel Principles qui les explique très clairement AMHA: ftp://ftp.cs.cmu.edu/afs/cs/project/mach/public/doc/osf/kernel_principles.ps. Je préfère voir ça comme deux choses distinctes: une tâche est une collection de ressources (espace d'addressage, fichiers ouverts, ...) dans laquelle s'exécute un plusieurs threads. Le problème, c'est que ce scheduleur doit essayer d'éviter les deadlocks entre les threads Ben, malheureusement, les algorithmes pour éviter les deadlocks sont loin d'être parfaits, et peu utilisables en pratique... Linux ne fait _rien_ pour éviter les deadlocks. Si je fais pthread_mutex_lock (mutexa); pthread_mutex_lock (mutexb); dans un thread et pthread_mutex_lock (mutexb); pthread_mutex_lock (mutexa); dans un autre, avec un peu de mal chance, mes deux threads vont être en deadlock, et Linux ne fera rien pour tenter de les sauver. Évidemment, lorsqu'on utilise des threads comme brique de base, il faut pouvoir commuter rapidement d'un processus à un autre Ben justement, non, la commutation de threads c'est beaucoup plus simple que la commutation de processus... changer de thread, c'est très simple, et ça peut même être fait uniquement en user-space (cf L4 et http://www.l4ka.org/publications/files/lazy-process-switching.ps ). C'est l'un des problèmes du noyau Linux actule où les notions de thread et de processus sont légèrement confondus (il n'y a pas de thread au sens propre, mais des processus pouvant partager certaines ressources, dont l'espace d'addressage).

            • [^] # Re: Ordonnanceur?

              Posté par  . Évalué à 8.

              Et voila, je savais bien que j'allais dire plein de bétises !!! :-) Au fait, quelqu'un sait comment se comporte le noyau de Windows (XP ou 2k) au point de vue des threads ??? Je veux dire, pas de trolls, des faits.

              • [^] # Re: Ordonnanceur? -1

                Posté par  . Évalué à -5.

                "comment se comporte le noyau de Windows (XP ou 2k) [...] ???" <troll>mal</troll> -1

              • [^] # Re: Ordonnanceur?

                Posté par  . Évalué à 10.

                C'est le meme type de scheduling que le noyau Linux(priority based round robin) avec des petites specificites propres. La grosse difference je pense est que le multithreading dans Win32 ne repose pas du tout sur les fonctions/structures Posix. Bon je vais m'arreter la sinon je suis parti pour pondre 3 pages :+)

          • [^] # Re: Ordonnanceur?

            Posté par  . Évalué à 10.

            L'algorithme proposé par Ingo, lui reste de complexité constante quelque soit le nombre de threads (O(1)). Et il semble marcher plutôt bien.

            Je me posais quelques questions, il semble évident que pousser à l'extrème le O(1) d'Ingo écrase ce qui existe, mais qu'en est-il avec un nombre de thread restreint (car dans ce cas la complexité théorique n'est plus la seule à compter, mais également le temps d'exécution de l'algo, si un passe de cet algo prend 10ms tandis que l'autre en O(n) prends 1ms... il faut plus de 10 threads pour que cela deviennent interessant)? Est-ce meilleurs que ce qu'il y'a actuellement? nettement meilleurs? En bref, verra-t-on la différence quand on fera autre chose qu'un bench?

    • [^] # Re: Ordonnanceur?

      Posté par  . Évalué à -3.

      Flûte, moi qui est essayé de ne mettre que des termes français dans la dépèche pour le pas me faire taper sur les doigts encore une fois... Est-ce que à l'avenir je devrais mettre les deux termes (français et anglais à la fois?) En tous cas, Aurélien, je te conseille de lire "Le Noyau Linux" qux éditions O'Reilly, tu apprendras plein de choses sur le fonctionnement d'un système multitâche en ayant en plus la possibilité de voir les algorithmes associés. Comme c'est une bouquin très cher, cherche d'abbord s'il existe pas à ta B.U. !

      • [^] # Re: Ordonnanceur?

        Posté par  . Évalué à 10.

        Je conseillerai plutôt le "Modern Operating Systems, 2nb edition" d'Andrew S. Tanenbaum, qui est plus complet, plus précis et plus exhaustif... "Le noyau Linux" est pas mal, mais trop Linux-centrique je pense pour quelqu'un qui débute en OS Dev.

        • [^] # Re: Ordonnanceur?

          Posté par  (site web personnel) . Évalué à 10.

          J'ai un reproche sur le book kernel linux, je pense que c'est un livre qui devient rapidement obsolète (à vrai dire, il l'est déjà). Beaucoup , mais beaucoup de termes qui sont mal/ ou utilisés inutilement, ça ne facilite pas la compréhension [..] C'est une pale copie de conception du système unix de chez at&t de bach, beaucoup plus théorique, qui reste une référence en la matière. @+ code34

        • [^] # Re: Ordonnanceur?

          Posté par  (site web personnel) . Évalué à 0.

          Bonsoir,

          dans la rubrique bibliographie:
          UNIX Systems for Modern Architectures: Symmetric Multiprocessing and Caching
          par Kurt Schimmel chez Addison-Wesley.

          A lire avant de coder avec des threads ou en environnement multitache.

          --
          Ueimor

      • [^] # Re: Ordonnanceur?

        Posté par  . Évalué à -4.

        Merci à toi et à KB et aux autres pour les infos. J'ai cru comprendre, mais je préfère rien dire pour pas me faire passer pour un abruti fini, au cas où. Merci aussi pour les bouquins. Pour la BU, ça va être embettant, je suis plus étudiant, mais bon, je trouverais.

    • [^] # Re: Ordonnanceur?

      Posté par  (site web personnel) . Évalué à 3.

      C'est le fondement du système multi-tache/préemptif sur mono processeur. L'ordonnanceur (placé dans le noyau - partie gestion des processus) attribue/met à jour le quantum temps, la priorité de chaque processus, et en préempte (un seul à la fois) en restaurant d'abord son contexte d'éxecution. L'algo le plus basique: L'ordonnanceur parcout sa liste des processus et préempte celui qui a la plus grande priorité et restaure son contexte. L'ordonnanceur permet d'avoir des meilleurs temps de réponse, une plus grande stabilité par rapport au systèmes coopératifs, ou les processus décidaient eux meme quand repasser la main à un autre processus (win 98). @+ code34

      • [^] # Re: Ordonnanceur?

        Posté par  (site web personnel) . Évalué à 8.

        L'ordonnanceur permet d'avoir des meilleurs temps de réponse, une plus grande stabilité par rapport au systèmes coopératifs, ou les processus décidaient eux meme quand repasser la main à un autre processus (win 98). Ah non, win 98 et même win 95 étaient déjà multitache préemptifs (c'est pas pasque ça se bloque que c'est non préemptif ;). C'était d'ailleurs un argument de vente (avec quelques années de retard sur d'autres OS, pourtant krosoft présentait ça comme une révolution). Les windows à multitache non préemptif sont les 3.11 et inférieurs. Sinon l'algo bien classique d'ordonnancement c'est le "round robin" où on donne un peu de temps CPU à chaque processus, chacun son tour. Pour les curieux, il y a un fichier à voir (beacoup plus simple que ce que j'aurais cru, la première fois que j'ai été y voir j'ai été étonné), c'est file:///usr/src/linux/kernel/sched.c qui est l'ordonnaceur de linux zut, l'url est pas clickable :(

        • [^] # Re: Ordonnanceur?

          Posté par  (site web personnel) . Évalué à -2.

          Oui, j'aurais du dire pseudo-préemptif , ça aurait été beaucoup plus correct.

          Tout ça me fait penser au bel écran bleu ...

          J'ai fais un superbe screenshot hier sur une box slack/kde, je vais vous laisser le soin de l'apprecier:

          http://membres.lycos.fr/code34/images/winxp.png(...)

          @+
          code34

          • [^] # Re: Ordonnanceur?

            Posté par  . Évalué à 10.

            Super, tu l'aurais pas provoqué ton stop-screen? (allez juste un peu?).

            Stop 0x0000007B or INACCESSIBLE_BOOT_DEVICE
            This Stop message, also known as Stop 0x7B, indicates that Windows 2000 lost access to the system partition during the startup process. This error always occurs while the system is starting and cannot be debugged because it generally occurs before the operating system has loaded the debugger.

            [-1 parce que HS, y'a pas de scheduler chargé quand on est arrivé que là...;-)]

            • [^] # Re: Ordonnanceur?

              Posté par  (site web personnel) . Évalué à -5.

              J'aime bien le principe sabordage/poisson qui se mort la queue sous win.

              "Comme windows ne gère pas le bug, il n'a pas démarré et tu as un beau message d'erreur de type 0x0000007B ..."

              Heureusement, tout est bien expliqué sur la page bleue: "Pour résoudre le bug, démarrez windows".

              En clair, si vous voyez cette page et que vous ne tournez pas sous autre chose que Xp: vous êtes mal ;))

              [-1 parce que HS, y'a pas de scheduler chargé quand on est arrivé que là...;-)]

              Et oui, tout le monde le sait: l'ordonnanceur sous xp est directement intégré dans internet explorer.

              @+
              Code34

        • [^] # Re: Ordonnanceur?

          Posté par  . Évalué à 4.

          <sarcasme>
          Si les win 9x étaient préemptifs, alors il y avait un appel système qui permet à un programme de bloquer tout le système en l'appellant.
          </sarcasme>

        • [^] # Multitâche préemptif

          Posté par  . Évalué à 6.

          C'était d'ailleurs un argument de vente (avec quelques années de retard sur d'autres OS

          Et quelques années d'avance sur Macintosh ;-).....

  • # rappel: les native threads clone() existent deja et sont très rapides

    Posté par  . Évalué à 10.

    Simplement pour rappeler que si pour vous la portabilité n'est pas un problème l'API Posix est assez complexe et ajoutera toujours de toutes façons des calculs supplémentaires à effectuer par rapport à l'API native de linux clone() qui existe depuis longtemps et est très simple à utiliser (man clone) On les appelle aussi les kernel threads. http://linas.org/linux/threads-faq.html "Are Linux threads the same as other implementations? No. They are better"

  • # 100 000 en parallele !

    Posté par  . Évalué à 10.

    (avec jusqu'à 50 threads à tourner en même temps). Non, c'est bien les 100 000 qui tournent en meme temps, d'apres Ingo. C'est pas parce que c'est Linus qui pose la question qu'il faut pas lire la réponse ! (Car, je suppose, cette phrase est tiré du thread à http://kerneltrap.org/node.php?id=422 )

    • [^] # Re: 100 000 en parallele !

      Posté par  . Évalué à 10.

      C'est bien ce que je pensais aussi mais bon vu que tout le monde acquiessait sans relever je pensais être à côté de la plaque. Je peux donc lacher mon Whaoooooooooooooouuuuuuu ! 100 000 en parallèle tout ça en mois de 2secondes c'est ahurissant !

      • [^] # Re: 100 000 en parallele !

        Posté par  . Évalué à 10.

        Mais qu'est-ce qui a pris 2.3s? Que chaque thread ait la main une fois? La machine avait combien de mémoire pour arriver à avoir 100000 thread en même temps?

        • [^] # Re: 100 000 en parallele !

          Posté par  . Évalué à 10.

          Lu dans kerneltrap : "ne test mentioned in Ulrich's email - running 100,000 concurrent threads on an IA-32 - generated some interesting discussion. Ingo Molnar explained that with the current stock 2.5 kernel such a test requires roughly 1GB RAM, and the act of starting and stopping all 100,000 threads in parallel takes only 2 seconds. In comparison, with the 2.5.31 kernel (prior to Ingo's recent threading work), such a test would have taken around 15 minutes. "

    • [^] # Re: 100 000 en parallele !

      Posté par  . Évalué à 10.

      hum quid de la note du moderateur alors ?

    • [^] # Re: 100 000 en parallele !

      Posté par  . Évalué à 10.

      Non, c'est bien les 100 000 qui tournent en meme temps, d'apres Ingo. C'est pas parce que c'est Linus qui pose la question qu'il faut pas lire la réponse ! Bah, tu sais, je suis comme toi, et je lis les documents cités en lien avant de poster une dépèche, et j'ai bien vu que dans paragraphe 19 écrit pas Ingo, il indique:
      On an old IA-32 dual 450MHz PII Xeon system 100,000 threads can be created and destroyed in 2.3 secs (with up to 50 threads running at any one time).
      En ce qui concerne le post de Linus, qui justement pointe du doigt que tous les threads ne sont pas actifs en même temps, Ingo déclare:
      On Fri, 20 Sep 2002, Linus Torvalds wrote: > Basically, the benchmark was how _fast_ thread creation is, not now many > you can run at the same time. 100k threads at once is crazy, but you can > do it now on 64-bit architectures if you really want to. we did both, and on the dual-P4 testbox i have started and stopped 100,000 *parallel* threads in less than 2 seconds. Ie. starting up 100,000 threads without any throttling, waiting for all of them to start up, then killing them all. It needs roughly 1 GB of RAM to do this test on the default x86 kernel, it need roughly 500 MB of RAM to do this test with the IRQ-stacks patch applied.
      Je suis donc complètement d'accord avec toi, sauf que dans ma dépèche, je parle du test sur le PII Xeon, pas du P4. De toutes façons, comme le dit si bien Ingo:
      Obviously with 100,000 threads running at once there's some shortage in CPU power :-) [ I will perhaps try that once, at SCHED_BATCH priority, just for kicks. Not that it makes much sense - they will get a 3 seconds worth of timeslice every 3 days. ]
      Ce qui veut grosso-modo dire que c'est débile avec les processeurs que l'on a maintenant d'espérer avoir autant de tâches en parallèles et obtenir un service utilisable, vu que chaque thread ne serait ordonnancé que tous les 36 du mois.... ;-) Le test était donc plus de voir quel était le <b>coût<b/> de l'ordonnancement et de la création/destruction de processus, plus que de pouvoir crâner dans la cours de récré demain matin devant les potes Windowsiens en prétendant que "mon Linux à moi il peut ripper 100 000 OGGs en même temps, nananère". J'adore ma Linuxette, mais perso je pense que c'est pas une raison de se ridiculiser en disant n'importe quoi quand même!

      • [^] # Re: 100 000 en parallele !

        Posté par  . Évalué à -4.

        " ...en prétendant que "mon Linux à moi il peut ripper 100 000 OGGs en même temps, nananère". J'adore ma Linuxette, mais perso je pense que c'est pas une raison de se ridiculiser en disant n'importe quoi quand même! " ben ouais, paske un .ogg ça se rippe pas, et pour ripper 100 000 CD il faudrait 100 000 lecteurs de CD ;-) -1

        La gent féminine, pas la "gente", pas de "e" ! La gent féminine ! Et ça se prononce comme "gens". Pas "jante".

  • # Le free a peur du proprio

    Posté par  . Évalué à 10.

    ------------------------------------------------- People who are interested in contributing must be aware that for any non-trivial change we need an assignment of the code to the FSF. The process is unfortunately necessary in today's world. People who are contaminated by having worked on proprietary thread library implementation should not participate in discussions on the mailing list unless they willfully disclose the information. Every bit of information is publically available from the mailing list archive. ------------------------------------------------- Marant mais http://www.dotgnu.org/ fait la même mise en garde.

    • [^] # Re: Le free a peur du proprio

      Posté par  . Évalué à 10.

      Normal, imagine qu'une technologie sous protegée par le secrée industriel ou quelqu'autre loie que ce soit , soit implementée dans le noyau linux. Le bordel que cela serait, la societée ayant droit pourrait demander l'interdiction immediate de la diffusion des source, faudrait auditer tous le code du kernel, etc etc, un travail de Titan en sorte, uniquemant parce que la sociéte a des soupçons sur l'utilisation de leurs techno. a cause d'un de leurs emploié qui a travaillier sur le kernel. Mieux vaux prevenir que guerire, la FSF n'a pas les moyens financier de ce lancer de ce genre d'aventure couteuse.

    • [^] # Re: Le free a peur du proprio

      Posté par  (Mastodon) . Évalué à 10.

      C'est pas "marrant", c'est une précaution utile pour éviter que des gens puissent les accuser d'avoir repompé des idées sur du code proprio, même involontairement. RMS explique au sujet du droit d'auteur que si vous pouvez prouver que vous avez écrit "Le Rouge et le Noir" sans avoir eu connaissance du vrai roman de Stendhal, par exemple en vivant enfermé dans une pièce sans contact avec l'extérieur, alors on ne peut pas vous accuser de plagiat. Ici c'est un peu la même idée.

      • [^] # Re: Le free a peur du proprio

        Posté par  . Évalué à 10.

        > vous avez écrit "Le Rouge et le Noir" sans avoir eu connaissance du vrai roman de Stendhal, ... C'est intéressant et je ne le savais pas. Pour moi, pour être sure de ne pas copier du proprio je demanderai que mon source soit "audité" par des gens bossants sur du proprio. Ben c'est une erreur. On peut "recréer" du proprio mais pas le copier. Mais en cas de procès, il faut prouver sa bonne foi.

        • [^] # Re: Le free a peur du proprio

          Posté par  . Évalué à 7.

          Microsoft rend disponible les sources de l'implémentation de .net MAIS si tu les lis, tu ne peux plus travailler sur un projet comme mono parce que tu le rendrais illégal. Sympathique non?
          D'où le nouveau combat inutile dans lequel MDI engage une bonne partie de la communauté.
          D'un côté, tu as un attrapesourcenigaud que tu ne dois absolument pas lire et de l'autre tu permets à tout le monde d'étudier les tiennes. Qu'est-ce qui empêche microsoft d'intenter un procés dés qu'il voit quelquechose de ressemblant dans les sources de mono? Pas les sous ni l'honnêteté en tout cas.
          De plus, une personne qui apprécierait mono sous linux ne sera-t-elle pas tentée d'aller voir chez le créateur de l'original pour aller plus loin?

      • [^] # Re: Le free a peur du proprio

        Posté par  . Évalué à 1.

        Eh c'est rigolo, quand les gens ont su que MS faisait de meme de son cote(interdire aux employes de faire de l'open source), MS s'est fait insulter, comme quoi c'etait du FUD, etc... Finalement on dirait que tout le monde est d'accord sur le fait qu'il y a un risque...

        • [^] # Re: Le free a peur du proprio

          Posté par  (Mastodon) . Évalué à 0.

          Tiens j'étais pas au courant de ça. C'est quoi les détails, interdiction de faire de l'open source, du logiciel libre ? Seulement en rapport avec ce sur quoi ils bossent chez MS ou carrément en général ?

          Sans ces détails je ne peux pas trop te répondre. Si l'interdiction concerne la GPL ou autres licences avec copyleft ça se comprend, de peur que du code sous copyleft se retrouve dans leurs softs à leur insu. Si ça ne concerne pas le copyleft c'est différent.

    • [^] # Re: Le free a peur du proprio

      Posté par  . Évalué à 10.

      Ca paraît logique. Dire que l'OpenSource craint le proprio faut pas pousser non plus. Disons plutôt qu'en cas de litige avec une boîte pensant être popriétaire d'une technologie breveté qui serait intégrer à la kernelle de façon intentionnée ou non, la FSF n'aura que peu de chance de pouvoir se défendre correctement surout si cette boîte en question a d'énormes moyens financiers. A mon avis y a plein d'autres points qui font que la FSF fait cette mise en garde et encore AMA ça doit pas être une nouveauté seulement eux réintèrent cette mise en garde pour être sûr.

  • # [HS ?] Ordre de complexité d'un alogrithme

    Posté par  . Évalué à 10.

    Juste une curiosité de ma part mais ça fait plusieurs fois que je vois des expressions du style O(n!), O(log n) et j'ai jamais réussi à savoir pourquoi :) Mon premier réflexe ça été de faire un peu (beaucoup) de googling mais j'ai rien trouvé de bien probant pour éclairer ma lanterne. Quelqu'un pourrait-il m'expliquer de façon simple (sic) ou me donner une bonne URL où je pourrais savoir à quoi cela correspond, comment on sait que tel ou tel algorithm est de telle ou telle compléxité, qu'est-ce que cela apporte au niveau performance de l'algorithme. Voila je pense que j'ai été clair.

    • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

      Posté par  . Évalué à 10.

      Quand je veux une réponse "newbie et concise" sur un sujet un peu technique, je vais souvent voir sur Everything essaie d'entrer le mot clef: "Big-oh notation" allez, je le fais pour toi: http://everything2.org/index.pl?node=big-oh%20notation

      • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

        Posté par  . Évalué à 5.

        Quand je veux une réponse "newbie et concise" sur un sujet un peu technique, je vais souvent voir sur Everything Merci je ne connaissais pas du tout ce site. Et désolé pour le dérangement :)

        • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

          Posté par  . Évalué à 3.

          Si tu ne connais pas ce site, prend garde, malheureux : ce site t'attrappe et peut te faire perdre des heures. Ici, on "moule", là bas, ils "nodent" (c'est un des sites de l'OSDN ou d'Andover je crois, c'est pratique aussi pour piger les private-joke de slashdot) -1 quand meme, malgré la gravité de ce post

        • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

          Posté par  . Évalué à 8.

          Bien que ce genre de sites soit très pratique, il me semble qu'il est vraiment bon, quand on s'intéresse et est confronté à ce genre de choses, d'essayer de s'y mettre vraiment. Essaye de te procurer - dans une bibliothèque universitaire, par exemple - des bouquins d'algorithmique, et en particulier « The Art of Computer Programming ». Bien que pas facile à appréhender, il est une référence et une merveille. Le volume 1 répondra à toutes tes questions, notamment sur cette notation en grand-O. Bien sûr, ça n'est pas le seul. Mais c'est le meilleur. Allez hop, -1, paske c'est quand même HS.

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  (site web personnel) . Évalué à -4.

            Ou là tu veux le faire furie ?

            Essait plutot, "algorythme en C" de je ne sais plus trop qui très didactique.

            nicO

            "La première sécurité est la liberté"

            • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

              Posté par  . Évalué à 7.

              Bof, j'ai toujours largement préféré, si l'on souhaite s'attaquer vraiment à la complexité, soit des bouquins spécialisés - oui, oui, il y'a des pav^Wbouquins entiers là-dessus - soit des bouquins d'étude des algorithmes pointus, et complets. Et le meilleur d'entre tous se trouve être « The Art Of Computer Programming », sans aucun doute.

              Bien entendu, ça n'est probablement pas le bouquin le plus adapté pour un étudiant qui commence juste l'algorithmique, ou un autodidacte qui veut apprendre quelques algorithmes classiques qu'il pourrait employer dans ses programmes personnels. Pas plus que ce n'est adapté pour quelqu'un intéressé par la "théorie des algorithmes". Mais en revanche, pour quelqu'un qui veut comprendre parfaitement l'analyse des algorithmes - et dispose d'un niveau de maths correct, c'est très adapté. Et zeDek m'avait l'air motivé .. :-)

            • [^] # Commentaire supprimé

              Posté par  . Évalué à 1.

              Ce commentaire a été supprimé par l’équipe de modération.

    • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

      Posté par  . Évalué à 10.

      O(1) ça veut dire que l'algom prend tjs le même temps. O(n) ça veut dire que le temps varie linéairement par rapport au nombre d'objects à traîter. Genre un algo de tri qui prend 1 seconde pour 10 objects, en prendra 10 pour 100 objects. Pis après y a les O(n^2), O(ln(n)), ... Tout ça valable pour n suffisament grand.

      • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

        Posté par  . Évalué à 3.

        C bon j'ai compris. Pac contre maintenant je cherche à savoir comment on fait pour connaître le degré. Par exemple tu dis qu'un algo de tri c'est O(n), ma question serait : pourquoi O(n) ? Comment le sait-on ? C'est ce que je suis en train d'essayer de piger grâce au lien du post un peu plus haut qui au passage est vraiment très interessant. Je le redonne au cas ou : http://everything2.org/index.pl?node=big-oh%20notation

        • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

          Posté par  . Évalué à 3.

          bof dans la plupart des cas il suffit de reflechir en lisant l'algo. O(1) : facile l'algo ne depend pas du nombre de donnees en entree. c'est rare :-) O(n) : en general l'algo a besoin de parcourir (lire) les donnees en entree au moins une fois. O(n^2) : mauvais. en general l'algo possede deux boucles imbriquées qui dependent du nombre de donnees en entree. En general aussi, on s'arrete la et on note direct O(e^n) pour dire exponentiel (mauvais). en log(n), ton algo ne lit jamais toutes les données, il utilise une astuce (elles sont triées avant d'entrer par exemple, ou dans un hash de mauvaise qualité ...). bon c'est pas academique, mais le feeling ca le fait bien ;-)

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à 10.

            En general aussi, on s'arrete la et on note direct O(e^n) pour dire exponentiel (mauvais). oulàlàlà... Tu connais un algo de multiplication de matrice en moins que O(n^2) ? Pourtant, ils sont loin d'être en exponentiel ! (le meilleur connu est on O(n^2.8) IIRC)... Ensuite, même un algo exponentiel, ben euh... O(2^n) c'est pas égal à O(e^n). O() c'est une notation mathématique qui a une définition exacte, merci de l'utiliser avec la rigueur qui convient.

            • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

              Posté par  . Évalué à 8.

              Moi, je connais et j'ai même implémenté des algos en O(e^n). Enfin pas completement exponentiels car ils sont P-space complet. Ce sont des algos de vérification de logiciels (model-checking). Mais, il est vrai qu'il s'agit là d'une limite. Cela dit, il est important de se rendre compte que lorsqu'on parle de O(.) on parle de complexité au pire et non pas en moyenne. Pour certains algorithmes les problèmes que l'on considère en pratique ont une complexité moindre que la complexité au pire. C'est le cas de l'algorithme du simplexe par exemple qui devrait être NP mais qui est P en pratique.

              • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                Posté par  . Évalué à 7.

                Cela dit, il est important de se rendre compte que lorsqu'on parle de O(.) on parle de complexité au pire et non pas en moyenne. Cf mon autre commentaire, non, il y a plusieurs complexités pour un même algorithme: complexité en temps ou en espace mémoire, et complexité en pire cas ou en moyen cas. Ce que l'on appelle usuellement la complexité tout court, c'est la complexité moyenne en temps, qui est celle qui est la plus souvent utilisée. La complexité en pire cas n'est rellement utilisée qu'en temps réel ou ce qui compte ce n'est pas d'avoir un algo globalement performant, mais de pouvoir dire "on peut garantir que le résultat sera disponible à temps".

                • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                  Posté par  . Évalué à 2.

                  Je crois que ce qui provoque notre désaccord provient d'une définition différente de la complexité. Devant le f(n) d'une complexité en O(f(n)), il y a une formule g(n) qui est de complexité moindre. Donc, le nombre d'opérations est f(n).g(n) dans la réalité (pour le pire cas toujours), mais on ne considère que les plus gros facteurs lorsqu'on parle de complexité. Mais par contre, c'est tout le temps la complexité pire cas qui est utilisée. La complexité en moyenne est extremement dure à calculer (pour ne pas dire impossible dans certains cas). Pour ce qui est de la complexité en temps et en espace, tu as raison.

            • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

              Posté par  . Évalué à 5.

              bon ok, je te rassure j'ai appris tout ca aussi a l'ecole il y a longtemps. mais la question c'etait "pour un newbie". on peut (je l'ai fait :-)) penser qu'un newbie ne va pas se lancer dans une demonstration mathematique pour demontrer qu'un algo est meilleur qu'un autre. c'est bon a l'ecole/la fac/l'inria. dans la vie professionnelle, on te (me) demande de savoir "a peut près" vers quoi on se dirige, de reflechir si c'est normal (ton cas des matrices) et d'ameliorer si c'est pas suffisant. Le calcul, la demonstration mathematique, personne ne veut plus la lire :-( . par contre des mesures concretes sur des vraies données, ca oui ca interesse les gens .. bref j'ai voulu me mettre a la portée de ceusse qui posent la question (a priori si ils la pose c'est qu'il ne l'ont meme pas abordée en cours ...). Je me rends compte en lisant plus bas que vous etes partis direct vers les definitions précises ... comme ca y aura de tout :-)

            • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

              Posté par  (site web personnel) . Évalué à 4.

              En fait, on peut calculer un produit matriciel n^(2+epsilon) pour tout epsilon>0. Le principal problème est que la constante devant le n dépend de epsilon et est énorme, donc ce n'est interessant que pour les tres grosses matrices.

        • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

          Posté par  . Évalué à 9.

          Un tri en O(n), je doute, un tri basé sur des comparaisons c'est minimum O(n*ln(n)) (ça se démontre). La complexité tu la calcules en analysant l'algo. Par exemple, un tri par fusion: * tu découpes ton tableau en 2 * tu tries chacune des deux moitiés * tu fusionnes les deux Fusionner les deux, ça prend O(n) comparaisons. Donc t(n) = 2 * t(n/2) + n . Ensuite tu as un simple problème de maths. n lg(n) = n lg (n/2) + lg(2) n = 2 * ( n/2 lg (n/2)) + lg(2) n = 2* (n/2 lg (n /2)) + n donc n lg(n) vérifie bien la relation de récurence, donc t(n) = n lg (n) (théorème d'unicité des suites récurentes avec conditions initiales (t(1) = 0)) J'espère que mes explications sont assez claires, mais le principe c'est ça. Bon, il manque un peu d'exactitude mathématiques, mais c'est pas le sujet.

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à -2.

            Argh, tu avais déjà répondu ! :-/ Désolé.

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à 7.

            Un tri en O(n), je doute Si, si, ça existe, c'est pas un algo de tri général, mais en faisant des suppositions sur les données, ça existe. Par exemple, si on suppose qu'il existe un nombre fini (petit) de valeurs possibles, alors tu peux créer un tableau avec une case par valeur et dans chaque case tu mets une liste chainée pour mettre les valeurs. Donc l'algo est le suivant : 1 - Pour chaque donnée, la placer à l'avant de la liste chainée dans la case qui lui correspond 2 - Parcourir le tableau pour mettre bout à bout chaque liste chainée (on suppose que ce sont des listes simplement chainées donc il faut reparcourir tous les éléments. Au final, on a parcouru deux fois la liste des éléments. On a donc bien un algo en O(n).

            • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

              Posté par  (site web personnel) . Évalué à 9.

              C'set un peu l'esprit du hash-sorting qui est lui aussi en O(n) : tu as une table de hash où tu balances toutes les valeurs à trier et à la fin tu la parcourt dans l'ordre pour recréer le tableau trié (si j'ai mal expliqué cf google ça doit y être).

              Et si on veut un tri basé sur des comparaisons on a les tris qui s'occupent d'abord des bits de poids fort puis des bits de poids faibles de ton entier, ça donne des complexités comme O(n*log(log(n))), ça doit aussi se trouver sur google.

              En fait, le tri O(n*log(n)) est optimal avec quelques hypothèses :
              - tu fais le tri in-situ
              - tu as une fonction de comparaison dont tu ne connais pas les propriétés à priori
              - tu as juste le droit de modifier ton tableau avec une fonction inverse(a,b) qui... inverse a et b.

            • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

              Posté par  . Évalué à 2.

              une doc pour les diff tris http://www-igm.univ-mlv.fr/~mac/ENS/DOC/trilexi_18.pdf(...)

        • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

          Posté par  . Évalué à 10.

          C'est bien là une grande partie - si ce n'est toute - la question de l'étude des algorithmes. Dans certains cas, ça paraît évident. Dans d'autres cas, c'est loin de l'être. Prenons par exemple l'algorithme d'Euclide (pour deux entiers m et n). On connait la valeur de n, et m est dans [0,+oo[. Quelle est le nombre de fois moyen Tn qu'on va opérer une "division euclidienne" ? C'est un problème mathématique pas du tout évident - et qui en fascine plus d'un, et c'est la base de l'analyse des algorithmes. (Pour mémoire, le livre que je te conseillais plus haut, The Art of Computer Programming, vol.1, donne une solution pour les valeurs de n les plus grandes, qui donnerait : Tn (approx)= (12(ln 2)/pi²)ln n. Le genre de constantes de proportionnalité qu'on aime.)

        • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

          Posté par  . Évalué à 10.

          En fait, la complexité s'obtient en considérant le pire cas pour un problème. C'est à dire que tu part toujours du pire cas pour l'algorithme que tu considères. Exemple concret: Je prend 'buble sort'. C'est un tri qui considère les élements d'une liste deux à deux et qui les tri. Par exemple: 3, 4, 1, 8 On prend d'abord 3 et 4, 4 est plus grand que 3 donc on le met devant: 4, 3, 1, 8 On considère ensuite 3 et 1. Là, 3 est plus grand que 1, on laisse comme ça. Puis, 1 et 8. 4, 3, 8, 1 Et ainsi de suite jusqu'à ce que l'on ne puisse plus rien changer. 4*, 3*, 8, 1 4, 3*, 8*, 1 4, 8, 3*, 1* 4*, 8*, 3, 1 8, 4*, 3*, 1 8, 4, 3*, 1* Et enfin un dernier tour où rien ne change. Ici, le pire cas est lorsque la liste est inversée par rapport à l'ordre initial. On évalue donc la complexité de cet algorithme à: O(n^2) Car passer à travers la liste une fois et comparer les éléments deux à deux requière n (le nombre d'élements) et comme la liste est inversée, on doit le faire n fois. Donc n*n = n^2. Et voila. :-) Ah oui, je tiens à préciser que la meilleur complexité pour les algos de tri c'est en O(n*log(n)) (quicksort) et pas en O(n).

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à 3.

            Bon ben vu que beaucoup on contribué à m'expliquer ça, je dois en choisir un (post) pour tous vous remercier. C'est passionnant comme sujet et je crois que je vais éplucher ça plus en détail. MERCI à tous toi, kbug, mmenal et tous les autres. N.B: j'aurais pe dû moins dormir pendant les cours d'algo moi :) Je trouvais ça barbant à l'époque mais là j'avoue que je suis intrigué.

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à 8.

            Ah oui, je tiens à préciser que la meilleur complexité pour les algos de tri c'est en O(n*log(n)) (quicksort) et pas en O(n). Bon, comme je le dit plus haut, ce n'est pas vrai, c'est seulement O(n*log(n)) est la complexité limite d'un algo de tri si on ne fait pas de suppositions sur les données, sinon il existe mieux (je donne un exemple avec un algo en O(n)). D'autre part quicksort est en O(n*log(n)) uniquement en moyenne, au pire cas il est en O(n^2). Notamment, pour retrier une liste presque triée, quicksort est quasiment en O(n^2) (en fait quicksort est au plus lent si on lui demande de trier une liste qui l'est déjà).

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à -3.

            Ah oui, je tiens à préciser que la meilleur complexité pour les algos de tri c'est en O(n*log(n)) (quicksort) et pas en O(n). Bon, comme je le dis déjà plus haut, O(n*log(n)) est la meilleur complexité possible pour un algo de tri qui ne fait pas de supposition sur les données. Si on en fait, on peut trouver des algo meilleurs, par exemple en O(n). D'autre part, quicksort est en O(n*log(n)) au meilleur cas au pire cas il est en O(n^2). Par exemple, si le but est de trier une liste qui est déjà presque triée (typiquement si on rajoute des données à une liste triée), alors quicksort est presque en O(n^2). Si on essaie de trier une liste déjà trier, quicksort est en O(n^2).

          • [^] # celui la je lai compris

            Posté par  . Évalué à 2.

            j avais jamais compris a quoi ca pouvais servir tot ces maths , mais là je vois . en plus le machin du 'buble' j ai compris =)

            mon avis est que Alan_T merite un point de plus pour avoir expliquer a un neuneu un algo de base ( tu veux pas m expliquer le quicksort maintenant steup .

            Enfin sans rire c vrai que c passionnat .

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à 4.

            Le quicksort est en O(n*log(n)) dans le meilleur cas justement (et on espère que par un choix judicieux on arrive à s'en approcher statistiquement). Le pire cas est bel et bien en O(n*n) : ainsi si chaque découpage te conduit à avoir un sous-tableau de un élément et un sous-tableau de (k-1), alors le tri dégénère et devient équivalent à un tri à bulles.

            • [^] # PS : Heapsort

              Posté par  . Évalué à 6.

              Si on veut du O(n*log(n)) en pire cas, on peut prendre un heapsort (tri par arbre). En plus, c'est un algo très mignon. On construit un arbre particulier de taille n dont la racine est toujours le plus élément de l'arbre. On extrait cette racine, on la place à la fin du tableau et on recommence avec l'arbre taille n-1. A chaque itération, la réorganisation de l'arbre prend O(log(k)), ceci n fois donne O(n*log(n)).

      • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

        Posté par  . Évalué à -4.

        Pourquoi 'n' devrait-il etre "suffisamment grand" ? Il s'agit de la complexité dans le pire cas. C'est toujours vrai.

        • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

          Posté par  . Évalué à 10.

          Pourquoi 'n' devrait-il etre "suffisamment grand" ? Ça, ça vient de la définition mathématique de O(). Si tu as un algo qui prend n^4+500*n^3, il est O(n^4), pourtant pour n=10, c'est le 500*n^3 qui compte. Il s'agit de la complexité dans le pire cas. C'est toujours vrai. Euh, pas toujours, non. L'algo de tri rapide, par exemple, est O(n^2) en pire cas, mais O(n ln(n)) en moyen cas. Et on le considère souvent comme un algo en O(n ln(n)) parce que sauf dans les applis temps réel, c'est plus la complexité en cas moyen qui nous intéresse.

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à -2.

            Non, là je crois que tu mélanges les notions de limites en O(.) et la notion de complexité... :-/ Cela dit, c'est un peu normal car ces abrutis ont pris la même notation pour deux choses différentes. :-)

            • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

              Posté par  . Évalué à 3.

              Non, là je crois que tu mélanges les notions de limites en O(.) et la notion de complexité... :-/ C'est _exactement_ la même chose. Dire qu'un algorithme est en O(n) c'est dire que la suite qui représente son temps d'exécution moyen (ou en pire cas) est un O(n) au sens mathématique du terme.

              • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                Posté par  . Évalué à -2.

                Ok, je précise. Le O(n) permet de ne pas avoir à évaluer la constante qui est devant le 'n'. Le nombre d'étapes que l'algorithme devra faire au pire est en 'C.n' (avec 'C' une constante). Mais le 'C' change d'un algo à un autre alors on ne considère que les plus gros facteurs, on parle alors de O(n) (et non de 'C.n') pour la classe d'algorithmes ou pour un problème donné. Évidemment, lorsque 'n' tends vers l'infini on peut négliger le 'C'. Jusque là, tu as raison. Cependant, lorsque tu dis que la 'complexité' est 'n' pour un 'n' grand, là je dis non ! :-) Ta complexité est toujours 'n' (la complexité est la mesure générale de ton algorithme ou de ton problème). Par contre, le nombre de tes opérations pour un algorithme précis va tendre vers 'n'. Je crois que c'est seulement, là-dessus que repose notre divergence... Juste un point de détail quoi. :-)

                • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                  Posté par  . Évalué à 4.

                  Le O(n) permet de ne pas avoir à évaluer la constante qui est devant le 'n'. Ainsi que tous les autres, j'en convient. Si ton algorithme est en O(n^2), les termes en n, nln(n) ou autres ne sont pas intéressant pour la complexité. Mais le 'C' change d'un algo à un autre Ben non, on calcule la complexité d'un algo. Par contre, C change suivant l'implémentation de l'algo, par exemple. Ta complexité est toujours 'n' Ta complexité n'est pas 'n', mais 'O(n)' Par contre, le nombre de tes opérations pour un algorithme précis va tendre vers 'n'. Non. 1/ on parle de la complexité d'un algorithme, donc c'est forcément la complexité d'un algorithme précis 2/ le nombre d'opérations ne tend pas vers, mais r(n) = nbop(n) / n va tendre vers un réel k non nul

                  • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                    Posté par  . Évalué à 0.

                    il me semble me souvenir que
                    O(f)=g signifie que f/g est borné... pas besoin de tendre vers quoi que ce soit.

                  • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                    Posté par  . Évalué à 6.

                    Je crois que tu confonds la complexité d'un algorithme ou d'un problème et son nombre d'opérations. Ce n'est pas bien grave car c'est souvent la même chose. Cependant, il existe ce que l'on appelle des 'classes de complexité' qui regroupent des problèmes de façon indépendante des algorithmes.

                    Par exemple, le test de primalité est P-complet(polynomial), le problème du voyageur de commerce est NP-complet (non polynomial), le problème de l'accessibilité dans un automate temporisé est P-space complet (polynomial en espace, on se fiche du temps), la résolution d'un système d'inéquations Diophantiennes est EXP-Time complet (exponentielle en temps), etc...

                    Tous ces problèmes peuvent avoir des algorithmes différents mais aucun algorithme ne peut avoir une complexité plus basse que la classe de complexité à laquelle appartient le problème. Maintenant, si tu considères le nombre d'opérations au pire cas, les algorithmes varient beaucoup, mais l'intéret est de considérer des problèmes et non des algorithmes. Évidemment, lorsque tu résouds un problème avec un algorithme calculer la complexité de ton algorithme te permet de voir si tu résoud de façon 'efficace' ou non ton problème (en gros, ton algorithme doit appartenir à la même classe de complexité que ton problème).

                    Par exemple, résoudre le problème du tri par bubble sort est une mauvaise idée car tu est au-dessus de la complexité du problème du tri (sans hypothèse sur les données).

                    • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                      Posté par  (site web personnel) . Évalué à 10.

                      Est-ce qu'on pourrait une bonne fois pour toute arrêter de dire que NP, ça veut dire non polynomial, étant donné que C'EST FAUX. Cf http://www.claymath.org/prizeproblems/pvsnp.htm(...) (surtout le pdf).

                      Pour mémoire, NP veut dire nondeterministe polynomial...

                      • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                        Posté par  . Évalué à 4.

                        Houla, pas la peine de crier !

                        J'ai dit ça pour aller plus vite.

                        Pour info, la classe NP regroupe l'ensemble des problèmes dont une entrée donnée peut être validée ou invalidée en temps polynomial.

                        par exemple, pour SAT (satisfiabilité d'une formule logique), si on se donne un ensemble de valeur booléennes, on peut savoir si la réponse est 0 (false) ou 1 (true) en temps polynomial. Par contre, si on se retrouve avec 0 (false), il est difficile de savoir si la formule est satisfiable ou non.

                        Là, tu ne pourra pas dire que je n'ai pas été précis, mais va écrire ça dans des parenthèses !!! :-)

                        J'ai l'impression que les gens sont vachement sensibles ici ! 8-)

                    • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                      Posté par  . Évalué à 1.

                      Ouhla ! On ne sait pas que NP-complet veut dire "non polynomial". Qui sait, peut-être dans quelques années quelqu'un démontrera que P=NP...

              • [^] # Turing

                Posté par  . Évalué à 2.

                En toute rigueur, la notation O(...) définit le nombre d'opérations nécessaires à une machine de Turing, pas le temps mis pour résoudre le problème. Cela veut dire par exemple que si tu considères une machine parallèle, les temps peuvent diminuer à O(...) constant. Cf. les récentes avancées en matière de cassage de RSA par Bernstein. Celui-ci n'a pas diminué la complexité algorithmique (vis-à-vis d'une machine de Turing), mais le temps mis par une machine "réelle" pour effectuer ces opérations.

          • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

            Posté par  . Évalué à -2.

            Il faut bien souligner (comme tu le fais) que O(...) est dans le cas "limite". Donc un système O(1) est "parfait" pour les charges élevées (le nombre de thread en cour n'impacte pas le temps de création d'un nouveau thread). Il sera meilleur qu'un O(n) si la charge est élevée mais peut-être pire si la charge est faible. Bref, actuellement on ne sait pas (je ne sais pas pour être plus précis) si c'est un plus pour les faibles charges (la majorité).

            • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

              Posté par  . Évalué à -3.

              Heu, aretez un peu de dire n'importe quoi ! :-) La complexité d'un algorithme est calculée quel que soit 'n'. Et c'est toujours la pire complexité que puisse atteindre cet algorithme (ou cette classe de problème). L'exemple du tri en O(n^2) est faux. Le problème du tri a une complexité en O(n.log(n)), il se trouve seulement que 'bubble sort' n'est pas un algorithme optimum pour résoudre un problème de tri. Je crois fermement que vous confondez votre cours de math sur les développements limités et votre cours d'info sur la théorie de la complexité. ;-)

              • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                Posté par  . Évalué à -2.

                > Heu, aretez un peu de dire n'importe quoi ! :-) J'ai dit quoi comme connerie (d'accord il y a un smile). Perso, je comprend rien de ton post ! Exemple, la première phrase : > La complexité d'un algorithme est calculée quel que soit 'n'. Et c'est toujours la pire complexité que puisse atteindre cet algorithme (ou cette classe de problème). Ou alors c'est de l'humour...

              • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                Posté par  . Évalué à 5.

                La complexité d'un algorithme est calculée quel que soit 'n'. hum ? Le problème du tri a une complexité en O(n.log(n)) certes, mais là je parlais de la complexité d'un algorithme, pas d'un problème. Donc mon exemple est bon. Je crois fermement que vous confondez votre cours de math sur les développements limités et votre cours d'info sur la théorie de la complexité. ;-) Ben vu que c'est la même chose...

                • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

                  Posté par  . Évalué à 2.

                  Introduction à l'algorithmique (thomas Cormen, Charles Leiserson, Ronald Rivest)
                  extrait :

                  "Les notation que nous utilisons pour décrire le temps d'execution asymptotique d'un algorithme sont définies en termes de fonctions, dont le domaine est l'ensemble des entiers naturels. De telles notations sont pratique pour décrire la fonction T(n) du temps d'executiondans le pire des cas, qui n'est en général définique sur des tailles d'entrées entières. Cependant, il est parfois avantageux d'étendre abusivement la notation asymptotique, et ce de plusieurs manières différentees(...) Mais il est important de comprendre la signification précise de la notation, de sorte q'en en abusant, on n'en mésus pas.
                  (...)
                  La notation \Theta borne une fonction asymptotique à la fois par excès et par défaut. (...) De même que la notation O (grand ô) fournit une borne asymptotique supérieur pour une fonction, la notation \Omega fournit une borne asymptotique inférieur.(...) La borne supérieur asymptotique fournie par la notation O peut être ou non asymptotiquement approchée.(...)On utilise la notation o pour signifier que la borne supérieure n'est pas asymptotiquement approchée.(...) Par analogie, la notation \omega est à la notation \Omega ce que la notation o est à la notation O. On utilise la notation /omega pour indiquer une borne inférieure qui n'est pas approchée asymptotiquement."

                  Même en étant nul en math et en ne connaissant pas cet outil (comme moi), après avoir lu ce que je viens de citer, je pense que tu as tord et qu'Alan_T à raison quand il dit que tu confond complexité et développement limité. Le second est un outil utilisé par le premier.

                  Le bouquin est évidement bien plus détaillé, j'ai coupé pour mettre les choses en valeur.

    • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

      Posté par  . Évalué à 10.

      C'est la notation de landau: "o" pour les petites roues à l'arrière du landau, et "O" pour les grandes roues à l'avant.

      ou bien ça a quelque chose à voir avec un mec qui s'appelait Landau:
      http://mathworld.wolfram.com/LandauSymbols.html(...)

      C'est vous qui voyez.

      -1 car complètement con ce que je raconte

    • [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

      Posté par  (site web personnel) . Évalué à 6.

      Tu peux toujours regarder ça:
      http://dmawww.epfl.ch/rose.mosaic/fr/cours/algorithmique/index.html(...)
      Ce sont des notes de cours fortement inspiré de 'Algorithms in C" de R.Sedgwick; regarde en particulier le cours 11 :)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.