dapper
Member
Hi all- I'm having a harder time finding information on the time complexity and implementation of the built-in data structures than I thought, and I was hoping somebody could point me to an authoritative reference.
My primary concern at the moment is that if, say, the built-in ds_list implementation is a linked list, and I want to iterate over that linked list, I don't see a trivial (and fast) way of doing that. Absent some interesting implementation, iteration over the entire list should be very slow for large lists (O(n^2)).
I suppose I can get around this by, say, removing each entry from the list as I am done with it. and perhaps proactively recreating the list... but I think that's something of a pain! Is there an easier way of iterating over the entire list in O(n) time?
Thanks!
Update
Here's a TL; DR, of what we know.
Edit 2: I've edited the title because I think broadening the scope in this topic would be useful. I'm really curious about every implementation, not just lists.
Edit 3: Re-reading this, it's obvious that I had a very strong (albeit erroneous) assumption that the ds_list implementation was a linked list- so much so that I took it for granted. I hope this edit provides that missing context.
My primary concern at the moment is that if, say, the built-in ds_list implementation is a linked list, and I want to iterate over that linked list, I don't see a trivial (and fast) way of doing that. Absent some interesting implementation, iteration over the entire list should be very slow for large lists (O(n^2)).
I suppose I can get around this by, say, removing each entry from the list as I am done with it. and perhaps proactively recreating the list... but I think that's something of a pain! Is there an easier way of iterating over the entire list in O(n) time?
Thanks!
Update
Here's a TL; DR, of what we know.
- Arrays:
- C++ Platforms:
- Implemented as a wrapper around an array, with size and out-of-bounds write detection
- HTML5
- Likely the same
- C++ Platforms:
- Lists
- C++ Platforms:
- Essentially an array list (per Juju, per Mike Dailly)
- HTML5:
- Unknown, probably the same?
- C++ Platforms:
- Grids
- Almost certainly a 2D array.
- Stacks
- Probably backed by an array, with an internal index that is updated to the last element.
- Queues
- Unknown
- Maps (Per Mike Dailly: see http://gmc.yoyogames.com/index.php?showtopic=544246)
- Used to be sorted lists (O(log(n)) lookup; O(n) ordered linear iteration)
- Now are true maps (O(1) lookup; O(n) unordered linear iteration)
- In both cases iterating through an entire map should be about the same, but now, finding the first/next element may be slower, and won't return elements in sorted order anymore.
- Hashing algorithm unknown; likely hashes on object ID
- Priority Queue
- Unknown
Edit 2: I've edited the title because I think broadening the scope in this topic would be useful. I'm really curious about every implementation, not just lists.
Edit 3: Re-reading this, it's obvious that I had a very strong (albeit erroneous) assumption that the ds_list implementation was a linked list- so much so that I took it for granted. I hope this edit provides that missing context.
Last edited: