Phương pháp hiệu quả để tính toán vectơ xếp hạng của một danh sách trong Python

Question

Tôi đang tìm một cách hiệu quả để tính toán vectơ xếp hạng của một danh sách bằng Python, tương tự như hàm rank của R. Trong một danh sách đơn giản không có mối quan hệ giữa các yếu tố, yếu tố i của vector hạng của một danh sách l nên x khi và chỉ khi l[i] là yếu tố -thứ x trong danh sách được sắp xếp. Đây là đơn giản cho đến nay, đoạn mã sau hiện các trick:

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

Mọi thứ trở nên phức tạp, tuy nhiên, nếu danh sách ban đầu có quan hệ (ví dụ: nhiều yếu tố với cùng giá trị). Trong trường hợp đó, tất cả các phần tử có cùng giá trị phải có cùng một thứ hạng, đó là mức trung bình của các cấp bậc của chúng thu được bằng cách sử dụng phương pháp ngây thơ ở trên. Vì vậy, ví dụ, nếu tôi có [1, 2, 3, 3, 3, 4, 5], thứ hạng ngây thơ cho tôi [0, 1, 2, 3, 4, 5, 6], nhưng những gì tôi muốn có là [0, 1, 3, 3, 3, 5, 6]. Cái nào sẽ là cách hiệu quả nhất để làm điều này trong Python?

---

Lưu ý: Tôi không biết liệu NumPy đã có phương pháp để đạt được điều này hay chưa; nếu có, xin vui lòng cho tôi biết, nhưng tôi sẽ được quan tâm đến một giải pháp Python tinh khiết anyway như tôi đang phát triển một công cụ mà nên làm việc mà không có NumPy là tốt.

Answer 1

Sử dụng scipy, chức năng bạn đang tìm kiếm là 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.]) 

Các cấp bậc bắt đầu từ 1, chứ không phải là 0 (như trong ví dụ của bạn), nhưng sau đó một lần nữa, đó là cách Chức năng 's rank cũng hoạt động.

Đây là một tương đương tinh khiết-python chức năng rankdata scipy 's:

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] 

Answer 2

này không cho kết quả chính xác mà bạn chỉ định, nhưng có lẽ nó sẽ có ích anyways. Đoạn sau đây cung cấp cho các chỉ số đầu tiên cho mỗi yếu tố, năng suất một vector thứ hạng cuối cùng của [0, 1, 2, 2, 2, 5, 6]

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

thử nghiệm riêng của bạn sẽ phải chứng minh tính hiệu quả của việc này.

Answer 3

Có một mô-đun thực sự tốt đẹp được gọi là Xếp hạng http://pythonhosted.org/ranking/ với trang hướng dẫn dễ làm theo. Để tải xuống, chỉ cần sử dụng easy_install ranking

Answer 4

Dưới đây là một biến thể nhỏ của mã của unutbu, bao gồm đối số 'phương pháp' tùy chọn cho loại giá trị của xếp hạng được gắn.

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 

Answer 5

Các mã này cho tôi rất nhiều cảm hứng, đặc biệt là mã của unutbu. Tuy nhiên, nhu cầu của tôi đơn giản hơn, vì vậy tôi đã thay đổi mã một chút.

Hy vọng sẽ giúp những người có cùng nhu cầu.

Đây là lớp học để ghi điểm và xếp hạng của người chơi.

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

Một số dữ liệu.

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

Đây là đoạn mã để tính:

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 

Answer 6

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 là 46.2us

Answer 7

Đây là một trong những chức năng mà tôi đã viết để tính toán xếp hạng.

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] 

đầu vào: calculate_rank ([1,3,4,8,7,5,4,6])
đầu ra: [1, 2, 3, 7, 6, 4, 3, 5]