三路并归排序算法在Python中的高效实现方式

Question

三路并归排序算法在Python中的高效实现方式

pythonalgorithmsorting

3

我正在尝试实现一种在（美国）体育比赛中可能会看到的三方平局打破程序。我想首先按胜利次数排序，如果并列则使用头对头的打破者。

我希望这个运行时尽可能快，对内存要求并不在意。如果有更好的方法来表示我的数据，使其易于使用，那也是一个有用的答案。

我要排序的数据最多只有15个值，因此从这个角度来说运行时间并不糟糕，我只想做100k次。

伪代码大致如下：

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']

如果需要，我可以提供更多的测试案例，但我相信这已经涵盖了边缘情况。

- qwertylpc

顺便说一下，你的输入数据格式非常奇怪，它是一个递归嵌套的列表，而不是元组列表。你为什么要使用那种格式，处理起来会很麻烦？这是从爬虫中获取的吗？ - smci

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- smci · Accepted Answer

更新的答案：您需要一种排序算法，在您定义的字段顺序中破解三路绑定：a）胜利 b）H2H Tiebreaks数量 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]