4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – halirutan
    Mar 29, 2013 at 13:53
  • $\begingroup$ In this case maxn=4, I've edited the question to fix this. Thanks! $\endgroup$
    – elear
    Mar 30, 2013 at 2:12

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – elear
    Mar 30, 2013 at 2:10

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.