A List implementation backed by multiple small arrays rather than the traditional single large array.

[Kevin L. Stern]

I realize that 2 * (2^(k/2) - 1) only works for even numbered superblocks,
the odd numbered superblocks need an additional term added (the number of
data blocks in SB_[k-1]) to jive with my interpretation; anyhow, I also came
across an alternative characterization of superblock in the paper which
states that data blocks are grouped within a superblock when they are the
same size - to me, though, that implies that my example structure below
would be

SB_0: [1]
SB_1: [2][2][2]
SB_2: [4][4][4][4][4][4]

which seems to contradict my understanding of (1) below.  I must be reading
this upside down.

On Wed, Mar 31, 2010 at 6:36 PM, Kevin L. Stern <kevin.l.stern at gmail.com>wrote:

> What am I missing here?  In "Resizable arrays in optimal time and space"
> the authors define their data structure with the following property:
>
> (1)  "When superblock SB_k is fully allocated, it consists of
> 2^(floor(k/2)) data blocks, each of size 2^(ceil(k/2))."
>
> Since the superblock is zero-based indexed this implies the following
> structure:
>
> SB_0: [1]
> SB_1: [2]
> SB_2: [2][2]
> SB_3: [4][4]
> SB_4: [4][4][4][4]
> [...]
>
> Let's have a look at Algorithm 3, Locate(i), with i = 3:
>
> r = 100 (the binary expansion of i + 1)
> k = |r| - 1 = 2
> p = 2^k - 1 = 3
>
> What concerns me is their statement that p represents "the number of data
> blocks in superblocks prior to SB_k."  There are only two data blocks in
> superblocks prior to SB_2, not three.  Given (1) above, unless I'm
> misinterpreting it, the number of data blocks in superblocks prior to SB_k
> should be:
>
> 2 * Sum[i=0->k/2-1] 2^i = 2 * (2^(k/2) - 1)
>
> This, of course, seems to work out much better in my example above, giving
> the correct answer to my interpretation of their data structure, but I have
> a hard time believing that this is their mistake rather than my
> misinterpretation.
>
> Thoughts?
>
> Kevin
>
>
> On Tue, Mar 30, 2010 at 5:20 PM, Martin Buchholz <martinrb at google.com>wrote:
>
>> On Tue, Mar 30, 2010 at 04:25, Kevin L. Stern <kevin.l.stern at gmail.com>
>> wrote:
>> > Hi Martin,
>> >
>> > Thanks much for your feedback.  The first approach that comes to mind to
>> > implement O(1) time front as well as rear insertion is to create a
>> cyclic
>> > list structure with a front/rear pointer - to insert at the front
>> requires
>> > decrementing the front pointer (modulo the size) and to insert at the
>> rear
>> > requires incrementing the rear pointer (modulo the size).  We need to
>> resize
>> > when the two pointers bump into each other.  Could you explain more
>> about
>> > your suggestion of introducing an arraylet that is shared by the front
>> and
>> > the rear?
>>
>> It was a half-baked idea - I don't know if there's a way to turn it into
>> something useful.  I was thinking of the ArrayDeque implementation,
>> where all the elements live in a single array.
>>
>> >  It's not clear to me how that would help and/or be a better
>> > approach than the cyclic list.  Anyhow, the paper that you reference,
>> > "Resizable arrays in optimal time and space", gives a deque so if we
>> take
>> > that approach then the deque is specified.
>>
>> Technically, ArrayList also supports the Deque operations -
>> just not efficiently.
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100331/8f364089/attachment.html>