5
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ data2 == data3 yielding True does not indicate that the data is the same, only numerically equivalent. For example if one set of data contains exact numbers (e.g. Integer, Rational) this set may be processed with exact arithmetic which is often far slower. $\endgroup$ – Mr.Wizard Feb 6 '15 at 16:44
  • 2
    $\begingroup$ Also, one of the sets may be a packed array while the other is not. Packed arrays, if supported by the functions involved, will be processed more quickly. $\endgroup$ – Mr.Wizard Feb 6 '15 at 16:46
  • $\begingroup$ But also data2===data3 yields true. Is this enough? I'll edit the question with this anyway! $\endgroup$ – CupiDio Feb 6 '15 at 16:47
  • $\begingroup$ Hm... That should rule out the exact/inexact numbers possibility but it leaves packed arrays. What do you get from Developer`PackedArrayQ /@ {data2, data3}? $\endgroup$ – Mr.Wizard Feb 6 '15 at 16:49
  • $\begingroup$ Returns {False, False} $\endgroup$ – CupiDio Feb 6 '15 at 16:50
9
$\begingroup$

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

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}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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