Соответствие шаблонов Mathematica плохо оптимизировано?

Question

Я недавно спросил, почему PatternTest вызывает множество ненужных оценок: PatternTest не оптимизирован? Леонид ответил, что это необходимо для того, что мне кажется довольно сомнительным методом. Я могу принять это, хотя я бы предпочел более эффективную альтернативу.

Теперь я понимаю, что, как мне кажется, Леонид говорил уже некоторое время, эта проблема намного глубже в Mathematica , и я обеспокоен. Я не могу понять, почему это не так или не может быть лучше оптимизировано.

Рассмотрим этот пример:

list = RandomReal[9, 20000];
Head /@ list; // Timing
MatchQ[list, {x__Integer, y__}] // Timing

{0., Null}

{1.014, False}

Проверка заголовков списка происходит практически мгновенно, но проверка шаблона занимает более секунды. Конечно, Mathematica может распознать, что, поскольку первый элемент списка не является целым числом, шаблон не может совпадать, и в отличие от случая с PatternTest я не могу видеть, как в шаблоне существует изменчивость. Чем это объясняется?

---

Кажется, есть некоторая путаница в отношении упакованных массивов, которые, насколько я могу судить, не имеют отношения к этому вопросу. Скорее, меня беспокоит сложность времени O (n ² ) во всех списках, упакованных или распакованных.

Answer 1

MatchQ распаковывает для этих видов испытаний.Причина в том, что особого случая для этого не было реализовано.В принципе, может содержать что-либо.

On["Packing"]
MatchQ[list, {x_Integer, y__}] // Timing

MatchQ[list, {x__Integer, y__}] // Timing

Улучшить это очень сложно - если вы нарушите механизм сопоставления с образцом, у вас возникнет серьезная проблема.

Редактировать1: Это правда, что распаковка не является причиной сложности O (n ^ 2).Это, однако, показывает, что для части MatchQ[list, {x__Integer, y__}] код переходит к другой части алгоритма (которая требует распаковки списков).Некоторые другие вещи, на которые следует обратить внимание: эта сложность возникает, только если оба шаблона равны __, если один из них равен _, алгоритм имеет лучшую сложность.

Затем алгоритм проходит через все n * n потенциальных совпаденийи, похоже, ранней помощи нет.Предположительно, потому что могут быть построены другие шаблоны, которые будут нуждаться в этой сложности. Проблема в том, что приведенный выше шаблон вынуждает сопоставителя к очень общему алгоритму.

Я тогда надеялся на MatchQ[list, {Shortest[x__Integer], __}] и друзей, но безрезультатно.

Итак, мои два цента: либо используйте другой шаблон (и включите On ["Packing"], чтобы увидеть, подходит ли он к общему совпадению), либо сделайте предварительную проверку DeveloperPackedArrayQ[expr] && Head[expr[[1]]]===Integer или какую-то другую.

Answer 2

@the author of the first answer. Насколько я знаю из реинжиниринга и чтения доступной информации, это может быть связано с различными способами проверки шаблонов. На самом деле, как говорится, для сопоставления с образцом используется специальный хеш-код. Этот хэш (в основном раунд FNV-1) позволяет очень легко проверять конкретные шаблоны, относящиеся к типу выражения (включая несколько операций xor). Алгоритм хеширования циклически переходит в выражение, и каждая его часть сортируется с выводом предыдущего. Для каждого выражения атома используются специальные значения xor - machineInts, machineReals, bigNums, Rationals и так далее. Следовательно, например, _Integer легко проверить, потому что хеш любого целого числа формируется со значением xor целого числа, поэтому все, что нам нужно сделать, это выполнить обратную операцию и посмотреть, совпадает ли она - т.е. получим ли мы какое-то конкретное значение или что-то вот так (извините, если я не совсем понимаю фактические детали реализации. Это WIP). Для общих или необычных шаблонов проверка может не использовать преимущества этого хэша и требовать чего-то другого.

@the OP Head[] просто воздействует на внутреннее выражение, принимая значение первого указателя выражения (выражения реализуются как массивы указателей). Делать это так же просто, как копировать и печатать строку - очень и очень быстро. В этом случае механизм сопоставления с образцом даже не вызывается.