Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Indexing of multi-dimensional arrays #467

Open
tturocy opened this issue Sep 20, 2024 · 0 comments
Open

Indexing of multi-dimensional arrays #467

tturocy opened this issue Sep 20, 2024 · 0 comments
Labels
c++ Items which involve writing in C++ enhancement

Comments

@tturocy
Copy link
Member

tturocy commented Sep 20, 2024

In two important places - the normal form and sequence form (the latter currently in src/solvers/enumpoly/gameseq.(cc,h)) we have the problem of indexing into an N+1 dimensional array representing an N-player game.

We want these to be efficient processes internally. There is a straightforward method for mapping ("raveling") an $(N+1)$-tuple of integers to an index in a contiguous vector. However, externally, calling code working with these objects operates in terms of game objects (strategies, sequences).

After a recent significant refactoring we've left the sequence form currently going through an indirect step - it converts a map of sequences to an array of integers, then passes this to a separate NDArray class, which is very inefficient. This isn't critical right now because the amount of time spent accessing these values is small relative to the computational runtime of solving such games. However, we should have a better implementation, not least because we can apply the same code to the strategic form representation.

Two additional observations:

  1. We may be able to take some inspirations from not only numpy arrays, but also DataFrames a la pandas - essentially we have a similar task of having $N$-dimensional array of data which we want to be able to refer to by labels, and also potentially to take slices of.
  2. A common need is to iterate over all (or a subset of) contingencies. For this the arithmetic to update the current integer raveled index is quite straightforward and efficient - so a bespoke iterator should be included.

The question is what's the best way to do this - the code to do this mapping is only a few lines in principle, but how best to package it so we can use it any place we need to have $N$ or $N+1$-dimensional tables.

@tturocy tturocy added c++ Items which involve writing in C++ enhancement labels Sep 20, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
c++ Items which involve writing in C++ enhancement
Projects
None yet
Development

No branches or pull requests

1 participant