3
$\begingroup$

I have a function that calculates the rank of a restricted growth string defined like so,

rankKRGS[{}] = 0;
rankKRGS[string_] :=
 With[{n = Length@string, k = Max@string + 1, alone = !MemberQ[Most@string, Last@string]},
  rankKRGS@Most@string +
   If[alone, k*StirlingS2[n - 1, k], Last@string*StirlingS2[n - 1, k]]]

However, if I simply change the order of the addition to,

rankKRGS[string_] :=
 With[{n = Length@string, k = Max@string + 1, alone = !MemberQ[Most@string, Last@string]},
  If[alone, k*StirlingS2[n - 1, k], Last@string*StirlingS2[n - 1, k]]
   + rankKRGS@Most@string]

It performs much slower. As an example, consider this:

First@RepeatedTiming@rankKRGS[{0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 6, 10, 11, 12, 12, 0, 7, 1, 8, 3, 13, 9, 6, 11, 14, 15, 16, 17, 6, 18, 19, 20, 6, 21, 17, 22, 15, 23, 23, 15, 23, 22, 6, 24, 25, 6, 22, 17, 24, 6, 26, 17, 27, 28, 6, 24, 15, 27, 17, 29, 6, 25, 30, 6, 20, 15, 24, 24, 15, 23, 22, 6, 21, 28, 6, 31, 17, 27, 6, 20, 15, 20, 24, 17, 27, 6, 25, 23, 6, 24, 31, 17, 6, 21, 19, 23, 32, 33, 6, 19, 23, 29, 6, 25, 30, 6, 31, 19, 26, 15, 23, 22, 6, 23, 25, 24, 31, 15, 23, 22, 6, 24, 25, 6, 29, 25, 34}]

Before the change, it outputs 0.00206 on my machine. After the change, it outputs 0.0050. It seems minor, but on large numbers of these strings it adds up.

$\endgroup$
11
  • 6
    $\begingroup$ Please provide a test case that shows the difference in speed that you are talking about, that we can run on our computers. $\endgroup$
    – C. E.
    Commented Aug 3, 2016 at 21:12
  • $\begingroup$ Please consider adding an example as @C.E. suggested. Otherwise, I am inclined to close this as "not enough information provided", although I don't want to because it seems like you've got something mysterious going on. $\endgroup$
    – march
    Commented Aug 4, 2016 at 16:32
  • $\begingroup$ It's a little tricky to provide an example without pages of example data, since the time differences really only come into play on large inputs. But I'll see if I can't do something with ExampleData or some other function. $\endgroup$ Commented Aug 4, 2016 at 20:17
  • 2
    $\begingroup$ @march, I've added an example. $\endgroup$ Commented Aug 4, 2016 at 21:11
  • $\begingroup$ confirmed , roughly a factor of two. $\endgroup$
    – george2079
    Commented Aug 4, 2016 at 22:14

1 Answer 1

2
$\begingroup$

Consider the order in which StirlingS2 is evaluated with the first definition:

rankKRGS[{}] = 0;
rankKRGS[string_] := With[{n = Length@string, k = Max@string + 1, alone = !MemberQ[Most@string, Last@string]},
    rankKRGS@Most@string + If[alone, k StirlingS2[n - 1, k], Last@string StirlingS2[n - 1, k]]
]

data = {0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 6, 10, 11, 12, 12, 0, 7, 1, 8, 3, 13, 9, 6, 11, 14, 15, 
16, 17, 6, 18, 19, 20, 6, 21, 17, 22, 15, 23, 23, 15, 23, 22, 6, 24, 25, 6, 22, 17, 24, 6, 26, 17,
27, 28, 6, 24, 15, 27, 17, 29, 6, 25, 30, 6, 20, 15, 24, 24, 15, 23, 22, 6, 21, 28, 6, 31, 17, 27, 
6, 20, 15, 20, 24, 17, 27, 6, 25, 23, 6, 24, 31, 17, 6, 21, 19, 23, 32, 33, 6, 19, 23, 29, 6, 25, 
30, 6, 31, 19, 26, 15, 23, 22, 6, 23, 25, 24, 31, 15, 23, 22, 6, 24, 25, 6, 29, 25, 34};

stir = Flatten @ Last @ Reap @ TracePrint[
    rankKRGS[data],
    StirlingS2[__Integer],
    TraceAction->Sow
];
stir //Short

{StirlingS2[0,1],StirlingS2[1,2],StirlingS2[2,2],StirlingS2[3,3],<<121>>,StirlingS2[125,34],StirlingS2[126,34],StirlingS2[127,35]}

Now consider the order in which StirlingS2 is evaluated with the second definition:

rankKRGS[{}] = 0;
rankKRGS[string_] := With[{n = Length@string, k = Max@string + 1, alone = !MemberQ[Most@string, Last@string]},
    If[alone, k StirlingS2[n - 1, k], Last@string StirlingS2[n - 1, k]] + rankKRGS@Most@string
]

stir2 = Flatten @ Last @ Reap @ TracePrint[
    rankKRGS[data],
    StirlingS2[__Integer],
    TraceAction->Sow
];
stir2 === Reverse[stir]

True

The two are reversed. Now, let's time how long it takes to evaluate these StirlingS2 objects:

ReleaseHold[stir]; //AbsoluteTiming
ReleaseHold[stir2]; //AbsoluteTiming

{0.001158, Null}

{0.003476, Null}

I think the above difference in timing explains the difference you're seeing. I'm not sure what's going on internally in Mathematica, perhaps there is some kind of per evaluation cache that gets populated, and is helpful only when StirlingS2 is computed with increasingly larger arguments.

$\endgroup$

Your Answer

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

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