How to store values indexed by integer partitions for fast access?

Question

I have a huge list of values indexed by integer partitions. If I store them simply in a list, then, when I want to access the value corresponding to some particular integer partition, I have to find the index of the given partition in the list of all partitions before I can access the value. This is slow. Is there a way to optimize this?

In my particular example, I have values indexed by pairs of partitions of the same integers. The first 4 levels look like this:

chars = {
  {{1}}, 
  {{1, 1}, {-1, 1}}, {{1, 1, 1}, {-1, 0, 2}, {1, -1, 1}}, 
  {{1, 1, 1, 1, 1}, {-1, 0, -1, 1, 3}, {0, -1, 2, 0, 2}, {1, 0, -1, -1, 3}, 
   {-1, 1, 1, -1, 1}}
}

Then to access a particular value, I use this function:

maxn = 4;
YDs = Array[IntegerPartitions[#] &, maxn];

findChar[y1_, y2_] := Module[{l1, l2, n1, n2, i1, j1},
  l1 = Length[y1];
  l2 = Length[y2];
  n1 = Sum[y1[[i]], {i, l1}];
  n2 = Sum[y2[[i]], {i, l2}];
  If[n1 != n2, Return["ERROR"];];
  i1 = Position[YDs[[n1]], y1, Heads -> False][[1, 1]];
  j1 = Position[YDs[[n2]], y2, Heads -> False][[1, 1]];
  Return[chars[[n1, i1, j1]]];
];

This seems to be a pretty inefficient way, but I don't know how to do it more effectively in Mathematica.

Answer 1

Create a dispatch table of indexes. To illustrate, let's make over a million integer partitions to work with:

y = Flatten[Array[IntegerPartitions, 50], 1]; Length[y]

$1295970$

Associate each with an index via a Rule and optimize the subsequent rule replacements with a dispatch table:

table = Dispatch[Rule @@@ Transpose[{y, Range@Length@y}]];

(This precomputation takes $2.8$ seconds here.) To test its use, let's work out the indexes for a million randomly selected integer partitions:

x = RandomChoice[y, 10^6]; First@AbsoluteTiming@(x /. table)

$1.7851021$

In other words, it takes less than two microseconds on average to look up the index for any of these partitions. I hope this is fast enough for the intended application.