Modifying sort and sortBy (make them faster) [not really, my bad]

(MartĂ­ Angelats i Ribera) #1

While i was making the code for the modification to support stage3D i realized that the functions quicksort and quicksortBy in the FP are not as fast as they can be. They use binary serch to sort the array/vector. Binary serch is the fastest way to serch into an array/vector but to sort it there is faster method. I post the code and if someone wants to make pull request it would be great (my github have enough with a pendent pull request and making the stage3D support).

        /** @private Quicksorts the array. */ 
        private static function quicksort(a:Object, left:int, right:int, ascending:Boolean):void
        {
            var i:int, j:int, temp:*;
            i = left + 1; 
            while (i <= right)
            {
                temp = a[i];
                j = i - 1;
                while (j >= left && ((ascending && temp > a[j]) || (!ascending && temp < a[j])))
                {
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = temp;
                i++;
            }
        }
        
        /** @private Quicksorts the array by the property. */ 
        private static function quicksortBy(a:Object, left:int, right:int, ascending:Boolean, property:String):void
        {            
            var i:int, j:int, temp:*;
            i = left + 1; 
            while (i <= right)
            {
                temp = a[i];
                j = i - 1;
                while (j >= left && ((ascending && temp > a[j][property]) || (!ascending && temp < a[j][property])))
                {
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = temp;
                i++;
            }
        }

PD: as you can see is way shorter and uses 1 loop less.

(rostok) #2

@Copying aren’t you missing recursion calls at the end of each function?

(Jacob Albano) #3

The ascending parameter works backwards in your implementation of quicksort, and as far as I can tell the quicksortby implementation does nothing at all?

var objs:Array = [];
for (var i:int = 0; i < 25; i++) 
{
    var val:int = Math.round(Math.random() * 100);
    objs.push( { x : val } );
}

FP.sortBy(objs, "x");
objs = objs.map(function(o, i, a) { return String(o.x); } );
trace(objs.join(", "));

Output from one run:

59, 83, 1, 19, 13, 74, 80, 67, 16, 83, 62, 64, 97, 88, 48, 14, 15, 32, 93, 46, 98, 53, 67, 23, 37
(MartĂ­ Angelats i Ribera) #4

I just realized that what i have to modify is the sort and sortBy itself. It may contain an error (i’ll redo it).

(MartĂ­ Angelats i Ribera) #5

Everything solved. Now they are sorting correctlly.

public static function sort(object:Object, ascending:Boolean = true):void
{
    if (object is Array || object is Vector.<*>)
    {
        if (object.length > 1)
        {
            var j:int, temp:*;
            for (var i:int = 1; i < object.length; i++)
            {
                j = i;
                temp = object[i];
                while (j-- && ((ascending && object[j] < temp) || (!ascending && object[j] > temp)))
                {
                    object[j + 1] = object[j];
                }
                object[j + 1] = temp;
            }
        }
    }
}

public static function sortBy(object:Object, property:String, ascending:Boolean = true):void
{
    if (object is Array || object is Vector.<*>)
    {
        if (object.length > 1)
        {
            var j:int, temp:*;
            for (var i:int = 1; i < object.length; i++)
            {
                j = i;
                temp = object[i];
                while (j-- && ((ascending && object[j][property] < temp[property]) || (!ascending && object[j][property] > temp[property])))
                {
                    object[j + 1] = object[j];
                }
                object[j + 1] = temp;
            }
        }
    }
}

PD: and yes quickSort and quickSortBy are deleted.

(MartĂ­ Angelats i Ribera) #6

I changed the way it works. The old one was using bynari serch using recursivity. This one no longer uses it. If you want me to explain how it works i will.

(rostok) #7

Initial function name mislead me as I thought it was a QuickSort optimization. But why did you choose to change it since your sort has o(n^2) complexity while quicksort’s average is o(nlog(n))?

(Jacob Albano) #8

How much benchmarking did you do here? The current implementation outperforms yours in every test I’ve thrown at it.

var sampleSize:int = 10000;
var nums:Array = [];
var objs:Array = [];
for (var i:int = 0; i < sampleSize; i++) 
{
    var val:int = Math.round(Math.random() * 100);
    nums.push(val);
    objs.push( { x : val } );
}

function measure(f:Function, args:Array):Number
{
     // clone the array each time so everything's fair
    args[0] = (args[0] as Array).concat();
     // don't start timing until cloning is finished
    var t:Number = flash.utils.getTimer();
    f.apply(null, args);
    return getTimer() - t;
}

trace("FP.sort() took", measure(FP.sort, [nums]), "ms");
trace("copying sort() took ", measure(sort, [nums]), "ms");
trace("FP.sortBy() took", measure(FP.sortBy, [objs, "x"]), "ms");
trace("copying sortBy() took", measure(sortBy, [objs, "x"]), "ms");

Output:

FP.sort() took 25 ms
copying sort() took 3948 ms
FP.sortBy() took 44 ms
copying sortBy() took 10014 ms

(MartĂ­ Angelats i Ribera) #9

I interpreted the code wrongly. So sorry for that.