Эффективный метод вычисления рангового индекса списка в Python

Я ищу эффективный способ вычисления рангового вектора списка в Python, аналогичном функции R rank. В простом списке без связей между элементами элемент я ранга-вектора списка l должен быть x тогда и только тогда, когда l[i] является x-м элементом в отсортированном списке. Пока это просто, следующий фрагмент кода делает трюк:

def rank_simple(vector):
    return sorted(range(len(vector)), key=vector.__getitem__)

Однако все сложнее, если исходный список имеет связи (т.е. несколько элементов с одинаковым значением). В этом случае все элементы, имеющие одинаковое значение, должны иметь одинаковый ранг, который является средним из их рангов, полученных с использованием наивного метода выше. Так, например, если у меня [1, 2, 3, 3, 3, 4, 5], наивное ранжирование дает мне [0, 1, 2, 3, 4, 5, 6], но я бы хотел иметь [0, 1, 3, 3, 3, 5, 6]. Какой из них был бы самым эффективным способом сделать это в Python?

Сноска: я не знаю, есть ли у NumPy метод для достижения этого или нет; если да, дайте мне знать, но меня все равно интересует чистое решение Python, поскольку я разрабатываю инструмент, который должен работать без NumPy.

Ответы

Ответ 1

Используя scipy, функция, которую вы ищете, - scipy.stats.rankdata:

In [13]: import scipy.stats as ss
In [19]: ss.rankdata([3, 1, 4, 15, 92])
Out[19]: array([ 2.,  1.,  3.,  4.,  5.])

In [20]: ss.rankdata([1, 2, 3, 3, 3, 4, 5])
Out[20]: array([ 1.,  2.,  4.,  4.,  4.,  6.,  7.])

Ранги начинаются с 1, а не 0 (как в вашем примере), но опять же, что работает функция R rank.

Вот эквивалент pure-python функции scipy rankdata:

def rank_simple(vector):
    return sorted(range(len(vector)), key=vector.__getitem__)

def rankdata(a):
    n = len(a)
    ivec=rank_simple(a)
    svec=[a[rank] for rank in ivec]
    sumranks = 0
    dupcount = 0
    newarray = [0]*n
    for i in xrange(n):
        sumranks += i
        dupcount += 1
        if i==n-1 or svec[i] != svec[i+1]:
            averank = sumranks / float(dupcount) + 1
            for j in xrange(i-dupcount+1,i+1):
                newarray[ivec[j]] = averank
            sumranks = 0
            dupcount = 0
    return newarray

print(rankdata([3, 1, 4, 15, 92]))
# [2.0, 1.0, 3.0, 4.0, 5.0]
print(rankdata([1, 2, 3, 3, 3, 4, 5]))
# [1.0, 2.0, 4.0, 4.0, 4.0, 6.0, 7.0]

Ответ 2

Это одна из функций, которые я написал для вычисления ранга.

def calculate_rank(vector):
  a={}
  rank=1
  for num in sorted(vector):
    if num not in a:
      a[num]=rank
      rank=rank+1
  return[a[i] for i in vector]

вход:

calculate_rank([1,3,4,8,7,5,4,6])

выход:

[1, 2, 3, 7, 6, 4, 3, 5]

Ответ 3

Это не дает точного результата, который вы указали, но, возможно, это было бы полезно в любом случае. Следующий фрагмент дает первый индекс для каждого элемента, дающий конечный ранг-вектор [0, 1, 2, 2, 2, 5, 6]

def rank_index(vector):
    return [vector.index(x) for x in sorted(range(n), key=vector.__getitem__)]

Ваше собственное тестирование должно было бы доказать эффективность этого.

Ответ 4

Существует действительно хороший модуль под названием Ranking http://pythonhosted.org/ranking/ с легко читаемой инструкцией. Чтобы загрузить, просто используйте easy_install ranking

Ответ 5

Вот небольшая вариация кода unutbu, включая необязательный аргумент "метод" для типа значения связанных рангов.

def rank_simple(vector):
    return sorted(range(len(vector)), key=vector.__getitem__)

def rankdata(a, method='average'):
    n = len(a)
    ivec=rank_simple(a)
    svec=[a[rank] for rank in ivec]
    sumranks = 0
    dupcount = 0
    newarray = [0]*n
    for i in xrange(n):
        sumranks += i
        dupcount += 1
        if i==n-1 or svec[i] != svec[i+1]:
            for j in xrange(i-dupcount+1,i+1):
                if method=='average':
                    averank = sumranks / float(dupcount) + 1
                    newarray[ivec[j]] = averank
                elif method=='max':
                    newarray[ivec[j]] = i+1
                elif method=='min':
                    newarray[ivec[j]] = i+1 -dupcount+1
                else:
                    raise NameError('Unsupported method')

            sumranks = 0
            dupcount = 0


    return newarray

Ответ 6

[sorted(l).index(x) for x in l]

sorted(l) предоставит отсортированный index(x) версии index(x) который даст index в отсортированном массиве

например:

l = [-1, 3, 2, 0,0]
>>> [sorted(l).index(x) for x in l]
[0, 4, 3, 1, 1]

Ответ 7

Эти коды дают мне много вдохновения, особенно код unutbu. Однако мои потребности проще, поэтому я немного изменил код.

В надежде помочь ребятам с одинаковыми потребностями.

Вот класс для записи баллов и рангов игроков.

class Player():
    def __init__(self, s, r):
        self.score = s
        self.rank = r

Некоторые данные.

l = [Player(90,0),Player(95,0),Player(85,0), Player(90,0),Player(95,0)]

Вот код для расчета:

l.sort(key=lambda x:x.score, reverse=True)    
l[0].rank = 1
dupcount = 0
prev = l[0]
for e in l[1:]:
    if e.score == prev.score:
        e.rank = prev.rank
        dupcount += 1
    else:
        e.rank = prev.rank + dupcount + 1
        dupcount = 0
        prev = e

Ответ 8

import numpy as np

def rankVec(arg):
    p = np.unique(arg) #take unique value
    k = (-p).argsort().argsort() #sort based on arguments in ascending order
    dd = defaultdict(int)
    for i in xrange(np.shape(p)[0]):
        dd[p[i]] = k[i]
    return np.array([dd[x] for x in arg])

timecomplexity - 46.2us

Ответ 9

Итак... это 2019 год, и я понятия не имею, почему никто не предложил следующее:

# Python-only
def rank_list( x, break_ties=False ):
    n = len(x)
    t = list(range(n))
    s = sorted( t, key=x.__getitem__ )

    if not break_ties:
        for k in range(n-1):
            t[k+1] = t[k] + (x[s[k+1]] != x[s[k]])

    r = s.copy()
    for i,k in enumerate(s):
        r[k] = t[i]

    return r

# Using Numpy, see also: np.argsort
def rank_vec( x, break_ties=False ):
    n = len(x)
    t = np.arange(n)
    s = sorted( t, key=x.__getitem__ )

    if not break_ties:
        t[1:] = np.cumsum(x[s[1:]] != x[s[:-1]])

    r = t.copy()
    np.put( r, s, t )
    return r

Этот подход имеет линейную сложность времени выполнения после начальной сортировки, он хранит только 2 массива индексов и не требует значений, которые можно хэшировать (требуется только попарное сравнение).

AFAICT, это лучше, чем другие подходы, предложенные до сих пор:

  • Подход @unutbu, по сути, похож, но (я бы сказал, слишком сложный для того, о чем спрашивал ОП);
  • Все предложения с использованием .index() ужасны, со сложностью времени исполнения N ^ 2;
  • @Yuvraj Singh немного улучшает поиск .index() используя словарь, однако при операциях поиска и вставки на каждой итерации это все еще крайне неэффективно как во времени (NlogN), так и в пространстве, а также требует, чтобы значения были хэшируемыми.