23
$\begingroup$

Observe:

l1 = l2 = RandomInteger[{1, 100000}, 1000000];
l2[[-1]] = -1;
t1 = First@Timing@Tally[l1];
t2 = First@Timing@Tally[l2];

l1 = l2 = RandomInteger[{1, 100000}, 1000100];
l2[[-1]] = -1;
t3 = First@Timing@Tally[l1];
t4 = First@Timing@Tally[l2];

l1 = l2 = RandomInteger[{1, 99999}, 1000000];
l2[[-1]] = -1;
t5 = First@Timing@Tally[l1];
t6 = First@Timing@Tally[l2];

{t1, t2, t3, t4, t5, t6}

(* {0.046800, 1.138807, 0.046800, 0.062400, 0.062400, 0.046800} *)

What's with the huge timing jump for t2? There's no unpacking or such going on - this has me scratching my noggin...

Improve this question
$\endgroup$
  • $\begingroup$ I am glad to see you are still willing to ask questions here, and boy that's a strange result. $\endgroup$ – Mr.Wizard May 9 '15 at 2:10
  • 1
    $\begingroup$ @Mr.Wizard: Well, of course - Don Quixote themed pursuits for rep justice (hmm, rep-justice warrior?) aside, this is the only game in town to tap brain power like yours and the other experts here, and to get feedback from WRI gang members. Glad you seem to find this tally behavior as interesting as I do... +1 on your comment / answer. $\endgroup$ – ciao May 9 '15 at 6:06
  • $\begingroup$ Which version are you using? $\endgroup$ – Yves Klett May 9 '15 at 8:46
  • $\begingroup$ @YvesKlett: Sorry for delay in response - not here as much.... in any case , 9.0.1 on Windoze.... $\endgroup$ – ciao May 9 '15 at 21:29
  • $\begingroup$ @ciao not to worry! Same effect on 10.1, in any case... $\endgroup$ – Yves Klett May 10 '15 at 7:18
10
$\begingroup$

My guess is that Tally preallocates a number of bins equal to 10% of the length of the list. If the need exceeds that, then it probably has to reallocate the bins, apparently in a time-consuming manner.

Table[
  l1 = l2 = RandomInteger[{1, max}, 10 max];
  l2[[-1]] = -1;
  {First@Timing@Tally[l1],
   First@Timing@Tally[l2]},
  {max, 2^Range[12, 21]}] // Grid

Mathematica graphics

Table[
  l1 = l2 = RandomInteger[{1, max}, 10 max + 10];
  l2[[-1]] = -1;
  {First@Timing@Tally[l1],
   First@Timing@Tally[l2]},
  {max, 2^Range[12, 21]}] // Grid

Mathematica graphics

Improve this answer
$\endgroup$
  • $\begingroup$ You won the coin flip... both your and Mr. W answers worthy. Thx! $\endgroup$ – ciao May 10 '15 at 21:19
9
$\begingroup$

This is more of a comment than an answer but it's too long for a comment box and I hope to extend it as I learn more.

My first thought was that the negative value might be preventing some optimization so I looked for a counterexample and found something surprising:

Table[
 With[{a = RandomInteger[{1, 100000}, 1000000 + x]},
  First @ Timing @ Do[Tally[a], {10}] / 10
 ],
 {x, -5000, 5000, 1000}
]

{0.121681, 0.117001, 0.113881, 0.115441, 0.118561, 0.00468003, 0.00468003,
 0.00468003, 0.00312002, 0.00468003, 0.00468003}

It seems that Tally invokes an optimization on (some) packed lists of integers over length 1×10^6 and this optimization has been present since at least version 7. This seems similar to things like "ArrayCompileLength" but I cannot find a System Option that applies. At least on the given example the crossover point seems poorly chosen as there is 40X speed-up indicating that an earlier point would have been better.

Since we do not know the details of this or other optimizations used by Tally I can only presume, but it seems plausible that the presence of a negative value causes the heuristic to trigger only on a slightly longer list. (1000010 is sufficient for both timings to be similar.)

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ I think it has to do with the range of values (or bins). Try l1 = l2 = RandomInteger[{1, 99999}, 1000000]; l2[[-1]] = -2; etc. The timings on this l2 are similar to the first l2. -- By "to do", I mean it's a factor. I don't have an explanation.... $\endgroup$ – Michael E2 May 9 '15 at 2:35
  • $\begingroup$ @MichaelE2: I think you're on to something there (I've often wondered if for things like this, MMA does a quick sample of the data to use in deciding algo/set-up/optimizations)... $\endgroup$ – ciao May 9 '15 at 6:01

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.