Re: [EXT] Re: Question about data structures

[Thompson, David]

On Sun, Nov 22, 2020 at 10:43 PM Taylan Kammer <taylan.kammer@gmail.com> wrote:
>
> Python lists, JDK's ArrayList, and .NET ArrayList, among probably many
> other "list" or "array" data structures in popular languages nowadays
> use a relatively straightforward data structure that is backed by an
> actual array which can have empty slots (e.g. your Python list with 3
> elements might be backed by an array of size 10), and is reallocated
> whenever there's no space left.  This means that appending an element at
> the end is usually dirt cheap, until there's no space left, at which
> point the append operation is much heavier for one call, then the
> following calls are dirt cheap again, until it's full again...
>
> Inserting an element at the beginning or middle is also relatively
> expensive with those implementations, since all elements need to be
> shifted forward to make space for the new element.  (Although this might
> be done with an operation like C's memcpy which is still actually very
> fast.)
>
> It's called a "dynamic array" by Wikipedia:
>
>      https://en.wikipedia.org/wiki/Dynamic_array
>
> If you want to go on an adventure, you could implement a Scheme data
> structure called DVector that implements this strategy, using plain
> Scheme vectors for the backing array.

If anyone is interested in such a data structure, I have an
implementation available here:

https://git.dthompson.us/chickadee.git/tree/chickadee/array-list.scm

I typically use them as object pools to reduce allocation and thus GC
pressure in the context of video games.  The array-list-push! and
array-list-pop! procedures make it easy to use as a dynamically
expanding stack.

- Dave