andmap stress test

andmap-stress-test.rkt

#lang racket

;; Allows for improper lists
(define (my-andmap proc l1 l2)
  (let loop ([l1 l1] [l2 l2])
    (cond [(and (null? l1) (null? l2)) #t]
          [(or (null? l1) (null? l2))
           (error "Lists must have the same length" (length l1) (length l2))]
          [(and (pair? l1) (pair? l2))
           (and (proc (car l1) (car l2))
                (loop (cdr l1) (cdr l2)))]
          [else
           (error "Pairs expected" l1 l2)])))

(begin
  (define N 10000)
  (define m 1000)

  (define ll
    (for/list ([i m])
      (for/list ([j N])
        (random 10))))

  (define l1 (first ll))

  ;; Custom my-andmap: ~7ms
  (time
   (for/sum ([l1 (in-list ll)])
     (if (for/or ([l2 (in-list ll)]
                  #:unless (eq? l1 l2))
           (my-andmap = l1 l2))
         1
         0)))

  ;; std andmap: 166s (!)
  (time
   (for/sum ([l1 (in-list ll)])
     (if (for/or ([l2 (in-list ll)]
                  #:unless (eq? l1 l2))
           (andmap = l1 l2))
         1
         0))))

#|
$ racket andmap-stress-test.rkt
cpu time: 7 real time: 7 gc time: 0
0
cpu time: 166744 real time: 166784 gc time: 176
0
|#

The reason is andmap checks the lengths of the lists at each call. But by contrast to list?, length is not memoized, which gives it O(m²N) running time instead of the high-probability O(m²) for the custom my-andmap in this case.

In principle, the length check could be lifted to the top level or be memoized.