caio.co/de/go-tdigest


Use a fenwick tree to optimize prefix sums 💬 by Caio 8 years ago (log)
This patch makes summary use the excellent fenwick package from
https://github.com/yourbasic/fenwick to dramatically speed
up Add() calls while adding a bounded cost to memory.

    benchmark             old ns/op     new ns/op     delta
    BenchmarkAdd1-4       187           206           +10.16%
    BenchmarkAdd10-4      332           274           -17.47%
    BenchmarkAdd100-4     1092          325           -70.24%

The tree creation could be faster, but profiling has shown that
it doesn't seem to be that much of a problem (that's because
`summary.setAt()` happens a *lot* more than `summary.Add()`)

Blob Gopkg.lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# This file is autogenerated, do not edit; changes may be undone by the next 'dep ensure'.


[[projects]]
  name = "github.com/leesper/go_rng"
  packages = ["."]
  revision = "5344a9259b21627d94279721ab1f27eb029194e7"

[[projects]]
  name = "github.com/yourbasic/fenwick"
  packages = ["."]
  revision = "7cb325001daae879940edf7b19da8557a51ca5f7"
  version = "1.2.0"

[solve-meta]
  analyzer-name = "dep"
  analyzer-version = 1
  inputs-digest = "eac5a7bc22a9b8d592de2752be2ab1f8707df0caf1a1e77087c88671cbb8c94d"
  solver-name = "gps-cdcl"
  solver-version = 1