In response to Jp (#19)
Yes, if you have associations to check, using if(list[item]) is much faster than if(key in list). Since all you're interested in knowing is whether an item exists in the list, not where, and you can know (depending on how you setup the list) that every item has an associated value, you can easily skip to looking for the associated value instead of using in/Find.

Lummox JR
In response to Loduwijk (#17)
Loduwijk wrote:
Let me see if I understand you correctly. A list object is backed by both a straightforward array and an r/b tree (possibly implemented in a second array?). Any time you add anything to a /list instance, it is added to the end of the array, and, if it has an associated value, it is also added to the tree that maps associations. Either way, all keys and non-associated elements are in the array, thereby duplicating all map keys.

Yes, everything in the tree is in the array. Any time something is removed from the array the tree is checked to see if it needs removal from there as well.

Is this correct? If so, is the array part kept around just to preserve insertion order? Also, do you know how array size is handled? Does it make a moderately sized array and create new arrays when old arrays are filled?

The array part is kept for two reasons. Actual list order is important to keep, but also the same item can appear more than once in a list.

To answer the size issue, lists are usually resized on demand, often with a little bit of slack space so they don't need reallocating all the time. I forget what their initial size is but an empty list usually starts out with a little slack. (This is another reason that list husbandry should be practiced, as keeping an empty list wastes memory.)

You can get some of the speed benefits of advanced data structures by using lists judiciously, like for instance if you know how to keep a binary tree in balance you can simply have a packed list where index i*2 is the left branch and i*2+1 is the right branch.

Do you mean us, on the Byond-user side, sizing the list appropriately and manually inserting elements at specific indices, using it as a tree? If so, are you implying that Byond will use the internal tree for all of this, or are you suggesting also doing search/deletion/traversal manually on our side? If the latter, I think that is what Garthor and I were getting at; if the former, I must be misunderstanding your explanation of how the list is working behind the scenes.

I'm suggesting manual search/deletion/traversal, yes. The purpose of that would be for handling your own advanced data structures though, for cases where BYOND's built-in list handling isn't ideal for your purposes. Usually that doesn't come up much, but in the case of a heap sort I found it to be incredibly helpful.

Either way, it is good to know that associations utilize a red-black tree. Why don't you have the tree keep track of non-associated data as well to increase speed for all searches, regardless of whether the data is mapped or not?

Because items in the list are not guaranteed to be unique. However, that does sound like a potentially good method to speed up any "in" test, which doesn't care about position in the list.

Lummox JR
Page: 1 2