Positionale Rankings und Umgang mit Gleichständen in Python

Question

(Es tut mir leid, dass in früheren Versionen dieser Frage die falsche Funktion angezeigt wurde, die ich korrigieren muss. Dies wurde behoben und ich hoffe, die Frage macht jetzt etwas mehr Sinn.)

Ich habe eine Liste von Objekten mit Punktzahlen und versuche, diesen Objekten basierend auf diesen Punktzahlen Ränge zuzuweisen. Unten ist im Grunde genommen, wie ich meine Daten ausgebe.

sorted_scores = [
    ('Apolo Ohno', 0),
    ('Shanie Davis', -1),
    ('Bodie Miller', -2),
    ('Lindsay Vohn', -3),  
    ('Shawn White', -3),
    ('Bryan Veloso', -4)
]

Ich habe ein Unentschieden. Die Funktion, die im Moment den Objekten Positionen zuweist, ist einfach eine Schleife, die den Wert von i als die endgültige Position des Objekts zuweist.

positions = {}

i = 1
for key, value in sorted_list:
    # Da in meinem Code die Zeichenfolgen IDs sind, verwende ich den Schlüssel, um das Objekt abzurufen.
    if value is not None:
        positions[key] = i
        i += 1

Das wird offensichtlich zurückgeben:

positions = {
    'Apolo Ohno': 1,
    'Shanie Davis': 2,
    'Bodie Miller': 3,
    'Lindsay Vohn': 4,        
    'Shawn White': 5,
    'Bryan Veloso': 6
}

Hoffentlich ergibt das etwas Sinn. Der Kern der Frage liegt in dieser Schleife. Es würde mehr Sinn ergeben, wenn sie sie wie folgt zurückgeben würde:

positions = {
    'Apolo Ohno': 1,
    'Shanie Davis': 2,
    'Bodie Miller': 3,
    'Lindsay Vohn': 4, # Gleicher Wert.
    'Shawn White': 4, # Gleicher Wert.
    'Bryan Veloso': 6
}

Wie würde ich die obige Funktion bearbeiten, um das zu erreichen, unter Berücksichtigung, dass ich zu einem beliebigen Zeitpunkt beliebig viele Gleichstände haben könnte, je nachdem, wie viele meiner Mitglieder das betreffende Objekt gerankt haben? Der höchste Rang sollte 1 sein, so dass er als solcher angezeigt werden kann: /

Vielen Dank im Voraus. :)

Answer 1

>>> sorted_scores = [
...     ('Apolo Ohno', 0),
...     ('Shanie Davis', -1),
...     ('Bodie Miller', -2),
...     ('Lindsay Vohn', -3),  
...     ('Shawn White', -3),
...     ('Bryan Veloso',-4)
... ]
>>> 
>>> res = {}
>>> prev = None
>>> for i,(k,v) in enumerate(sorted_scores):
...     if v!=prev:
...         place,prev = i+1,v
...     res[k] = place
... 
>>> print res
{'Apolo Ohno': 1, 'Bryan Veloso': 6, 'Shanie Davis': 2, 'Lindsay Vohn': 4, 'Bodie Miller': 3, 'Shawn White': 4}

Denken Sie daran, dass dicts ungeordnet sind. Um in der Reihenfolge des Platzes zu iterieren, müssen Sie dies tun:

>>> from operator import itemgetter
>>> print sorted(res.items(),key=itemgetter(1))
[('Apolo Ohno', 1), ('Shanie Davis', 2), ('Bodie Miller', 3), ('Lindsay Vohn', 4), ('Shawn White', 4), ('Bryan Veloso', 6)]

Answer 2

\=== Update nach Änderung/Klärung der Spezifikationen ===

# coding: ascii

def ranks_from_scores(sorted_scores):
    """sorted_scores: eine Liste von Tupeln (object_id, score), sortiert nach absteigendem Score
       gibt eine Zuordnung von Objekt-IDs zu Rängen zurück
    """
    ranks = {}
    previous_score = object()
    for index, (obj_id, score) in enumerate(sorted_scores):
        if score != previous_score:
            previous_score = score
            rank = index + 1
        ranks[obj_id] = rank
    return ranks

from operator import itemgetter
import pprint

scores0 = dict([
    ('Apolo Ohno', 0),
    ('Shanie Davis', -1),
    ('Bodie Miller', -2),
    ('Lindsay Vohn', -3),
    ('Shawn White', -3)
    ])

scores1 = {
    'lorem': 100,
    'ipsum': 200,
    'dolor': 300,
    'sit': 300,
    'amet': 300,
    'quia': 400,
    'consectetur': 500,
    'adipiscing': 500,
    'elit': 600,
    }

scores2 = {
    'lorem': 100,
    'ipsum': 200,
    'dolor': 300,
    'sit': 300,
    'amet': 300,
    'quia': 400,
    'consectetur': 500,
    'adipiscing': 500,
    'elit': 6000,
    }

import pprint
funcs = (ranks_from_scores, ) # Halten Sie diesen Bereich im Auge!
tests = (scores0, scores1, scores2)

for test in tests:
    print
    test_list = sorted(test.items(), key=itemgetter(1), reverse=True)
    print "Eingabe:", test_list
    for func in funcs:
        result = func(test_list)
        print "%s ->" % func.__name__
        pprint.pprint(result)

Ergebnisse:

Eingabe: [('Apolo Ohno', 0), ('Shanie Davis', -1), ('Bodie Miller', -2), ('Lindsay
 Vohn', -3), ('Shawn White', -3)]
ranks_from_scores ->
{'Apolo Ohno': 1,
 'Bodie Miller': 3,
 'Lindsay Vohn': 4,
 'Shanie Davis': 2,
 'Shawn White': 4}

Eingabe: [('elit', 600), ('consectetur', 500), ('adipiscing', 500), ('quia', 400),
 ('dolor', 300), ('sit', 300), ('amet', 300), ('ipsum', 200), ('lorem', 100)]
ranks_from_scores ->
{'adipiscing': 2,
 'amet': 5,
 'consectetur': 2,
 'dolor': 5,
 'elit': 1,
 'ipsum': 8,
 'lorem': 9,
 'quia': 4,
 'sit': 5}

Eingabe: [('elit', 6000), ('consectetur', 500), ('adipiscing', 500), ('quia', 400),
 ('dolor', 300), ('sit', 300), ('amet', 300), ('ipsum', 200), ('lorem', 100)]
ranks_from_scores ->
{'adipiscing': 2,
 'amet': 5,
 'consectetur': 2,
 'dolor': 5,
 'elit': 1,
 'ipsum': 8,
 'lorem': 9,
 'quia': 4,
 'sit': 5}

\=== Original Einreichung ===

Dieser Code geht davon aus, dass Sie tatsächlich möchten, dass der höchste Score Rang 1 erhält, nicht der niedrigste Score Rang 1 (oder 0!).

# coding: ascii

def ranks_from_scores(scores, debug=False):
    """scores (eine Zuordnung von Objekt-IDs zu Scores)
       gibt eine Zuordnung von Objekt-IDs zu Rängen zurück
    """
    alist = [(v, k) for k, v in scores.items()]
    alist.sort(reverse=True)
    if debug: print 'alist:', alist
    bdict = {}
    previous_score = object()
    for posn, (score, obj_id) in enumerate(alist):
        if score != previous_score:
            previous_score = score
            rank = posn + 1
        bdict[obj_id] = rank
    if debug:
        print 'bdict:', bdict
        blist = [(v, k) for k, v in bdict.items()]
        print 'blist:', sorted(blist)
    return bdict

ranks_from_scores(
    {'q': 10, 'w': 20, 'e': 20, 'r': 20, 't': 30},
    debug=True,
    )

Ausgabe:

alist: [(30, 't'), (20, 'w'), (20, 'r'), (20, 'e'), (10, 'q')]
bdict: {'q': 5, 'r': 2, 'e': 2, 't': 1, 'w': 2}
blist: [(1, 't'), (2, 'e'), (2, 'r'), (2, 'w'), (5, 'q')]

Answer 3

Der Weg, dies zu tun, besteht nicht darin, die Position des Elements in einer beliebigen Sequenz zu berechnen, sondern vielmehr zu berechnen, wie viele andere Elemente eine bessere Punktzahl haben.

BEARBEITEN:

Auf vielfachen Wunsch, alles mit O(n):

positionen = {}
cur_score = None # Punktzahl, die wir untersuchen
cur_count = 0 # Anzahl der anderen, die wir mit dieser Punktzahl gesehen haben

for ix, (name, score) in enumerate(sorted_scores):
  if score == cur_score: # Gleiche Punktzahl für diesen Spieler wie zuvor
    cur_count += 1
  else: # Unterschiedliche Punktzahl von zuvor
    cur_score = score
    cur_count = 0
  positionen[name] = ix - cur_count + 1 # 1 hinzufügen, weil ix 0-basiert ist

print positionen

Answer 4

Sie können die sorted und enumerate builtins, die groupby Methode von itertools und die itemgetter Methode von operator verwenden. Es wird angenommen, dass höhere Punktzahlen besser sind... (wenn niedrigere Punktzahlen besser sind, ändern Sie reverse=True in reverse=False)

>>> from itertools import groupby
>>> from operator import itemgetter
>>> scores = {
...     'lorem': 100,
...     'ipsum': 200,
...     'dolor': 300,
...     'sit': 300,
...     'amet': 300,
...     'quia': 400,
...     'consectetur': 500,
...     'adipiscing': 500,
...     'elit': 600,
...     }
>>> sorted_items = sorted(scores.items(), key=itemgetter(1), reverse=True)
>>> groups = groupby(sorted_items, itemgetter(1))
>>> for rank, (score, items) in enumerate(groups):
...     print rank+1, map(itemgetter(0), items)
... 
1 ['elit']
2 ['consectetur', 'adipiscing']
3 ['quia']
4 ['dolor', 'sit', 'amet']
5 ['ipsum']
6 ['lorem']

Answer 5

Lösung

Hier ist eine einfache Möglichkeit, dies zu tun, indem Sie Ihren Code ein wenig anpassen, anstatt Module zu importieren:

prev = None
rank = 0
incr = 1
positions = {}
for key, value in sorted_list:
    if value is not None:
        if value != prev:
            rank += incr
            incr = 1
        else:
            incr += 1
        positions[key] = rank
        prev = value

Ein Test

Für

sorted_list = [
    ('Apolo Ohno', 0),
    ('Shanie Davis', -1),
    ('Bodie Miller', -2),
    ('Lindsay Vohn', -3),  
    ('Shawn White', -3),
    ('Bryan Veloso',-4)
]

Ich erhalte die Positionen als:

{'Apolo Ohno': 1, 
'Shanie Davis': 2,
 'Bodie Miller': 3,
 'Lindsay Vohn': 4,
 'Shawn White': 4,
 'Bryan Veloso': 6}

was ich für das Ergebnis halte, auch wenn Sie nicht ganz klar sind, ob nach den beiden 4ern eine 6 stehen sollte.