具有三路决胜局的Python高效排序算法

Question

我正在尝试实现您可能会在(美国)体育运动中看到的(三向)打破平局的程序。我想先按获胜次数排序，如果平局则使用头对头决胜局。

我需要它作为尽可能快的运行时，我并不真正关心内存需求。如果有更好的方式来表示我的数据，那么这也是一个有用的答案。

我要排序的数据最多有 15 个值，所以运行时在这方面还不错，我只想做 10 万次。

伪代码看起来像这样:

Iterator = 0    
maxVal = max value of wins
maxes = teams with wins == maxVal
If len(maxes) == 1
    rank[values] = iterator
    iterator += 1
    sort(restOfData)
Else 
    # H2Hwins computes the amount of wins for teams currently tied incase of 2 or more teams tied  
    counts = sorted([(h2hwins(t, maxes), pointDifferential) for team in maxes])
    for c in counts
        rank[value] = iterator
        iterator += 1
    sort(restOfData)
return rank

所以如果我有以下输入，这些将是输出:

# Columns are Team, Wins, H2H Tiebreaks, Point Differential
# Lakers win tie based on H2H with Clippers
testData = [['Lakers', 48, ['Clippers'], 6], ['Clippers', 48, ['Warriors'], 8], ['Warriors', 47, ['Lakers'], 10]]
magicSort(testData)
>>> ['Lakers', 'Clippers', 'Warriors']

# Warriors have 2 H2H tiebreakers so they are 1st.  Lakers have 1 H2H tiebreaker so they are 2nd.
testData2 = [['Lakers', 48, ['Clippers'], 6], ['Clippers', 48, [''], 8], ['Warriors', 48, ['Lakers', 'Clippers'], 10]]
magicSort(testData2)
>>> ['Warriors', 'Lakers', 'Clippers']

# All 3 are tied so we default to point differential
testData3 = [['Lakers', 47, ['Clippers'], 6], ['Clippers', 47, ['Warriors'], 8], ['Warriors', 47, ['Lakers'], 10]]
magicSort(testData3)
>>> ['Warriors', 'Clippers', 'Lakers']

如果需要，我可以想出更多的测试用例，但我相信这涵盖了边缘情况

Answer 1

更新后的答案:您需要一个排序算法来打破您定义的字段顺序中的三向关系:a) 获胜 b) H2H 平局数 c) 分差

我建议您在任何时候使用数据做一些复杂的事情(例如多键排序，像这样)时使用 pandas。首先，我们必须将您奇怪的数据格式(递归嵌套列表)转化为可用的形式来构建数据框:

• 4 元组列表:Team、Wins、H2H_Tiebreaks、Point_Differential
  • 请注意，H2H_Tiebreaks 应该是一个元组，即使它的长度为 1 或 0。严格来说，我们只关心它的长度 (Num_H2H_Ties)，而不关心它的内容<
• 然后我们执行 df.sort_values(by=['Wins','Num_H2H_Ties', 'Point_Differential'], ascending=False)。代码在底部:
  • 如果您只想要获胜队的行，请执行 .iloc[0]
  • 如果您只想要获胜队的名字，请执行 .iloc[0, 0]

解决方法:

import pandas as pd

cols = ['Team', 'Wins', 'H2H_Tiebreaks', 'Point_Differential']

# 1) Lakers win tie based on H2H with Clippers
dat = [('Lakers', 48, ('Clippers',), 6), ('Clippers', 48, ('Warriors',), 8), ('Warriors', 47, ('Lakers',), 10)]
df1 = pd.DataFrame(data=dat, columns=cols)

# 2) Warriors have 2 H2H tiebreakers so they are 1st.  Lakers have 1 H2H tiebreaker so they are 2nd.
dat2 = [('Lakers', 48, ('Clippers',), 6), ('Clippers', 48, (), 8), ('Warriors', 48, ('Lakers', 'Clippers'), 10)]
df2  = pd.DataFrame(data=dat2, columns=cols)

# 3) All 3 are tied so we default to point-differential
dat3 = [('Lakers', 47, ('Clippers',), 6), ('Clippers', 47, ('Warriors',), 8), ('Warriors', 47, ('Lakers',), 10)]
df3  = pd.DataFrame(data=dat3, columns=cols)

############    
df1['Num_H2H_Ties'] = df1['H2H_Tiebreaks'].apply(len)
df1.sort_values(by=['Wins','Num_H2H_Ties', 'Point_Differential'], ascending=False)

# Result:
       Team  Wins H2H_Tiebreaks  Point_Differential  Num_H2H_Ties
1  Clippers    48   (Warriors,)                   8             1
0    Lakers    48   (Clippers,)                   6             1
2  Warriors    47     (Lakers,)                  10             1

############
df2['Num_H2H_Ties'] = df2['H2H_Tiebreaks'].apply(len)
df2.sort_values(by=['Wins','Num_H2H_Ties', 'Point_Differential'], ascending=False)

# Result:
   Team  Wins       H2H_Tiebreaks  Point_Differential  Num_H2H_Ties
2  Warriors    48  (Lakers, Clippers)                  10             2
0    Lakers    48         (Clippers,)                   6             1
1  Clippers    48                  ()                   8             0
############
df3['Num_H2H_Ties'] = df3['H2H_Tiebreaks'].apply(len)
df3.sort_values(by=['Wins','Num_H2H_Ties', 'Point_Differential'], ascending=False)

# Result:
       Team  Wins H2H_Tiebreaks  Point_Differential  Num_H2H_Ties
2  Warriors    47     (Lakers,)                  10             1
1  Clippers    47   (Warriors,)                   8             1
0    Lakers    47   (Clippers,)                   6             1

这里是一个函数:

def sort_nway_tiebreaker(df):

    # Filter only teams with max-Wins
    df = df[df['Wins'] == df['Wins'].max()]

    df['Num_H2H_Ties'] = df['H2H_Tiebreaks'].apply(len)

    df = df.sort_values(by=['Wins','Num_H2H_Ties', 'Point_Differential'], ascending=False)

    return df.iloc[0]