Category Archives: arrays

Array.push() Vector.push() Optimization

By Zevan | May 14, 2009
CLICK HERE TO COPY
Actionscript:
  1. var tVerts:Vector.<Number> = new Vector.<Number>();
  2. var inc:int = 0;
  3. var t:Number, i:Number, j:Number, k:Number;
  4.  
  5.  // fast way
  6. t = getTimer();
  7. for (i= -2; i<2; i+=.03){
  8.     for (j = -2; j<2; j+=.03){
  9.         for (k = -2; k<2; k+=.03){
  10.             tVerts[inc] = i;
  11.             inc++;
  12.             tVerts[inc] = j;
  13.             inc++;
  14.             tVerts[inc]= k;
  15.             inc++;
  16.         }
  17.     }
  18. }
  19. trace(getTimer() - t);
  20.  
  21. tVerts  = new Vector.<Number>();
  22.  
  23. // slow way
  24. t = getTimer();
  25. for (i= -2; i<2; i+=.03){
  26.     for (j = -2; j<2; j+=.03){
  27.         for (k = -2; k<2; k+=.03){
  28.  
  29.             tVerts.push(i, j, k);
  30.         //  tVerts.push(j);
  31.         //  tVerts.push(k);
  32.         }
  33.     }
  34. }
  35. trace(getTimer() - t);

Today I needed to populate a Vector in the above manner... populating the vector using push() was quite slow in this case because (among other reasons) push() is a method call. I was curious how much faster populating the Vector without push would be... so I wrote this snippet - in this case it was significantly faster - took less than a third of the time. You can run this snippet to see what kind of results you get.

It's important to note that this nested for loop could be optimized further but I wanted to focus on the push() optimization alone.

Warning

The most HORRIBLE thing about testing the speed of ActionScript code is that you CANNOT rely on the debug player to test optimizations. Always use the release version of the flash player. The debug player will give unusual (usually slower) results...

Also posted in Vector | Tagged , | 1 Comment

Hill Climbing

By Zevan | May 4, 2009
CLICK HERE TO COPY
Actionscript:
  1. var target:Array = ("actionsnippet").split("");
  2. var leng:int=target.length;
  3. var iterations:int = 0;
  4.  
  5. var alphabet:Array = ("abcdefghijklmnopqrstuvwxyz").split("");
  6. var search:Array = randomString();
  7. var indices:Array = new Array();
  8. for (var i:int = 0; i<leng; i++) indices.push(i);
  9.  
  10. addEventListener(Event.ENTER_FRAME, onLoop);
  11. function onLoop(evt:Event):void {
  12.     for (var i:int = 0; i<10; i++){
  13.         if (indices.length> 0){
  14.            var ii:int = int(Math.random()*indices.length);
  15.            var index:int = indices[ii];
  16.          
  17.            search[index] = randomChar();
  18.            
  19.            if (search[index] == target[index]){
  20.                indices.splice(ii,1);  
  21.            }
  22.            trace(search);
  23.            iterations++;
  24.         }else{
  25.             trace("found after "+iterations+" iterations");
  26.             removeEventListener(Event.ENTER_FRAME, onLoop);
  27.             break;
  28.         }
  29.     }
  30. }
  31. function randomChar():String { return alphabet[int(Math.random()*alphabet.length)]; };
  32. function randomString():Array {
  33.     var str:Array = new Array();
  34.     for (var i:int = 0; i<leng; i++) {
  35.         str.push(randomChar());
  36.     }
  37.     return str;
  38. }

A little random hill climbing...

Here are the last few iterations... lowest number of iterations I noticed was round 250...

....
j,c,t,i,o,n,s,n,i,p,p,e,t
y,c,t,i,o,n,s,n,i,p,p,e,t
s,c,t,i,o,n,s,n,i,p,p,e,t
w,c,t,i,o,n,s,n,i,p,p,e,t
e,c,t,i,o,n,s,n,i,p,p,e,t
j,c,t,i,o,n,s,n,i,p,p,e,t
z,c,t,i,o,n,s,n,i,p,p,e,t
l,c,t,i,o,n,s,n,i,p,p,e,t
f,c,t,i,o,n,s,n,i,p,p,e,t
a,c,t,i,o,n,s,n,i,p,p,e,t
found after 361 iterations

Also posted in misc, strings | Tagged , | 5 Comments

Vector.sortOn()

By Zevan | April 11, 2009
CLICK HERE TO COPY
Actionscript:
  1. var a:Vector.<Sprite> = new Vector.<Sprite>();
  2.  
  3. trace("unsorted");
  4. for (var i:int = 0; i<10; i++){
  5.     var s:Sprite = new Sprite();
  6.     s.x = int(Math.random()*100);
  7.     a.push(s);
  8.     trace(s.x);
  9. }
  10.  
  11. quickSortOn(a, "x", 0, a.length-1);
  12.  
  13. trace("sorted");
  14. for (i= 0; i<10; i++){
  15.     trace(a[i].x);
  16. }
  17.  
  18. // modified code from kirupa.com
  19. // http://www.kirupa.com/developer/actionscript/quickSort.htm
  20. function quickSortOn(a:Vector.<Sprite>, prop:String, left:int, right:int):void {
  21.     var i:int = 0, j:int = 0, pivot:Sprite, tmp:Sprite;
  22.     i=left;
  23.     j=right;
  24.     pivot = a[Math.round((left+right)*.5)];
  25.     while (i<=j) {
  26.         while (a[i][prop]<pivot[prop]) i++;
  27.         while (a[j][prop]>pivot[prop]) j--;
  28.         if (i<=j) {
  29.             tmp=a[i];
  30.             a[i]=a[j];
  31.             i++;
  32.             a[j]=tmp;
  33.             j--;
  34.         }
  35.     }
  36.     if (left<j)  quickSortOn(a, prop, left, j);
  37.     if (i<right) quickSortOn(a, prop, i, right);
  38. }
  39. /* outputs something like:
  40. unsorted
  41. 26
  42. 33
  43. 20
  44. 63
  45. 7
  46. 68
  47. 75
  48. 39
  49. 67
  50. 53
  51. sorted
  52. 7
  53. 20
  54. 26
  55. 33
  56. 39
  57. 53
  58. 63
  59. 67
  60. 68
  61. 75
  62. */

This demo is my first quick stab at using at a sortOn() function for the Vector class. It sorts a Vector of Sprites by their x property.

Recently there were a few times when I was prototyping ideas and suddenly realized that I needed to change my Vector to an Array because I needed to use sortOn().(If you don't already know, there is no built in sortOn() method for the Vector class). In the past I spent some time with sorting algorithms, bubble, insertion etc... so I knew I could pretty easily write my own sortOn(), but I also realized that a generic implementation wouldn't be easy/possible without loosing the type of the Vector. What I mean is, if you have a Vector of Sprites, you need a sorting method that takes a Vector.< Sprite > type as an argument (as seen above), if you have a Vector of TextFields you need a Vector.< TextField > type as an argument. You could of course use a generic type, but this kind of defeats the purpose of using a vector in the first place...

I will likely post a revised version of this in the near future with a slightly improved implementation of QuickSort. I haven't spent that much time with this, but If I recall correctly this is not the ideal implementation. I ported this code from a nice Kirupa tutorial and modified it to sort based on a property...

Also posted in Object, Vector, associative arrays, sortOn | Tagged , | 3 Comments

Fracture a Number

By Zevan | April 8, 2009
CLICK HERE TO COPY
Actionscript:
  1. var target:Number = 1024;
  2. var slices:Array = [target];
  3. var leng:int = 11;
  4.  
  5. for (var i:int = 0; i<leng-1; i++){
  6.      var index:int = int(Math.random()*slices.length);
  7.      var val:Number = slices[index];
  8.      var rand:Number = Math.random() * val/2;
  9.      slices[index] = val - rand;
  10.      slices.push(rand);
  11. }
  12.  
  13. trace(slices);
  14.  
  15. // test that they all add up
  16. var sum:Number = 0;
  17. for (i = 0; i<slices.length; i++){
  18.     sum += slices[i];
  19. }
  20. trace("test that they all add up: ", sum);

The above snippet creates an array of a specified length whose elements all add up to the variable target. Here is some example output:


165.31133050055192,322.23456030456015,
257.47582363389245,26.9984893942173,1.96283924962002,
5.466277873168191,21.362282634705164,62.68168197512457,
76.63028224500404,36.27274381401516,12.558309228795265,35.04537914634583
test that they all add up: 1024

Also posted in misc | Tagged , | Leave a comment