为具有自动值的结构字段执行合同，测量时间复杂度

Question

我是一个新手，试图通过制作一个结构作为计算过程调用的工具来基本理解结构和契约（在我的 class 中，我们刚刚进入时间复杂度）基本上，我想知道您是否可以在具有自动值的结构字段上执行合同。

这是我正在使用的代码：

#lang racket
(struct counter (name [count #:mutable #:auto])
  #:auto-value 0
  #:property prop:procedure
  (lambda(c-id)
    (set-counter-count! c-id (add1 (counter-count c-id)))))

(define (counter-print! counter)
  (printf "~a: ~a\n" (counter-name counter) (counter-count counter)))

(define (counter-reset! counter)
  (set-counter-count! counter 0))

(provide (contract-out (struct counter ([name string?]
                                        [count integer?])))
         counter-print! counter-reset!)

我会通过在感兴趣的过程前面定义计数器来使用该结构，在我想计算内部过程调用的地方插入对计数器的调用，然后重复运行具有不同输入的过程大小和 printing/reseting 计数器（你可以让我知道这是否也是一种收集复杂性数据的愚蠢方法）。

现在我知道我的代码不起作用，因为合同似乎强制要求计数器采用 2 个参数，但结构定义规定计数器采用 1 个参数。一个简单的解决方法是删除 auto 关键字，但我我想知道是否有一种方法可以将计数自动设置为 0 但仍然强制执行，以便使数据类型更安全，即设置计数器计数！调用非整数值时失败。有什么建议吗？

Answer 1

我似乎从来没有使用过 #:auto，因为它似乎从来没有像我希望的那样工作。

在这种情况下，我想我会简单地 provide 为个人 struct 构造函数和访问函数制定合同：

(provide (contract-out [counter (-> string? counter?)]
                       [counter-count (-> counter? integer?)]
                       [counter-name (-> counter? string?)])
         counter-print! counter-reset!)

然后像这样使用：

#lang racket

(require "counter.rkt")

(define c (counter "a"))
(counter-name c)  ;=> "a"
(counter-count c) ;=> 0
(c) ;increment
(counter-count c) ;=> 1

说了这么多，对于你所描述的，我想我可能只使用 mutable 散列-table。另外，我可能会将哈希-table 键设置为 procedure? 而不是 string?。例如：

(define ht (make-hash)) ;(hash/c procedure? integer?)

(define (increment-counter proc)
  (hash-update! ht
                proc
                (λ (v) (add1 v))
                0))

(define (get-counter proc)
  (hash-ref ht proc #f))

(increment-counter display)
(get-counter display) ;=> 1
(increment-counter display)
(get-counter display) ;=> 2

(increment-counter displayln)
(get-counter displayln) ;=> 1

ht ;=> '#hash((#<procedure:displayln> . 1) (#<procedure:display> . 2))

为具有自动值的结构字段执行合同，测量时间复杂度

Enforcing contracts for struct fields with auto values, measuring time complexity

struct

time-complexity

racket