Mathematica "связанные списки" и производительность

Question

В Mathematica я создаю односвязные списки, например, так:

toLinkedList[x_List] := Fold[pair[#2, #1] &, pair[], Reverse[x]];

fromLinkedList[ll_pair] := List @@ Flatten[ll];

emptyQ[pair[]] := True;
emptyQ[_pair] := False;    

Использование символа pair для cons-ячеек дает преимущество в Flatten безопасной работе, даже если списки содержат стиль MathematicaList s, и позволяет вам определять пользовательские обозначения, используя MakeExpression / MakeBoxes, что делает все намного приятнее.Чтобы избежать необходимости использовать $IterationLimit, я написал функции для работы с этими списками, используя либо циклы While, либо NestWhile вместо рекурсии.Естественно, я хотел посмотреть, какой подход будет быстрее, поэтому я написал два кандидата, чтобы я мог посмотреть их бой:

nestLength[ll_pair] := 
 With[{step = {#[[1, -1]], #[[-1]] + 1} &},
  Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]];

whileLength[ll_pair] := 
 Module[{result = 0, current = ll},
  While[! emptyQ@current,
   current = current[[2]];
   ++result];
  result];

Результаты были очень странными.Я протестировал функции в связанных списках длиной 10000, и whileLength обычно был примерно на 50% быстрее, примерно с 0,035 секунды до nestLength с 0,055 секундами.Однако иногда whileLength может занять около 4 секунд.Я подумал, что может быть какое-то поведение при кэшировании, поэтому я начал генерировать новые случайные списки для проверки, и whileLength не обязательно будет медленным при первом запуске с новым списком;это может занять десятки раз, чтобы увидеть замедление, но затем оно не повторится (по крайней мере, для 200 прогонов, которые я пробовал с каждым списком).

Что может происходить?

Для справки, функция, которую я использовал для тестирования, такова:

getTimes[f_, n_] :=
 With[{ll = toLinkedList@RandomInteger[100, 10000]},
  Table[Timing[f@ll], {n}][[All, 1]]]

РЕДАКТИРОВАТЬ: Я не упомянул версию ранее;Я получил эти результаты с Mathematica 8.

РЕДАКТИРОВАТЬ второе: Когда я прочитал Ответ Даниэля Лихтблау , я понял, что мои времена для «типичных» пробегов опущены ведущие0. Это было исправлено.

РЕДАКТИРОВАТЬ третье: Я думаю Леонид Шифрин правильно связать проблему с Module;Я могу получить такое же поведение от NestWhile версии, заменив With на Module:

nestModuleLength[ll_pair] := 
  Module[{step = {#[[1, -1]], #[[-1]] + 1} &}, 
   Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]];

In[15]:= Select[getTimes[nestModuleLength, 100], # > 3 &]
Out[15]= {3.797}

Answer 1

Примеры, приведенные ниже, дают типичные результаты.

Один медленный пример в прогоне длиной 20.

In[18]:= getTimes[whileLength, 20]

Out[18]= {0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, \
0.031, 0.047, 0.032, 0.031, 0.031, 3.547, 0.047, 0.031, 0.031, 0.032, \
0.031, 0.031}

Попутно отмечу, что время примерно в 10 раз быстрее, чем в исходном посте.За исключением медленных случаев, которые сопоставимы.Не уверен, что объясняет эту разницу в соотношениях.

Нет медленных примеров.

In[17]:= getTimes[nestLength, 20]

Out[17]= {0.047, 0.047, 0.062, 0.047, 0.047, 0.062, 0.047, 0.047, \
0.047, 0.063, 0.046, 0.047, 0.047, 0.063, 0.047, 0.046, 0.047, 0.063, \
0.047, 0.047}

Один медленный пример в пробеге длиной 100.

In[19]:= getTimes[whileLength, 100]

Out[19]= {0.031, 0.031, 0.031, 0.032, 0.031, 3.594, 0.047, 0.031, \
0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, \
0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.047, 0.031, 0.031, \
0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, \
0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, \
0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.031, \
0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.032, \
0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.046, 0.032, \
0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.032, 0.031, \
0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.031, 0.032, 0.031, \
0.031, 0.031}

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

В некоторых случаях это может быть сложно различить (из-за эффекта, похожего на хеш-коллизии), а выражения могут быть излишнеперепроверены.Глубоко вложенные выражения имеют тенденцию быть худшим случаем для этого.У нас есть дополнительный код, который часто решает эти проблемы даже в случаях коллизий.

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

Одно время я был знаком с кодом обнаружения переоценки, написав его фрагмент.Но он был переписан для версии 8. Так что даже после того, как я увидел это неоптимальное поведение в отладчике, для меня это загадка.Все, что я могу сейчас сказать, это то, что я подал отчет об ошибке.

Как заметил Леонид Шифрин, символы с атрибутом HoldAllComplete неуязвимы для этой проблемы.Поэтому использование этого атрибута может быть полезным для этого типа кода.

Daniel Lichtblau Wolfram Research

Answer 2

Отказ от ответственности: ниже приводится предположение.Похоже, это связано с поиском UpValues.Похоже, что это было оптимизировано для глобальных переменных (так что система пропускает этот шаг, когда она может определить, что может это сделать), но не для сгенерированных Module локальных переменных.Чтобы проверить это, присвойте атрибут HoldAllComplete pair, и эффект исчезнет (с тех пор UpValues не проверяется на current):

SetAttributes[pair, HoldAllComplete];

In[17]:= ll = toLinkedList@RandomInteger[100, 10000];
Max[Table[Timing[whileLength[ll]], {1000}][[All, 1]]]

Out[18]= 0.047

HTH

Answer 3

Кажется, это связано с управлением памятью локальных символов модуля.

Я покажу временные ряды из некоторых прогонов. Каждый прогон, конечно, дает уникальный график, но я проверял «последовательность» между прогонами. Посмотрите:

whileLength[l2_pair] := 
  Module[{result = 0}, current = l2; 
   While[! emptyQ@current, current = current[[2]];
    ++result];
   result];  

дает следующие временные ряды:

При использовании только глобальных символов:

whileLength[l2_pair] := 
  Module[{}, result = 0; current = l2; 
   While[! emptyQ@current, current = current[[2]];
    ++result];
   result];

дает: