bigmlcom/histogram — pull request #40 by ashenfad (2013-02-21 23:49:52+00:00)
Title: Performance improvements

This PR includes two significant changes for performance improvement and bumps the version to `3.1.0`.

First, the code for inserting, merging, and accessing bins was abstracted to `BinReservoir`. `TreeBinReservoir` encapsulates the old implementation for these tasks. It uses trees for `O(log(n))` inserts. `ArrayBinResorvoir` adds an option backed by `ArrayList`. It has `O(n)` inserts, but is much faster for histograms with small #s of bins. Histograms <= 256 bins will use the `ArrayBinReservoir` by default, although the implementation can be requested explicitly.

The second performance improvement is for querying the histogram (such as `sum`, `density`, `uniform`, etc.). The sum results at every bin mean are cached after a query, making future queries fast. Insertions or merges into the histogram will invalidate the cache.