www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 11597] New: Speed up std.random.dice

reply d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=11597

           Summary: Speed up std.random.dice
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: zshazz gmail.com



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.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 24 2013
next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=11597


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc





 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).

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=11597




Associated pull request:
https://github.com/D-Programming-Language/phobos/pull/1716

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 24 2013
prev sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=11597


Joseph Rushton Wakeling <joseph.wakeling webdrake.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |joseph.wakeling webdrake.ne
                   |                            |t



2013-11-30 02:07:50 PST ---


 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).

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 30 2013