search

MaxHalford / vose

Cython implementation of Vose's Alias method
MIT License
5 stars 5 forks source link

Implemented #2 #3

Closed Theomat closed 2 years ago

Theomat commented 2 years ago

Implemented #2, I have not run the benchmark notebook so performances are not up to date. Since we do not use the same random number generator this change breaks reproducibility from seeds before the update, as such I have bumped the minor version number and updated the tests in the README.md. Finally, I have also added the test I mentioned in #2.

Theomat commented 2 years ago

Could you run it again? I tried many different options to no avail at least on my machine, this is my best attempt.

I would understand if this becomes a problem for your package, at least from my POV it is not since we generate millions of integers we do not care about initialization, it would still be worth it if it even took 1 sec.

MaxHalford commented 2 years ago

Here you go:

n k np.random.choice random.choices vose.Sampler vose_sampler.VoseAlias
3 1 61ns 4ns 40ns 21ns
3 2 69ns 5ns 45ns 21ns
3 3 47ns 6ns 39ns 20ns
3 10 57ns 10ns 39ns 38ns
3 100 52ns 65ns 43ns 262ns
3 1000 79ns 671ns 56ns 2μs, 215ns
30 1 52ns 11ns 36ns 108ns
30 2 52ns 13ns 42ns 111ns
30 3 45ns 12ns 40ns 110ns
30 10 53ns 18ns 41ns 136ns
30 100 63ns 102ns 60ns 381ns
30 1000 154ns 1μs, 87ns 85ns 3μs, 580ns
300 1 68ns 104ns 42ns 1μs, 157ns
300 2 54ns 97ns 44ns 1μs, 57ns
300 3 52ns 78ns 40ns 966ns
300 10 46ns 76ns 39ns 977ns
300 100 56ns 158ns 41ns 1μs, 202ns
300 1000 147ns 1μs, 120ns 62ns 3μs, 458ns
3000 1 93ns 676ns 63ns 10μs, 74ns
3000 2 90ns 673ns 67ns 10μs, 134ns
3000 3 85ns 666ns 63ns 9μs, 990ns
3000 10 78ns 604ns 54ns 8μs, 561ns
3000 100 82ns 674ns 55ns 8μs, 691ns
3000 1000 182ns 1μs, 503ns 76ns 10μs, 593ns

The code is slower because I'm running something else on my laptop. But the difference is still there.

I don't know, I'm a bit hesitant to merge this PR.

Theomat commented 2 years ago

I completely understand your POV and it is completely up to you.

Note that for our use case, we can change our clone from my your repository to my fork which solves everything, so feel free to close it if you do not want to merge.

MaxHalford commented 2 years ago

At least you've done the hard work, and this pull request is visible. We can circle back to it if we find a cheaper way to do the initialization. Thanks!