Mathematica 执行时间错误：符号名称

Question

Mathematica有一个奇怪的bug存在多年，至少从5.1版本开始存在，并在7版本中仍然存在。

---

Module[{f, L}, L = f[];
  Do[L = f[L, i], {i, 10^4}]] // Timing

 {0.015, Null} 

Module[{weirdness, L}, L = weirdness[];
  Do[L = weirdness[L, i], {i, 10^4}]] // Timing

{2.266，Null}

---

• 这是什么原因引起的？是哈希问题吗？

• 在8版本中是否已经修复？

• 是否有办法知道哪些符号名称会导致减速，而不是测试？

- Mr.Wizard

---

真是一个非常奇怪的错误！幸运的是，它似乎在8版本中已经修复了。 - Simon

@Simon 这个问题可能会让人发疯。我希望它已经被修复了；虽然在Mma 8中可能会影响不同的符号名称，但仍然存在某种形式。 - Mr.Wizard

@Mr.Wizard：没错。我测试了一些在7中出现但在8中没有出现的错误案例……但这并不能证明它已经被修复了。 - Simon

“weirdness[ ]”是WR内部保留的函数，用于编写Stephen Wolfram的书籍。 - Dr. belisarius

@Mr. 无语[ ] 是 怪异函数[ ] 的回调函数。 - Dr. belisarius

@belisarius：你有时候有一种奇怪的幽默感... - Simon

Answer 1

这是什么造成的？这是哈希问题吗？

是的，或多或少。

在第8版中，它是否已被修复？

是的（或多或少）。也就是说，它无法被完全修复。但是最常见的情况得到了更好的处理。

除了测试之外，还有其他方法可以知道哪些符号名称会导致减速吗？

我不知道其他的方式。

在版本7中，有一种类似于版本8中的早期修复方法。默认情况下它是关闭的（当我们发货时，我们没有足够的时间测试它，并且它在版本7.0.1中没有被打开）。您可以按照以下步骤访问它。

SetSystemOptions["NeedNotReevaluateOptions"->{"UseSymbolLists"->True}];

这将使您的示例回到合理的范畴。

Module[{weirdness, L}, L = weirdness[];
  Do[L = weirdness[L, i], {i, 10^4}]] // Timing

Out[8]= {0.020997, Null}

---edit---

这里稍微详细地解释一下所涉及的优化。首先需要记住的是，Mathematica模拟“无限评估”，也就是说，表达式会不断评估直到它们不再改变。这可能会很耗时，因此需要仔细的短路优化来尽可能地避免。

我们使用的机制是哈希的一种变体，用于指示可能依赖于表达式的符号未更改，因此表达式未更改。这里可能会发生冲突，从而需要更多的工作。

在糟糕的情况下，Mathematica内核可能需要遍历整个表达式才能确定它是否未更改。这种遍历的成本可以与重新评估一样昂贵。版本7中引入的一项优化（如上所述）是明确记录某些类型的表达式依赖的符号。然后，只需检查自上次评估表达式以来这些符号是否已更改，就可以缩短重新评估检查的时间。

实现细节有点复杂（也有点专有，但也许不难猜到）。但总之，这就是底层发生的事情。早期版本有时需要对表达式进行重大遍历，只是为了发现表达式不需要重新评估。现在这种情况仍然可能发生，但它现在是一种更为罕见的事件。

Daniel Lichtblau Wolfram Research

---end edit---

- Daniel Lichtblau

---

你能更精确地说明这个错误的原因吗？ - Alexey Popkov

要描述导致这种行为的工作原理需要花费一些时间和精力。如果有时间的话我可能会这样做（但这似乎不太可能）。但无论是什么，这都不是一个错误。特别是，“修复”这个词是我选的一个糟糕的选择。 - Daniel Lichtblau

如果您至少能普及地解释一下机制，那将是非常有价值的。打破神秘总是有价值的... - Alexey Popkov

Answer 2

关于版本8：我尝试了100,000个长度不同的随机字符串，并没有发现任何异常情况。

chars = StringCases[CharacterRange["A", "z"], WordCharacter] //Flatten;
res = Table[
       ToExpression[
        StringReplace[
         "First[AbsoluteTiming[Module[{weirdness,L},L=weirdness[];\
    \[IndentingNewLine]Do[L=weirdness[L,i],{i,10^4}]]]]", 
         "weirdness" -> 
          StringJoin[
           RandomChoice[chars, RandomInteger[{1, 20}]]]]], {100000}];

- Sjoerd C. de Vries