SortedArray in JavaScript?
I'm not sure I understand what use this container would have in common cases. You can simply sort an ordinary array and then binary search it. A 'SortedArray' primitive would be very strange in JS also since as soon as you modified the value at an index, either the array becomes unsorted or it has to be resorted and now the value you just wrote isn't there anymore, that is:
a[i] = 1;
a[i] !== 1;
Which is pretty strange for a container. Normally a container like this would not allow those sorts of operations, which makes it somewhat less useful. If all you want is has/remove (I have no idea what 'set' would do in this case - is it just add?), why not use Set? Do you just need the ability to store duplicates? If so, I think a map of item->count might suffice, though I'm not sure precisely how easy that is to express in JS.
It sounds like all you really need here is Array.binarySearch as a builtin (or JS polyfill) to implement the container you want, but it's also not clear why you want this container or what it would do for you.
JS-based implementations can outperform native implementations in some cases; it depends. I think in this case a self-hosted implementation would end up faster, but only if it were specialized for the element type(s) in the array.
I can see the use of a sortedArray with get, set, indexOf, push, pop, shift and unshift.
I doubt you want to let it be indexed using [] and I see little reason why it would need to be built into the language. It would make far more sense as a nice little library, which creates a much smaller maintenance burden.
On Sat, Aug 10, 2013 at 3:19 AM, Forbes Lindesay <forbes at lindesay.co.uk> wrote:
I doubt you want to let it be indexed using
[]and I see little reason why it would need to be built into the language. It would make far more sense as a nice little library, which creates a much smaller maintenance burden.
For example, montagejs/collections/blob/master/sorted-array.js
folks. After a year of computer science courses (yay for learning fundamentals), I've been thinking about arrays and their indexOf() method, and wondering: why don't we have an array type that sorts the items for us in JavaScript?
(By the way, I love the Map & Set implementations in Firefox. Very, very handy.)
Because arrays in JS are assumed to be unsorted, indexOf is an O(n) operation. But if I have an array of values, and use a simple comparator function, indexOf becomes O(log n), plus whatever the invocation time is for the comparator.
In the simplest cases, I'm sorting numbers or strings, which wouldn't need a fancy comparator function. If I'm sorting objects, I can write my comparator function just like I would for Array.sort.
Many of the methods for manipulating arrays would go away (unshift, shift, push, pop, splice). There would also be a need to add .has(), .set(), .remove() methods, probably (like a Map).
I'm sure I'm just repeating the obvious now, so I'm wondering if it would be worth adding to the language in some form. I'm well aware it would be easy to implement in JavaScript, but would a JS-based implementation be faster than a native one?