A List implementation backed by multiple small arrays rather than the traditional single large array.
Kevin L. Stern
kevin.l.stern at gmail.com
Thu Apr 1 00:08:12 UTC 2010
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
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
> SB_0: 
> SB_1: 
> SB_2: 
> SB_3: 
> SB_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
> 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>
>> > 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
>> > list structure with a front/rear pointer - to insert at the front
>> > decrementing the front pointer (modulo the size) and to insert at the
>> > requires incrementing the rear pointer (modulo the size). We need to
>> > when the two pointers bump into each other. Could you explain more
>> > your suggestion of introducing an arraylet that is shared by the front
>> > 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
>> > that approach then the deque is specified.
>> Technically, ArrayList also supports the Deque operations -
>> just not efficiently.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the core-libs-dev