schematics-development — Discussion of Schematics project and code development

You can subscribe to this list here.

 2002 2003 2004 2005 2006 2007 2008 2013 Jan Feb Mar Apr May Jun Jul Aug Sep (21) Oct (24) Nov (80) Dec (13) Jan (13) Feb (34) Mar (22) Apr (21) May (48) Jun (33) Jul (3) Aug (2) Sep (3) Oct (12) Nov (12) Dec (7) Jan (22) Feb (5) Mar (58) Apr (80) May (74) Jun (79) Jul (15) Aug (122) Sep (63) Oct (8) Nov (1) Dec (2) Jan (13) Feb (24) Mar (5) Apr (16) May (27) Jun Jul (5) Aug Sep Oct (3) Nov (8) Dec (2) Jan (1) Feb (5) Mar (11) Apr (1) May (16) Jun (5) Jul (2) Aug Sep Oct (1) Nov (1) Dec (5) Jan (4) Feb (4) Mar (4) Apr (5) May (1) Jun Jul Aug (3) Sep (1) Oct (1) Nov (1) Dec (3) Jan (1) Feb Mar (1) Apr May (1) Jun (1) Jul (6) Aug (5) Sep (3) Oct Nov Dec Jan (1) Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
S M T W T F S

1
(2)
2
(4)
3

4
(1)
5
(6)
6
(7)
7

8

9
(3)
10
(2)
11
(1)
12
(5)
13
(3)
14
(4)
15

16
(1)
17
(1)
18

19

20
(1)
21

22

23

24

25
(1)
26

27
(3)
28

29

30
(2)
31
(1)

Showing 1 results of 1

 Re: [Schematics-development] discrete random variables From: - 2003-05-04 13:04:21 ```sebastian.egner@... wrote: > Mike Sperber forwarded me a short discussion related to using > pseudo random values with given probability distribution. > In other words, given probabilities p[0], .., p[n-1] summing to one, > construct a pseudo-random process for values x in {0..n-1} > such that Pr{x = k} = p[k]. > > I would like to bring to your attention that there is a method to > draw the next pseudo-random value in O(1), after having > prepared a datastructure of size O(n). This method is known > as the "method of aliases" by A. J. Walker (Electronic Letters 1974). > It will be much faster than the code currently used in Schemathics > which uses time O(n) for drawing the next random value. For those that have Knuth, I have found the algorithm in volume 2, section 3.4.1 (page 120). He writes: However, there is actually a faster way to select x1,...,xk with arbitrarily given probabilities, based on an ingenious approach introduced by A. J. Walker [Electronics Letters 10, 8 (1974)]. Note the "ingenious". > For convenience, I just wrote some code for this :-) > If there would be a good implementation for priority queues > around, the preparation phase could be improved... Is there special requirements for the priority queue? At first glance at the exercise in Knuth, it seems that one must be able to find both the minimum and the maximum element of the priority queue. Is the priority queue used after the initial preparation of the table? -- Jens Axel Søgaard ```

Showing 1 results of 1