列表过滤+计数 vs. 直接计数？奇怪的测试结果

Question

这是关于计算列表中有多少元素满足给定测试。

我看到了这个函数

(define (numsof p lst)
  (length (filter p lst)))

并认为它效率低下，因为它必须遍历两个列表，第一个列表用于过滤，然后用 length 计算结果。所以我实现了这个来直接计算有多少元素满足测试 p.

 (define (amount p lst [acc 0])
  (if (empty? lst)
      acc
      (amount p (cdr lst) (if
                           (p (car lst))
                           (add1 acc)
                           acc))))

然后我运行使用辅助函数进行了如下测试：

; Creates list of natural numbers in [0, range) of given length
(define (random-list length range)
  (if (zero? length)
      null
      (cons (random range) (random-list (sub1 length) range))))

(for ([i 10])
  (display "numsof: ") (time (numsof odd? (random-list 999999 9999999)))
  (display "amount: ") (time (amount odd? (random-list 999999 9999999)))
  (displayln ""))

现在我得到的结果对我来说非常出乎意料，因为我认为我的定义 amount 应该是 numsof 的两倍左右，但我还没有真正进入算法性能，所以这个无论如何，猜测对你来说可能显然是错误的。

这里，给大家一些测试结果：

numsof: cpu time: 2875 real time: 2710 gc time: 2060
amount: cpu time: 2578 real time: 2590 gc time: 1872

numsof: cpu time: 1484 real time: 1494 gc time: 719
amount: cpu time: 2547 real time: 2586 gc time: 1779

numsof: cpu time: 2422 real time: 2449 gc time: 1748
amount: cpu time: 2593 real time: 2608 gc time: 1843

numsof: cpu time: 1375 real time: 1360 gc time: 658
amount: cpu time: 2641 real time: 2662 gc time: 1842

numsof: cpu time: 2609 real time: 2593 gc time: 1873
amount: cpu time: 1406 real time: 1400 gc time: 655

numsof: cpu time: 2640 real time: 2652 gc time: 1938
amount: cpu time: 1360 real time: 1384 gc time: 623

有人可以向我解释一下我的函数是快点还是慢点吗？无论如何，为什么？还有测试结果是怎么回事，我也看不懂。

Answer 1

更新：其中大部分都是完全错误的。跳到最后的“更新：请阅读此内容”。

我得到了类似的结果。

一个可能的解释是，如果 Racket lists —— 记住，它们是不可变的 —— 存储它们的长度，那么 length 就像结构成员一样简单地查找一个值，因为反对遍历所有列表元素。（我依稀记得在 Racket 邮件列表上读过类似的东西，但不幸的是现在找不到。）

可能的证据是，随着列表大小的增加，length 是否需要明显更长的时间：

(for ([len (in-list (list 100 1000 10000 100000 1000000))])
  (define xs (build-list len values))
  (time (length xs)))

cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 0 real time: 0 gc time: 0
cpu time: 1 real time: 0 gc time: 0
cpu time: 4 real time: 3 gc time: 0

好的，最后两个时间不为零。但是它们很小。出于实际目的，O(1) 而不是 O(n)，即使对于相当大的 n。

更新

其实我跳过了一大步。我的回答解释了我认为你的散文在问什么，而不是你展示的测试代码。我认为您所指的测试代码——实际上符合您的问题——应该是这样的：

(for ([i 10])
  (define xs (random-list 999999 9999))
  (display "numsof: ") (time (numsof odd? xs))
  (display "amount: ") (time (amount odd? xs))
  (displayln ""))

这会创建一个随机列表，然后仅在该列表上 numsof 与 amount 本身运行的时间。

这为 numsof 和 amount 提供了基本相同的时间。

对此的解释是，如果 length 实际上是 O(1)，因为 Racket 列表存储它们的长度。

至于为什么您提供的原始测试代码在 random-list 的调用中显示如此不同的结果？我认为这仅仅是因为内存分配和垃圾收集时间难以预测。

更新：请阅读本文

我在这个回答中所说的几乎所有内容都被证明是错误的。具体来说：

length 不缓存。 list? 确实如此。
我打破了剖析的第一条规则。我没有使用普通的命令行 Racket。结果，我的测量值受到 errortrace 注释的影响。
此外，我可能应该在每个 time 之前使用 (for ([_ 3]) (collect-garbage))，以专注于独立于垃圾收集时间的算法。

关于我最初的答案中唯一的价值是这样的想法，即对于足够小的列表，编写 length 和 filter 之类的事情可能没问题。但实际上，对于 "Are there ever times when it's OK to favor clarity of expression over speed?" 这样的问题，这是一个显而易见的答案。对这个问题的更简短的回答是，"Yes, it depends".

列表过滤+计数 vs. 直接计数？奇怪的测试结果

List filtering+counting vs. directly counting? Weird test results

list

counting

racket

更新：请阅读本文