CODEWITHSUNDEEP
javascriptalgorithmsortingv8
smileham
smileham

Reputation: 1460

JavaScript Sorting Runtime of Object acting as Array and Dictionary

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:

  1. Where specifically in the above code does it devolve into an O(n log(n)) algorithm?
  2. 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.

Upvotes: 0

Views: 103

Answers (2)

smileham
smileham

Reputation: 1460

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.

Upvotes: 0

jmrk
jmrk

Reputation: 40501

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 ;-)

Upvotes: 2

Related Questions