带三方决胜机制的Python高效排序算法实现问询

Got it, let's break down how to implement this US sports-style tiebreaker sorting efficiently—especially since you need to run it 100k times with up to 15 teams, speed is key. Here's a practical, optimized approach:

1. Optimized Data Representation #

First, let's tweak your input format to speed up tiebreaker calculations:

• Replace the H2H tiebreak list with a set (O(1) membership checks instead of O(n) for lists)
• Optional: Preprocess a bidirectional H2H win map for even faster lookups (great for 100k runs)

Example formatted input:

# Using sets for H2H wins (faster lookups)
testData = [['Lakers', 48, {'Clippers'}, 6], ['Clippers', 48, {'Warriors'}, 8], ['Warriors', 47, {'Lakers'}, 10]]

# Optional preprocessed H2H map (run once before all 100k sorts)
def preprocess_h2h(teams):
    h2h_map = {}
    for name, _, h2h_wins, _ in teams:
        h2h_map[name] = {opp: 1 for opp in h2h_wins}
    return h2h_map

h2h_map = preprocess_h2h(testData)

2. Fast Sorting Implementation #

We'll leverage Python's built-in sorted() (powered by Timsort, a highly optimized C implementation) instead of writing custom sorting logic. The core logic iteratively handles groups of teams with the same max wins, applying tiebreakers as needed:

def magic_sort(teams):
    remaining = teams.copy()
    ranked = []
    
    while remaining:
        # Get current highest win count
        max_wins = max(team[1] for team in remaining)
        # Filter teams tied for max wins
        tie_group = [t for t in remaining if t[1] == max_wins]
        
        if len(tie_group) == 1:
            # No tie: add directly to rankings
            ranked.append(tie_group[0][0])
            remaining.remove(tie_group[0])
        else:
            # Calculate H2H wins within the tie group
            tie_group_names = [t[0] for t in tie_group]
            
            def get_tiebreaker_key(team):
                name, _, h2h_wins, point_diff = team
                # Count wins against other teams in the tie group
                h2h_count = sum(1 for opp in tie_group_names if opp != name and opp in h2h_wins)
                # Sort by: -H2H wins, -point differential (higher = better)
                return (-h2h_count, -point_diff)
            
            # Sort the tie group using the custom key
            sorted_tie = sorted(tie_group, key=get_tiebreaker_key)
            # Add sorted teams to rankings and remove from remaining
            for team in sorted_tie:
                ranked.append(team[0])
                remaining.remove(team)
    
    return ranked

Why This Is Fast #

• Built-in sorted() is far faster than handwritten Python sorting logic
• Set-based H2H checks cut down tiebreaker calculation time
• Iterative grouping avoids recursive overhead (though recursion would work for 15 teams, iteration is more straightforward)
• For 15 teams, each sort runs in near-constant time—100k runs will be completed in milliseconds

3. Test Case Validation #

Let's verify with your examples:

Test Case 1 #

testData = [['Lakers', 48, {'Clippers'}, 6], ['Clippers', 48, {'Warriors'}, 8], ['Warriors', 47, {'Lakers'}, 10]]
print(magic_sort(testData))  # Output: ['Lakers', 'Clippers', 'Warriors']

Explanation: Lakers beat Clippers in their head-to-head, so they take the top spot in the 48-win group.

Test Case 2 #

testData2 = [['Lakers', 48, {'Clippers'}, 6], ['Clippers', 48, set(), 8], ['Warriors', 48, {'Lakers', 'Clippers'}, 10]]
print(magic_sort(testData2))  # Output: ['Warriors', 'Lakers', 'Clippers']

Explanation: Warriors have 2 H2H wins in the tie group, Lakers have 1, Clippers have 0.

Test Case 3 #

testData3 = [['Lakers', 47, {'Clippers'}, 6], ['Clippers', 47, {'Warriors'}, 8], ['Warriors', 47, {'Lakers'}, 10]]
print(magic_sort(testData3))  # Output: ['Warriors', 'Clippers', 'Lakers']

Explanation: All 3 teams have 1 H2H win, so we fall back to point differential (highest first).

内容的提问来源于stack exchange，提问作者qwertylpc