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 <marti...@google.com>wrote: > On Tue, Mar 30, 2010 at 04:25, Kevin L. Stern <kevin.l.st...@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. >
