Spaß am Freitag: Ranking erstellen

[Hyperion]

Moin moin,

ich las heute morgen auf reddit eine nette Aufgabe und dachte, dass ich das mal selber probieren muss:

Rank Vectors

Given an array (or list) of scores, return the array of ranks for each value in the array. The largest value has rank 1, the second largest value has rank 2, and so on. Ties should be handled by assigning the same rank to all tied values. For example:

ranks([9,3,6,10]) = [2,4,3,1] and ranks([3,3,3,3,3,5,1]) = [2,2,2,2,2,1,7]

because there is one 1st place value, a five-way tie for 2nd place, and one in 7th place.

Meine Lösung so weit:

Code: Alles auswählen

def ranks(values):
    counts = Counter(values)
    rank_sum = 1
    rank_values = {}
    for value in sorted(counts.keys(), reverse=True):
        rank_values[value] = rank_sum
        rank_sum += counts[value]
    return [rank_values[value] for value in values]
    
assert(ranks([9,3,6,10]) == [2,4,3,1])
assert(ranks([3,3,3,3,3,5,1]) == [2,2,2,2,2,1,7])

Abgesehen davon, dass es da für ``numpy`` ggf etwas fertiges gibt - wer hat andere interessante (und ggf. effizientere) Ansätze? Oder vielleicht auch in anderen Sprachen?

Man könnte das ganze natürlich als Iterator-Funktion schreiben, aber laut Aufgabe soll ja ein "Array" (was offenbar eine Liste sein soll) zurück gegeben werden.

Ich habe tatsächlich noch nicht auf reddit gespickt, was da so an Lösungen angeboten wird

[bwbg]

Ein erster Ansatz:

Code: Alles auswählen

#!/usr/bin/env python3
def rank(x, xs):
    return len(xs) - sum( 1 for e in xs if x >= e ) + 1

def ranks(xs):
    return [rank(e, xs) for e in xs]
    
assert ranks([9, 3, 6, 10]) == [2, 4, 3, 1]
assert ranks([3, 3, 3, 3, 3, 5, 1]) == [2, 2, 2, 2, 2, 1, 7]

[Hyperion]

@bwbg: Hübsch kurz Aber natürlich sehr ineffizient - O(n^2) als Laufzeit...

(Mein Ansatz hat O(n log n))

[snafu]

In Sachen Effizienz würde mir auch nichts besseres einfallen. Höchstens `groupby()` anstelle des `Counter()`s benutzen:

Code: Alles auswählen

from itertools import groupby

def ranks(values):
    value_ranks = {}
    rank = 1
    grouped = ((key, list(group)) for key, group in groupby(values))
    for key, group in sorted(grouped, reverse=True):
        value_ranks[key] = rank
        rank += len(group)
    return [value_ranks[val] for val in values]

Das ändert aber nichts am generellen Laufzeitverhalten. Man könnte das Erstellen der Listen sogar als negativen Punkt ansehen.

[BlackJack]

JavaScript, mit `underscore.js` als `_`:

Code: Alles auswählen

var ranks = function (values) {
  var result = [];
  _.chain(values)
    .map(function (v, i) {return {value: v, index: i};})
    .sortBy('value')
    .reverse()
    .each(
      function (x, i) {
        if (x.value === this.previousValue) {
          this.correction++;
        } else {
          this.previousValue = x.value;
          this.correction = -1;
        }
        result[x.index] = i - this.correction;
      },
      {previousValue: null, correction: -1}
    );
  return result;
};

[jerch]

Bucketsort und unpythonisch macht der Sache Beine

Code: Alles auswählen

def ranks(values):
    highest = max(values)
    bucket = [0] * (highest + 1)
    for value in values:
        bucket[value] += 1
    value2rank = {}
    rank = 1
    for i in xrange(len(bucket)-1, -1, -1):
        if bucket[i]:
            value2rank[i] = rank
            rank += bucket[i]
    return [value2rank[value] for value in values]

[Sirius3]

@jerch: und warum kann man das ganze nicht auch pythonisch schreiben?

Code: Alles auswählen

def ranks(values):
    bucket = [0] * (max(values) + 1)
    for value in values:
        bucket[value] += 1
    rank = 1
    ranks = []
    for cnt in reversed(bucket):
        ranks.append(rank)
        rank += cnt
    ranks.reverse()
    return [ranks[value] for value in values]

[BlackJack]

Den JavaScript-Code 1:1 in CoffeeScript umgeschrieben:

Code: Alles auswählen

ranks = (values) ->
    result = []
    _.chain(values)
        .map (v, i) ->
            value: v
            index: i
        .sortBy 'value'
        .reverse()
        .each (x, i) ->
            if x.value == @previousValue
                @correction++
            else
                @previousValue = x.value
                @correction = -1
            result[x.index] = i - @correction
        ,
            previousValue: null
            correction: -1
    result

Edit: Und noch mal mehr mit CoffeeScript-Sprachmitteln:

Code: Alles auswählen

ranks = (values) ->
    result = []
    previousValue = null
    correction = -1
    for [value, index], i in _.sortBy(([v, i] for v, i in values), 0).reverse()
        if value == previousValue
            correction++
        else
            previousValue = value
            correction = -1
        result[index] = i - correction
    result

[Hyperion]

@snafu: ``groupby`` klappt aber nur eingeschränkt, wenn die Ränge nicht verteilt im Vektor vorkommen.

Am folgenden scheitert Dein Code:

Code: Alles auswählen

assert ranks([9, 3, 10, 6, 10]) == [3, 5, 1, 4, 1]

[Sr4l]

Ohne imports und schnick schnack

Code: Alles auswählen

def ranks(score):
    score_sorted = score[:]
    score_sorted.sort(reverse=True)
    rank = []
    for e in score:
        rank.append(score_sorted.index(e)+1)
    return rank

assert ranks([9,3,6,10]) == [2,4,3,1] 
assert ranks([3,3,3,3,3,5,1]) == [2,2,2,2,2,1,7]

*edit*
kürzer

Code: Alles auswählen

def ranks(score):
    score_sorted = sorted(score, reverse=True)
    return [score_sorted.index(e)+1 for e in score]

[BlackJack]

@Sr4l: Zählt Effizienz zu Schnick Schnack? Das `index()` da drin sorgt für eine unschöne Laufzeit.

[Sr4l]

Bis 10.000 Einträge absolut vertretbar. Bei mehr muss man dann halt Hardware mäßig aufrüsten.

[jerch]

@Sirius3:
Haha schönes Ding - zeigt sehr eindrucksvoll, dass ein O(n) in einer Pythonschleife sehr viel mehr Konstantenanteil mitschleppt als in C. Von der Komplexität sind beide Versionen in O(n), allerdings hat Deine Variante 2 n-Durchläufe mehr drin (2x reversed). Und trotzdem läuft das selbst mit dünn besetzten Rängen schneller als das value2rank Mapping, welches hier eigentlich bei Speicherverbrauch und Laufzeit abkürzen kann.

[Sirius3]

@jerch: das erste reverse ist nur virtuell, braucht also gar keine Rechenzeit.

[Hyperion]

@jerch: das erste reverse ist nur virtuell, braucht also gar keine Rechenzeit.

Und das zweite kann man sich sparen, wenn man eine ``deque`` statt einer Liste für die Ränge verwendet:

Code: Alles auswählen

from collections import deque    
    
def ranks(values):
    bucket = [0] * (max(values) + 1)
    for value in values:
        bucket[value] += 1
    rank = 1
    ranks = deque()
    for cnt in reversed(bucket):
        ranks.appendleft(rank)
        rank += cnt
    return [ranks[value] for value in values]
    
assert(ranks([9,3,6,10]) == [2,4,3,1])
assert(ranks([3,3,3,3,3,5,1]) == [2,2,2,2,2,1,7])
assert ranks([9, 3, 10, 6, 10]) == [3, 5, 1, 4, 1])

Müsste man mal timen, was das so spart...

[jerch]

@Hyperion:
deque kann hier nichts einsparen, da der Indexzugriff O(n) ist (was im return zu n*n wird). Und `reverse()` selbst arbeitet inplace mit Anfangs-/Endpointer-Vergleich, was die schnellste Variante in C sein dürfte.

@Sirius3:
War immer davon ausgegangen, das `reversed()` die Eingabe klont. Manchmal hilft Doku-Lesen.

[Hyperion]

@Hyperion:
deque kann hier nichts einsparen, da der Indexzugriff O(n) ist (was im return zu n*n wird).

Manchmal hilft Doku-Lesen.

Ja, weil:

In addition to the above, deques support iteration, pickling, len(d), reversed(d), copy.copy(d), copy.deepcopy(d), membership testing with the in operator, and subscript references such as d[-1]. Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.

Edit: Oops... im ``return``... stimmt

[EyDu]

@Hyperion:
deque kann hier nichts einsparen, da der Indexzugriff O(n) ist (was im return zu n*n wird). Und `reverse()` selbst arbeitet inplace mit Anfangs-/Endpointer-Vergleich, was die schnellste Variante in C sein dürfte.

Man könnte vor dem Indexzugriff eine Liste daraus machen. Oder eine eigene Deque-Implementierung für das Problem basteln, da die Anzahl der Elemente vorher bekannt ist. Oder man lässt gleich die Deque weg, weil sie gar nicht benötigt wird:

Code: Alles auswählen

def ranks(values):
    bucket = [0] * (max(values) + 1)
    for value in values:
        bucket[value] += 1
    rank = 1

    ranks = []
    for cnt in reversed(bucket):
        ranks.append(rank)
        rank += cnt
    return [ranks[-value-1] for value in values]
    
assert(ranks([9,3,6,10]) == [2,4,3,1])
assert(ranks([3,3,3,3,3,5,1]) == [2,2,2,2,2,1,7])
assert(ranks([9, 3, 10, 6, 10]) == [3, 5, 1, 4, 1])

[jerch]

Hmm sehr seltsam, EyDus Variante läuft insgesamt schlechter, mit größerer Liste nimmt der Abstand sogar zu (Abhängigkeit zur Größe der Liste? WTH ). Hätt ich nicht erwartet, zumal man einen n-Durchlauf spart. Mag CPython keine negativen Indices? :K

@Hyperion:
Das O(n) bezog ich auf den "zufälligen" Indexzugriff (worst case). Das O(1) an den Rändern ist klar bei doppelt verlinkten Listen.

Edit:
Anscheinend ist der Zeitaufwand fürs Umrechnen der negativen Indices etwas größer als die Rechenzeit pro Eintrag in reverse(), was in der Summe die Abhängigkeit von der Größe erklären würde.

[Hyperion]

@Hyperion:
Das O(n) bezog ich auf den "zufälligen" Indexzugriff (worst case). Das O(1) an den Rändern ist klar bei doppelt verlinkten Listen.

Jo, das hatte ich just nach Absetzen des Postings erkannt