1

我有这个代码：

(define tree `(A (B (C)) (D (E)) (C (E))))

(define (prog1 graph)
    (let ([seen `()])
      (define (sub g)
          (cond 
              [(member (car g) seen) `()]
              [else 
               (set! seen (cons (car g) seen))
               (cond
                 [(null? (cdr g)) (list (car g))]
                 [else
                  (cons (car g) (map sub (cdr g)))])])) 
    (delete `() (sub graph))))

(define delete
  (lambda (x y)
      (if (null? y )
            `()
      (if (eqv? (car y) x)
           (delete x (cdr y))
      (cons (car y) (delete x (cdr y)))))))

它打印一个连接图，其中所有节点都出现一次。

跑步(prog1 tree)

印刷：(A (B (C)) (D (E)))

我已经查看了 lisp 中的各种深度优先搜索（类似于我正在尝试做的事情），它们似乎对此更加优雅，有些使用迭代方法。我知道该程序效率不高（在大树上运行速度很慢）所以我将如何提高这段代码的效率？

谢谢，詹姆斯

4

2 回答 2

1

在大多数情况下，此代码中的瓶颈不是树遍历，而是member查找。您的函数的复杂性似乎大致为 O(M*N)，其中 M 是不同节点的数量，N 是总节点的数量。M 将其作为一个因素的原因是因为您正在查找线性列表中的节点，这需要与列表长度成正比的时间（在您的情况下与不同节点的数量成正比）。

摆脱 M 的方法是使用更高效的数据结构进行查找。例如，R6RS 定义了哈希表。

于 2012-12-27T20:13:37.170 回答
1

该过程在每次调用时都会对列表member进行查找。O(n)这不是我们想要快速测试集合成员资格的东西，因为您应该使用一种数据结构，为O(1)在集合中添加元素和测试元素成员资格提供复杂性，理想情况下是 Set 数据结构或代替它的 Hash Table。例如，在 Racket 中尝试替换这些行（或使用 Scheme 解释器中的默认哈希表实现）：

(let ([seen `()]) => (let ([seen (make-hash)])

[(member (car g) seen) `()] => [(hash-has-key? seen (car g)) '()]

(set! seen (cons (car g) seen)) => (hash-set! seen (car g) 'ok)

此外，通常您希望在代码中使用引号'()：而不是quasiquotes : `()，请参阅链接以了解差异以及何时适合使用 quasiquoting。

最后，您可以使用内置remove程序，无需自己实现delete.

于 2012-12-27T20:40:18.233 回答