hadley/plyr — pull request #149 by muelleki (2013-04-06 19:10:28+00:00)
Title: performance improvements for rbind.fill

This pull request will contain a performance test for `rbind.fill` and a fix that will change the run time to linear (instead of now quadratic).

The test tests the run time of `rbind.fill` for different list sizes and fits several linear models to check whether the dependence is O(n), O(n log n) or O(n^2). It runs in just a few seconds. These are the test results on my machine:

```
.id .n user.self sys.self elapsed user.child sys.child N NlogN N2
1 25 1 0.008 0.000 0.008 0 0 25 80.4719 625
2 25 2 0.008 0.000 0.007 0 0 25 80.4719 625
3 50 1 0.016 0.000 0.020 0 0 50 195.6012 2500
4 50 2 0.016 0.000 0.021 0 0 50 195.6012 2500
5 100 1 0.028 0.028 0.056 0 0 100 460.5170 10000
6 100 2 0.040 0.012 0.057 0 0 100 460.5170 10000
7 200 1 0.152 0.004 0.232 0 0 200 1059.6635 40000
8 200 2 0.152 0.004 0.271 0 0 200 1059.6635 40000
9 400 1 0.604 0.020 0.879 0 0 400 2396.5858 160000
10 400 2 0.540 0.020 0.774 0 0 400 2396.5858 160000
.id r.squared
1 linear 0.9594638
2 loglinear 0.9748034
3 squared 0.9907632
```

The second table shows model fits for the different run time assumptions. Currently the run time clearly is O(N^2) for N = length of list.