prog


Cartesian product.

9 2019-01-12 05:15

>>8
Interestingly memoizing this function actually resulted in identical performance on all tested implementations. This must be due to some common code transformation shifting previous loop values within scope or some such thing (I've not looked into these transformations to know for sure). Needless to say this is actually exceedingly fast, I was able to calculate the cartesian product of a 5000 dimension 2000 wide set of non-repeating data on my x220 in 15 seconds in Gauche, and around 50 seconds in Chibi. Just for the sake of it I'll go ahead and post the memoized version here, but there is really no reason to use it, it's uglier, requires a helper, and depends on outside libraries. I hope these functions solve your problem sufficiently anon, I'm sorry I wasn't able to respond in a more timely manner.

(import (scheme base) (scheme hash-table) (scheme comparator))

(define (memo-cartesian-product . An)
  (define table
    (make-hash-table (make-default-comparator)))

  (define cartesian-product-iter
    (memoize
      (lambda (values An)
        (if (null? An)
          (values '())
          (map
            (lambda (x)
              (cartesian-product-iter
                (lambda (y) (values (cons x y)))
                (cdr An)))
            (car An))))
      (lambda (x) (cadr x))
      table))

  (cartesian-product-iter (lambda (x) x) An))

; a generalised memoize function based off of SICP exercise 3.27
(define (memoize function convertor table)
  (lambda x
    (let* ((hashable-x (convertor x))
           (memoized-value (hash-table-ref table hashable-x (lambda () #f))))
      (or memoized-value
          (let ((result (apply function x)))
            (hash-table-set! table hashable-x result)
            result)))))
11


VIP:

do not edit these