[racket] Fannkuch-redux benchmark

From: Chris (c.bowdon at gmail.com)
Date: Sun Mar 18 04:38:21 EDT 2012

Hi all,

I've implemented the 'pfannkuchen' algorithm for the fannkuch-redux benchmark on shootout.alioth.debian.org, since this is the only remaining benchmark without a Racket attempt. It seemed like a fun newbie project.

I'd appreciate any optimization hints or general comments and criticism of my coding. The full code is at https://github.com/cbowdon/Fannkuch-Redux.

In terms of optimization, the worst offender is the following function:

;; perform flipping on a single permutation, return number of flips
(define (fannkuch input)
  ;; perform a single rearrangement
  (define (single-flip source result count)
    (if [= count 0]
        (single-flip (cdr source) (cons (car source) result) (sub1 count))))      
  ;; flip until (car lst) is 1
  (define (multi-flip lst number-of-flips)
    (let ([l (car lst)])
      (if [= l 1]
          (multi-flip (single-flip lst (drop lst l) l) (add1 number-of-flips)))))  
  (multi-flip input 0))

Any advice? Profiling suggested that 70% of time is spent in this function.

Best regards,

P.S. Kindly note that this is a question about some code, not a meta-discussion on computer language benchmarks etc.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120318/2a612e63/attachment-0001.html>

Posted on the users mailing list.