JavaScript Sorting Runtime of Object acting as Array and Dictionary

Question

EDIT: It looks like what I've written below is a form of Pigeonhole Sort.

I've been looking into how JavaScript Arrays are really special Objects and additionally have in-order iterators (since they are collections).

Because of that, this code is possible:

let inputArray = []; // inputArray.length === n
// non-duplicate entries for the sake of this question (easy to alter)
let sparse = new Array(); // Sets up as dictionary

// O(n)
inputArray.forEach(function(entry) { // Uses Dictionary mode
    sparse[entry] = entry; // O(1) 
});

// O(n) (actual is n log n)
let sortedArray = [];
for (let entry of sparse) { // Uses Array mode
    sortedArray.push(entry); // O(1)
}

But since sorting algorithms have a fastest runtime of O(n log(n)), the conversion between JavaScript's object dictionary mode and array mode must slow it down. I tested it, and it does slow down as expected (although it is faster than the native .sort()), but it only covers sorting by toString() so obviously I'd go with the native version.

So I have the following questions:

Where specifically in the above code does it devolve into an O(n log(n)) algorithm?
Can you link me the source code for this? In V8 for example.

I'm assuming it would be a lazy iterator creation or access during the for...of phase, but I would love to see the code and why it is.

jmrk · Accepted Answer · 2017-01-19 11:48:15Z

2

Only comparison-based sorting is never faster than O(n log n). In your code, the sorting happens in the sparse[entry] = entry line, where you do index-based sorting. This works in O(n) time, but comes with limitations: mainly, it only works if you know the range of values in advance. In this case, the implicitly defined range of valid values is the set of valid array indices, i.e. the integers from 0 to 2^32 - 1. (Try adding a negative number, or a (non-integer) double, or a string, to your input array.)

A few more clarifications:

new Array() does not set up anything in dictionary mode. You could use var sparse = []; and your code would work exactly the same. Depending on engine heuristics, subsequent usage patterns may or may not transition the array into dictionary mode under the hood, but you won't see a difference in behavior from that.
for..of and for..in have the same iteration order (by default). One of their biggest differences is that for..in iterates over keys (which are spec'ed to have type string), whereas for..of iterates over values (which have whatever type you put in). (Try it with [3, 4, "5"]: for..in will return "0", "1", "2", for..of will return 3, 4, "5".)
the biggest issue with for..in loops is that they include stuff from the prototype chain. If any of the libraries you include does Array.prototype.myFancyFunction = ..., then all your for..in loops over arrays will return one more element than you'd expect ;-)

answered Jan 19, 2017 at 11:48

jmrk

42.1k7 gold badges74 silver badges93 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

smileham Over a year ago

Wow thank you so much. I was aware of most of the points, but I definitely missed the comparison-based sorting limit. I'll look more into other sorting algorithms. Thanks!

smileham Over a year ago

Looks like I was using a pigeonhole sorting algorithm. Good to know.

smileham · Accepted Answer · 2017-01-20 19:18:28Z

0

It appears that for...of, while going through enumerable properties, has to check each successive number (key) until it has hit length elements. If this were sorted (and in array mode), then it would be easy to have a next element for the iterator, but since it is not sorted (since it was created in the mapping mode), it has to check each potential number in order (0,1,...[last defined element]). I didn't bother checking the source code, but from more time tests and print statments, this seems to be the answer.

edited Jan 20, 2017 at 19:18

answered Jan 11, 2017 at 21:20

smileham

1,4602 gold badges18 silver badges29 bronze badges

3 Comments

Redu Over a year ago

My experience says a for of loop is the slowest of all while the for in loop is the fastest if you would like to disregard the sparse items.

smileham Over a year ago

@Redu - Absolutely. This is because for...in can go through each key in the order they were added, while for...of has to go through in sorted (toString) order, so it adds that overhead. So if you care about order, use for...of, but if it doesn't matter, definitely use for...in.

camillobruni Over a year ago

@smileham for..in and for..of have the same default iteration order. With for...of you can specify your own iterator which can have an arbitrary iteration order.

Collectives™ on Stack Overflow

JavaScript Sorting Runtime of Object acting as Array and Dictionary

2 Answers 2

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related