球拍:矢量上的滑动窗口

Question

在Racket中对有限序列执行滑动窗口有哪些好方法，例如找到任何4个数字的子序列的最高和？

(define example #(3 1 4 5 10 23 1 50 0 12 40 12 43 20))

Answer 1

首先找到前缀总和：

#lang racket
(define example #(3 1 4 5 10 23 1 50 0 12 40 12 43 20))
(define-values (sums sum)
(for/fold ([sums '()] [sum 0]) ([x example])
(values (cons sum sums) (+ sum x))))
(list->vector (cons sum sums))

结果：

'#(224 204 161 149 109 97 97 47 46 23 13 8 4 3 0)

然后。。。利润。

利润可能是这样的：

#lang racket
(define example #(3 1 4 5 10 23 1 50 0 12 40 12 43 20))
(define (prefix-sums xs)
(define-values (sums sum)
(for/fold ([sums '()] [sum 0]) ([x xs])
(values (cons sum sums) (+ sum x))))
(list->vector (reverse (cons sum sums))))
(define (sum4 xs i)
(- (vector-ref xs (+ i 4))
(vector-ref xs    i)))
(define (sum4s xs)
(for/list ([i (- (vector-length xs) 4)])
(sum4 (prefix-sums xs) i)))
(apply max (sum4s example))

Answer 2

对于更通用的方法，下面是一个序列构造函数，它从向量返回一个包含len个元素的滑动窗口，一次len个值，然后可以与for推导一起使用：

(define (in-vector-window v len)
(make-do-sequence
(lambda ()
(values
(lambda (i) (vector->values v i (+ i len)))
add1
0
(lambda (i) (<= (+ i len) (vector-length v)))
#f
#f))))

还有一些示例用法：

> (for/list ([(a b c d) (in-vector-window example 4)]) (list a b c d))
'((3 1 4 5) (1 4 5 10) (4 5 10 23) (5 10 23 1) (10 23 1 50) (23 1 50 0) (1 50 0 12) (50 0 12 40) (0 12 40 12) (12 40 12 43) (40 12 43 20))
> (define sums (for/list ([(a b c d) (in-vector-window example 4)]) (+ a b c d)))
> (foldl max (car sums) (cdr sums))
115