Just to state the obvious, though, operations will be somewhat slower with the optimal space structure. Retrieval, for instance, requires more than simply a shift and a bit mask (although not too much more).
On Tue, Mar 30, 2010 at 6:25 AM, 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'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. > > Shrinking the array is not a problem - this comes 'for free' (in the sense > that it's required) in the optimal space data structure that you reference. > > Regarding the gap array suggestion, it is not clear to me how we will still > compute the correct arraylet/offset for an index in O(1) time if we have > arraylets of arbitrary size. Even worse, if we go with the optimal space > data structure we will not have the option of creating arraylets of > arbitrary size or with arbitrary gaps between elements. > > You are absolutely right about the n^(1/2) space overhead; I was not aware > of this research. I'll go ahead and implement the structure defined in > "Resizable arrays in optimal time and space" (once I find some time to do > so). > > Regards, > > Kevin > > > On Mon, Mar 29, 2010 at 2:23 AM, Martin Buchholz <marti...@google.com>wrote: > >> On Sun, Mar 28, 2010 at 04:55, Kevin L. Stern <kevin.l.st...@gmail.com> >> wrote: >> > I put together the following class, ChunkedArrayList, in response to >> > Martin's request (excerpted from an earlier conversation on this web >> board) >> > below. >> > >> > >> https://docs.google.com/leaf?id=0B6brz3MPBDdhMGNiNGIwMTQtMTgxMi00ODlmLTk4ZGYtOWY2NDE0M2E5M2Zl&sort=name&layout=list&num=50 >> > >> > Thoughts? >> >> This class is well on the way to what I was thinking of, >> but my bar for acceptance is a little higher. >> In particular, I don't want to add yet another class >> that is can replace some, but not all of existing >> list implementations. >> >> Most obviously, I don't want to lose the ability, >> introduced in ArrayDeque, of having O(1) insertion >> at the front and end of the collection. >> Perhaps you can do this by having one "arraylet" >> always be shared by both ends, which >> grow towards each other in circular fashion. >> >> I also think we should shrink the array when >> necessary, so that occupancy never drops >> below, say 50%. >> >> Perhaps we should also have amortized O(1) >> insertion in the middle by using a "gap array". >> Probably more important for byte/char collections >> like StringBuilder... >> >> I believe there are more complicated implementations >> that permit O(1) insertions at the ends, and only >> O(sqrt(N)) space overhead. >> >> .... >> >> E.g. Use your favorite search engine to do >> some research on: >> Resizable arrays in optimal time and space >> Succinct dynamic data structures >> >> Meta-comment: there is not enough transfer of >> academic research results into practice; I would think this >> is one of the responsibilities of the researchers. >> >> I presume you'd be willing to sign a >> contributor agreement to get your changes into >> the JDK someday. >> >> Martin >> >> > Regards, >> > >> > Kevin >> > >> > >> > On Tue, Mar 9, 2010 at 3:15 PM, Martin Buchholz <marti...@google.com> >> > wrote: >> > >> > It surely is not a good idea to use a single backing array >> > for huge arrays. As you point out, it's up to 32GB >> > for just one object. But the core JDK >> > doesn't offer a suitable alternative for users who need very >> > large collections. >> > >> > It would have been more in the spirit of Java to have a >> > collection class instead of ArrayList that was not fastest at >> > any particular operation, but had excellent asymptotic behaviour, >> > based on backing arrays containing backing arrays. >> > But: >> > - no such excellent class has been written yet >> > (or please point me to such a class) >> > - even if it were, such a best-of-breed-general-purpose >> > List implementation would probably need to be introduced as a >> > separate class, because of the performance expectations of >> > existing implementations. >> > >> > In the meantime, we have to maintain what we got, >> > and that includes living with arrays and classes that wrap them. >> > >> > Changing the spec is unlikely to succeed.. >> > >> > Martin >> > >> > >
