Почему Cases [] настолько медленны здесь? Есть ли уловки, чтобы ускорить его?

При попытке вставить изображения я заметил, что Cases[] очень медленный.

Чтобы воспроизвести, сначала скопируйте большое изображение в буфер обмена (просто нажмите Print Screen), затем оцените следующее:

^{(я сделал это в Windows, не уверен, что код вставки одинаковый для других систем.)}

Обратите внимание, что извлечение данных с помощью Cases происходит крайне медленно по сравнению с использованием Part напрямую, хотя я явно указываю Cases, что мне нужно только одно совпадение.

Я выяснил (как показано выше), что Cases запускает распаковку по какой-либо причине, даже если поиск останавливается, прежде чем он достигнет упакованного массива внутри. Использование более мелкой спецификации уровня, чем Infinity, может избежать распаковки.

Вопрос: Использование Cases здесь проще и надежнее, чем Part (что, если подвыражение может появляться в разных позициях?) Есть ли способ сделать Cases быстро здесь, возможно, используя другой шаблон или различные варианты?

Ответы

Ответ 1

У меня нет доступа к Mathematica прямо сейчас, поэтому следующее непроверено. Я предполагаю, что Cases распаковывается здесь, потому что он выполняет поиск по глубине, и сначала видит упакованный массив. Если это правильно, вы можете использовать правила вместо (ReplaceAll, not Replace) и вызывать исключение при первом совпадении:

Module[{tag},
   Catch[
     nb /. r_RasterBox :> Block[{}, Throw[First[r], tag] /; True]; 
     $Failed, 
     tag]
]

Как я уже сказал, это всего лишь непроверенная догадка.

Редактировать 2: подход, основанный на защите частей выражения от шаблона-сопоставителя

Преамбула

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

Код

Вот модификация Cases, которая делает именно это:

Clear[casesShielded];
casesShielded[expr_,pt_,shieldPattern_,levspec_,n_,opts:OptionsPattern[]]:=
   Module[{dummy,inverseShieldingRules, shielded, i=0},
      inverseShieldingRules =
        If[#==={},#,[email protected]@#]&@
           Reap[shielded= expr/.(p:shieldPattern):>
             With[{eval = With[{ind = ++i},Sow[dummy[ind]:>p];dummy[ind]]},
                eval/;True];
           ][[2]];
      Cases[shielded,pt,levspec,n,opts]/.inverseShieldingRules];

Эта версия Cases имеет один дополнительный параметр shieldPattern (третий), который указывает, какие подвыражения должны быть экранированы из шаблона-сопоставителя.

Преимущества и применимость

Приведенный выше код довольно легкий (по сравнению с предложением edit1 ниже), и он позволяет полностью повторно использовать и использовать существующие функции Cases. Это будет работать в случаях, когда основной шаблон (или правило) нечувствителен к экранированию соответствующих частей, что является довольно распространенной ситуацией (и, в частности, охватывает шаблоны типа _h, в том числе и в данном случае). Это также может быть быстрее, чем применение myCases (описано ниже).

Случай под рукой

Здесь нам нужен этот вызов:

In[55]:=    
([email protected][nb,x_RasterBox:>[email protected],
    p_List/;Developer`PackedArrayQ[p],Infinity,1]);//Timing

Out[55]= {0.,Null}

и результат, конечно, такой же, как и раньше:

In[61]:= d2===d4
Out[61]= True

Изменить: альтернативная функция, подобная случаям

Мотивация и код

Мне потребовалось некоторое время, чтобы создать эту функцию, и я не уверен на 100%, что она всегда работает правильно, но вот версия Cases, которая, хотя и работает в глубине, анализирует выражение как целое до суб- -expressions:

ClearAll[myCases];
myCases[expr_, lhs_ :> rhs_, upToLevel_: 1, max : (_Integer | All) : All, 
    opts : OptionsPattern[]] :=
 Module[{tag, result, f, found = 0, aux},
   With[{
    mopts = FilterRules[{opts}, {Heads -> False}],
    frule =
       Apply[
         RuleDelayed,
         Hold[lhs, With[{eval =  aux}, Null /; True]] /.
            {aux :> Sow[rhs, tag] /; max === All, 
             aux :> (found++; Sow[rhs, tag])}
       ]
    },
    SetAttributes[f, HoldAllComplete];
    If[max =!= All,
       _f /; found >= max := Throw[Null, tag]
    ];
    f[x_, n_] /; n > upToLevel := Null;
    f[x_, n_] :=
      Replace[
       HoldComplete[x],
       {
          frule,
          ex : _[___] :> 
            With[{ev = 
              Replace[
                HoldComplete[ex],
                y_ :> With[{eval = f[y, n + 1]}, Null /; True],
                {2},
                Sequence @@ mopts
              ]}, 
              Null /; True
            ]
       },
       {1}
      ]
   ]; (* external With *)
   result = 
     If[# === {}, #, [email protected]#] &@
        Reap[Catch[f[expr, 0], tag], tag, #2 &][[2]];
   (* For proper garbage-collection of f *)
   ClearAll[f]; 
   result
 ]

Как это работает

Это не самая тривиальная часть кода, так что вот некоторые замечания. Эта версия Cases основана на той же идее, которую я предложил сначала, а именно: использовать семантику замены правил, чтобы сначала попытаться совместить шаблон с целым выражением, и только если это не удается, перейдите к подвыражениям. Я подчеркиваю, что это по-прежнему первое пересечение глубины, но отличается от стандартного (которое используется в большинстве функций перемещения по выражению, таких как Map, Scan, Cases и т.д.). Я использую Reap и Sow для сбора промежуточных результатов (совпадений). Самая сложная часть здесь заключается в том, чтобы предотвратить подвыражения от оценки, и мне пришлось обернуть подвыражения в HoldComplete. Следовательно, мне пришлось использовать (вложенную версию) технику Trott-Strzebonski (возможно, есть более простые способы, но я не мог их видеть), чтобы включить эвауацию rhsides правил внутри удерживаемых (под) выражений, и использовал Replace с надлежащей спецификацией уровня, учитывая дополнительные добавленные обертки HoldComplete. Я возвращаю Null в правила, так как основное действие - на Sow части, поэтому не имеет значения, что вводится в исходное выражение в конце. Некоторая дополнительная сложность была добавлена кодом для поддержки спецификации уровня (я поддерживаю только один целочисленный уровень, указывающий максимальный уровень, до которого можно искать, а не весь диапазон возможных значений lev.spec), максимальное количество найденных результатов и Heads. Код для frule служит для того, чтобы не вводить накладные расходы на подсчет найденных элементов в тех случаях, когда мы хотим найти их все. Я использую тот же тег Module -генерированный как тег для Sow, и как тег для исключений (который я использую, чтобы остановить процесс, когда найдено достаточное количество совпадений, как и в моем первоначальном предложении).

Тесты и тесты

Чтобы иметь нетривиальный тест этой функции, мы можем, например, найти все символы в DownValues of myCases и сравнить с Cases:

In[185]:= 
[email protected]@Flatten[
    Outer[
       myCases[DownValues[myCases],s_Symbol:>Hold[s],#1,Heads->#2]  ===
       Cases[DownValues[myCases],s_Symbol:>Hold[s],#1,Heads->#2]&,
       Range[0,20],
       {True,False}
    ]]

Out[185]= True

Функция myCases примерно в 20-30 раз медленнее, чем Cases, хотя:

In[186]:= 
Do[myCases[DownValues[myCases],s_Symbol:>Hold[s],20,Heads->True],{500}];//Timing
Out[186]= {3.188,Null}

In[187]:= Do[Cases[DownValues[myCases],s_Symbol:>Hold[s],20,Heads->True],{500}];//Timing
Out[187]= {0.125,Null}

Случай под рукой

Нетрудно проверить, что myCases решает исходную проблему распаковки:

In[188]:= AbsoluteTiming[[email protected][nb,r_RasterBox:>First[r],Infinity,1];]
Out[188]= {0.0009766,Null}

In[189]:= d3===d2
Out[189]= True

Можно надеяться, что myCases может быть в целом полезен для подобных ситуаций, хотя оценка эффективности использования вместо Cases является существенной и должна быть принята во внимание.