Эффективный способ вычислить вектор разряда списка в Python
Я просто опубликую свою реверсивную логику здесь, и теперь она работает. бесплатно комментировать
def reverse(self):
if self.head is None or self.head.next is None: return
cur = self.head
def reverse_node(node):
if node is None: return node
node.next, node.prev = node.prev, node.next
if node.prev is None: return node
return reverse_node(node.prev)
self.head = reverse_node(cur)
4 ответа
Используя 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 .
Вот чистый Python-эквивалент функции rankdata scipy :
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]
Эти коды вдохновляют меня, особенно код 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
Итак ... это 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), так и в пространстве, а также требует, чтобы значения были хэшируемыми.
Это не дает точного результата, который вы указали, но, возможно, это все равно будет полезно. Следующий фрагмент кода дает первый индекс для каждого элемента, что дает окончательный вектор ранжирования [0, 1, 2, 2, 2, 5, 6]
def rank_index(vector):
return [vector.index(x) for x in sorted(range(n), key=vector.__getitem__)]
. Ваше собственное тестирование должно доказать эффективность этого.