codepad

Language:

; reservoir sampling

(define (take n xs)
  (let loop ((n n) (xs xs) (ys '()))
    (if (or (zero? n) (null? xs))
        (reverse ys)
        (loop (- n 1) (cdr xs)
              (cons (car xs) ys)))))

(define (drop n xs)
  (let loop ((n n) (xs xs))
    (if (or (zero? n) (null? xs)) xs
      (loop (- n 1) (cdr xs)))))

(define rand ; knuth random number generator with shuffle box
  (let* ((a 69069) (c 1234567) (m 4294967296) (k 32) ; 32-bit
         ; (a 6364136223846793005) (c 1442695040888963407)
         ; (m 18446744073709551616) (k 256) ; 64-bit
         (seed (current-seconds))
         (next (lambda ()
           (set! seed (modulo (+ (* a seed) c) m)) seed))
         (init (lambda (seed) (let ((box (make-vector k)))
           (do ((j 0 (+ j 1))) ((= j k) box)
             (vector-set! box j (next))))))
         (box (init seed)))
    (lambda args
      (when (pair? args)
        (set! seed (modulo (car args) m)) (set! box (init seed)))
      (let* ((j (quotient (* k seed) m)) (n (vector-ref box j)))
        (set! seed (next)) (vector-set! box j seed) (/ n m)))))

(define (randint . args)
  (let ((lo (if (pair? (cdr args)) (car args) 0))
        (hi (if (pair? (cdr args)) (cadr args) (car args))))
    (+ lo (floor (* (rand) (- hi lo))))))

(define (sample k xs)
  (let ((resv (list->vector (take k xs))))
    (do ((xs (drop k xs) (cdr xs)) (i k (+ i 1))) ((null? xs) resv)
      (let ((j (randint i)))
        (when (< j k) (vector-set! resv j (car xs)))))))

(define xs '(a b c d e f g h i j k l m n o p q r s t u v w x y z))
(display (sample 3 xs)) (newline)
(display (sample 3 xs)) (newline)
(display (sample 3 xs)) (newline)

Private [?]

Run code