One of the most common data structure in Flash is Array, which provides a fast way to construct a list of data items with compact memory cost. This data structure is working fine and rather fast, except for some operations, for example, insert / remove items randomly (splice) or pushing things to the beginning of the Arrays (unshift). Because of the compact memory implementation, all the existed items after the insert position will need to be migrated. With o(n) complexity, operated time goes up linearly with the number of items. And it’s just the same for Vector, although Vector is way faster than Array as there are no dense checking and converting between Dense Array & Hash Table (there are more reasons ? ). In short : Array is slowing down by items migration
A rather popular solution is using Linked List – either double or single. Linked list has ability to add and remove items very fast at an arbitrary position as no item is being migrated. Double linked list cost more memory (~ 1.5x ) and a bit slower than single Linked List (which, consume 2x more memory than Array) but it allows traversing in both direction. For some operations, the doubles run faster (~ 2x faster) than single ones. But as we won’t have random access to items by numeric indexes like Arrays, it’s really slow if we need to skip forward / backward to get to some random position. In short : Linked List is slowed down by skipping to specific position
In the classic presentation of Array and Linked List above, Array performs better than Linked List. It’s a popular fact that Linked List out performs Array in term of inserting / removing items at specific position, remember that it’s only true if our current position is also the needed-to-be remove item’s position (a popular case is we are trying to remove a dead item at current position while traversing through the whole linked list). Randomly remove an item in linked list will be much slower than that as we need to skip to the delete item’s position.
So if you have a fixed set of data items like book indexes, address indexes … using Array will be fit for most of the case. Prevent using Linked List unless you really know how it works, as the rule of thumb : Never try random access on a Linked List. There are also cases that we don’t have all data items available at the beginning as items getting added to / removed from the list at random position, random time : a delayed tween queue or a loading queue. In this case, using Array.sort() once for every insertion or call Linked List’s insert() won’t yield any in good performance as the complexity of inserting n items randomly in both case is o(n^2).
We definitely have some better way doing that !
- With Array, we can use a binary search for position and insert new items using splice(). The complexity is now o(log2(n)) + o(n) = o(n).
- With Linked list, we have several options to choose from, regarding Binary Tree, Bias Linked List, or Indexed Linked List. These methods use various strategies to index items so we can both traverse to a specific position faster than linked list, with o(l0g2(n)) complexity.
The Linked List speed gains come with some memory suffers (2x more) for saving indexes positions, initialization (the structure is more complex and heavy) and maintain works (some kind of tree status checking and make changes in the structure as data items come in / out). To minimize the initialization delay and maintain works, Linked List should implements lazy-loading to minimize the works needed for performance gains. Without lazy loading implemented, Linked List is not really a considerable option to choose.
I might update this post with some performance benchmark so you guys can see how each one performs yourself. Specific details on how Linked List being implemented might not fit into a single post so let’s wait for some other ones ….