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.
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.
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 !
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.
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é ?
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.
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.
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.
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).
j'apprécie aussi http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
Si les amateurs de java pouvaient m'expliquer pourquoi certains de ces tris y buggent et ratent parfois leur tri je suis preneur (même si a mon avis java explique tout ...)
# Schneier sort
Posté par Frédéric Perrin (site web personnel) . Évalué à 3.
http://www.schneierfacts.com/fact/780
Il y a aussi la version en place, pour les tableaux.
# complexité algorithmique
Posté par Krunch (site web personnel) . Évalué à 10.
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 Krunch (site web personnel) . É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 Dr BG . Évalué à 5.
On appelle ça un arbre bicolore en français.
[^] # Re: complexité algorithmique
Posté par lasher . Évalué à 2.
Mon introduction à l'algorithmique me dit « arbre rouge-noir ».
[^] # Re: complexité algorithmique
Posté par Obsidian . É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 Krunch (site web personnel) . É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 Obsidian . É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 Krunch (site web personnel) . Évalué à 1.
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 rewind (Mastodon) . É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 Michaël (site web personnel) . É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 BB . É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 Obsidian . É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 Obsidian . É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 dinomasque . Évalué à 9.
Attention, il y a un piège (au fond ...).
BeOS le faisait il y a 20 ans !
[^] # Re: Slip sort
Posté par Gniarf . Évalué à 6.
en tout cas, ça trace.
[^] # Re: Slip sort
Posté par tom120934 . Évalué à 1.
Pan !
# Dans ce cas
Posté par insert_coincoin . Évalué à 6.
Je recommande fortement ce compte Youtube, pour découvrir divers algorithmes de tri : http://www.youtube.com/user/AlgoRythmics
[^] # Re: Dans ce cas
Posté par vincent LECOQ (site web personnel) . Évalué à 1.
j'apprécie aussi http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
Si les amateurs de java pouvaient m'expliquer pourquoi certains de ces tris y buggent et ratent parfois leur tri je suis preneur (même si a mon avis java explique tout ...)
# Solution en Erlang
Posté par TaXules . É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 Krunch (site web personnel) . Évalué à 6.
perl -ne'fork&&sleep$_,print,last'
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
[^] # Re: perl
Posté par Thomas Douillard . É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 Krunch (site web personnel) . Évalué à 5.
Gah, au temps pour moi et que tous ceux qui ont plussé mon exemple se flagellent.
Ça prend les nombres séparés par une retour à la ligne :
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.