DistoGram
DistoGram is a library that allows to compute histogram on streaming data, in distributed environments. The implementation follows the algorithms described in Ben-Haim's Streaming Parallel Decision Trees
Get Started
First create a compressed representation of a distribution:
import numpy as np
import distogram
distribution = np.random.normal(size=10000)
# Create and feed distogram from distribution
# on a real usage, data comes from an event stream
h = distogram.Distogram()
for i in distribution:
h = distogram.update(h, i)Compute statistics on the distribution:
nmin, nmax = distogram.bounds(h)
print("count: {}".format(distogram.count(h)))
print("mean: {}".format(distogram.mean(h)))
print("stddev: {}".format(distogram.stddev(h)))
print("min: {}".format(nmin))
print("5%: {}".format(distogram.quantile(h, 0.05)))
print("25%: {}".format(distogram.quantile(h, 0.25)))
print("50%: {}".format(distogram.quantile(h, 0.50)))
print("75%: {}".format(distogram.quantile(h, 0.75)))
print("95%: {}".format(distogram.quantile(h, 0.95)))
print("max: {}".format(nmax))count: 10000
mean: -0.005082954640481095
stddev: 1.0028524290149186
min: -3.5691130319855047
5%: -1.6597242392338374
25%: -0.6785107421744653
50%: -0.008672960012168916
75%: 0.6720718926935414
95%: 1.6476822301131866
max: 3.8800560034877427Compute and display the histogram of the distribution:
hist = distogram.histogram(h)
df_hist = pd.DataFrame(np.array(hist), columns=["bin", "count"])
fig = px.bar(df_hist, x="bin", y="count", title="distogram")
fig.update_layout(height=300)
fig.show()
Install
DistoGram is available on PyPi and can be installed with pip:
pip install distogramPlay With Me
You can test this library directly on this live notebook.
Performances
Distogram is design for fast updates when using python types. The following numbers show the results of the benchmark program located in the examples.
On a i7-9800X Intel CPU, performances are:
| Interpreter | Operation | Numpy | Req/s |
|---|---|---|---|
| pypy 7.3 | update | no | 6563311 |
| pypy 7.3 | update | yes | 111318 |
| CPython 3.7 | update | no | 436709 |
| CPython 3.7 | update | yes | 251603 |
On a modest 2014 13" macbook pro, performances are:
| Interpreter | Operation | Numpy | Req/s |
|---|---|---|---|
| pypy 7.3 | update | no | 3572436 |
| pypy 7.3 | update | yes | 37630 |
| CPython 3.7 | update | no | 112749 |
| CPython 3.7 | update | yes | 81005 |
As you can see, your are encouraged to use pypy with python native types. Pypy's jit is penalised by numpy native types, causing a huge performance hit. Moreover the streaming phylosophy of Distogram is more adapted to python native types while numpy is optimized for batch computations, even with CPython.
Credits
Although this code has been written by following the aforementioned research paper, some parts are also inspired by the implementation from Carson Farmer.
Thanks to John Belmonte for his help on performances and accuracy improvements.