Считаю результаты
Вот часть некоторой грамматики: B ::= |AB. Фактически, это обычное регулярное повторение B ::= A*.
При любом параллельном разборе такой части грамматики мы получаем O((длина последовательности A)2) количество промежуточных вариантов разбора. Можно и куб получить, в общем, нехорошо получается.
В статье про параллельный разбор разумных грамматик предлагается переводить правила такого вида в вид B ::= AA|A|, дополнять правила для A специальными битами и правилами последовательного разбора для A с разными дополнениями (это раздел 5). Проблема с дополнением специальными битами в том, что я не могу доказать себе, что это преобразование справедливо для всех грамматик, и что оракул не будет бутылочным горлышком.
(В статье, кстати, есть табличка сложности алгоритмов и их параллельного ускорения, там всё, что имеет степенной вид O(n(1+x)) (x > 0) в шаге сборки, не представляет выгоды при параллельном выполнении)
Я подумал, что можно же разбирать, фактически, ограниченную грамматику, которая достаточно хорошо приближает бесконечность. Например, если мы считаем, что бесконечность хорошо приближается числом восемь, то мы можем разбирать последовательности до семи включительно:
B ::= (A4|)(A2|)(A|)|
A4 ::= A2 A2
A2 ::= A A
Вот результаты этого я и считаю.
Пока получается, что промежуточных результатов будет не более O((длины последовательности)*log(длины последовательности)).
Что, если я всё правильно понимаю, позволяет, таки, получить ускорение при параллельном разборке.
PS
Перефразируя Гейтса, 2256 достаточно для любых нужд. ;)
При любом параллельном разборе такой части грамматики мы получаем O((длина последовательности A)2) количество промежуточных вариантов разбора. Можно и куб получить, в общем, нехорошо получается.
В статье про параллельный разбор разумных грамматик предлагается переводить правила такого вида в вид B ::= AA|A|, дополнять правила для A специальными битами и правилами последовательного разбора для A с разными дополнениями (это раздел 5). Проблема с дополнением специальными битами в том, что я не могу доказать себе, что это преобразование справедливо для всех грамматик, и что оракул не будет бутылочным горлышком.
(В статье, кстати, есть табличка сложности алгоритмов и их параллельного ускорения, там всё, что имеет степенной вид O(n(1+x)) (x > 0) в шаге сборки, не представляет выгоды при параллельном выполнении)
Я подумал, что можно же разбирать, фактически, ограниченную грамматику, которая достаточно хорошо приближает бесконечность. Например, если мы считаем, что бесконечность хорошо приближается числом восемь, то мы можем разбирать последовательности до семи включительно:
B ::= (A4|)(A2|)(A|)|
A4 ::= A2 A2
A2 ::= A A
Вот результаты этого я и считаю.
Пока получается, что промежуточных результатов будет не более O((длины последовательности)*log(длины последовательности)).
Что, если я всё правильно понимаю, позволяет, таки, получить ускорение при параллельном разборке.
PS
Перефразируя Гейтса, 2256 достаточно для любых нужд. ;)