Sorry if this has been asked before but I've already done quite a bit of work here and I feel like I'm quite close to an answer.

I am interested in testing whether the PHP function array_key_exists depends on the size of the array. If it did, we should expect that the growth of the computation time for the function would depend on the size of the array. If it does not, then the computation time should be constant. In other words, I want to test the strength of a possible linear relationship.

I measured the computation time for varying sizes of arrays. A few things I see, in ascending order of importance:

  1. There lots of points (almost half of them) where the time actually decreases as the size increases. This basically gives me grounds to accept the null hypothesis immediately, because any linear relationship would entail a monotonically increasing function of the size.
  2. Very low standard deviation in the time, indicating that the values are tightly clustered.
  3. The slope of the simple linear regression is quite small.
  4. Exceedingly low Pearson coefficient and its square has practically vanished.

If my null hypothesis is that the real Pearson coefficient is zero, namely there is no relationship between the array size and computation time, how small does my sample Pearson coefficient or its square need to be to reject it? What assumptions do I need to make (perhaps acceptable probabilities of Type I and Type II) to do so?

Is it better to formulate the null hypothesis from the Pearson coefficient or from the linear regression slope? Are they about the same as far as explanatory power in this circumstance?

  • Only conclusion (3) is consistent with your data. The rest are not. In (1), the number of increases is an exceptionally poor test statistic and so gives you no grounds for any conclusion for or against a linear relationship. In (2), the SD is actually quite large compared to the size of the slope. (That's what a small $R^2$ is telling you.) In (4), you are being misled by a single anomalous value (the first in the series). – whuber Feb 16 '13 at 13:31
up vote 2 down vote accepted

There are many potential issues.

Your first problem is that the first point really doesn't fit the (roughly) pattern of the rest (look at your data - see below). The linear model simply doesn't describe the data.

You could apply a more complex model, or you could try fitting a simpler model to a subset of the data.

Plot of CompTime vs ArraySize

The red line is the line of fit that corresponds to your Pearson correlation; clearly that Pearson correlation is meaningless with the anomalous point included.

The green line is the line if you omit it; it's imperfect, but does make it clear that there is some relationship between Computation Time and Array Size - apart from the that one point at the low end, it's a slowly increasing relationship.

The blue curve is a quadratic fit (without the stray point) - that turns out to add almost nothing to the description of the data. To be honest, to me it looks flat between 100 and 700 and then appears to increase above 700, but I'd hesitate to fit a model for that without an a priori reason (humans are great at identifying patterns in noise).

To revisit the question you asked:

I am interested in testing whether the PHP function array_key_exists depends on the size of the array.

The answer - even for a quick inspection of the data - is fairly plainly, yes - the data at hand are inconsistent with the idea that the computation time doesn't depend on array size. The relationship is noisy, and not of an obvious form, but there's a fairly clear increasing relationship between expected Computation Time and Array Size (for the latter between 100 and 1000) .

So if the relationship is changing but not obvious, we might just try smoothing it. Below are loess smooths to (i) all the data (grey), (ii) the data omitting the first point (in red, which lies over the grey curve in the right half of the plot), and (iii) the data also omitting the last two points (in green, in case you might be tempted to say there's no relationship without those two end points).

In each case, there's some indication of some kind of increase with array size, except for the effect of the 50.

Plot of data with loess smooths

  • ..? I'm confused, so much so that either I'm way off track or you are responding to the wrong post. I'm not trying to fit a line to the data. You said it yourself - the linear model doesn't describe the data. That's what I'm trying to prove. If you plot the data on a histogram it's obvious - and this was known beforehand. Hash tables are supposed to be constant time, this was all just an exercise. – Jacob Greenleaf Feb 16 '13 at 13:26
  • +1 Upon removing the initial anomalous value, linear regression shows the slope is moderately significant (p = 0.0165) but small (slope of just 3.5 parts per million) and the intercept is highly significant, estimated as 0.2873. There's a tiny bit of curvature but the fit isn't bad. – whuber Feb 16 '13 at 13:28
  • @Leafy Plotting the data on a histogram isn't the best way to see that the point doesn't fit; that's most obvious in a scatterplot, as in my edited post above. Secondly, you mention Pearson correlation - that is, you raised the idea of a linear relationship (what Pearson measures), not me. Why have such an attitude when I investigate something you raise? Please see my updated answer which more explicitly addresses the question in your post. – Glen_b Feb 17 '13 at 0:23
  • Sorry, I may have misunderstood. I misspoke and meant a scatterplot. Thanks. – Jacob Greenleaf Feb 17 '13 at 3:36
  • 1
    I went and re-wrote my code to remove a small problem, as well as learned quite a bit of R. As it turns out, array_key_exists does correlate with array size, and the documentation is misleading. Should have known to trust the analysis over the developer's word! – Jacob Greenleaf Feb 18 '13 at 17:09

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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