In the good old Java world ( not that i’m that familiar with it ) real data structures are a well non secret. Not only in Java but in all older object oriented progaming languages exists different of Design Patterns for effecient data structures and fast access to data structures for different kind of use cases.
With data structures i don’t mean an normal or byte array which might be the data structures an the flash world, because you use it without waisting any thought of it ( me included ). in the very most situations were you used the Flash plattform right now this might be ok, because often you don’t have the mass of data. So the performance of the Flash Player is well enough.
But the possiblities of the Flash Plattform are growing ( very fast in the last time :) ) and more and more applications ( also real applications ) are written for the web ( or for both worlds if you use AIR ).
So you might now run in the situation to build an realy big application which has to handle a lot of data and you have to think about performance. One big thing in performance is the datastructure itself. Each application is different. Is it important for your app to write data fast or read it fast; which happens mor often; do you process all data always complete or do you just need a small part of it ?! For each use case there is for sure a very well data structure.
Data Structure
Example A: Joa Ebert had a talk on Flash Forum Conference 09 (which also inspired me for the second part – see below – and made me happy to see that datstructures are already present in the flash world ) where he presented his data structure for the audio tool. When they output the audio stream they always have to process a (large) list of single audio-items ( one for each bit of the stereo 44.100kHz Audiostream ). -> Fast access of elements (always complete and in the same order ) one by one. Best datastructure: Linked List.
What is a linked list ? A linked list is an list of very light weight elements where each element holds a reference to it next neightbour. In your app you only have one reference to the first node of this list and that loop over the list by setting the reference further (example for calculating the length of the list):
/** * Returns the cardinality of the map - the number of elements * @return A value of <code>Int</code>, the number of elemets */ public function card():int{ var ref:SimplyLinkedListElement = this._root; var card:int = 0; while( ref ){ ref = ref.next; ++card; } return card; } |
You also could insert a new element very fast ( if it is ok to put it on the first position ). You just have to change the reference to the root element to the new element and link the next reference of the new element to the old root element.
Example B: You have an application which often reads from its datastructure, but always only searches on random element. If you would use a linked list, in the worst case you have to look at each element if it is the searched one. Looking at each element is to expensive. One solution are Tree-Datastructures. The simplest is the Binary Tree. Again you have an root reference. But each element now have to references to the next elements. One to the right ( bigger element ) and one to the left ( smaller element ). If you insert an element in the tree you’ll look at the existing node. Is your new node larger, you will look at the right reference, is it smaller at the left reference of the node. Is the reference empty you could place it there.
If not you will look at the data again. In the worst case you now don’t need to look at each element because you have a structure and will find the fastest way by compare the keys. The search is logarithmic not linear.
Garbadge Collector / Pooling
The next big thing with datastructure and performance in the Flash Player is the Garbadge Collector ( which it don’t were that aware before Joas talk ). So the Garbadge Collector is realy slow. So we have to avoid that he is coming to action. How ? By reusing your elements or pool them.
The Garbadge Collector will free space in the memory if there are no more references to an allocted section. So you have to control the references. In your mass of objects you should not drop unused items, because the are not used for now, but pool them. You remove the reference from the main datastructure to the unused element and reference it within a list of unsed elements. When you now need a new element you don’t have to create a new one ( which is also realy expensive ) but you could take one element from you pool.
Find attached some of my older datastructures (LinkedList, DoubleLinkedList, BinarySearchTree) which i just updated so they will now use pooling for unused elements ( and of course there are also some simple FlexUnit Testcases included ! :) – Florian Salihovic).
Binary Search Tree
Here is one longer example of an Binary Search Tree implementation. It’s not fully done yet, but most common methods are implemented and ready to use. I’m sure the is some optimaziation potential (please let me know if you find anything, then i will correct it).
Because there are no real Generics in ActionScript this is an Example for a Map which uses an String value as Key and an Number value as data. This has of course to be adopted for your case:
package com.nonstatics.as3collection.map.MapAsBinarySearchTree { /** * Implements a map as binary search tree * * @author Sebastian Martens http://www.sebastian-martens.de || http://blog.sebastian-martens.de * @copyright Creative Commons, free to use "as is" * @date $Id: MapAsBinarySearchTree.as 21 2009-05-18 20:06:59Z dinnerout $ */ public class MapAsBinarySearchTree { /** * root reference */ private var _root:MapAsBinarySearchTreeElement; /** * root reference of pooled elements */ private var _poolRoot:MapAsBinarySearchTreeElement; /** * cardinality of map */ private var _cardV:int = 0; /** * is vadinality valid */ private var _validCard:Boolean = false; /** * construction method */ public function MapAsBinarySearchTree( n:int = 0 ){ // build pool elements to avoid construction on runtime while( n>0 ){ this.poolPush( new MapAsBinarySearchTreeElement() ); --n; } this._cardV = 0; this._validCard = false; } /** * Test if Map is an empty map * @return A value of code>Boolean, if map is empty */ public function isEmpty():Boolean{ return this._root == null; } /** * Returns the cardinality of the map - the number of elements * @return A value of <code>Int</code>, the number of elemets */ public function card():int{ if( this.isEmpty() ) return 0; if( this._validCard ) return this._cardV; this._cardV = this._card( this._root ); this._validCard = true; return this._cardV; } /** * recursiv card() helper method * @private * @param node value of <code>MapAsBinarySearchTreeElement processed node */ private function _card( node:MapAsBinarySearchTreeElement ):int{ if( !node ) return 0; return 1 + this._card( node.l ) + this._card( node.r ); } /** * returns an element by its key * @param key value of </code><code>String</code>, search key * @return value of <code>MapAsBinarySearchTreeElement</code> */ public function getElement( key:String ):MapAsBinarySearchTreeElement{ return this._getElement( this._root, key ); } /** * recursive helper method for getElement * @private * @param node value of <code>MapAsBinarySearchTreeElement</code>, processing node * @param key value of <code>String</code>, search key */ private function _getElement( node:MapAsBinarySearchTreeElement, key:String ):MapAsBinarySearchTreeElement{ var l:MapAsBinarySearchTreeElement; var r:MapAsBinarySearchTreeElement; if( !node ) return null; if( node.key == key ) return node; return ( key > node.key )?this._getElement( node.r, key ):this._getElement( node.l, key ); } /** * checkes if an value v is in the map * @param v a value of <code>Number</code>,element value to search for * @return true if value is containing in one element */ public function containsValue( v:Number ):Boolean{ return this._containsValue( this._root, v ); } /** * recursive helper method for containsValue * @private * @param node value of <code>MapAsBinarySearchTreeElement processed node * @param v value of </code><code>Number</code>, search value * @return value of <code>Boolean</code>, value found in tree */ private function _containsValue( node:MapAsBinarySearchTreeElement, v:Number ):Boolean{ if( !node ) return false; if( node.value == v ) return true; return ( v > node.value )?this._containsValue( node.r, v ):this._containsValue( node.l, v ); } /** * Test if this map equals to another map ( equals means same elements not same structure ) * @param map value of <code>MapAsBinarySearchTree</code> to test this map with * @return a value of <code>Boolean</code> */ public function isEqualTo( map:MapAsBinarySearchTree ):Boolean{ if( this == map ) return true; if( this.isEmpty() && map.isEmpty() ) return true; if( (this.isEmpty() && !map.isEmpty()) || (!this.isEmpty() && map.isEmpty()) ) return false; if( this.card() != map.card() ) return false; return this._isEqualTo( map, this._root ); } /** * recursive helper method for isEqualTo * @param map value of <code>MapAsBinarySearchTree</code>, map to compare with * @param node value of <code>MapAsBinarySearchTreeElement, processing node of this map * @return false if element not in reference tree */ private function _isEqualTo( map:MapAsBinarySearchTree, node:MapAsBinarySearchTreeElement ):Boolean{ if( !node ) return true; var item:MapAsBinarySearchTreeElement = map.getElement( node.key ); if( !item || item.value!=node.value ) return false; return this._isEqualTo( map, node.l ) && this._isEqualTo( map, node.r ); } /** * inserts a new value into the map * @param k value of </code><code>String</code>, key * @param v value of <code>Number</code>, value * @return this */ public function insert( k:String, v:Number ):MapAsBinarySearchTree{ // invalidate cardinality this._validCard = false; // empty map if( !this._root ){ var item:MapAsBinarySearchTreeElement = this.poolPop(); item.value = v; item.key = k; item.l = null; item.r = null; this._root = item; return this; } // non empty map this._insert( this._root, k, v ); return this; } /** * recursive helper method for insert method * @param node value of <code>MapAsBinarySearchTreeElement</code>, processed node * @param k value of <code>String</code>, key * @param v value of <code>Number</code>, value */ private function _insert( node:MapAsBinarySearchTreeElement, k:String, v:Number ):void{ // existing keys will be updated if( node.key == k ){ node.value = v; return; } var item:MapAsBinarySearchTreeElement; // insert left or right if( k > node.key ){ // right node exist if( node.r ){ this._insert( node.r, k, v ); // new node at right leave }else{ item = this.poolPop(); item.key = k; item.value = v; item.l = null; item.r = null; node.r = item; } }else{ // left node exists if( node.l ){ this._insert( node.l, k, v ); // new node at left leave }else{ item = this.poolPop(); item.key = k; item.value = v; item.l = null; item.r = null; node.l = item; } } } /** * returns if the map contains an element with k * @param k value of <code>String</code>, key to search for * @return true if mao contains key */ public function contains( k:String ):Boolean{ return this._contains( k, this._root ); } /** * recursive helper method for contains * @param k value of <code>String</code>, key to search for * @param node value of <code>MapAsBinarySearchTreeElement</code>, start node * @return */ private function _contains( k:String, node:MapAsBinarySearchTreeElement ):Boolean{ if( !node ) return false; if( node.key==k ) return true; if( k > node.key ) return this._contains( k, node.r ); if( k < node.key ) return this._contains( k, node.l ); return false; } // Traverse the tree complete private function _containsF( k:String, node:MapAsBinarySearchTreeElement ):Boolean{ if( !node ) return false; return (node.key==k) || this._containsF(k,node.l) || this._containsF(k,node.r); } /** * returns the rightes leave of an part tree * @private * @param node value of <code>MapAsBinarySearchTreeElement, start node * @return latest right leave from node */ private function _getRight( node:MapAsBinarySearchTreeElement ):MapAsBinarySearchTreeElement{ // already latest right node if( !node.r ) return node; // find right while( node.r ){ node = node.r; } return node; } /** * returns the most left leave of an part tree * @private * @param node value of <code>MapAsBinarySearchTreeElement</code>, start node * @return latest left leave from node */ private function _getLeft( node:MapAsBinarySearchTreeElement ):MapAsBinarySearchTreeElement{ // already latest right node if( !node.l ) return node; // find right while( node.l ){ node = node.l; } return node; } /** * finds the parent node of the element with key k * @private * @param k value of <code>String</code> * @param nod value of <code>MapAsBinarySearchTreeElement</code>, processed element * @return parent node of node with key k, null if not found */ private function _findKeyParent( k:String, node:MapAsBinarySearchTreeElement ):MapAsBinarySearchTreeElement{ // root node to remove if( node.key == k ) return node; if( !node ) return null; if( (node.l && node.l.key == k) || (node.r && node.r.key == k) ) return node; return (k > node.key)?this._findKeyParent( k, node.r ):this._findKeyParent( k, node.l ); } /** * removes an element by its key * @param k value of <code>String</code>, key of element to remove */ public function remove( k:String ):MapAsBinarySearchTree{ // empty list if( this.isEmpty() ) return this; // search for parent node of key element var searchN:MapAsBinarySearchTreeElement = this._findKeyParent( k, this._root ); var ref:MapAsBinarySearchTreeElement; var ref2:MapAsBinarySearchTreeElement; // parent of key found, remove element if( searchN ){ // invalidate cardinality this._validCard = false; // remove root node if( searchN == this._root && this._root.key == k ){ ref = this._root; if( !this._root.l && !this._root.r ){ this._root = null; // only root element this.poolPush( ref ); return this; } if( this._root.r && !this._root.l ){ this._root = this._root.r; // empty left tree this.poolPush( ref ); return this; } if( !this._root.r && this._root.l ){ this._root = this._root.l; // empty right tree this.poolPush( ref ); return this; } // both trees are filled ref2 = this._root.r; this._root = this._root.l; this._getRight( this._root ).r = ref2; this.poolPush( ref ); return this; // remove node from tree middle }else{ // found in left tree if( searchN.l && searchN.l.key == k ){ ref = searchN.l; searchN.l = searchN.l.l; if( searchN.l ){ this._getRight( searchN.l ).r = ref.r; }else searchN.l = ref.r; this.poolPush( ref ); return this; // found in right tree }else{ ref = searchN.r; searchN.r = searchN.r.l; if( searchN.r ){ this._getRight( searchN.r ).r = ref.r; }else searchN.r = ref.r; this.poolPush( ref ); return this; } } }else return this; return this; } /** * @return the ratio of left to right tree card * large number means heavy weight on left side, negavtive numbers means weight on right side */ public function getTreeBalance():Number{ if( this.isEmpty() ) return 0; var l:Number = this._card( this._root.l ); var r:Number = this._card( this._root.r ); if( l > r ) return l / Math.max( r, 0.01 ); if( r > l ) return -1* ( r / Math.max( l, 0.01 ) ); return 0; } /** * creates an string representation of the map * @return String value of map */ public function toString():String{ return this._toString( this._root ); } /** * recursice helper method for toString * @param node value of <code>MapAsBinarySearchTreeElement</code>, processed node * @return string reprsentation */ private function _toString( node:MapAsBinarySearchTreeElement ):String{ if( !node ) return ""; return this._toString( node.l ) + ' {k:' + node.key + ' v:'+ node.value +'} ' + this._toString( node.r ); } /** * Returns the cardinality of the pool - the number of elements * @return A value of <code>Int</code>, the number of elemets */ public function getPoolSize():int{ var ref:MapAsBinarySearchTreeElement = this._poolRoot; var card:int = 0; while( ref ){ ref = ref.r; ++card; } return card; } /** * removes all unused elements from pool */ public function emptyPool():void{ this._poolRoot = null; } /** * pushed an element to the local pool * @private * @param n a value of <code>MapAsBinarySearchTreeElement</code> Item to push into pool */ private function poolPush( n:MapAsBinarySearchTreeElement ):void{ // empty pool if( this._poolRoot == null ){ this._poolRoot = n; this._poolRoot.r = null; this._poolRoot.l = null; // non empty pool, keep reference }else{ n.r = this._poolRoot; this._poolRoot = n; this._poolRoot.l = null; } } /** * gets an objects from pool. if pool is empty element will be created * @private * @return a value of <code>MapAsBinarySearchTreeElement</code> - single list item */ private function poolPop():MapAsBinarySearchTreeElement{ // non empty pool, take first from pool if( this._poolRoot ){ var res:MapAsBinarySearchTreeElement = this._poolRoot; this._poolRoot = this._poolRoot.r; res.r = null; // empty reference to pool nodes res.l = null; return res; } // empty pool, create new element return new MapAsBinarySearchTreeElement(); } } } |
… to be continued.
cheers,
Sebastian