It’s a rumor that Linked List should be a better Data structure to choose if we only need to traverse linearly one after another, without the need of randomly access, plus the ability to remove/ insert items at arbitrary positions.
For 1000 items double linked list
- Pushing items into the first, or last position is 15x faster than put items randomly as we need to search for the correct position, as an important side note : searching time will go up linearly with the List size.
- Pushing items into Array is much faster than insert into first/last position of the list : Push/Pop is 4x faster and even randomly splice is 1.2x faster.
- List seems to use much more memory than Array, about 5x more, as each node of the list is an Object, that has at least 2 variables refer to prev and next items.
- Traverse from first to last item is 2x slower than the same task with Array.
- Checking existances using indexOf in both Array and List is not efficient, it’s very slow as we need to traverse one after another to find out.
- For huge number of items, list operations should go linearly while Array won’t
Using Linked List seems not to be any more efficient than using an Array in constructing, traversing, splicing … May we should improve Array a little bit by implement binary sorted in to Array insert.
What we need ?
- Ascending presorted items Array
- Quick item finding by implementing Binary search
- Simple and quick Quick item insert/remove by Binary search + splice
- Property sorted support, we can change the property to sort anytime
What to consider ?
- Checking Vector vs Array vs Alchemy byte-code implement (should we keep FP9 compatible ? )
- Using Array nullize instead of splicing
- Checking performance with push + sort for 4000 items Array
What is the result ?
[swfobj src=”media/sorted_array_performance.swf” width=”300″ height=”88″]
- With 4000 items, Sorted Array insert by (Binary search + Array splicing) gets 5x slower than normal push, 2.5x faster than pushing till complete and sort only once. And continuously calling sortOn for each item inserted resulted in timeout. The difference is minimizing as the number of items decrease
- Although the result is pretty impressive for 4000 items, larger list that has more than 20k items show that there is almost no difference because splicing insert is then very expensive, so we need to find a better way to handle large data set if we need to insert / remove items for these case, may using Array indexes chunk will improve the speed so we will never allow array’s size to go up more than 4000 items by using many arrays.