Hi Kevin,<div><br></div><div>It implements List, as well as Deque. It is indeed based on ArrayDeque, with the added operations to implement list. It does so reasonably efficiently, moving the fewest elements possible on each operation, that is zero for the queue operations, at most n/2 for the rest and all of them for a backing array resize.<div>

<br></div><div>The idea is to get a replacement for arraylist that performs like arraydeque on remove(0). As a side effect, we should be able to get better performance on other operations by requiring fewer elements to be moved.<br>

<div><br></div><div>Thanks,</div><div>Joe<br><br><div class="gmail_quote">2010/4/14 Kevin L. Stern <span dir="ltr"><<a href="mailto:kevin.l.stern@gmail.com">kevin.l.stern@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Hi Joe,<br><br>I was referring to the ChunkedArrayList when I stated that add does not amortize to constant time when the data structure employs the circular list trick to achieve deque behavior; ChunkedArrayList potentially resizes every n^(1/2) operations.<br>


<br>Regarding your CircularArrayList, does it differ from Java's ArrayDeque?  I took only a cursory look at it, so please understand if I have missed your reason for creating CircularArrayList altogether.<br><br>Regards,<br>

<font color="#888888">
<br>Kevin</font><div><div></div><div class="h5"><br><br><div class="gmail_quote">On Tue, Apr 13, 2010 at 6:52 AM, Joe Kearney <span dir="ltr"><<a href="mailto:joe.j.kearney@googlemail.com" target="_blank">joe.j.kearney@googlemail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">
<div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><div>Hi Kevin, Martin,</div><div><br></div><div>To add another discussion point, I've been writing a draft/proof-of-concept of retrofitting the List interface onto ArrayDeque. This works over the raw array, it doesn't use the fancier structures being discussed elsewhere on this list that deal with splitting huge arrays into arraylets, or that provide for O(1) insert in the middle.</div>




<div><br></div><div><a href="http://code.google.com/p/libjoe/source/browse/trunk/src/joe/collect/CircularArrayList.java" style="color:rgb(64, 100, 128)" target="_blank">http://code.google.com/p/libjoe/source/browse/trunk/src/joe/collect/CircularArrayList.java</a></div>




<div><br></div><div>I'd be interested if you have any comments in the context of this discussion. The code is not entirely ready yet, a couple of tests fail (6/789) because of a corner case I haven't nailed yet, but the idea is there at least. I'd like to add array shrinking later, when the size dips below capacity*0.4 perhaps, to avoid flickering up and down around...</div>




<div><br></div><div>Tests show performance to be close to ArrayList for the O(1) operations. Timings for indexed reads and writes showed no discernible difference between implementations last time I ran the tests. I don't understand at the moment why the iterator add at index size/3, size/2 perform 30% slower than ArrayList on smaller lists, nor the dodgy numbers for ArrayList.insert(5), I'll look at this soon.  Those operations that become O(1) in a circular implementation (that are implemented and tested here) are faster than in ArrayList. Insert/remove in the middle are somewhat faster than ArrayList because we only have to copy at most half of the elements, except when resizing the array.</div>




<div><br></div><div>Kevin, I don't fully understand your point about not amortizing to O(1). Certainly that's true for insert not at head or tail. Otherwise this implementation only moves array elements to the front on an array resize operation which happens every O(ln n) operations at most, if we do lots of adds, maybe a little more if we add array shrinking too.  This is the same as ArrayList. Are you just referring to the add-in-the-middle case?</div>




<div><br></div><div>Some performance results below, code for these is in the repository above too. This was the second run, after a warmup.</div><div><br></div><div>Thanks,</div><div>Joe</div><div><br></div><div><div><font face="'courier new', monospace"><span style="font-size:x-small">------------------------------------------------ CircularArrayList ------------------------------------------------</span></font></div>




<div><font face="'courier new', monospace"><span style="font-size:x-small">  size         add         get         set   iterAdd/3   iterAdd/2   insert(5)   removeRnd   removeMid   remove(0)</span></font></div>
<div>
<font face="'courier new', monospace"><span style="font-size:x-small">    10          20          67          70         125         102          90         240         191         138</span></font></div><div>
<font face="'courier new', monospace"><span style="font-size:x-small">   100          19          67          70         166         138          94         230         194         118</span></font></div>
<div><font face="'courier new', monospace"><span style="font-size:x-small">  1000          28          64          67         681         538          91         324         382         119</span></font></div>
<div>
<font face="'courier new', monospace"><span style="font-size:x-small"> 10000          30          65          67        5884        4425          94        1296        2330         124</span></font></div><div>
<font face="'courier new', monospace"><span style="font-size:x-small">---------------------------------------------------- ArrayList ----------------------------------------------------</span></font></div>
<div><font face="'courier new', monospace"><span style="font-size:x-small">  size         add         get         set   iterAdd/3   iterAdd/2   insert(5)   removeRnd   removeMid   remove(0)</span></font></div>
<div>
<font face="'courier new', monospace"><span style="font-size:x-small">    10          23          68          70         100          69       32913         162         130         105</span></font></div><div>
<font face="'courier new', monospace"><span style="font-size:x-small">   100          20          67          70         129         104       21944         169         134         135</span></font></div>
<div><font face="'courier new', monospace"><span style="font-size:x-small">  1000          29          63          67         651         506        9602         364         333         526</span></font></div>
<div>
<font face="'courier new', monospace"><span style="font-size:x-small"> 10000          30          63          66        5878        4414        9947        2312        2280        4437</span></font></div></div>


</span><br></div><div class="gmail_quote">2010/4/13 Kevin L. Stern <span dir="ltr"><<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>></span><div><div></div><div><br><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">




Hi Martin,<br><br>I had intended to address your request for absolute O(1) operations in the previous email.  The approach to achieving this suggested in [Brodnik99resizablearrays] is tantamount to making ArrayList operations absolute O(1) by keeping around an array of size (3/2)*n and filling it with a constant number of entries from the main array each time add is called.  Although this distributes the work done during a resize across the n operations required to enter a resize-required state, it is at the expense of additional memory usage and slower add operations.  My thought is that this would be a fine approach for a real-time application that requires hard guarantees on performance but would be a liability in so many Java applications that do not require these hard guarantees.  I look forward to hearing your thoughts on the matter, though.<br>




<font color="#888888">
<br>Kevin</font><div><div></div><div><br><br><div class="gmail_quote">On Tue, Apr 13, 2010 at 6:18 AM, Kevin L. Stern <span dir="ltr"><<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>></span> wrote:<br>




<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">
Hi Martin,<br><br>It's interesting to note that the old circular list trick will not suffice to turn this data structure into a deque since we might be copying all n elements back to the front = 0 position every n^(1/2) operations (add wouldn't amortize to O(1)).  We could use the old two stacks trick (push elements onto one stack, flip (the bottom) half (of) the elements to the 'other' stack when the 'other' stack becomes empty), mentioned in [Brodnik99resizablearrays], but I find this to be a bit CS 101.  In [Brodnik99resizablearrays] the authors suggest a method for making all blocks roughly the same size, allowing us to expand/shrink capacity at the beginning or the end; this is the approach that I will take to create a deque.<br>






<br>The FAQ for the Sun Contributor Agreement Q3 (<a href="http://www.sun.com/software/opensource/contributor_agreement.jsp#sa_3" target="_blank">http://www.sun.com/software/opensource/contributor_agreement.jsp#sa_3</a>) indicates that one should check with the project to determine where the SCA should be sent.  Do you know where I would find this information?<br>






<br>Kevin<br><br>@MISC{Brodnik99resizablearrays,<br>    author = {Andrej Brodnik and 
Svante Carlsson and Erik D. Demaine and J. Ian Munro and Robert 
Sedgewick},<br>    title = {Resizable Arrays in Optimal Time and Space},<br>    year
 = {1999}<div><div></div><div><br>}<br><br><div class="gmail_quote">On Sun, Apr 11, 2010 at 4:17 PM, Martin Buchholz <span dir="ltr"><<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>></span> wrote:<br>





<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">
Hi Kevin,<br>
<br>
Thanks for your continuing work on this.<br>
<br>
I like the test results, and agree with your analysis.<br>
I'm especially happy that you're beating<br>
ArrayList at some operations.<br>
<br>
I'd like to see O(1) addition at the beginning,<br>
implement both List and Deque (I regret<br>
our not having done this with ArrayDeque).<br>
<br>
An additional property that would be nice to<br>
have (but don't try too hard)<br>
is to provide some kind of real-time<br>
guarantees on the cost of an individual operation,<br>
not just amortized time.  E.g. ArrayList.add<br>
is worst-case O(n), making it unsuitable for use<br>
in some real-time applications.<br>
<br>
I will help get your changes into the obvious<br>
software distributions.  I assume you're happy<br>
with having this class included in any of<br>
Doug Lea's jsr166, guava-libraries, or the JDK itself.<br>
You should sign a Sun contributor agreement,<br>
or whatever the Oracle equivalent is,<br>
if you have not done so yet.<br>
<br>
Doug Lea likes public domain,<br>
guava-libraries likes the Apache license.<br>
<br>
We should get various people a chance to give<br>
a thumbs up on the design of this class -<br>
Doug Lea, Josh Bloch.<br>
<font color="#888888"><br>
Martin<br>
</font><div><div></div><div><br>
On Sun, Apr 11, 2010 at 09:32, Kevin L. Stern <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>> wrote:<br>
> Hello Martin,<br>
><br>
> I spent some time this weekend trying to bring out bugs in the<br>
> implementation; I believe the latest version to be in decent shape.  I have<br>
> also gathered some data on the performance of ChunkedArrayList over<br>
> ArrayList using the latest 1.6 JDK, which I've included below (note that the<br>
> numbers represent the time spent performing the specified operation with<br>
> ChunkedArrayList over the time spent with ArrayList, so 1.00 indicates<br>
> equivalent performance, < 1.00 indicates that ChunkedArrayList is less<br>
> costly and > 1.00 indicates that ArrayList is less costly).  I've noticed<br>
> relatively significant variability in a few of the numbers when I switch<br>
> hardware; though, these data do seem to represent rough performance<br>
> expectations.  For my test I generated x elements and then timed the process<br>
> of adding them to ArrayList/ChunkedArrayList, then I performed a get<br>
> operation on each for indices 0 through x-1 and finally I used the iterator<br>
> mechanism to retrieve the first through xth element (of course, I performed<br>
> each of these operations multiple times throwing away the timing for the<br>
> first few iterations to warm up the JVM).<br>
><br>
> Regarding the question of whether or not this belongs in java.util, I would<br>
> suggest that if it is desirable from a GC point of view to eliminate the<br>
> large backing array from ArrayList then your suggestion of achieving this by<br>
> way of a data structure that is both time and space optimal is a<br>
> particularly elegant solution as it not only guarantees that no backing<br>
> array will be larger than sqrt(n) elements but it also provides dynamic<br>
> shrinking behavior, has less maximum memory overhead than ArrayList, and<br>
> copies (asymptotically) fewer elements during a resize than ArrayList.  Of<br>
> course, this data structure does not do everything better than ArrayList; in<br>
> particular, indexed access is more costly, due to the required decomposition<br>
> of the index into backing array index and offset and the additional memory<br>
> indirection, and insertion-at-an-index is more costly, due to the multiple<br>
> array copies necessary to complete the shift.  That being said, I think that<br>
> the additional cost of indexed access is partially mitigated by the<br>
> availability of iterator and listIterator, whose implementations do not use<br>
> the index decomposition procedure, and the additional cost of<br>
> insertion-at-an-index is partially mitigated by the fact that<br>
> insertion-at-an-index is already an undesirable operation on ArrayList due<br>
> to its linear time complexity.<br>
><br>
> Kevin<br>
><br>
> 1000000 elements:<br>
> Client JVM:<br>
> Add to ChunkedArrayList over ArrayList: 1.30<br>
> Indexed access ChunkedArrayList over ArrayList: 1.80<br>
> Iterator ChunkedArrayList over ArrayList: 0.52<br>
><br>
> Server JVM:<br>
> Add to ChunkedArrayList over ArrayList: 0.81<br>
> Indexed access ChunkedArrayList over ArrayList: 2.87<br>
> Iterator ChunkedArrayList over ArrayList: 1.31<br>
><br>
> 100000 elements:<br>
> Client JVM:<br>
> Add to ChunkedArrayList over ArrayList: 0.96<br>
> Indexed access ChunkedArrayList over ArrayList: 1.86<br>
> Iterator ChunkedArrayList over ArrayList: 0.48<br>
><br>
> Server JVM:<br>
> Add to ChunkedArrayList over ArrayList: 0.96<br>
> Indexed access ChunkedArrayList over ArrayList: 1.89<br>
> Iterator ChunkedArrayList over ArrayList: 2.68<br>
><br>
> 10000 elements:<br>
> Client JVM:<br>
> Add to ChunkedArrayList over ArrayList: 1.04<br>
> Indexed access ChunkedArrayList over ArrayList: 2.33<br>
> Iterator ChunkedArrayList over ArrayList: 0.53<br>
><br>
> Server JVM:<br>
> Add to ChunkedArrayList over ArrayList: 0.97<br>
> Indexed access ChunkedArrayList over ArrayList: 2.45<br>
> Iterator ChunkedArrayList over ArrayList: 2.52<br>
><br>
> 1000 elements:<br>
> Client JVM:<br>
> Add to ChunkedArrayList over ArrayList: 0.99<br>
> Indexed access ChunkedArrayList over ArrayList: 2.27<br>
> Iterator ChunkedArrayList over ArrayList: 0.54<br>
><br>
> Server JVM:<br>
> Add to ChunkedArrayList over ArrayList: 0.84<br>
> Indexed access ChunkedArrayList over ArrayList: 1.23<br>
> Iterator ChunkedArrayList over ArrayList: 1.11<br>
><br>
><br>
> On Fri, Apr 9, 2010 at 7:42 PM, Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>> wrote:<br>
>><br>
>> My feeling on whether to support O(1) at both ends<br>
>> is that any flavor of this that ends up in the JDK eventually<br>
>> should really do this.  My idea is that we can<br>
>> wholeheartedly recommend this collection class<br>
>> for overall good behavior without any of the surprising<br>
>> performance traps of existing collection classes.<br>
>><br>
>> But for the preliminary version, it makes sense to<br>
>> support only O(1) at one end, if it simplifies the<br>
>> implementation.  Random access will of course<br>
>> be worse than ArrayList, but by how much?<br>
>> We can do some benchmarking and look for<br>
>> micro-optimizations now.<br>
>><br>
>> Kevin, what is you own personal feeling?<br>
>> Is the algorithm correct, and efficient enough?<br>
>> Do you think your new collection belongs in java.util?<br>
>><br>
>> Martin<br>
>><br>
>> On Sun, Apr 4, 2010 at 04:12, Kevin L. Stern <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> wrote:<br>
>> > The data structure is available at the second link that I originally<br>
>> > provided (once again, it is<br>
>> ><br>
>> > <a href="https://docs.google.com/Doc?docid=0Aabrz3MPBDdhZGdrbnEzejdfM2M3am5wM2Mz&hl=en" target="_blank">https://docs.google.com/Doc?docid=0Aabrz3MPBDdhZGdrbnEzejdfM2M3am5wM2Mz&hl=en</a>).<br>
>> > This does not have O(1) time insertion at the front as yet as it was<br>
>> > unclear<br>
>> > to me whether or not it was agreed upon:<br>
>> > _________________<br>
>> > From: Osvaldo Doederlein <<a href="mailto:opinali@gmail.com" target="_blank">opinali@gmail.com</a>><br>
>> > Date: Mon, Mar 29, 2010 at 10:08 AM<br>
>> > Subject: Re: A List implementation backed by multiple small arrays<br>
>> > rather<br>
>> > than the traditional single large array.<br>
>> > To: Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
>> > Cc: "Kevin L. Stern" <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>>,<br>
>> > <a href="mailto:core-libs-dev@openjdk.java.net" target="_blank">core-libs-dev@openjdk.java.net</a><br>
>> ><br>
>> > Initially, it would be good enough to replace only java.util.ArrayList<br>
>> > with<br>
>> > minimal overhead. ArrayList does not support efficient add-at-front or<br>
>> > other<br>
>> > enhancements of ArrayDeque; but ArrayList is still a much more important<br>
>> > and<br>
>> > popular collection, it's the primary "straight replacement for primitive<br>
>> > arrrays" and I guess it should continue with that role.<br>
>> > _________________<br>
>> ><br>
>> > As a disclaimer, I'm still tinkering with this so I'll be updating the<br>
>> > document at the provided link as I find improvements.<br>
>> ><br>
>> > Thoughts?<br>
>> ><br>
>> > Thanks,<br>
>> ><br>
>> > Kevin<br>
>> ><br>
>> > On Thu, Apr 1, 2010 at 10:28 PM, Martin Buchholz <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
>> > wrote:<br>
>> >><br>
>> >> Hi Kevin,<br>
>> >><br>
>> >> You're probably the only one on this list who has<br>
>> >> seriously read the paper.  It is not surprising that<br>
>> >> taking a research paper into production would<br>
>> >> discover bugs - the research never had to undergo<br>
>> >> rigorous testing.  (I like the Java culture of<br>
>> >> combining spec + implementation + test suite)<br>
>> >><br>
>> >> I suggest you ask the authors directly about the bug.<br>
>> >> They would probably also be interested to hear<br>
>> >> about your implementation.<br>
>> >><br>
>> >> Are you aware of Integer.numberOfLeadingZeros?<br>
>> >><br>
>> >><br>
>> >> <a href="http://download.java.net/jdk7/docs/api/java/lang/Integer.html#numberOfLeadingZeros%28int%29" target="_blank">http://download.java.net/jdk7/docs/api/java/lang/Integer.html#numberOfLeadingZeros(int)</a><br>







>> >><br>
>> >> Martin<br>
>> >><br>
>> >> On Wed, Mar 31, 2010 at 19:34, Kevin L. Stern <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> >> wrote:<br>
>> >> > I'm almost convinced now that the paper is incorrect.  The code below<br>
>> >> > gives<br>
>> >> > me the appropriate index into the index array and the offset into the<br>
>> >> > data<br>
>> >> > block.  That being said, remember when I mentioned that this will<br>
>> >> > include a<br>
>> >> > bit more work to access an element than a simple bit shift and a bit<br>
>> >> > mask?<br>
>> >> > Well this is more than a bit more - we'll be doing this each time an<br>
>> >> > index<br>
>> >> > is requested.  I'll spend some time trying to twiddle the bits to see<br>
>> >> > if<br>
>> >> > I<br>
>> >> > can eliminate/combine some of the operations.<br>
>> >> ><br>
>> >> >         for (int r = 1; r < 33; r++) {<br>
>> >> >             int k = lg(r);<br>
>> >> >             int floorKO2 = k >> 1;<br>
>> >> >             int powFloorKO2 = (1 << floorKO2);<br>
>> >> >             int p = ((1 << floorKO2) - 1) << 1;<br>
>> >> >             int ceilKO2;<br>
>> >> >             if ((k & 1) == 1) {<br>
>> >> >                 ceilKO2 = floorKO2 + 1;<br>
>> >> >                 p += powFloorKO2;<br>
>> >> >             } else {<br>
>> >> >                 ceilKO2 = floorKO2;<br>
>> >> >             }<br>
>> >> >             int e = r & ((1 << ceilKO2) - 1);<br>
>> >> >             int b = (r >> ceilKO2) & (powFloorKO2 - 1);<br>
>> >> ><br>
>> >> >             System.out.println((r - 1) + " " + (p + b) + " " + e);<br>
>> >> >         }<br>
>> >> ><br>
>> >> > Kevin<br>
>> >> ><br>
>> >> > On Wed, Mar 31, 2010 at 7:08 PM, Kevin L. Stern<br>
>> >> > <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> >> > wrote:<br>
>> >> >><br>
>> >> >> I realize that 2 * (2^(k/2) - 1) only works for even numbered<br>
>> >> >> superblocks,<br>
>> >> >> the odd numbered superblocks need an additional term added (the<br>
>> >> >> number<br>
>> >> >> of<br>
>> >> >> data blocks in SB_[k-1]) to jive with my interpretation; anyhow, I<br>
>> >> >> also<br>
>> >> >> came<br>
>> >> >> across an alternative characterization of superblock in the paper<br>
>> >> >> which<br>
>> >> >> states that data blocks are grouped within a superblock when they<br>
>> >> >> are<br>
>> >> >> the<br>
>> >> >> same size - to me, though, that implies that my example structure<br>
>> >> >> below<br>
>> >> >> would be<br>
>> >> >><br>
>> >> >> SB_0: [1]<br>
>> >> >> SB_1: [2][2][2]<br>
>> >> >> SB_2: [4][4][4][4][4][4]<br>
>> >> >><br>
>> >> >> which seems to contradict my understanding of (1) below.  I must be<br>
>> >> >> reading this upside down.<br>
>> >> >><br>
>> >> >> On Wed, Mar 31, 2010 at 6:36 PM, Kevin L. Stern<br>
>> >> >> <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> >> >> wrote:<br>
>> >> >>><br>
>> >> >>> What am I missing here?  In "Resizable arrays in optimal time and<br>
>> >> >>> space"<br>
>> >> >>> the authors define their data structure with the following<br>
>> >> >>> property:<br>
>> >> >>><br>
>> >> >>> (1)  "When superblock SB_k is fully allocated, it consists of<br>
>> >> >>> 2^(floor(k/2)) data blocks, each of size 2^(ceil(k/2))."<br>
>> >> >>><br>
>> >> >>> Since the superblock is zero-based indexed this implies the<br>
>> >> >>> following<br>
>> >> >>> structure:<br>
>> >> >>><br>
>> >> >>> SB_0: [1]<br>
>> >> >>> SB_1: [2]<br>
>> >> >>> SB_2: [2][2]<br>
>> >> >>> SB_3: [4][4]<br>
>> >> >>> SB_4: [4][4][4][4]<br>
>> >> >>> [...]<br>
>> >> >>><br>
>> >> >>> Let's have a look at Algorithm 3, Locate(i), with i = 3:<br>
>> >> >>><br>
>> >> >>> r = 100 (the binary expansion of i + 1)<br>
>> >> >>> k = |r| - 1 = 2<br>
>> >> >>> p = 2^k - 1 = 3<br>
>> >> >>><br>
>> >> >>> What concerns me is their statement that p represents "the number<br>
>> >> >>> of<br>
>> >> >>> data<br>
>> >> >>> blocks in superblocks prior to SB_k."  There are only two data<br>
>> >> >>> blocks<br>
>> >> >>> in<br>
>> >> >>> superblocks prior to SB_2, not three.  Given (1) above, unless I'm<br>
>> >> >>> misinterpreting it, the number of data blocks in superblocks prior<br>
>> >> >>> to<br>
>> >> >>> SB_k<br>
>> >> >>> should be:<br>
>> >> >>><br>
>> >> >>> 2 * Sum[i=0->k/2-1] 2^i = 2 * (2^(k/2) - 1)<br>
>> >> >>><br>
>> >> >>> This, of course, seems to work out much better in my example above,<br>
>> >> >>> giving the correct answer to my interpretation of their data<br>
>> >> >>> structure, but<br>
>> >> >>> I have a hard time believing that this is their mistake rather than<br>
>> >> >>> my<br>
>> >> >>> misinterpretation.<br>
>> >> >>><br>
>> >> >>> Thoughts?<br>
>> >> >>><br>
>> >> >>> Kevin<br>
>> >> >>><br>
>> >> >>> On Tue, Mar 30, 2010 at 5:20 PM, Martin Buchholz<br>
>> >> >>> <<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>><br>
>> >> >>> wrote:<br>
>> >> >>>><br>
>> >> >>>> On Tue, Mar 30, 2010 at 04:25, Kevin L. Stern<br>
>> >> >>>> <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>><br>
>> >> >>>> wrote:<br>
>> >> >>>> > Hi Martin,<br>
>> >> >>>> ><br>
>> >> >>>> > Thanks much for your feedback.  The first approach that comes to<br>
>> >> >>>> > mind<br>
>> >> >>>> > to<br>
>> >> >>>> > implement O(1) time front as well as rear insertion is to create<br>
>> >> >>>> > a<br>
>> >> >>>> > cyclic<br>
>> >> >>>> > list structure with a front/rear pointer - to insert at the<br>
>> >> >>>> > front<br>
>> >> >>>> > requires<br>
>> >> >>>> > decrementing the front pointer (modulo the size) and to insert<br>
>> >> >>>> > at<br>
>> >> >>>> > the<br>
>> >> >>>> > rear<br>
>> >> >>>> > requires incrementing the rear pointer (modulo the size).  We<br>
>> >> >>>> > need<br>
>> >> >>>> > to<br>
>> >> >>>> > resize<br>
>> >> >>>> > when the two pointers bump into each other.  Could you explain<br>
>> >> >>>> > more<br>
>> >> >>>> > about<br>
>> >> >>>> > your suggestion of introducing an arraylet that is shared by the<br>
>> >> >>>> > front<br>
>> >> >>>> > and<br>
>> >> >>>> > the rear?<br>
>> >> >>>><br>
>> >> >>>> It was a half-baked idea - I don't know if there's a way to turn<br>
>> >> >>>> it<br>
>> >> >>>> into<br>
>> >> >>>> something useful.  I was thinking of the ArrayDeque<br>
>> >> >>>> implementation,<br>
>> >> >>>> where all the elements live in a single array.<br>
>> >> >>>><br>
>> >> >>>> >  It's not clear to me how that would help and/or be a better<br>
>> >> >>>> > approach than the cyclic list.  Anyhow, the paper that you<br>
>> >> >>>> > reference,<br>
>> >> >>>> > "Resizable arrays in optimal time and space", gives a deque so<br>
>> >> >>>> > if<br>
>> >> >>>> > we<br>
>> >> >>>> > take<br>
>> >> >>>> > that approach then the deque is specified.<br>
>> >> >>>><br>
>> >> >>>> Technically, ArrayList also supports the Deque operations -<br>
>> >> >>>> just not efficiently.<br>
>> >> >>><br>
>> >> >><br>
>> >> ><br>
>> >> ><br>
>> ><br>
>> ><br>
><br>
><br>
</div></div></blockquote></div><br>
</div></div></blockquote></div><br>
</div></div></blockquote></div></div></div><br>
</blockquote></div><br>
</div></div></blockquote></div><br></div></div></div>