I am trying to do some exploration around the multi-dimensional version of [truncated moment problem], where I work with various distributions (uni- or multi-variate), and use some truncated moment sequences of them. I frequently use three different types of sequences:

  • when the distribution is a fully independent joint, the truncated sequence is represented as a $K\times \tau$ matrix, where $K$ is the valence of the distribution and $\tau$ is the truncation to the order of moments; from this matrix desired joint moments can be readily computed.

  • when the distribution is correlated:

    • independent truncations $\tau_k$ for each variate $x_k$: the truncated sequence is represented as a $\tau_1\times\tau_2\times\cdots\times\tau_K$-dimensional array
    • one overall truncation $\tau$: sometimes I need all the joint moments whose order is $\leqslant\tau$; if I use the previous scheme, I would have to save a $\tau^K$-dimensional array, where the majority of entries are not used.

Therefore, I am trying to find out which construct I should use to represent the third kind of truncated sequence. The options that I currently know of are:

  1. a ragged array (a nested List in which each sublist is of different length)
  2. an association (hash map) where I use multi-indices (Lists with integer entries) as keys.

Which has the better performance? Is there better ways to handle such arrays?

Update I find a similar question at MMA SE; the accepted answer suggests using a dispatch table, but as associations are introduced, won't (speaking for this case only) replacing dispatch tables with associations avoid invoking the pattern-matching mechanism and make things faster?

Theoretically, with some optimised byte alignment, float-valued integer-partition (from now on I'll call them intpart for short) indexed arrays can be represented compactly in the memory; these however may be slow to access, and will definitely be hard to mutate. A hash map is a more flexible alternative. The real problem is which Wolfram built-in hashes the way best suited for this case (for the lack of better phrasing). Compared to Dispatch and Association, is using compiled ragged lists a good idea?

  • 2
    $\begingroup$ (1) Ragged arrays do not at this time have reasonable support from Compile. This may change as the new compiler matures. Dispatch and Association are likely to be roughly equivalent in speed, and the only way to know which is better is to run timing tests. Both will use hashing under the hood, and I suspect they use the same (or at least similar) hashing schemes (your phrasing was quite clear, by the way). $\endgroup$ Mar 5, 2021 at 14:11
  • 2
    $\begingroup$ (2) This is related to handling of multivariate Maclaurin/Taylor expansions, wherein one wants to expand to a given total degree. Depending oin what exactly you require in terms of data to store, you might find some reasonable ideas by searching MSE for threads on that topic. $\endgroup$ Mar 5, 2021 at 14:13
  • $\begingroup$ @DanielLichtblau Thanks a lot for your suggestion, this is really helpful. Searching for these posts will take some time, and I'll be back at this post later. I have made some test on the built-in SeriesData; it basically uses a verbose ragged array, though. After all, it is designed for symbolic computation and display and compactness is not its goal. So this is a dead end. :D $\endgroup$
    – Gravifer
    Mar 5, 2021 at 14:55
  • 1
    $\begingroup$ The multivariate case constrained by total degree actually is done as a univariate expansion. Whether the result can be adapted to your specific needs is another question though. $\endgroup$ Mar 5, 2021 at 14:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.