random-sample: replace algorithm R.

* rand.c (random_sample): The brnach of the code for lists is
converted from the naive algorithm R which requires a random
integer for each element of the sequence to a list adaptation
of the smarter algorithm L used for vector. We don't have
random access through the list being sampled, but we can step
to new positions without generating random numbers.

1 files changed, 13 insertions, 4 deletions

diff --git a/rand.c b/rand.c
index d9fe796d..3e676ff1 100644
--- a/rand.c
+++ b/rand.c
@@ -543,10 +543,19 @@ static val random_sample(val size, val seq, val state_in)
       }
     }
   } else {
-    for (; seq_get(&iter, &elem) && i <= INT_PTR_MAX; i++) {
-      cnum r = c_n(random(state, unum(i)));
-      if (r < sz)
-        samp->v.vec[r] = elem;
+    double weight = elrd(sz, state);
+
+    for (;;) {
+      cnum nx = i + flrd(weight, state) + 1;
+      for (; seq_get(&iter, &elem) && i < nx; i++)
+        ; /* nothing */
+
+      if (i < nx)
+        break;
+
+      samp->v.vec[c_n(random(state, size))] = elem;
+      mut(samp);
+      weight *= elrd(sz, state);
     }
   }