Sean O'Rourke wrote: > On Tue, 24 Sep 2002, Leopold Toetsch wrote: > >>Sean O'Rourke (via RT) wrote:
> The real-world version would increase the array's allocation by some fixed > multiple, e.g. double its size, which would still improve things from O(n) > to O(log n) reallocations. I suspect that this would be almost as fast. Of course. > If we expect these (especially shift) to be as frequent as push/pop, and > we want fast indexing as well, then maybe something like the SGI STL > implementation of a dequeue (dequeueue?) would be best: keep an array of > (pointers to) fixed-size chunks (rather than intlist's linked-list). Exactly this is, what my recent patch actually did: list->chunk_list holds pointers to chunks, an index lookup is one "div" more expensive then in array. > This would also allow gaps in the middle to remain unallocated, and could > speed up some splices. Yep. With some additional overhead we could also have sparse arrays and cheap splice. > It's an improvement over the current implementation, but I don't think > it's the best solution for perlarray's requirements: > > 1 - front insertion/removal > 2 - back insertion/removal > 3 - indexing > 4 - less-frequent insertion/removal in the middle (splice) > > The current approach is necessarily bad for 1, good for 3, and > unnecessarily bad for 2. IntList is good for 1 and 2, but bad for 3. No indexing is solved. Please look at intlist_get / find_chunk. > Both are not-so-hot for 4, but I don't think a lot of people use splice. Also for splice the chunk based solution is much better. > /s leo
