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

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.

• Welcome to Mathematica.stackexchange. It would be extremely helpful if you would provide a small working example of what you try to achieve. What is maxn in your code? Can you edit your question and fix this? – halirutan Mar 29 '13 at 13:53
• In this case maxn=4, I've edited the question to fix this. Thanks! – elear Mar 30 '13 at 2:12

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.

• By just quickly hacking this solution into my code, I obtained a 2- to 10-fold increase in speed in my functions that work with these kinds of lists. – elear Mar 30 '13 at 2:10