search

dlangBugzillaToGithub / migration_test

0 stars 0 forks source link

Speed up std.random.dice #794

Open dlangBugzillaToGithub opened 11 years ago

dlangBugzillaToGithub commented 11 years ago

zshazz reported this on 2013-11-24T16:48:21Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=11597

CC List

Description

Currently, dice is a bit slower than it could be. It would be nice if dice used a binary search to speed up the search for which element the chosen point corresponds to.
dlangBugzillaToGithub commented 11 years ago

bearophile_hugs commented on 2013-11-24T16:52:57Z

(In reply to comment #0)
> Currently, dice is a bit slower than it could be. It would be nice if dice used
> a binary search to speed up the search for which element the chosen point
> corresponds to.

See Vose's Alias Method:
http://www.keithschwarz.com/darts-dice-coins/

But regarding dice speed see Issue 5849, so perhaps this is a dupe (or you can move your requests there).
dlangBugzillaToGithub commented 11 years ago

zshazz commented on 2013-11-24T17:14:18Z

Associated pull request:
https://github.com/D-Programming-Language/phobos/pull/1716
dlangBugzillaToGithub commented 11 years ago

joseph.wakeling commented on 2013-11-30T02:07:50Z

(In reply to comment #2)
> Associated pull request:
> https://github.com/D-Programming-Language/phobos/pull/1716

Follow-up here based on feedback provided to Chris' pull request.  We agreed that it wasn't an appropriate solution, simply because the cost of allocating (ouch!) and then filling (O(N)) an array containing a cumulative sum of the proportions, was actually worse than the (also O(N) but no allocation and no extra operations) traversing of the proportions that dice() currently does.

However, it occurs to me that it might be possible to offer an overload for dice() if it receives a SortedRange containing the cumulatively summed proportions.  This could provide the best of all possible worlds as it might offer a reliable means to binary-search dice _without requiring any allocation at all_ (e.g. if your proportions are an iota(), or some other predictable range).
dlangBugzillaToGithub commented 6 years ago

greensunny12 commented on 2018-03-31T15:26:52Z

> See Vose's Alias Method:

Here's my implementation for mir:

https://github.com/libmir/mir/blob/da76cf406d06957e472b9ba90b4c90b917480cb9/source/mir/random/discrete.d

tl;dr:
- std.random's methods should be available as Generators / "Variables"
- Until std.random isn't rewritten it probably doesn't make sense to patch it partially

There's also:

https://issues.dlang.org/show_bug.cgi?id=5849