Subject: Re: Test
From: Anton Orlov (orlov@mccme.ru)
Date: Tue Dec 30 2003 - 01:02:10 MSK
Дробрый вечер!
On Mon, Dec 29, 2003 at 11:44:09 +0300, Mike Potanin wrote:
> On Sun, 28 Dec 2003, Sergei M. Abramov (home) wrote:
>
> > День добрый, всем!
> >
> > К статье про компиляцию синт. отождествления я написал примерчик (приложена
> > программа, исходник и EXE) -- функцию, которая проверяет, что ее аргумент
> > имеет вид e.Y e.Y e.Y:
> >
> > IsTriplet eX = {
> > eX : e.Y e.Y e.Y = True;
> > = False;
> > };
> >
> > В старом ДОС-рефале-плюс один шаг выполнения этой функции (при длине
> > аргумента 49152) занимает (на моей машине) 74.26 секунд.
>
> Странно. На Perl тоже самое отрабатывает мгновенно.
>
> perl -e '$_ = ("a"x49152); print "true\n" if(/^(.*)\1\1$/);'
>
> Вроде бы алгоритм сопоставления не может сильно отличаться.
Алгоритм _может_ сильно отличаться.
Сколько разных алгоритмов напридумывано для такой простой вещи,
как поиск подстроки в строке. А мы имеем дело с гораздо более
общим случаем.
Однако в данном случае Perl, похоже, ведёт себя также, как старые
реализации Рефалов: в цикле удлинняет значение (.*). Только этим
я могу объяснить, что при замене 49152 на 49151 время работы
увеличивается более, чем в 2 раза.
Да и работает он не мгновенно ;-). На данном примере следует
работать гораздо быстрее.
Антон.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD