Racket set performance

General
8

A couple more variants using nested hasheq:

(define mutable-set make-hasheq)

(define (in-set s)
  (for*/list ([(x hx) s] [(y hy) hx])
    (make-rectangular x y)))

(define (set-add! s v)
  (hash-set! (hash-ref! s (real-part v) make-hasheq)
             (imag-part v)
             #t))

(define (set-member? s v)
  (hash-has-key? (hash-ref s (real-part v) make-hasheq) 
                 (imag-part v)))

This takes 770ms on my machine, but in-set will create a potentially long list, so it’s not ideal.

We can change in-set to

(define (in-set s)
  (for*/stream ([(x hx) s] [(y hy) hx])
    (make-rectangular x y)))

This takes 1.1s.

An efficient solution would use define-sequence-syntax, which uses for*/stream when it’s not used directly in a for form, and uses :do-in when it appears directly in a for form. This should make it even faster than the for*/list variant.

1 Like