Subject: Re: Re: Как следует компилировать рефальскую операцию отождествления
From: Andrey Slepuhin (pooh@msu.ru)
Date: Wed Dec 06 2000 - 11:05:03 MSK
Arkady Klimov wrote:
> Сергей Михайлович, привет,
> привет участникам дискуссии!
> Спасибо за инициативу и интересные материалы.
> Прошу прощения, что долго не включался, отвечать было недосуг, но я все
> читал и более-менее разбирался. Все очень интересно. Для Р+ и вообще
> отображение в массивное представление это то, что надо. Но в первом письме
> ты писал, что эти методы будут также интересны для реализаторов Р-5 и т.п.,
> то есть рефалов на списковом представлении. У меня есть в этом сомнения,
> попробуй их развеять. Ты справедливо замечаешь, что сложность операций может быть
> (и будет для списков) O(L). Но дальше ты писал, что алгоритм от этого не зависит.
> Согласен, алгоритм не зависит, но сложность его зависит и возможно радикально.
> Рассмотрим пример такого образца (из функции доступа к копилке):
>
> (e.name) (e.1 (e.name '=' e.value) e2)
>
> При существующей реализации его сложность - это объем символов из содержимого
> правого списка, которые надо просмотреть при поиске. Когда сравнение неудачное,
> это обычно 1-2 символа на одно имя. То есть время будет грубо пропорционально
> количеству имен. Если же перед сравнением мы будет сначала вычислять длину,
> тратя O(L), то время поиска резко увеличится в разы - пропорционально средней
> длине имени.
С моей точки зрения правильная списковая реализация для рефал-выражений
должна отслеживать их длину при конкатенациях и отщеплениях - это
не вносит никакого оверхеда. Также могут существуют другие полезные
инварианты, следить за которыми не мешало бы. Так, в новом рантайме
рефала+ реализован флаг, указывающий, что выражение является "flat",
т.е. не содержит скобочных термов.
Андрей(С)
-- A right thing should be simple (tm)
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD