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）Wins b）H2H中断次数c）点微分

我建议您在任何时候使用pandas来处理复杂的数据（比如像这样的多键排序）。 首先，我们必须将您奇怪的数据格式（递归嵌套列表）转换为可用的形式，以构建数据帧：

• 四元组列表：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]