Vitter's reservoir sampling algorithm D: randomly selecting unique items

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by dfabulich on Monday April 04, 2016 @03:13AM (#11419958)

The C code in this article is a mirror of the code from Appendix 2 in Vitter's paper, which I guess explains/excuses the abbreviated variable names. The paper says things like, "use an exponentially distributed random variate Y," and uses variable names like n, N, U, S, X, y1, and y2 in the appendix.

Nonetheless, I find this coding style unreadable. "Y" is not a very good name for an exponentially distributed random variate, especially in a function that defines 24 variables with mostly meaningless names. :-(

[ Parent | on HN ]

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by chipsambos on Monday April 04, 2016 @07:08AM (#11420862)

var naming aside, the whitespacing is perplexing:

      U = random_double(); negSreal=-S;
      y1=exp(log(U*Nreal/qu1real)*nmin1inv);
      Vprime = y1 * (-X/Nreal+1.0)*(qu1real/(negSreal+qu1real));
      if(Vprime <= 1.0) break;       y2=1.0; top = -1.0+Nreal;       if(-1+n > S){bottom=-nreal+Nreal;limit=-S+N;}
      else{bottom=-1.0+negSreal+Nreal; limit=qu1;}

Sometimes two statements per line, sometimes one. Sometimes spaces before and after equals, sometimes none. Sometimes multiple ifs, breaks and statements on one line.

It looks like it was copy-pasted from a pdf. Maybe it was.

[ Parent | on HN ]

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by retbull on Monday April 04, 2016 @01:37PM (#11423737)

I feel like 2 seconds in an ide would have saved readability quite a bit. A simple automated cleanup would have helped worlds.

[ Parent | on HN ]

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by wodenokoto on Monday April 04, 2016 @03:43AM (#11420079)

On the other hand, you need the original names in order to reference back to the paper.

[ Parent | on HN ]

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by Gibbon1 on Monday April 04, 2016 @04:05AM (#11420155)

random_variate_y

[ Parent | on HN ]