BlueMountainCapital/Deedle — pull request #181 by tpetricek (2014-03-24 01:01:34+00:00)
Title: Support merging of N series and speedup alignment functions (cf. #179)

I first thought I could just add merging of N series using a similar pattern
to the one that we were using for 2 series. This worked, but it was pretty slow.
So, in the end, this is a fairly major revision of how the "aligning" functions
work.

The key changes are in 'Common.fs'. Previously, the functions returned a single
sequence with keys and optional values containing old addresses. To build the
"relocate" command, we had to iterate over this repeatedly. I changed them to just
build relocation tables directly. So, the functions `Seq.align[All][Un]ordered`
now return new array with keys together with relocation arrays that are directly
passed to the `Relocate` vector construction (this removes quite a lot of overhead
and the new implementation is also more straightforward imperative code with
more predictable performance).

Although it now works for N series (`Seq.alignAll[Un]ordered`), I also kept functions
for just 2 series (named `Seq.align[Un]ordered`). These are generally faster and
they also support calculating intersections. At the moment, I kept Union/Intersection
to just work on 2 indices (we could generalize this in the future if there is need).

I also added one optimization in `ArrayVector.fs`. The above commonly creates vector
commands that look as `CombineN [ Relocate v1; Relocate v2; ..]`. Previously, we would
build all the child vectors (by allocating array and filling it according to the
relocation table). I added a special case that looks for this pattern and avoids creating
the temporary vectors (it creates vectors `v1`, `v2`, ... and then combines them
while handling relocations at the same time).

This makes things a lot faster - I will post some performance measurements to GitHub.

I have not done renaming in this checkin yet (as suggested in #179) but will do that next.

I also removed `LazyList.fs` which was not needed anymore.