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.

Advertisements