Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
Thanks a lot, that helped! –  elear Mar 30 '13 at 2:02
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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