如何在 Scheme(Racket 或 ChezScheme)中实现 Python 风格的生成器? [英] How to implement Python-style generator in Scheme (Racket or ChezScheme)?

问题描述

今天我使用 Scheme 解决了 N-queen 问题，但与相同版本的 Python 相比，它非常慢.当 N = 8 时，Scheme 需要 90+ 秒！我知道一个原因是我不能在Scheme中使用生成器，我的代码必须先形成大列表，这对内存和计算来说是一场噩梦.

today I solve the N-queen problem using Scheme but it is extremely slow compared to the same version of Python. when N = 8, Scheme takes 90+ seconds! I know one reason is that I can't use a generator in Scheme, my code has to form large lists first, which is a nightmare for memory and calculation.

Scheme 中关于生成器的主题很少，这个一个是我发现可能有用的唯一一个，但遗憾的是它在球拍或切斯方案中都不起作用.

There is few topics about generator in Scheme, this one is the only one I found maybe useful but sadly it doesn't work in both racket or chez scheme.

其实我只是想要一个简单版的python生成器，也就是不要形成整个列表，一次发送一个值给我.即:

Actually, I just want a simple version of python generator, that is, do not form the whole list, just send me one value at one time. i.e:

(range 100000) ; will consume a large memory

(define g (generator 100000)) ; will do nothing
(next g) ;0 <-you call it with next one time, it returns one value
(next g) ;1
;...
(next g) ;100000
(next g) ;return a value that indicates the end, such as #f.

如果这很难，也欢迎任何相关链接或类似的实现主题.我真的厌倦了寻找.谢谢！

If this is hard, any related links or similar implementation topics are also appreciated. I'm really tired of searching. Thanks!

如果需要，这是我的 N-queen Scheme 代码:

This is my N-queen Scheme code, if needed:

(define (range n)
    (define (recur n)
        (if (= n -1)
            '()
            (cons n (recur (- n 1)))))
    (recur (- n 1)))

(define (flatten a)
    (if (null? a)
        '()
        (append (car a) (flatten (cdr a)))))

(define (safe? x y sln)
    (if (null? sln)
        #t
        (let ((px (car (car sln))) (py (cadr (car sln))))
            (if (or (= y py) (= (- py y) (- px x)) (= (- py y) (- x px)))
                #f 
                (safe? x y (cdr sln))))))

(define (nqueen n)
    (define (recur x)
        (if (= x -1)
            (list '())
            (flatten (map (lambda (y) (map (lambda (sln) (cons (list x y) sln)) (filter (lambda (sln) (safe? x y sln)) (recur (- x 1))))) (range n)))))
    (recur (- n 1)))

(define (pl a)
    (if (null? a)
        '()
        (begin (display (car a)) (display "\n") (pl (cdr a)))))

(pl (nqueen 4))

推荐答案

在这种情况下使用延续(如链接中的建议)是不合理的.这是一个更简单的想法:让我们将生成器定义为一个 thunk(一个无参数函数)，它将起点、最大允许值、增量和当前元素作为其环境的一部分存储.每次我们调用该过程时，都会更新当前元素.以下代码的行为类似于 Python 3.x range() 函数(或 Python 2.x xrange()):

Using continuations for this case (as suggested in the link) is unjustified. Here's a simpler idea: let's define our generator as a thunk (a no-args function) that stores as part of its environment the starting point, the maximum allowed value, the increment and the current element. Every time we call the procedure, the current element will be updated. The following code behaves similar to Python 3.x range() function (or Python 2.x xrange()):

(define (generator start stop step)
  (let ((current (- start 1)))
    (lambda ()
      (cond ((>= current stop) #f)
            (else
             (set! current (+ current step))
             current)))))

现在 next 过程将简单地调用生成器直到达到最大值，此时生成器将开始为每个后续调用返回 #f :

Now the next procedure will simply call the generator until the maximum value is reached, at this point the generator will start returning #f for each subsequent call:

(define (next generator)
  (generator))

例如:

(define g (generator 0 3 1))
(next g) ; 0
(next g) ; 1
(next g) ; 2
(next g) ; 3
(next g) ; #f

另一种选择是使用流，但我会坚持上述解决方案，它很简单，应该适用于任何 Scheme 解释器.还有另一种选择 - 如果您在 Racket 中编码，只需使用 sequence(这也是一个流)，像这样:

Another alternative would be to use streams, but I'll stick with the above solution, it's simple enough and should work on any Scheme interpreter. And yet another alternative - if you're coding in Racket, just use a sequence (which is also a stream), like this:

(for ([i (in-range 0 4 1)])
  (display i))

=> 0123

这篇关于如何在 Scheme(Racket 或 ChezScheme)中实现 Python 风格的生成器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！