Blogroll

Testing Merge Sort with Jasmine

When designing algorithms you are looking to get the correct results in the least number of steps possible.  The running time of an algorithm is part of the analysis of any algorithm.  A key question in this analysis is:  When your data set grows what happens to the run time of your solution? For that reason I am running my algorithm class homework solutions through test runners and I’ll post them here.

A few observations during this process :

  • It’s generally better to run these tests on the command line.  Making a test suite run within a blog post has its challenges.
  • You’re probably more interested in the results than in me figuring out how to do this within the confines of a blog post.
  • Hence, in future posts I will probably post the code for a Node JS set-up and not for the browser.
  • I used Jasmine JS which is very nice and easy to use and it does provide test results.  However, I did make the mistake of running a failing spec on a 100k entry array which yielded 100k errors and crashed my browser!
  • I used a 100k array for the run time to be observable.  To make my life easier I will run several tests off the browser and instead post a chart of the results.
  • I was curious to see how long it takes to sort a large array in the browser.  Why did I want to see this happen? I don’t know.

The Merge Sort code is here (in my previous post).

In order to run the algorithm on this page I decided to load a file with random entries.  The code for the load uses the jQuery Ajax function.  It’s very straightforward to set up.  In the txt file, each line is a new entry.  Hence, the success function creates an array by doing a split on the regexp: /\n|\r\n|\r/ which is just matching a new line.  Each entry is then forced to be an integer.

	$.ajax({
        type: "GET",
        url: "./jslib/IntegerArray.txt",
        dataType: "text",
        success: function (data) {

        	var array = data.split(/\r\n|\r|\n/);
        	for(var i =0; i<array.length; i++) {
        		array[i] = parseInt(array[i]);
        	}
        	A = array.slice(0);

        }

    }).done(function(){ 
    	console.log("loaded"); 
    	runSpec();
    });

 

When the load is complete, the runSpec function is called.  This is the test suite for Jasmine.  I run four tests:

  1. Make sure the length of the array is 100k
  2. Call Merge Sort and make sure every item in the array is in ascending order.
  3. Call JavaScript sort and make sure every item in the array is in ascending order.
  4. Verify that the native (JavaScript) sort if faster.

The test suite is below:

describe("Load file",function(){

			it("Should split into array correctly", function(){

				expect(A.length).toBe(100000);

			});

		});

		describe("Items should be sorted", function(){
			it("It is sorted if all items are in ascending order", function(){
				mst = new Date();
				M = splitArray(A);
				met = new Date();
				for (var n=0; n<M.length-1; n++) {
					expect(M[n]).toBeLessThan(M[n+1]);
				}
			});
		});

		describe("JavaScript Sort", function(){
			it("It is sorted if all items are in ascending order", function(){
				nst = new Date();
				X = A.sort(function(a,b) { return a-b; });
				net = new Date();
				for (var n=0; n<X.length-1; n++) {
					expect(X[n]).toBeLessThan(X[n+1]);
				}
			});
		});

		describe("Native vs Merge Sort", function () {
			it("Native sort should be quicker", function(){

				expect(net-nst).toBeLessThan(met-mst);

			});
		});

All those tests are run on this post.  So keep scrolling down to see the Jasmine Spec runner test output!

Test is running …. Jasmine test runner will load shortly at the bottom of the screen…

Run time Summary:




    Merge Sort in Javascript

    The Merge Sort algorithm is a divide and conquer algorithm and its basic premise is to grab a problem that can be solved recursively and break it down into smaller chunks.  Then put the chunks back together and you will have a solution that grows higher than a linear solution but better than a quadratic solution.  This algorithm was discovered and applied a long time ago but I wrote my own version in JavaScript as a homework assignment for my Algorithms class.

    Keep in mind that JavaScript has a sort method already!  It has been in place since ECS1 so this is not an attempt to improve on the solution – it is just an exercise.  I have also done some run time tests and will be plotting those results shortly.  I will also compare my run time results to the native JavaScript implementation (spoiler: the native implementation is faster!) and a Java version of the algorithm by Robert Sedgewick & Kevin Wayne.

    The annotated JS code is below:

    /* Merge Sort in Javascript by Carlos Moran */
    
    //mergeSort gets two arrays and returns a sorted array
    
    function mergeSort(A, B) {
        var s = A.length;
        var t = B.length;
        var u = s + t;
    
        var i = 0;
        var j = 0;
    
        // if only two values are to be compared then return the sorted array immediately
    
        var C = u == 2 ? (A[0] < B[0] ? [A[0], B[0]] : [B[0], A[0]]) : [];
        if(B[0]>A[0]) counter++;
        if (C.length > 0) return C.slice(0);
    
        //otherwise merge taking into account arrays that have different dimensions i.e. one array has 3 elements, one has 2
        for (var m = 0; m < u; m++) {
    
            if (j > (t - 1)) {
                C.push(A[i++]);
                counter++;
                continue;
            }
            if (i > (s - 1)) {
                C.push(B[j++]);
                continue;
            }
    
            A[i] <= B[j] ? C.push(A[i++]) : C.push(B[j++]);
            if(A[i]>B[j]) counter++;
    
        }
    
        return C.slice(0);
    
    }
    
    function splitArray(R) {
    
    //split array in two
        var l = R.length;
        var n = ~~ (l / 2);
    
    //merge recursively until smallest split is achieved then return merged array
        if (n > 0) {
    
            return mergeSort(splitArray(R.slice(0, n)), splitArray(R.slice(n)));
        } else {
    
            return mergeSort(R.slice(0, 1), R.slice(1));
        }
    
    }
    
    	return {ms: M[0], iterations: counter}; // return first array value and total operations
    });

    The test was run on Mocha on my desktop and the run times will be posted in a future post! Meanwhile, you can check my next post which runs a test suite of this algorithm in the browser.

     

     


    Lazy loading images

    The other day I decided to show a random post from my images blog on my main moranjr.com page. The issue is that because of the number of images, the page was loading slowly so I wrote a lazy loader to the site a faster load even with the random posts.

    What the script does is simply to load the images in the post but it only the displays those that are in the current view port.  By deferring some heavy image loads, your site will render much quicker if you have a lot of images to show.

    There are other requirements too:

    • Make it as lean as possible
    • Have no JS library dependencies (jQuery or others)

    The annotated code is below:

    /* 	
    	A lazy load script with no jQuery dependencies
    	Script by Carlos Moran
    	License MIT
    */
    
    var ll = function(document, window, soffset, imgs){
    
    	var i, 							// counter for DOM
    	j; 							// counter for img data array 
    	var imgsData = [];  		// Collect img src attributes in an array
    	var innerHeight = window.innerHeight; // get view port dimensions
    
    	if(imgs) {
    		for(i=0; i < imgs.length; i++) {
    
    			var pos = imgs[i].getBoundingClientRect();
    
    			/* if image is visible already then exclude from images to load later */
    			/* if its not loaded then save its position [i] in the imgs array, its vertical position, its load status and src attribute*/
    			pos.top < innerHeight ? imgs[i].src = imgs[i].getAttribute("data-lsrc") : imgsData.push({
    			i: i, y:pos.top, loaded: false, dsrc: imgs[i].getAttribute("data-lsrc")});
    
    		}
    	}
    
    /* Call check elements on scroll - this will get the current top position and will set the src of the image to its proper value if it should be now in view */
    	function checkElements(elems) {
    
    		var offset = soffset || 0;
    
    		/*elems refers to imgsData */
    		for(j=0; j<elems.length; j++) {
    
    			if(!elems[j].loaded && (elems[j].y < innerHeight+document.body.scrollTop+offset)) {
    				imgs[elems[j].i].src = elems[j].dsrc;
    				elems[j].loaded = true;
    				console.log('Img '+ elems[j].i + ' loaded.');
    			} 
    		}
    
    	}
    
    	document.onscroll = function(){
    
    			checkElements(imgsData);
    
    	};
    /* run the function once to load images that are initally in view - prior to any scrolling */
    	checkElements(imgsData); 
    /* when you call ll it will return the number of images that were processed by LLL */
    	return {count: imgsData.length};
    
    };

    The usage of the script is below:

    Call the ll function with window, document as is first two parameters and offset as its third parameter. I use offset to tell the image loader to load images early (before the image reaches the view port). The reason is simply so that the user doesn’t have to see that the images are loading just now. Some people (like Politico) use a jQuery ‘fade in’ to give the user a better impression.

    The last parameter is the collection of images in the DOM with the data-lsrc attribute.  When you call ll it will look something like this:

    var imgs = $("img[data-lsrc]");
    lz = ll(document, window, 1000, imgs);

    In my next post I will show you how I populated the data-lsrc attribute in WordPress+PHP and how I added the images to the colorbox to give them a nice lightbox effect when the user clicks on an image.