15

假设我有这个功能：（Haskell 语法）

f x = (x,x)

该函数执行的工作（计算量）是多少？

起初我以为它显然是恒定的，但如果类型x不是有限的，意思是 x 可以占用任意数量的内存呢？人们还必须考虑通过复制完成的工作x，对吗？

这使我相信该函数所做的工作实际上与输入的大小呈线性关系。

这本身不是家庭作业，而是在我必须定义该函数完成的工作时提出的：

f x = [x]

我相信这也有类似的问题。

4

2 回答 2

33

非常非正式地，所做的工作取决于您的语言的操作语义。Haskell，嗯，它很懒，所以你只需支付恒定的因素：

  • 将指针压入x堆栈
  • 为(,)
  • 适用(,)于其论点
  • 返回指向堆单元的指针

完毕。O(1)工作，当调用者查看f.

现在，如果您查看内部，您将触发进一步的评估(,)-- 并且该工作依赖于评估x自身的工作。由于在 Haskell 中对的引用x是共享的，因此您只需对其进行一次评估。

因此，如果您完全评估结果，Haskell 中的工作是O(work of x) 。您的函数f仅添加常数因子。

于 2012-05-31T00:20:46.057 回答
1

Chris Okasaki has a wonderful method of determining the work charged to function call when some (or total) laziness is introduced. I believe it is in his paper on Purely Functional Data Structures. I know it is in the book version -- I read that part of the book last month. Basically you charge a constant factor for the promise/thunk created, charge nothing for evaluating any passed in promises/thunks (assume they've already been forced / are in normal form [not just WHNF]). That's an underestimate. If you want an overestimate charge also the cost of forcing / converting to normal form each promise / thunk created by the function. At least, that's how I remember it in my extremely tired state.

Look it up in Okasaki: http://www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis -- I swear the thesis used be be downloadable.

于 2012-06-07T04:17:01.730 回答