Monthly Archives: October 2013

Don’t get fancy with JavaScript

Today, I thought it would be a good idea to finally apply all the JavaScript knowledge  that I have accumulated in the past few months. While I was at it, I thought it would be a good idea to review all the Computer Sciencey stuff like design patterns, and sorting algorithms. For design patterns, I decided to use the command pattern, the strategy pattern, and the factory method pattern. For the sorting, I used merge sort, selection sort, and insertion sort. I implemented the merge sort, and it sorted 1,000 numbers perfectly; But 1,000 numbers is nothing, so I bumped it up to a million to see how fast it could sort 1,000,000 numbers, but it started hanging and performed like shit.

At first, I thought it might have been my number generator taking too long to generate my array of random numbers. A console.log later, and I quickly found out that the counter in my for-loop would hang at 99,999. No biggie there, I rewrote it with a while-loop and just counted down to 0. Time to start sailing.

     function TopDownSplitMerge(arrayOfNumbers) {
            var length = arrayOfNumbers.length
            var middleIndex = parseInt(length/2);

            if(length <= 1) {
                return arrayOfNumbers;
            }

            // Split left side
            var left = TopDownSplitMerge(arrayOfNumbers.slice(0, middleIndex));

            // Split right side
            var right = TopDownSplitMerge(arrayOfNumbers.slice(middleIndex, length-1));

            // Merge every back together
            return TopDownMerge(left, right);
        }

        function TopDownMerge(left, right) {
            var results = []

            while(left.length || right.length) {
                // Check if both sides are NOT empty, if so, then just finish shifting the non-empty side
                if(left.length && right.length) {
                    if(left[0] <= right[0]) {
                       results.push(left.shift())
                    } else {
                       results.push(right.shift())
                    }
                } else if(left.length) {
                   results.push(left.shift())
                } else {
                   results.push(right.shift())
                }

            }

What do you think? It shouldn’t be a problem right? And look at all the fancy JavaScript array functions that I am using. Gotta drink that Kool-aid!

kool-aid-man

10 minutes later. My terminal explodes and gives me this:

FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memory

I knew that there was no way merge sort would take this long since I implemented it in Java before. Upon closer observation, my next culprit was the slice() function because I thought it would have to use some kind of loop in order for it to copy the elements in order to return a new array. I did some Googling and found this StackOverflow post saying:

… all JavaScript objects (including Array instances) are maps…

Well, that explains a lot. That means, not only is the slice() hurting my performance, but the shift() is as well. For each recursion, I was running a bajillion slices times a bajillion shifts resulting in O(bajillion²). I ended up keeping track of indexes and just directly accessing the element in the array, and I was able to sort 10,000,000,000 numbers in 14360 milliseconds. The lesson here is to stick with the proven algorithm, and to not get fancy with JavaScript.

You can find the rest of my code here: JavaScript Sorting Algorithms

What would they call us?

I like to go into my brother’s room and just see what he is working on from time to time. I try to help him with anything I can, especially if its related to math. I wanted to know what his history class was going over, since they were in the 1700s, I asked him “what happened during that time?” He told me, “the Age of Enlightenment”. He explained how it was a time when society began adopting the scientific method and a time when people started challenging faith and other ideals. Cool. I started asking him more questions and that eventually led to the late 1700s when the French Revolution took place.

I started thinking about all the technology advances in this century so far, and it is just mind boggling to think about how much has changed in only a few decades. With all the technology advances and paradigm changes such as computers, the internet, social networks, and iPhones (just to name a few), what would the future generations title this era?