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

Недавно я спросил, почему 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 ²) во всех списках, упакована или распакована.

Ответ 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 потенциальных совпадений, и, похоже, не существует ранней помощи. Предположительно, потому что могут быть построены другие шаблоны, которые нуждаются в такой сложности. Проблема заключается в том, что вышеупомянутый шаблон заставляет matcher использовать очень общий алгоритм.

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

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

Ответ 2

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

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