Function takes hugely different times to evaluate on sets of virtually (but also literally) identical data

Question

I'm experiencing something which I believe to be weird with a function that I wrote.

Briefly: what happens is that I generate random data to feed my function in two different but equivalent ways (RandomInteger, or "fast", and RandomChoice, or "slow") and the time needed for the function to run changes of a factor 60. Even weirder if export the "fast" dataset in a file, then reimport it, running the function on it (so EXACTLY on the same data) again takes 60 times longer. Finally if I run the same exact code which is the definition of the function just as normal code in a cell, execution on "slow" data is 20 times faster, but execution on "fast" data takes about the same time.

In detail: This is how I generate the data

pr1 = 0.5;
pr2 = 0.5;
slow = N@{RandomChoice[{pr1, 1 - pr1} -> {1, 0}, 1350], 
RandomChoice[{pr2, 1 - pr2} -> {1, 0}, {1131, 1350}]};
fast = N@{RandomInteger[1, 1350], RandomInteger[1, {1131, 1350}]};
Export["/Users/Andrea/Desktop/test1.txt", fast[[1]], "List"];
Export["/Users/Andrea/Desktop/test2.txt", fast[[2]], "Table"];
slow2 = {Import["/Users/Andrea/Desktop/test1.txt", "List"], 
Import["/Users/Andrea/Desktop/test2.txt", "Table"]};

I pack the data in these structures for practical reasons needed in other parts of my code

data1 = {{{1, 0.}}, slow, tree[{{1, 0.}}]};
data2 = {{{1, 0.}}, fast, tree[{{1, 0.}}]};
data3 = {{{1, 0.}}, slow2, tree[{{1, 0.}}]};

Then I run my DataSplit function on the datasets:

res1 = AbsoluteTiming[DataSplit[data1]];
res2 = AbsoluteTiming[DataSplit[data2]];
res3 = AbsoluteTiming[DataSplit[data3]];
res1[[1]]
res2[[1]]
res3[[1]]
data2 === data3
res2[[2]] == res3[[2]]

Out[3146]= 2.399091
Out[3147]= 0.040865
Out[3148]= 2.370376
Out[3149]= True
Out[3150]= True

As you can see execution times have BIG differences among them. Even when data3 is an exact copy of data2...

Here is the code of DataSplit, should it be useful:

DataSplit[data_] := 
 Module[{infogains, tempdata, gathered, fullent, node, th, scalp, 
   maintot, tots, resdat, irrelevant},
  If[Length@data[[2, 1]] < 2, Return@data];
  th = 0.;
  tempdata = data[[2]];
  fullent = Entropy[data[[2, 1]]];
  scalp = data[[2, 2]].data[[2, 1]];
  maintot = Total@data[[2, 1]];
  tots = Total /@ data[[2, 2]];
  irrelevant = 
   Join[Flatten[Position[tots, 0.]], Flatten[Position[tots, N[Length@data[[2, 1]]]]]];
  infogains =Table[
    hd = tots[[i]] + maintot - 2*scalp[[i]];
    p2 = If[maintot > tots[[i]], 1 - (hd - Abs[tots[[i]] - maintot])/(2 tots[[i]]), 1 - (hd + Abs[tots[[i]] - maintot])/(2 tots[[i]])];
    p2b = (maintot - p2*tots[[i]])/(Length@data[[2, 1]] - tots[[i]]);
    {i, fullent - (BinaryEntropy[p2]*tots[[i]] + BinaryEntropy[p2b]*(Length@data[[2, 1]] - tots[[i]]))/Length@data[[2, 1]]},
    {i, Complement[Range[Length[tempdata[[2]]]], Union[data[[1, All, 1]], irrelevant]]}
];
  infogains = SortBy[infogains, -#[[2]] &];
Return[infogains]
]

and BinaryEntropy is simply

BinaryEntropy[p_] :=   If[p > 0. && p < 1., -(p*Log[p] + (1 - p) Log[1 - p]), 0.];

Finally here is what happens when I execute the code for DataSplit not as a function but just as simple code: timings of slow data decrease of a factor 20 whereas fast data takes about the same time

(*DATA 1*)
data = data1;
AbsoluteTiming[
  th = 0.;
  tempdata = data[[2]];
  fullent = Entropy[data[[2, 1]]];
  scalp = data[[2, 2]].data[[2, 1]];
  maintot = Total@data[[2, 1]];
  tots = Total /@ data[[2, 2]];
  irrelevant = Join[Flatten[Position[tots, 0.]], Flatten[Position[tots, N[Length@data[[2, 1]]]]]];
  infogains = Table[
    hd = tots[[i]] + maintot - 2*scalp[[i]];
    p2 = If[maintot > tots[[i]], 1 - (hd - Abs[tots[[i]] - maintot])/(2 tots[[i]]), 1 - (hd + Abs[tots[[i]] - maintot])/(2 tots[[i]])];
    p2b = (maintot - p2*tots[[i]])/(Length@data[[2, 1]] - tots[[i]]);
    {i, fullent - (BinaryEntropy[p2]*tots[[i]] + BinaryEntropy[p2b]*(Length@data[[2, 1]] - tots[[i]]))/Length@data[[2, 1]]},
{i, Complement[Range[Length[tempdata[[2]]]], Union[data[[1, All, 1]], irrelevant]]}
];
  infogains = SortBy[infogains, -#[[2]] &];
  ][[1]]
(*DATA 2*)
data = data2;
AbsoluteTiming[
  th = 0.;
  tempdata = data[[2]];
  fullent = Entropy[data[[2, 1]]];
  scalp = data[[2, 2]].data[[2, 1]];
  maintot = Total@data[[2, 1]];
  tots = Total /@ data[[2, 2]];
  irrelevant = Join[Flatten[Position[tots, 0.]], Flatten[Position[tots, N[Length@data[[2, 1]]]]]];
  infogains = Table[
    hd = tots[[i]] + maintot - 2*scalp[[i]];
    p2 = If[maintot > tots[[i]], 1 - (hd - Abs[tots[[i]] - maintot])/(2 tots[[i]]), 1 - (hd + Abs[tots[[i]] - maintot])/(2 tots[[i]])];
    p2b = (maintot - p2*tots[[i]])/(Length@data[[2, 1]] - tots[[i]]);
    {i, fullent - (BinaryEntropy[p2]*tots[[i]] + BinaryEntropy[p2b]*(Length@data[[2, 1]] - tots[[i]]))/Length@data[[2, 1]]},
{i, Complement[Range[Length[tempdata[[2]]]], Union[data[[1, All, 1]], irrelevant]]}
];
  infogains = SortBy[infogains, -#[[2]] &];
  ][[1]]
(*DATA 3*)
data = data3;
AbsoluteTiming[
  th = 0.;
  tempdata = data[[2]];
  fullent = Entropy[data[[2, 1]]];
  scalp = data[[2, 2]].data[[2, 1]];
  maintot = Total@data[[2, 1]];
  tots = Total /@ data[[2, 2]];
  irrelevant = Join[Flatten[Position[tots, 0.]], Flatten[Position[tots, N[Length@data[[2, 1]]]]]];
  infogains = Table[
    hd = tots[[i]] + maintot - 2*scalp[[i]];
    p2 = If[maintot > tots[[i]], 1 - (hd - Abs[tots[[i]] - maintot])/(2 tots[[i]]), 1 - (hd + Abs[tots[[i]] - maintot])/(2 tots[[i]])];
    p2b = (maintot - p2*tots[[i]])/(Length@data[[2, 1]] - tots[[i]]);
    {i, fullent - (BinaryEntropy[p2]*tots[[i]] + BinaryEntropy[p2b]*(Length@data[[2, 1]] - tots[[i]]))/Length@data[[2, 1]]},
{i, Complement[Range[Length[tempdata[[2]]]], Union[data[[1, All, 1]], irrelevant]]}
];
  infogains = SortBy[infogains, -#[[2]] &];
  ][[1]]
0.139358
0.058034
0.123588

As a final remark: DataSplit returns correct results (I have crosschecked with a completely different implementation of it, that is just always slow) and returns the SAME results when applied to the same data (e.g. data2 and data3)...

Does anyone have a clue about what is happening here? Has it something to do with how data is represented in memory? But why is data from RandomInteger so special? Will I be able to put my REAL dataset in such a form that is as "special" as that from RandomInteger?

And finally: What can I do to have the FUNCTION DataSplit run as fast as its code outside a function? A factor 20 would also be of great help... And I need to use it recursively so I just need it to be a function!

Answer 1

I believe the difference you are observing is attributable to packed arrays.

• What is a Mathematica packed array?

The difference between slow and fast is due to the behavior of RandomChoice. Observe:

<< Developer`

RandomChoice[{pr1, 1 - pr1} -> {1, 0}, 1350] // PackedArrayQ
RandomInteger[1, 1350]                       // PackedArrayQ

False

True

You could pack the first output after generation but a better solution is to pack the list {1, 0} in the first argument:

RandomChoice[{pr1, 1 - pr1} -> ToPackedArray@{1, 0}, 1350] // PackedArrayQ

True

In the case of the Export/Import you either need to export the data in the .MX binary format or re-pack it after importing.

Export["fast.m", fast];
Export["fast.mx", fast];

PackedArrayQ /@ Import["fast.m"]
PackedArrayQ /@ Import["fast.mx"]

{False, False}

{True, True}

Repacking:

fixed = ToPackedArray /@ Import["fast.m"];
PackedArrayQ /@ fixed

{True, True}