3
\$\begingroup\$

I was working on an Limit Order Book structure in JS and came up with this algorithm. I am pretty sure this must have already been implemented but couldn't even find a clue over the web.

The thing is, it's very fast especially when you have an array of many duplicate items. However the real beauty is, after inserting k new items into an array of already sorted n items the pseudo sort (explained below) takes only O(k) and sort takes only O(n+k). To achieve this i keep a pseudo sorted array of m items in a sparse array where m is the number of unique items.

Take for instance we need to sort [42,1,31,17,1453,5,17,0,5] where n is 9 and then we just use values as keys and construct a sparse array (Pseudo Sorted) like;

Value: 1 1 2  2  1  1    1
Index: 0 1 5 17 31 42 1453

Where Value keeps the repeat count. I think now you start to see where I am getting at. JS have a fantastic ability. In JS accessing the sparse array keys can be very fast by jumping over the non existent ones. To achieve this you either use a for in loop of Object.keys().

So you can keep your sparse (pseudo sorted) array to insert new items and they will always be kept in pseudo sorted state having all insertions and deletions done in O(1). Whenever you need a real sorted array just construct it in O(n). Now this is very important in a Limit Order Book implementation because say you have to respond to your clients with the top 100 bids and bottom 100 asks in every 500ms over a web socket connection, now you no longer need to sort the whole order book list again even if it gets updated with many new bids and asks continuously.

So here is sparseSort code which could possibly be trimmed up by employing for loops instead of .reduces etc. Still beats Radix and Array.prototype.sort().

function sparseSort(arr){
    var tmp = arr.reduce((t,r) => t[r] ? (t[r]++,t) : (t[r]=1,t),[]);
    return Object.keys(tmp)
                 .reduce((a,k) => {
                           for (var i = 0; i < tmp[k]; i++) a.push(+k);
                           return a;
                         },[]);
}

Here you can see a bench against Array.prototype.sort() and radixSort. I just would like to know if this is reasonable and what might be the handicaps involved.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ The radix sort in jsben.ch/s6Ld2 is very poorly written. This jsben.ch/96YZc bench has a better (not best) example of a radix sort \$\endgroup\$ – Blindman67 May 10 at 14:19
  • \$\begingroup\$ @Blindman67 Yes that seems to make difference however there many curious things in play (Chrome or new Edge). You may test radixSort against sparseSort on dev tools snippets with performance.now() and try data = $setOf(12500, () => $randI(12500)) anddata = $setOf(13000, () => $randI(13000)) to notice a huge difference. Apart from such breaking points Radix Sort and Sparse Sort give very close results however when you enforce duplicates like data = $setOf(12500, () => $randI(125)) then it suddenly becomes a different game. \$\endgroup\$ – Redu May 10 at 17:08
  • \$\begingroup\$ I'm afraid this is a modification of the counting sort \$\endgroup\$ – Norhther May 10 at 17:51
  • \$\begingroup\$ @Norhther Well it is and it is not. It seems to be a union of Radix Sort and Count Sort. You may read more in my self answer. Especially the last paragraph. \$\endgroup\$ – Redu May 10 at 18:01
  • \$\begingroup\$ @Redu I don't think this is Radix (I mean the algorithm, not the actual implementation). I think this is just the natural improvement of Counting Sort, just storing the actual elements and not the full range \$\endgroup\$ – Norhther May 10 at 18:06
5
\$\begingroup\$

I think you re-invented counting sort, but with some small differences. Also you probably need to sort your sparse array keys before iterating over them so that's O(k log k) at least unless your possible range of values is small (let's call it N) so you can just try all N values and it will be O( N ).

Performance wise, it's hard to beat if you have a small range of value N.

\$\endgroup\$
7
  • \$\begingroup\$ Iterating over the sparse array keys in JS make them come in a sorted manner as string values so i do +k. However we best care there are no other properties than indices in order to prevent an unexpected failure. So i think the sparse array must be kept private, totally in our control, away from prying eyes. \$\endgroup\$ – Redu May 9 at 20:15
  • 3
    \$\begingroup\$ Ok well, I'm not familiar with JavaScript, but if it's already sorted, somebody already did the sort for you at some point (the language). It means that inserting into the array probably cost at least O( log k ) (more if they shift stuff around) and you do it k times so it ends up costing O (k log k). After that I agree that reading the list cost only O ( k ). \$\endgroup\$ – Cedric May 9 at 20:17
  • 2
    \$\begingroup\$ It's not necessarily faster, actually it's slower in many cases. They just made a different trade-off. If your counting array is sorted.. You paid that price. There is no free lunch. \$\endgroup\$ – Cedric May 9 at 22:30
  • 1
    \$\begingroup\$ Let me break it down a little. If we look at this logically, without even knowing how JavaScript does it under the hood, we can still see why. In your code you start by counting and placing the count in a "sparse array" here : "var tmp = arr.reduce((t,r) => t[r] ? (t[r]++,t) : (t[r]=1,t),[]);". If you print that array, you'll see that it's already sorted. It means that something sorted it for you. Optimistic worst case, you are looking at O ( k log k ).. but I suspect it's actually O ( k ^ 2 ) with all the shifting around needed to insert the new elements in the right position. \$\endgroup\$ – Cedric May 9 at 22:35
  • 1
    \$\begingroup\$ Meanwhile for counting sort, they just insert it into their array at O( 1 ) cost, and then they go through their array at O ( N ) cost. Overall, it's probably always better to use traditional counting sort unless you have a very big range ( N ) and not a lot of elements ( k ). \$\endgroup\$ – Cedric May 9 at 22:36
0
\$\begingroup\$

So to me this seems to be a really efficient sorting algorithm at least for a very particular case as follows;

  1. Sorting positive integers only or negative integers only (zero included).
  2. Works much more efficient if you have duplicates
  3. Works much more efficient when elements are discontinuous (sparse)

The Array structure in JS is complicated and in time has been optimized greatly. You may like to watch this before proceeding any further but i will try to summarize. Depending on their structures there are basically 6 types of arrays.

enter image description here

PACKED_SMI_ELEMENTS   : [1,2,3]
PACKED_DOUBLE_ELEMENTS: [1.1,2,3]
PACKED_ELEMENTS       : [1,2,"c"]

These are dense arrays and there are three separate optimization layers for them. Then we have three more types coming with their own optimization layers.

HOLEY_SMI_ELEMENTS    : [1,,3]
HOLEY_DOUBLE ELEMENTS : [1.1,,3]
HOLEY_ELEMENTS        : [1,,"c"]

In our case we may have a HOLEY_SMI_ELEMENTS type of array at hand. But i think not all HOLEY_SMI_ELEMENTS type arrays are the same. I guess if the gap between the elements are big enough we end up with a NumberDictionary type where the elements are now of DICTIONARY_ELEMENTS. Now most probably we are here. Normally this is very inefficient compared to normal arrays when normal array operations are performed but in this very particular case it shines. Further reading here.

Now what i couldn't find is, how exactly the number keys (indices) are stored in a NumberDictionary type array. Perhaps balanced BST or Heap with O(log n) access

OK then can we not use a map to start with..? Perhaps we can but it wont be a NumberDictionary and possibly the map keys are not handled like in NumberDictionary. For example In Haskell there is the Map data type which takes two types like Ord k => Map k v which says k type is requried to be a member or Ord type class so that we can apply operations like < or > on k type. Map is implemented on Balanced BST. However there is also an IntMap type where keys have to be Integers. This is how it is explained in Data.IntMap reference.

The implementation is based on big-endian patricia trees. This data structure performs especially well on binary operations like union and intersection. However, my benchmarks show that it is also (much) faster on insertions and deletions when compared to a generic size-balanced map implementation.

It turns out the mentioned big-endian patricia trees are in fact Radix Trees. I think once you end up with a NumberDictionary your keys are stored in a Radix Tree. So in this very algorthm, having duplicates in the array enforce you do Radix sort on keys and count sort on values at the same time. This way of sorting in some particular cases in JS might be reasonable.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.