Re: 5.2 work3 manual
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: 5.2 work3 manual
- From: "Juris Kalnins" <juris@...>
- Date: 2010年5月25日 16:20:22 +0300
On 2010年5月25日 15:56:49 +0300, Tony Finch <dot@dotat.at> wrote:
On 2010年5月25日, Javier Guerra Giraldez wrote:
[..]
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.
well, with the way it's currently made, you can
currently, array part is an array of TValue, which is big enough to be
a double-linked list node.
So make it:
union ANode {
struct { ANode **prev; ANode *next; } l;
TValues d;
};
struct Table {
...;
ANode *array;
ANode *firstNil;
...
};
When resizing array part, link all nil nodes into firstNil list;
then #t is:
*firstNil ? #t == array - firstNil : sizearray;
And you have O(1) #t, plus amortized O(1) cost of list upkeep.
- References:
- Re: 5.2 work3 manual, Luiz Henrique de Figueiredo
- Re: 5.2 work3 manual, Gavin Wraith
- Re: 5.2 work3 manual, Gavin Wraith
- Re: 5.2 work3 manual, Duncan Cross
- Re: 5.2 work3 manual, Gavin Wraith
- Re: 5.2 work3 manual, Roberto Ierusalimschy
- Re: 5.2 work3 manual, Gavin Wraith
- Re: 5.2 work3 manual, Gavin Wraith
- Re: 5.2 work3 manual, Tony Finch
- Re: 5.2 work3 manual, Florian Weimer
- Re: 5.2 work3 manual, Javier Guerra Giraldez
- Re: 5.2 work3 manual, Tony Finch