满足多查询需求的两人游戏对战结果存储最优数据结构咨询

Great question! The single hash map (key: Player, value: list of losers) approach you mentioned definitely hits efficiency roadblocks for certain queries—like finding who beat a specific player or listing all their opponents—since you’d have to scan the entire map to dig up that info. Here’s an optimized, multi-structure setup that makes all your required operations fast:

Core Data Structures #

We’ll maintain three complementary structures (using sets instead of lists where possible for O(1) membership checks):

• wins: Dict[Player, Set[Player]]: Maps each player to the set of players they’ve beaten. Using a set lets us quickly verify if a specific win exists.
• losses: Dict[Player, Set[Player]]: Maps each player to the set of players who’ve beaten them. This eliminates the need to scan the entire dataset to find a player’s losses.
• all_matches: List[Tuple[Player, Player]]: Stores every match result as a tuple (winner, loser). This gives us a direct, ready-to-use list for full result queries.

How Each Query Works (and Their Efficiency) #

Let’s walk through your required operations to show why this setup shines:

1. Check if Player A beat Player B:
   Simply check if B is in wins.get(A, set()). This runs in O(1) time thanks to the set’s membership check.
2. List all players Player A has beaten:
   Return wins.get(A, []) (converting the set to a list if needed). Retrieving the set is O(1), and iterating over the results is O(k) where k is the number of wins—this is unavoidable since you have to output all results.
3. List all players who beat Player A:
   Return losses.get(A, []). Same as above: O(1) to retrieve the set, O(m) to iterate over losses (m = number of losses).
4. List all players Player A has played against:
   Combine the sets from wins.get(A, set()) and losses.get(A, set()) (using a union operation). This runs in O(k + m) time, which is optimal since you’re collecting all unique opponents.
5. List all game results:
   Return the all_matches list directly. Retrieval is O(1), and iterating over all matches is O(n) where n is the total number of games—again, unavoidable for this query.

Why This Is Better Than a Single Hash Map #

• No more full scans of your dataset for loss/opponent queries: The losses map puts that info at your fingertips instantly.
• Membership checks (like "did A beat B?") are lightning fast with sets, whereas a list would require O(k) time to scan through all wins.
• All operations scale well even as the number of players and matches grows—no unexpected slowdowns for common queries.

One small note: When adding a new match result (winner, loser), make sure to update all three structures:

• Add loser to wins[winner] (initialize the set if the winner isn’t already in the map)
• Add winner to losses[loser] (same initialization logic)
• Append the tuple to all_matches

This extra setup work during data insertion pays off huge dividends for query performance.

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