From 09010c1509a30cdd042f1b31a1ecd84922adbba2 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Sat, 29 Jan 2022 00:27:09 -0800 Subject: 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. --- rand.c | 17 +++++++++++++---- 1 file 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); } } -- cgit v1.2.3