# log(N) algo for sampling from vector

**URL:** <https://discourse.julialang.org/t/log-n-algo-for-sampling-from-vector/8713>\
**Category:** Performance\
**Created:** [January 31, 2018, 9:42am UTC](https://discourse.julialang.org/t/log-n-algo-for-sampling-from-vector/8713 "2018-01-31T09:42:11Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [January 31, 2018, 9:42am UTC](https://discourse.julialang.org/t/log-n-algo-for-sampling-from-vector/8713/1 "2018-01-31T09:42:12Z")

</div>

Hi,

I am using the following piece of code

```julia
using StatsBase
pf = StatsBase.Weights(rand(10))
e = sample(pf)

```

Upon using `@which sample(pf)`, one gets  
`sample(wv::StatsBase.AbstractWeights) in StatsBase at .../StatsBase/src/sampling.jl:425`

for which the algorithm is super straightforward. For example, if `t` in this algorithm is very close to `sum(wv)`, I would say it is better to go over `wv` starting from the end.

Hence my question, is it possible to do something like a binary search (like `searchsorted`) to do the same as `StatsBase.sample`?

I tried and I could not.

Thank you for your help,

Best regards

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [January 31, 2018, 10:21am UTC](https://discourse.julialang.org/t/log-n-algo-for-sampling-from-vector/8713/2 "2018-01-31T10:21:39Z")

</div>

Look further in that file for very efficient methods, eg the alias method.

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [January 31, 2018, 1:57pm UTC](https://discourse.julialang.org/t/log-n-algo-for-sampling-from-vector/8713/3 "2018-01-31T13:57:30Z")

</div>

I forgot to mention that I need to draw only one sample from the vector.

---

<div class="post-metadata">

**Author:** ![simonbyrne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simonbyrne/32/19_2.png) [@simonbyrne](https://discourse.julialang.org/u/simonbyrne)\
**Post date:** [January 31, 2018, 7:40pm UTC](https://discourse.julialang.org/t/log-n-algo-for-sampling-from-vector/8713/4 "2018-01-31T19:40:54Z")

</div>

If all you have is a vector of relative weights, then you need to do at least some sort of O(n) preprocessing (since you have no idea where the weight is).

If there is some way that you could get the _cumulative_ weights cheaply (i.e. cheaper than `cpf = cumsum(pf)`, which is also O(n)), then you could do:

```julia
u = rand()*cpf[end]
searchsortedfirst(cpf, u)

```

which is O(log(n)).

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [February 1, 2018, 7:02am UTC](https://discourse.julialang.org/t/log-n-algo-for-sampling-from-vector/8713/5 "2018-02-01T07:02:45Z")

</div>

I tend to agree for most of your answer… I would improve the algo by starting from the beginning and from the last element at the same time though.

---

<div class="post-metadata">

**Author:** ![simonbyrne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simonbyrne/32/19_2.png) [@simonbyrne](https://discourse.julialang.org/u/simonbyrne)\
**Post date:** [February 7, 2018, 4:59am UTC](https://discourse.julialang.org/t/log-n-algo-for-sampling-from-vector/8713/6 "2018-02-07T04:59:24Z")

</div>

I’m not sure what you mean: could you explain further?