CODEWITHSUNDEEP
pythondata-structures
skyork
skyork

Reputation: 7401

Alternative data structure needed for deeply nested dictionary/map situation

Some background of the data: some different games are being played, and each of them hosts a number of players. Each game consists of a number of rounds, and during each round each player involved makes an action. What I am trying to do here is to construct a data structure in memory for storing the complete history of individual actions taken by the players across all the games being played.

An obvious structure is a deeply nested dictionary/hashmap, where each game_id is mapped to a number of player_ids, and each player_id is mapped to different round_numbers, and each round_number is mapped to an action.

In other words, game_id:player_id:round_number:action. On the other hand, I can also use game_id:round_number:player_id:action

Problem arises when I try to access the data structures above for different analytical purposes. For example, it's inconvenient to have game_id:player_id:round_number:action, if I want to know all the actions made by players in a particular round of a given game. Conversely, it is equally inconvenient to have game_id:round_number:player_id:action, if I want to know all the actions made by a particular player during the course of a given game. Unfortunately, in my case, I need to ask both those questions frequently.

I wonder if there is a single data structure which can store such data and is convenient for accessing both player-level and round-level data as described above. The implementation will be in Python, if that matters.

EDIT: a few people have recommended in-memory sqlite database to handle such relational queries. However, its performance may be an issue for me, as discussed here: SQLite Performance Benchmark -- why is :memory: so slow...only 1.5X as fast as disk?

Upvotes: 4

Views: 1390

Answers (3)

Paddy3118
Paddy3118

Reputation: 4772

You could store a set of tuples where each tuple stores just plain (game_id, player_id, round_number, action). You might also just use interned strings of the player name instead of an id. If you don't know what analysis you are to do then this format leaves each field equally accessible for statistical analysis and is simple to convert to storage in a database if you feel the need in the future.

A named tuple might also be used.

Upvotes: 0

Gerrat
Gerrat

Reputation: 29710

One way would be to store the data in a dict, but maintain indexes to allow quick access to various views into your data. You could structure this with a class, or just functions. Here is the jist of it (untested):

from collections import defaultdict

game_dict = {}  # keyed by (game, player, round) tuple
game_player_ix = defaultdict(list)
game_round_ix = defaultdict(list)

def add_action(game, player, round):
    game_dict[(game, round, player)] = action # track the action in the main dict
    game_player_ix[(game, player)].append(round)  # keep an index for lookups by player
    game_round_ix[(game, round)].append(player) # another index for lookups by round

def get_all_player_actions(game, player):
    return (game_dict[(game,player,round)] for round in game_round_ix[(game, player)]) # iterator

def get_all_round_actions(game, round):
    return (game_dict[(game,player,round)] for player in game_player_ix[(game, round)]) # iterator

Upvotes: 3

cabbagebot
cabbagebot

Reputation: 386

I would recommend either

  1. Writing a class that has functions that wrap common access pattern to your nested maps.
  2. Using an sqlite3 database.

EDIT:

I misread the question, sorry.

I can't think of a single data structure that would do this, though it wouldn't be too bad to replicate data slightly. Make player a class, and you could have rounds store a map of players to actions, and also have the player class contain a list of actions taken by that player.

Upvotes: 1

Related Questions