• # Schneier sort

    Posté par (page perso) . Évalué à 3.

    1. Choisir un élément au hasard
    2. Le mettre à la fin de la liste résultat
    3. Répéter pour les autres éléments

    http://www.schneierfacts.com/fact/780

    Il y a aussi la version en place, pour les tableaux.

  • # complexité algorithmique

    Posté par (page perso) . Évalué à 10.

    il reste qu'on ne sait pas bien exprimer théoriquement la complexité d'un tel algorithme

    Heu ben si. Ça dépend de l'algo utilisé par l'ordonnanceur pour les timers. Dans Linux les timers sont implémentés avec un red-black tree donc au mieux c'est O(n*log(n)) (et pas O(N^2)). Après il y a évidemment un facteur constant assez conséquent.

    pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

    • [^] # Re: complexité algorithmique

      Posté par (page perso) . Évalué à 4.

      Et quand je dis « au mieux » c'est « au pire » (en admettant que le red-black tree des timers est bien O(log(n)) et qu'il n'y a pas une subtilité quelconque qui rajoute un facteur dépendant de N quelque part).

      pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

    • [^] # Re: complexité algorithmique

      Posté par . Évalué à 5.

      Ah mais justement, tout est là : l'algo utilisé pour trier les timers sur le système d'exploitation ne peut pas être considéré comme étant sous-jacent au sleep sort.

      Si j'éteins mon ordinateur et si je prends dix minuteurs (pour cuire les œufs, par exemple), que je leur colle tous un numéro et que je veux trier ces minuteurs sur mon étagère, je peux tous les programmer à une durée correspondant à leur numéro respectif (donc en seule fois : complexité linéaire), et prendre chaque minuteur qui sonne pour le ranger à la suite des autres sur mon étagère, ou les mettre les uns sur les autres dans une boîte, ce qui revient à les empiler (donc, exit toute nécessité de conditions d'accès particulières).

      Certes, j'utilise la propriété qu'ont ces minuteurs de pouvoir se signaler eux-même, mais il est de fait que je me retrouve ainsi avec mes dix minuteurs triés, alors qu'à aucun moment, je ne les ai comparés entre eux !

      Et ça, c'est assez remarquable !

      • [^] # Re: complexité algorithmique

        Posté par (page perso) . Évalué à 2.

        OK, si tu as autant de timers matériel que d'éléments à trier et que l'implémentation de sleep les utilise « correctement », ça peut devenir intéressant mais d'un point de vue pratique ça reste peu plausible.

        pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

        • [^] # Re: complexité algorithmique

          Posté par . Évalué à 2.

          Même pas, parce que pour que cela vaille le coup, il faudrait que l'intervalle entre les timers soit égal à l'overhead nécessaire à leur traitement, qui de toutes façons couvrirait un temps suffisant pour comparer entre eux des dizaines d'éléments. C'est efficace, mais ça reste lent.

          L'intérêt de la chose n'est pas là. D'une part, il suffit que ce soit vrai une fois pour valider l'algorithme. Ensuite, c'est la première fois, à ma connaissance, qu'on exploite la dimension temporelle de manière active pour parvenir à ses fins.

          Et ce qui est vraiment notable, c'est que cet algo, comme ses frères, est complètement transposable dans le monde réel, même si tu éteins ton PC. Il ne repose pas sur un « sous-algorithme ».

          T'en connais beaucoup des algos de tri qui, à la fois, fonctionnent sans comparer les éléments entre eux, ont une complexité en O(n) et sont stables par dessus le marché ?

          • [^] # Re: complexité algorithmique

            Posté par (page perso) . Évalué à 1.

            T'en connais beaucoup des algos de tri qui, à la fois, fonctionnent sans comparer les éléments entre eux, ont une complexité en O(n) et sont stables par dessus le marché ?

            Bah le spaghetti sort c'est pas nouveau non plus.

            pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

  • # Tri comptage

    Posté par . Évalué à 5.

    Pour moi, c'est juste une variante du tri comptage, sauf qu'à la place d'utiliser de la mémoire, on utilise le temps. Mais le principe reste le même.

    • [^] # Re: Tri comptage

      Posté par (page perso) . Évalué à 2.

      Tu as raison, en lisant un texte sur le sleep sort je suis tombé sur le spaghetti sort qui est une autre variante du tri comptage.

    • [^] # Re: Tri comptage

      Posté par . Évalué à 1.

      C’est ce que j’ai pensé aussi, d’un point de vue algorithmique, si on considère le petit bout de code du lien, c’est le cas.

      Mais comme dit au dessus et dans le lien, les propriétés (complexité&co) dépendent de la façon dont tu prépares tes tâches pour les réveiller au moment opportun, à la fin du sleep. Si le système d’exploitation utilise un algorithme de tri pour préparer les processus qui dorment, alors la complexité du sleep sort ne pourra pas être meilleure que la complexité du tri fait par le système :
      — c’est un peu couillon vu que le tri comptage est en O(N), je classerais même presque le sleep sort dans la classe O(1), car l’opération de tri ne dépend pas de la taille du tableau (presque car il reste les opérations d’accès mémoire&co) ;
      — on ne peut plus parler de tri par comptage car lorsqu’on déroule l’opération sleep un tri apparaîtra, c’est qu’il n’est pas explicite mais bien présent ;
      — toute la question est alors de savoir ce qui est implémenté derrière sleep pour vraiment parler d’un tri comptage.

      • [^] # Re: Tri comptage

        Posté par . Évalué à 2.

        Oui mais, comme indiqué dans le fil juste au-dessus, ce n'est pas inhérent à l'algorithme lui-même. Tu peux très bien ranger n réveils sur ton étagère en les programmant en fonction de leur numéro, et ce sans avoir à recourir à un système d'exploitation ni même allumer un ordinateur.

  • # IGNobel

    Posté par . Évalué à 10.

    Je pense que ça mérite au moins au moins le prix Ig nobel, si l'on considère son plus récent objectif, soit récompenser les initiatives qui ont faire rire d'abord puis réfléchir juste après.

    Qu'en pensez-vous ? (On pourrait même dire « Quand pensez-vous ? », ce serait approprié ici).

  • # Slip sort

    Posté par . Évalué à 9.

    1. choisir un slip au hasard
    2. ...
    3. Profit !

    Attention, il y a un piège (au fond ...).

    BeOS le faisait il y a 15 ans !

  • # Dans ce cas

    Posté par . Évalué à 6.

    Je recommande fortement ce compte Youtube, pour découvrir divers algorithmes de tri : http://www.youtube.com/user/AlgoRythmics

  • # Solution en Erlang

    Posté par . Évalué à 4.

    Marrant ! :)
    Voici ma petite solution en Erlang, langage pour lequel ce genre d'algo prend tout son sens.

    -module(sleepsort).
    -export([sort/1]).

    result(0) -> [];
    result(N) -> receive Nb -> [ Nb | result(N-1) ] end.

    sort(List) -> result(lists:foldl(fun(X,Acc) -> erlang:send_after(X, self(), X), Acc+1 end, 0, List)).

    • [^] # perl

      Posté par (page perso) . Évalué à 6.

      perl -ne'fork&&sleep$_,print,last'

      pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

      • [^] # Re: perl

        Posté par . Évalué à 4.

        Marche pas. Ou il me faut le mode d'emploi, mais j'ai testé plusieurs trucs et impossible de le faire marcher.

        • [^] # Re: perl

          Posté par (page perso) . Évalué à 5.

          Gah, au temps pour moi et que tous ceux qui ont plussé mon exemple se flagellent.

          perl -ne'fork and sleep$_,print,last'
          

          Ça prend les nombres séparés par une retour à la ligne :

          echo 4 3 8 2 9 10000000000 | sed 's/ /\n/g' | perl -ne'fork and sleep$_,print,last'
          

          pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

Suivre le flux des commentaires

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