[phobos] [D-Programming-Language/phobos] a47707: Rewrite of RandomSample to use Jeffrey Scott Vitte...

[GitHub]

  Branch: refs/heads/master
  Home:   https://github.com/D-Programming-Language/phobos
  Commit: a47707a19796c41a9cb77ae9ae09605afd56fa6f
      https://github.com/D-Programming-Language/phobos/commit/a47707a19796c41a9cb77ae9ae09605afd56fa6f
  Author: Joseph Rushton Wakeling <joe at webdrake.net>
  Date:   2012-04-24 (Tue, 24 Apr 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  Rewrite of RandomSample to use Jeffrey Scott Vitter's Algorithm D.

This algorithm calculates a random sample of size n in O(n) time,
generating O(n) random variates, as opposed to the previously
implemented Algorithm S where both scale with the size of the
data being sampled.

Variable names in the implementation follow those in Vitter's
papers introducing the algorithm:

  * Vitter, J. S. (1984) Faster methods for random sampling.
    Commun. ACM 27(7): 703--718.

  * Vitter, J. S. (1987) An efficient algorithm for sequential
    random sampling.  ACM Trans. Math. Softw. 13(1): 58--67.


  Commit: 34c7d2f9ecc3250577aeeb55fb1ebea3ff3c8f1f
      https://github.com/D-Programming-Language/phobos/commit/34c7d2f9ecc3250577aeeb55fb1ebea3ff3c8f1f
  Author: Joseph Rushton Wakeling <joe at webdrake.net>
  Date:   2012-04-26 (Thu, 26 Apr 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  Tweaks to authorship & comments.


  Commit: 39bc5ae412f4646dabbec27dbce97457e2afc0f7
      https://github.com/D-Programming-Language/phobos/commit/39bc5ae412f4646dabbec27dbce97457e2afc0f7
  Author: Joseph Rushton Wakeling <joe at webdrake.net>
  Date:   2012-05-04 (Fri, 04 May 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  skip() and skipA() should not be called as properties.

Ensures code builds with -property and -unittest flags
both enabled.


  Commit: 56ef13997ece3eef5290a175834342956d7b8c81
      https://github.com/D-Programming-Language/phobos/commit/56ef13997ece3eef5290a175834342956d7b8c81
  Author: Joseph Rushton Wakeling <joe at webdrake.net>
  Date:   2012-05-04 (Fri, 04 May 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  Bring code in line with D style.


  Commit: 40a79b32e2391189a0a53ddcfbbeeec46251fdf9
      https://github.com/D-Programming-Language/phobos/commit/40a79b32e2391189a0a53ddcfbbeeec46251fdf9
  Author: Joseph Rushton Wakeling <joe at webdrake.net>
  Date:   2012-05-04 (Fri, 04 May 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  RandomSample should check if input is InputRange.


  Commit: d7f5bb0aa5e00ea8c2b33a2c6fb4a650cb85c153
      https://github.com/D-Programming-Language/phobos/commit/d7f5bb0aa5e00ea8c2b33a2c6fb4a650cb85c153
  Author: Joseph Rushton Wakeling <joe at webdrake.net>
  Date:   2012-05-04 (Fri, 04 May 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  Small typo correction in comment/doc.


  Commit: 5f539a16220b2d38cea71ead2e9ffb4873359c86
      https://github.com/D-Programming-Language/phobos/commit/5f539a16220b2d38cea71ead2e9ffb4873359c86
  Author: Joseph Rushton Wakeling <joe at webdrake.net>
  Date:   2012-05-04 (Fri, 04 May 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  Fix link errors in Ddoc comments.


  Commit: 205c3bf4cbfb38f0603ea821a3858e433ff30aa0
      https://github.com/D-Programming-Language/phobos/commit/205c3bf4cbfb38f0603ea821a3858e433ff30aa0
  Author: Joseph Rushton Wakeling <joe at webdrake.net>
  Date:   2012-05-09 (Wed, 09 May 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  Fix problem of first sample point always being identical.


  Commit: ae15e0ec1459d2af5e1b99eda0d4a44527ab6a29
      https://github.com/D-Programming-Language/phobos/commit/ae15e0ec1459d2af5e1b99eda0d4a44527ab6a29
  Author: Andrei Alexandrescu <andrei at erdani.com>
  Date:   2012-07-01 (Sun, 01 Jul 2012)

  Changed paths:
    M std/random.d

  Log Message:
  -----------
  Merge pull request #553 from WebDrake/master

Rewrite of RandomSample to use Jeffrey Scott Vitter's Algorithm D.


Compare: https://github.com/D-Programming-Language/phobos/compare/ec693afc67ec...ae15e0ec1459