In this post Super fast sorting with FlashSort !, I presented a really fast algoryhm to sort integers.
What about changing it to try to beat the Array.sortOn, and by this making it more usable ?
So as far as the API, we want to go from
static public function
flashSortInt2(a:Vector.<int> , multiplier:Number = 0.43):void
{
}
to something like that:
static public function
flashSortOn(o:Vector.<Object> , key:String , multiplier:Number = 0.43):void
{
}
Attempt1
So what we can do, is to simply change each access to a[index] in the code to
o[index][key]
Here with the changes:
static public function flashSortOn2(o:Vector.<Object> , key:String , multiplier:Number = 0.43):void
{
var n:int = o.length;
var i:int = 0, j:int = 0, k:int = 0;
var m:int = n*multiplier;if(m>262143)m=262143;
var l:Vector.<int> = new Vector.<int>(m);
var anmin:int = o[0][key];
var anmax:int = anmin;
var nmax:int = 0;
var nmove:int = 0;
var lk:int;
i =0;
var kmin:int,kmax:int,kimin:int,kimax:int;
for (i=0; (i+=2) < n;)
{
if( (kmin = o[i][key])>(kmax = o[i-1][key]))
{
if (kmax< anmin) anmin = kmax;
if (kmin> anmax) { anmax = kmin; nmax = i;}
}
else
{
if (kmin< anmin) anmin = kmin;
if (kmax > anmax) { anmax = kmax; nmax = i-1;}
}
}
if(--i < n)
{
if ((k = o[i][key]) < anmin) anmin = k;
else if (k > anmax) { anmax = k; nmax = i;}
}
if (anmin == anmax) return;
var c1:int = ((m - 1)<<13) / (anmax - anmin);
for (i = -1; ++i < n;)
{
++l[(c1*(o[i][key] - anmin))>>13];
}
lk = l[0];
for (k = 0; ++k < m;)
{
lk = (l[k] += lk);
}
var holdo:Object = o[nmax];
o[nmax] = o[0];
o[0] = holdo;
var flasho:Object;
j = 0;
k = (m - 1);
i = (n - 1);
while (nmove < i)
{
while (j >= l[k])
{
k = (c1 * (o[ (++j)][key] - anmin))>>13;
}
flasho = o[j];
var flash:int = flasho[key];
lk = l[k];
while (j !=lk)
{
holdo = o[(lk = (--l[(k = ((c1 * (flash - anmin))>>13))]))];
o[lk] = flasho;
flasho = holdo;
++nmove;
}
}
for(j = 0; ++j < n;)
{
holdo = o[j];
var hold:int = holdo[key];
i = j;
while((--i >= 0) && (((holdo=o[i])[key]) > hold))
{
o[i+1] = holdo;
}
o[(i+1)] = holdo;
}
}
Great, with minimum changes, we have a flashSort with a key sortOn capability
… lets try, humm … slower than Array.sort, much slower.
Attemp2
So, what is slow here, is to access the o[index][key] over and over again,
One thing we can do, is to copy all the keys into a separate Vector.<int> (assuming the key is an integer),in the first loop when we first find the min and the max, and from there use our temporary buffer..
Then, later, each time we swap or move something in that Vector from one index to another, we can apply the same transform in our o object Vector.
Here the code:
static public function flashSortOn(o:Vector.<Object> , key:String , multiplier:Number = 0.43):void
{
var n:int = o.length;
var i:int = 0, j:int = 0, k:int = 0;
var a:Vector.<int> = new Vector.<int>(n);
var m:int = n*multiplier;if(m>262143)m=262143;
var l:Vector.<int> = new Vector.<int>(m);
var anmin:int = a[0] = o[0][key];
var anmax:int = anmin;
var nmax:int = 0;
var nmove:int = 0;
var lk:int;
i =0;
var kmin:int,kmax:int,kimin:int,kimax:int;
for (i=0; (i+=2) < n;)
{
a[i] = kmin = o[i][key];
a[i-1] = kmax = o[i-1][key];
if( kmin>kmax)
{
if (kmax< anmin) anmin = kmax;
if (kmin> anmax) { anmax = kmin; nmax = i;}
}
else
{
if (kmin< anmin) anmin = kmin;
if (kmax > anmax) { anmax = kmax; nmax = i-1;}
}
}
if(--i < n)
{
a[i] = k = o[i][key];
if (k < anmin) anmin = k;
else if (k > anmax) { anmax = k; nmax = i;}
}
//var time3:int = getTimer();
//time2 = time3-time2;
//trace(time1,time2);
if (anmin == anmax) return;
var c1:int = ((m - 1)<<13) / (anmax - anmin);
for (i = -1; ++i < n;)
{
++l[(c1*(a[i] - anmin))>>13];
}
lk = l[0];
for (k = 0; ++k < m;)
{
lk = (l[k] += lk);
}
//swap a[nmax] and a[0]
var hold:int = anmax;
var holdo:Object = o[nmax];
a[nmax] = a[0];
o[nmax] = o[0];
a[0] = hold;
o[0] = holdo;
var flash:int;
var flasho:Object;
j = 0;
k = (m - 1);
i = (n - 1);
while (nmove < i)
{
while (j >= l[k])
{
k = (c1 * (a[ (++j)] - anmin))>>13;
}
flash = a[j];
flasho = o[j];
lk = l[k];
while (j !=lk)
{
hold = a[(lk = (--l[(k = ((c1 * (flash - anmin))>>13))]))];
holdo = o[lk];
a[lk] = flash;
o[lk] = flasho;
flash = hold;
flasho = holdo;
++nmove;
}
}
for(j = 0; ++j < n;)
{
hold = a[j];
holdo = o[i=j];
while((--i >= 0) && ((k=a[i]) > hold))
{
o[i+1] = o[i];
a[i+1] = k;
}
if(++i != j)
{
a[i] = hold;
o[i] = holdo;
}
}
}
Attempt3
Final attempt, we can rewritte this with Alchemy, alchemy byteArray is used as our temporary buffer…
static public function flashSortOnAlchemy(o:Vector.<Object> , key:String , multiplier:Number = 0.43):void
{
var n:int = o.length;
var i:int = 0, j:int = 0, k:int = 0;
var m:int = n*multiplier;if(m>262143)m=262143;
var m4:int = m<<2;
var m4end:int = m4 + (n<<2);
var anmin:int = o[0][key];
var anmax:int = anmin;
var nmax:int = 0;
var nmove:int = 0;
var lk:int;
i =0;
var zero:Number =0;
for(i=-8;(i+=8)<m4;)
{
fastmem.fastSetDouble(zero,i);
}
//set first element
fastmem.fastSetI32(anmin,m4);
//method 1 - 1 index / iteration
/*
var time1:int = getTimer();
for (; ++i < n;)
{
if ((k = a[i]) < anmin) anmin = k;
else if (k > anmax) { anmax = k; nmax = i;}
}
var time2:int = getTimer();
time1 = time2-time1;
trace(anmin,anmax,nmax);
time2 = getTimer();
//anmax = anmin = a[0]; - enable that if you want to test both mryhois
*/
//method2 - do 2 indexes / iterations
var kmin:int,kmax:int,kimin:int,kimax:int;
var a_i:int = m4+4; //start at element 1
for (i=0; (i+=2) < n;)
{
//a[i-1] = kmax = o[i-1][key];
fastmem.fastSetI32(kmax = o[i-1][key],a_i);
//a[i] = kmin = o[i][key];
fastmem.fastSetI32(kmin = o[i][key],a_i+4);
a_i+=8;
if( kmin>kmax)
{
if (kmax< anmin) anmin = kmax;
if (kmin> anmax) { anmax = kmin; nmax = i;}
}
else
{
if (kmin< anmin) anmin = kmin;
if (kmax > anmax) { anmax = kmax; nmax = i-1;}
}
}
if(--i < n)
{
//a[i] = k = o[i][key];
fastmem.fastSetI32(k = o[i][key],a_i);
if (k < anmin) anmin = k;
else if (k > anmax) { anmax = k; nmax = i;}
}
if (anmin == anmax) return;
var c1:int = ((m - 1)<<13) / (anmax - anmin);
var tilde3:int = ~3;
;
for (a_i = m4-4; (a_i+=4) < m4end;)
{
fastmem.fastSetI32(fastmem.fastGetI32((k=(((c1*(fastmem.fastGetI32(a_i) - anmin))>>11) & tilde3)))+1,k);
}
lk = fastmem.fastGetI32(0);
for (k = 0; (k+=4) < m4;)
{
fastmem.fastSetI32((lk += fastmem.fastGetI32(k)),k);
}
//swap a[nmax] and a[0]
var hold:int = anmax;
var holdo:Object = o[nmax];
//a[nmax] = a[0];
fastmem.fastSetI32(fastmem.fastGetI32(m4),m4+(nmax<<2));
o[nmax] = o[0];
//a[0] = hold;
fastmem.fastSetI32(hold,m4);
o[0] = holdo;
var flash:int;
var flasho:Object;
j = 0;
k = (m - 1);
i = (n - 1);
while (nmove < i)
{
a_i = m4 + (j<<2);
while (j >= fastmem.fastGetI32(k))
{
k = ((c1 * (fastmem.fastGetI32(a_i+=4) - anmin))>>11)&tilde3;
j++;
}
flash = fastmem.fastGetI32(m4 +(j<<2));
flasho = o[j];
lk = fastmem.fastGetI32(k);
while (j !=lk)
{
hold = fastmem.fastGetI32(m4 + ((lk = (fastmem.fastGetI32((k = (((c1 * (flash - anmin))>>11)&tilde3)))-1))<<2));
fastmem.fastSetI32(lk,k);
//hold = a[(lk = (--l[(k = ((c1 * (flash - anmin))>>13))]))];
holdo = o[lk];
//a[lk] = flash;
fastmem.fastSetI32(flash,m4+(lk<<2));
o[lk] = flasho;
flash = hold;
flasho = holdo;
++nmove;
}
}
for(j = 0; ++j < n;)
{
//hold = a[j];
hold = fastmem.fastGetI32(m4 + (j<<2));
holdo = o[i=j];
while((--i >= 0) && ((k=fastmem.fastGetI32(m4 + (i<<2))) > hold))
{
o[i+1] = o[i];
//a[i+1] = k;
fastmem.fastSetI32(k,m4 + ((i+1)<<2));
}
if(++i != j)
{
//a[i] = hold;
fastmem.fastSetI32(hold,m4 + (i<<2));
o[i] = holdo;
}
}
}
Okay, lets try !!!!
* we are faster than the Array.sortOn !
* alchemy changes didn’t help
Leave a Reply