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!
data2 == data3
yieldingTrue
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$Developer`PackedArrayQ /@ {data2, data3}
? $\endgroup$