[GO] [Réinvention des roues] Tri de tournois à propulsion humaine [Python]

Environnement: Python 2.7

introduction

Lorsque vous passez ce que vous voulez trier, les éléments sont combinés dans une formule de tournoi et les deux éléments sont comparés manuellement. Le résultat final est un classement complet sans chevauchement dans le classement. (Toutes les relations d'ordre)

Il y a peut-être une meilleure implémentation, mais je voulais voir si ce que j'avais trouvé était correct, alors j'en ai fait une.

__ Addendum (2014/12/04) __ Implémentation trop naturelle → Re: Human power sorting [Python]

Aperçu de l'algorithme

Les grandes lignes de l'algorithme sont les suivantes.

Tout d'abord, placez tous les éléments dans un format de tournoi et laissez-les s'affronter (photo ci-dessus). A ce moment, gardez un taple qui a le gagnant au début de l'index. Le gagnant final est le plus fort de ces facteurs. C'est donc le rang 1 (flèche verte).

Deuxièmement, le rang 2 est le deuxième plus fort, donc bien sûr, vous auriez dû perdre quelque part contre ce champion. Vous pouvez rechercher cela à partir du taple que vous avez enregistré précédemment (la partie entourée de rouge et la flèche rouge). Par conséquent, si vous repositionnez ces éléments dans un format de tournoi et que vous participez (voir la figure ci-dessous), le rang 2 l'emportera définitivement.

Après cela, le rang 3 a dû être vaincu par le rang 2 dans les batailles précédentes (la partie entourée de bleu et la flèche bleue), je vais donc répéter cela. En faisant cela, il est stocké dans le rang du tableau à partir du rang le plus élevé, et vous pouvez voir que vous pouvez continuer jusqu'à ce qu'il n'y ait plus d'éléments.

Commentaire de code

Commentaire?

J'ai écrit en Python ce qui implémente l'algorithme ci-dessus.

Comme je l'ai écrit dans la description, cela a été écrit pour l'auto-analyse (rires) Je voulais quelque chose qui deviendrait éventuellement un classement lorsque j'énumérerais les mêmes genres et répondrais à celui que j'aimais. est.

• L'argument est géré par argparse.
• Comme vous pouvez le voir dans les 7 dernières lignes, la fonction est exécutée de manière récursive.

Une chose à garder à l'esprit est lorsque le nombre d'éléments est de 1 et que le tournoi ne peut pas avoir lieu, ou quand la fin finale aura lieu.

~~ La fonction de comparaison commentée dans la classe Rank était utilisée lorsqu'il était difficile de saisir à chaque fois à l'étape de test, et elle était également utilisée pour mesurer la quantité de calcul affichée plus tard. D'autres commentaires imprimés sont également à tester. Si vous affichez ceci, il sera plus facile de comprendre comment cela fonctionne. ~~

(Ajout) Dans le commentaire épuisé, en ajoutant "-v" à l'option, l'affichage est divisé selon la vérité de self.verbose. Il semble y avoir un meilleur moyen. Compare bascule également entre default_compare et auto_compare avec l'option "-t".

ranking.py

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#
# written by ssh0, September 2014.

description = """
Interface de classement pour l'auto-analyse.
Dans cette application
Créer une question comparative basée sur la liste donnée
Le classement est terminé lorsque l'utilisateur y répond.
              """

import argparse
import sys


class Rank:

    def __init__(self, args):
        self.pair = []  # match pairs
        self.rank = []  # sorted list
        self.args = args
        self.verbose = self.args.verbose
        if self.args.test:
            self.compare = self.auto_compare
        else:
            self.compare = self.default_compare
        self.N = 0

    def default_compare(self, a, b):
        self.N += 1
        print '\nQ[%d] which ones do you like?' % self.N
        print '  [j]: %s, [k]: %s' % (a, b)
        key_input = raw_input(">>> ")
        if key_input == 'j':
            ans = (a, b)
        elif key_input == 'k':
            ans = (b, a)
        else:
            raise ValueError('please select by "j" or "k".')
        return ans

    def auto_compare(self, a, b):  #Pour la mesure
        self.N += 1
        ans = (max(a, b), min(b, a))
        return ans

    def first_matching(self, data):
        n = len(data)
        N = 1
        if n == 0:
            self.func_finally()
        elif n == 1:
            self.rank.append(data[0])
            if self.verbose:
                print "n = 1 ::",
                print self.rank
            return self.first_matching(self.narrowing(data[0]))
        else:
            while n >= N:
                N = N*2
            unseed = 2*n - N
            first_winner = []
            for i in range(unseed/2):
                a, b = data.pop(0), data.pop(0)
                ans = self.compare(a, b)
                g, l = ans[0], ans[1]
                first_winner.append(g)
                self.pair.append((g, l))            
            data += first_winner
            member = [(data[2*i], data[2*i+1]) for i in range(len(data)/2)]
            return member

    def tournament(self, data):
        member = self.first_matching(data)
        if self.verbose:
            print "next tournament",
            print member
        while len(member) > 1:
            winner = []
            for p in member:
                ans = self.compare(p[0], p[1])
                g, l = ans[0], ans[1]
                self.pair.append((g, l))
                winner.append(g)
            member = [(winner[2*i], winner[2*i+1]) for i 
                      in range(len(member)/2)]
        ans = self.compare(member[0][0], member[0][1])
        top, l = ans[0], ans[1]
        self.pair.append((top, l))
        self.rank.append(top)
        if self.verbose:
            print "pairs",
            print self.pair
            print "champion",
            print top
            print "current rank",
            print self.rank
        return top

    def narrowing(self, x):
        unsort_table = []
        for_delete = []
        for i, pair in enumerate(self.pair):
            if x == pair[0]:
                unsort_table.append(pair[1])
                for_delete.append(i)
        for j in for_delete:
            self.pair[j] = None
        self.pair = [k for k in self.pair if k is not None]

        if self.verbose:
            print "unsort_table",
            print unsort_table
        return unsort_table
        
    def func_finally(self):
        result = ''
        for i, x in enumerate(self.rank):
            result += ' %d: %s\n' % (i+1, x)

        if self.args.outfile:
            outfile = self.args.outfile
            with open(outfile, 'a') as out:
                out.write(result)
            if not self.args.test:
                print result
                print "these result is saved in '%s'." % outfile
            else:
                print self.N
        elif self.args.test:
            print self.N
        else:
            print result
        sys.exit()


if __name__ == '__main__':

    parse = argparse.ArgumentParser(description=description)
    parse.add_argument('-l', '--list',
                       dest='obj',
                       nargs='*',
                       type=str,
                       help='list of some objects',
                       default=argparse.SUPPRESS
                       )
    parse.add_argument('-o', '--output',
                       dest='outfile',
                       type=str,
                       help='OPTIONAL: file to save output',
                       default=None
                       )
    parse.add_argument("-v", "--verbose",
                       help="increase output verbosity",
                       action="store_true"
                       )
    parse.add_argument("-t", "--test",
                       help="auto comparing mode (int, descending) for test",
                       action="store_true"
                       )
    args = parse.parse_args()
    data = args.obj

    rank = Rank(args)

    def ranking(pair_lists):
        result = rank.narrowing(rank.tournament(pair_lists))
        return result
        
    a = ranking(data)
    while True:
        a = ranking(a)

Exemple d'exécution 1

L'exemple d'exécution est le suivant.

➤  python ranking.py -l apple orange banana melon berry                      

Q[1] which ones do you like?
  [j]: apple, [k]: orange
>>> j

Q[2] which ones do you like?
  [j]: banana, [k]: melon
>>> j

Q[3] which ones do you like?
  [j]: berry, [k]: apple
>>> j

Q[4] which ones do you like?
  [j]: banana, [k]: berry
>>> k

Q[5] which ones do you like?
  [j]: apple, [k]: banana
>>> j

Q[6] which ones do you like?
  [j]: orange, [k]: banana
>>> j
 1: berry
 2: apple
 3: orange
 4: banana
 5: melon

Exemple d'exécution 2

Puisqu'il est difficile de dire si le tri est effectué correctement uniquement avec l'exemple ci-dessus, je vais montrer le cas où les nombres de 0 à 9 sont triés par ordre décroissant en affichant le débogage. Pairs est la liste des tuples dans la figure, et unsorted_table est les éléments du prochain tournoi spécifié par les flèches dans la figure. Dans la seconde moitié, le nombre d'éléments de unsorted_table peut devenir 1, il est donc nécessaire de séparer le traitement. Le processus se termine lorsque unsorted_table est vide.

➤  python ranking.py -l 1 0 6 3 4 9 5 7 8 2 -v

Q[1] which ones do you like?
  [j]: 1, [k]: 0
>>> j

Q[2] which ones do you like?
  [j]: 6, [k]: 3
>>> j
next tournament [('4', '9'), ('5', '7'), ('8', '2'), ('1', '6')]

Q[3] which ones do you like?
  [j]: 4, [k]: 9
>>> k

Q[4] which ones do you like?
  [j]: 5, [k]: 7
>>> k

Q[5] which ones do you like?
  [j]: 8, [k]: 2
>>> j

Q[6] which ones do you like?
  [j]: 1, [k]: 6
>>> k

Q[7] which ones do you like?
  [j]: 9, [k]: 7
>>> j

Q[8] which ones do you like?
  [j]: 8, [k]: 6
>>> j

Q[9] which ones do you like?
  [j]: 9, [k]: 8
>>> j
pairs [('1', '0'), ('6', '3'), ('9', '4'), ('7', '5'), ('8', '2'), ('6', '1'), ('9', '7'), ('8', '6'), ('9', '8')]
champion 9
current rank ['9']
unsort_table ['4', '7', '8']

Q[10] which ones do you like?
  [j]: 4, [k]: 7
>>> k
next tournament [('8', '7')]

Q[11] which ones do you like?
  [j]: 8, [k]: 7
>>> j
pairs [('1', '0'), ('6', '3'), ('7', '5'), ('8', '2'), ('6', '1'), ('8', '6'), ('7', '4'), ('8', '7')]
champion 8
current rank ['9', '8']
unsort_table ['2', '6', '7']

Q[12] which ones do you like?
  [j]: 2, [k]: 6
>>> k
next tournament [('7', '6')]

Q[13] which ones do you like?
  [j]: 7, [k]: 6
>>> j
pairs [('1', '0'), ('6', '3'), ('7', '5'), ('6', '1'), ('7', '4'), ('6', '2'), ('7', '6')]
champion 7
current rank ['9', '8', '7']
unsort_table ['5', '4', '6']

Q[14] which ones do you like?
  [j]: 5, [k]: 4
>>> j
next tournament [('6', '5')]

Q[15] which ones do you like?
  [j]: 6, [k]: 5
>>> j
pairs [('1', '0'), ('6', '3'), ('6', '1'), ('6', '2'), ('5', '4'), ('6', '5')]
champion 6
current rank ['9', '8', '7', '6']
unsort_table ['3', '1', '2', '5']
next tournament [('3', '1'), ('2', '5')]

Q[16] which ones do you like?
  [j]: 3, [k]: 1
>>> j

Q[17] which ones do you like?
  [j]: 2, [k]: 5
>>> k

Q[18] which ones do you like?
  [j]: 3, [k]: 5
>>> k
pairs [('1', '0'), ('5', '4'), ('3', '1'), ('5', '2'), ('5', '3')]
champion 5
current rank ['9', '8', '7', '6', '5']
unsort_table ['4', '2', '3']

Q[19] which ones do you like?
  [j]: 4, [k]: 2
>>> j
next tournament [('3', '4')]

Q[20] which ones do you like?
  [j]: 3, [k]: 4
>>> k
pairs [('1', '0'), ('3', '1'), ('4', '2'), ('4', '3')]
champion 4
current rank ['9', '8', '7', '6', '5', '4']
unsort_table ['2', '3']
next tournament [('2', '3')]

Q[21] which ones do you like?
  [j]: 2, [k]: 3
>>> k
pairs [('1', '0'), ('3', '1'), ('3', '2')]
champion 3
current rank ['9', '8', '7', '6', '5', '4', '3']
unsort_table ['1', '2']
next tournament [('1', '2')]

Q[22] which ones do you like?
  [j]: 1, [k]: 2
>>> k
pairs [('1', '0'), ('2', '1')]
champion 2
current rank ['9', '8', '7', '6', '5', '4', '3', '2']
unsort_table ['1']
n = 1 :: ['9', '8', '7', '6', '5', '4', '3', '2', '1']
unsort_table ['0']
n = 1 :: ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']
unsort_table []
 1: 9
 2: 8
 3: 7
 4: 6
 5: 5
 6: 4
 7: 3
 8: 2
 9: 1
 10: 0

Mesure du montant du calcul

Maintenant, puisque ce programme lui-même est fondé sur une contribution humaine, je voudrais que le nombre de comparaisons soit le plus petit. J'ai donc mesuré le nombre d'opérations de comparaison effectuées sur N éléments.

Préparez un script de test comme indiqué ci-dessous,

test_ranking.py

#!/usr/bin/env python
# -*- coding:utf-8 -*-

import numpy as np
import matplotlib.pyplot as plt
import commands

Ns = [10*i for i in range(1, 11)]
cal = []

for N in Ns:
    raw = [i for i in range(N)]
    x = np.random.choice(raw, N, replace=False)
    lists = ''
    for _x in x:
        lists += str(int(_x)) + ' '

    command = "python ranking.py -l %s -t" % lists
    result = commands.getoutput(command)
    cal.append(result)

f = plt.figure()
ax = f.add_subplot(111)
ax.plot(Ns, cal)
ax.set_xlabel(r"$N$")
ax.set_ylabel("calculate times")
plt.show()

Le graphique obtenu à la suite de l'exécution est présenté dans la figure ci-dessous. L'axe horizontal représente le nombre d'éléments N (par incréments de 10) et l'axe vertical représente le nombre d'opérations de comparaison.

[Limites théoriques du tri comparatif (Wikipedia)](http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88#.E6.AF.94.E8 .BC.83.E3.82.BD.E3.83.BC.E3.83.88.E3.81.AE.E7.90.86.E8.AB.96.E9.99.90.E7.95.8C) est O $ ( Pour n \ log n) $, 100 $ \ log 100 \ simeq 460,5 $ et $ N = 100 $, le montant de l'opération de comparaison était de 626, il semble donc que l'ordre ne puisse pas être réduit. A l'inverse, je pense que l'algorithme créé cette fois-ci était un bon algorithme de tri par comparaison.

Résumé

Le type de tournoi lui-même aurait dû être implémenté quelque part, donc je pense que j'aurais pu faire la même chose en définissant moi-même la définition de l'opérateur de comparaison. Cependant, je suis personnellement satisfait car j'ai pu y réfléchir moi-même. Je m'en fiche si cela s'appelle une réinvention de la roue. (Si vous connaissez les méthodes, merci de me le faire savoir)

cette? Qu'est-ce que l'auto-analyse?