Ошибка выполнения Mathematica: имена символов

Question

Существует странная ошибка, которая существует в Mathematica в течение многих лет, по крайней мере, начиная с версии 5.1 и сохраняется до версии 7.

---

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

<b>  {0.015, Null}</b>

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

<b>  {2.266, Null}</b>

---

• Что вызывает это?Это проблема хеширования?

• Исправлено ли это в Версии 8?

• Есть ли способ узнать, какие имена символов вызывают замедление,кроме тестирования?

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}

--- редактировать ---

Я могу объяснить описанную здесь оптимизацию чуть более подробно. Сначала напомним, что Mathematica эмулирует «бесконечную оценку», то есть выражения продолжают оцениваться до тех пор, пока они больше не изменятся. Это может быть дорогостоящим и, следовательно, требует тщательной оптимизации короткого замыкания, чтобы предотвратить его, когда это возможно.

Механизм, который мы используем, представляет собой вариант хеширования, который служит для указания того, что символы, от которых может зависеть выражение, не изменяются и, следовательно, это выражение не изменяется. Именно здесь могут происходить столкновения, что требует дополнительной работы.

В плохом случае ядру Mathematica, возможно, потребуется пройтись по всему выражению, чтобы определить, что оно не изменилось. Эта прогулка может быть такой же дорогой, как и переоценка. Оптимизация, новая для версии 7 (отмеченная выше), заключается в явной записи для некоторых типов выражений тех символов, от которых она зависит. Затем проверку переоценки можно сократить, просто проверив, что ни один из этих символов не был изменен с момента последней оценки выражения.

Детали реализации немного сложны (а также немного запатентованы, хотя, возможно, не так сложно догадаться). Но это, вкратце, то, что происходит под капотом. Более ранние версии иногда делали существенный обход выражения только для того, чтобы обнаружить, что выражение не нуждается в переоценке. Это все еще может случиться, но сейчас это гораздо более редкое событие.

--- конец редактирования ---

Даниэль Лихтблау Wolfram Research

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}];