L'analyse de FrogSort dans les céréales du Petit déjeuner du samedi matin est-elle correcte?

Dans a récent samedi matin petit déjeuner céréales comic, l'auteur décrit un algorithme appelé Frog Sort pour trier une liste de nombres naturels. L'algorithme est décrit dans la bande dessinée, mais pour simplifier, je l'ai réimprimé ici:

  1. pour chacun des nombres naturels à trier, faites une boîte avec autant de mouches dedans.
  2. Mettez une grenouille dans chaque boîte.
  3. Bien que toutes les grenouilles n'aient pas encore sauté de leurs boîtes:
    1. attendez qu'une grenouille saute de sa boîte.
    2. Notez le nombre de mouches initialement placées dans la boîte.
  4. la séquence résultante des nombres est la liste originale des nombres, mais dans l'ordre trié.

Cet algorithme fait l'hypothèse que toutes les grenouilles mangent des mouches au même rythme. En conséquence, la première grenouille à sauter de sa boîte sera la grenouille qui avait le moins de mouches à chacune, la deuxième grenouille la deuxième-le moins de mouches à manger, etc.

Au milieu du comique, un enseignant demande aux élèves " quel est le nombre maximum de pas?, "que j'interprète comme signifiant" Quel est le nombre maximum d'étapes requis pour que cet algorithme se termine?; "c'est-à-dire, quelle est la durée d'exécution de l'algorithme? L'étudiant répond alors "loggrenouille(boîtes)."

Est-ce une analyse précise de l'exécution de cet algorithme? Ou est l'auteur du mal?

23
demandé sur templatetypedef 2012-12-24 03:50:30

3 réponses

Cette analyse d'exécution est clairement fausse; nous pouvons obtenir un runtime Ω trivial de max(n_elements, largest_element) (puisque nous avons des boîtes make n_elements, et ensuite chaque Boîte prend autant de temps à vider que la taille de son contenu). Un algorithme de tri qui a pris moins de n temps serait... très surprenant.

Si vous voulez trouver plus d'analyse sur internet quelque part, cet algorithme est équivalent à Sleep-sort. Dans le cas où vous n'êtes pas familier avec cet algorithme ridicule, le voici dans bash: 

#!/bin/bash

function sort() {
    for num in "$@" ; do
        (
        sleep $num
        echo $num
        ) &
    done
    wait
}

sort 6 1 3 4
12
répondu roguelazer 2012-12-24 02:13:36

Je suis assez sûr que l'auteur de la bande dessinée a tort. Voici une analyse plus formelle de l'algorithme.

Pour commencer, nous devrons mettre en place des règles de base sur la façon dont les grenouilles mangent les mouches. Je suppose que toutes les grenouilles peuvent manger des mouches à un taux constant R. c'est-à-dire qu'il faut r secondes pour qu'une grenouille mange une mouche, 10R secondes pour qu'une grenouille mange dix mouches, etc. Ensuite, faisons l'hypothèse (raisonnable) que toutes les grenouilles mangent en parallèle. Nous supposerons également qu'il faut j temps pour une grenouille de sauter d'une case vide.

Nous devons également prendre en compte le temps d'installation. Supposons que nous ayons sous la main un approvisionnement illimité de mouches, de grenouilles et de boîtes, et disons qu'il faut du temps b pour obtenir une boîte et du temps y pour mettre une seule mouche dans une boîte. Enfin, nous supposerons qu'il faut du temps pour mettre une grenouille dans une boîte. Pour simplifier, nous supposerons que les grenouilles ne commencent pas à manger des mouches jusqu'à ce que nous les instruisons explicitement, de sorte que les grenouilles placées dans des boîtes avant les autres grenouilles ne pas obtenir une longueur d'avance.

Un dernier détail-supposons qu'il faut du temps pour écrire un nombre.

Dans ce cas, l'exécution de cet algorithme est donnée comme suit. Supposons que notre liste de nombres à trier est x1, x2, ..., xn. Dans ce cas, le temps nécessaire pour configurer toutes les cases sera n (b + f) + y (Σx i ). La raison en est que nous devons obtenir n boîtes et mettre une grenouille dans chaque boîte (d'où le premier terme), plus y unités de temps pour chacun des mouches (d'où le deuxième terme).

Au cours de l'algorithme, nous devrons écrire chaque nombre exactement une fois, lorsque la grenouille saute hors de sa boîte. Cela signifie que sur l'ensemble de l'algorithme, nous ferons un travail nw en écrivant la séquence triée.

Enfin, nous devons considérer combien de temps il faut pour que toutes les grenouilles finissent. Puisque toutes les grenouilles mangent en parallèle, tout ce dont nous devons nous soucier est la grenouille qui a le plus de mouches à manger. Cette grenouille va avoir xmax mouches à manger, où xmax est le nombre maximum dans la liste d'entrée. Ainsi, le temps passé par les grenouilles dans leur alimentation est donné par r xmax. En tenant compte du saut effectué par la grenouille finale, les grenouilles, toutes travaillant en parallèle, finiront collectivement en RXmax + J time.

Cela signifie que le temps global pour l'algorithme est donné par

N(f + b) + yΣx, je + nw + rxmax + J.

Si nous supposons maintenant qu'une "unité de travail" suffira à faire des opérations individuelles (ont une grenouille qui mange une mouche, ou de sauter hors de la boîte, ou pour mettre une grenouille dans une boîte, etc.), le temps total requis est au maximum

N + Σ(x, je) + xmax + 1

Notant que xmax ≤ Σx, je, nous obtenons que l'ensemble de l'exécution de cet algorithme est de Θ(n + Σx, je). en d'autres termes, le temps d'exécution est proportionnel aux deux le nombre de nombres à trier, et la taille totale des nombres à trier.

Notez que ce runtime n'a pas de logarithmes, donc nous pouvons immédiatement conclure que l'analyse d'exécution de l'auteur est incorrecte.

Enfin, notez qu'il s'agit d'un très mauvais algorithme de tri. L'algorithmecounting sort peut trier n nombres naturels dans le temps O (n + U), où U est la valeur maximale à trier, ce qui est asymptotiquement meilleur que FrogSort. La radix l'algorithme sort pourrait le faire en temps O (n LG U), ce qui est mieux pour les grandes valeurs de U. là encore, les deux algorithmes nécessitent des machines sophistiquées, qui n'existeraient probablement pas dans le cadre décrit par la bande dessinée.

J'espère que cela aide!

5
répondu templatetypedef 2012-12-23 23:50:30

Ce n'est pas une réponse, mais Zach lui-même a obtenu un coup de pied de celui-ci. Il fait partie d'un œuf de Pâques dans le langage de programmation ésotérique cbrain, http://esolangs.org/wiki/Cbrain . un dérivé bf, compilé avec OpenCOBOL. Pour être off-by-frog, la valeur conditionnelle juste pourrait être définie sur 2 au lieu de 1. frogSort à COBOL.

      *> ********************************************************
      *>  frogSort, called for help with 10-94, request for count
      *> ********************************************************
       identification division.
       program-id. frogsort.
       data division.
       working-storage section.
       01 opinion          usage binary-long.
       01 shared-value     pic 99.
          88 fair          value 1.
       01 caveman-count    pic x(12) value "[-]+++++++++".
       01 spacer           pic x(10) value spaces.

       linkage section.
       01 jars.
          05 flies        pic 9 occurs 21 times.

      *> ********************************************************
       procedure division using jars.
       start-here.
       move function length(jars) to shared-value
       display "Grog sort jars.  frogSort" end-display
       display "http://www.smbc-comics.com/?id=2831" end-display
       .

       forkyourself.
           call "fork" returning opinion end-call
           if opinion is zero then
               subtract 1 from shared-value
               if not fair then go forkyourself.
       .

       call "sleep" using by value flies(shared-value) end-call
       display
           "Jar: " function char(shared-value + 65) " reporting "
           caveman-count(1 : flies(shared-value) + 3) " flies,"
           spacer(1 : 10 - flies(shared-value))
           "that would be " flies(shared-value) " to you, futureman."
       end-display
       call "wait" using by value 0 end-call

       stop run returning 107.
       end program frogsort.

Avec l'oeuf de Pâques lancé avec L'appel "frogsort" en utilisant" "012345678901234567890" END-CALL 

$ ./cbrainrun 
10-12 Welcome to cbrain v0.42
cb: 1094
cb: help
Grog sort jars.  frogSort
http://www.smbc-comics.com/?id=2831
Jar: U reporting [-] flies,          that would be 0 to you, futureman.
Jar: K reporting [-] flies,          that would be 0 to you, futureman.
Jar: A reporting [-] flies,          that would be 0 to you, futureman.
Jar: L reporting [-]+ flies,         that would be 1 to you, futureman.
Jar: B reporting [-]+ flies,         that would be 1 to you, futureman.
Jar: M reporting [-]++ flies,        that would be 2 to you, futureman.
Jar: C reporting [-]++ flies,        that would be 2 to you, futureman.
Jar: N reporting [-]+++ flies,       that would be 3 to you, futureman.
Jar: D reporting [-]+++ flies,       that would be 3 to you, futureman.
Jar: O reporting [-]++++ flies,      that would be 4 to you, futureman.
Jar: E reporting [-]++++ flies,      that would be 4 to you, futureman.
Jar: P reporting [-]+++++ flies,     that would be 5 to you, futureman.
Jar: F reporting [-]+++++ flies,     that would be 5 to you, futureman.
Jar: Q reporting [-]++++++ flies,    that would be 6 to you, futureman.
Jar: G reporting [-]++++++ flies,    that would be 6 to you, futureman.
Jar: R reporting [-]+++++++ flies,   that would be 7 to you, futureman.
Jar: H reporting [-]+++++++ flies,   that would be 7 to you, futureman.
Jar: S reporting [-]++++++++ flies,  that would be 8 to you, futureman.
Jar: I reporting [-]++++++++ flies,  that would be 8 to you, futureman.
Jar: T reporting [-]+++++++++ flies, that would be 9 to you, futureman.
Jar: J reporting [-]+++++++++ flies, that would be 9 to you, futureman.
0
répondu Brian Tiffin 2013-04-08 18:43:36