Re: 5.2 work3 manual

[Tony Finch <dot@...>]

On Tue, 25 May 2010, Javier Guerra Giraldez wrote:

> On Sun, May 23, 2010 at 10:09 AM, Florian Weimer <fw@deneb.enyo.de> wrote:
> >> Your definition requires an O(n) search to evaluate #x, whereas Lua's
> >> definition allows an O(log n) search.
> >
> > Not really, you could use balanced binary trees or Judy trees, which
> > would bring you down to O(log n).  On the other hand, I'm sure that
> > the constants would be far worse than the current implementation.
>
> and a reverse linked list could keep it at O(1); but all these assume
> maintaining extra structure and keep it current on every assignment.

I don't see how you can get it to O(1) with something as simple as a list.
The hard part is dealing with splitting and joining contiguous sections of
non-nil array elements, where one assignment can change #t by a large
number. I think the best you can do (except for the constant factors!) is
to have an auxiliary balanced tree containing information about the
contiguous sections, in which case array updates would cost O(log n) where
n is the number of sections.

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
PORTLAND PLYMOUTH: NORTHEAST, BECOMING CYCLONIC IN PLYMOUTH, 3 OR 4,
INCREASING 5 AT TIMES. SLIGHT OR MODERATE. FOG PATCHES THEN THUNDERY SHOWERS.
MODERATE OR GOOD, OCCASIONALLY VERY POOR.