[AS3] Do I need an Object, an Array or a Dictionary?

[Rezmason]

Hey, guys. Could someone tell me about when to use Arrays, Objects (associative arrays) and Dictionaries? My latest project iterates through a slew of data, and I want to get the most out of my for loops.

All of the objects I'm iterating are of the same class, and there are about sixty-two thousand of them, at first. Optimization then brings the tally down to about six thousand, but I'm certain I can improve the data structure and logic of my program to run in tighter circles, so to speak.

I already understand the differences between Dictionary, and Object and Array implementation. I would like to know which is more suitable for different tasks. I'm using more Arrays now than I know I ought to, but what's nice about them is when you're iterating through something huge (like sixty-two thousand elements), a for loop going through an array can stop at a certain index, wait, and continue, so that Flash doesn't time out. A for-in loop won't do that, and as far as I know, you can't iterate through Objects or Dictionaries by index.

So. Recap: what should I store my data-slew in, to get the most out of Flash?

[Aquilonian]

Dictionaryes i still cant found a use for them.
But you know, you should consider using XML too, with xml you can have the advantages of both using arrays and objects, like for example, if the objects in a array from index 10 to 150 are from a certain type you can get them out of the XML using that type and loop just on those

[eudora]

Correct me if I am wrong...

For a Dictionary, it works like a real dictionary. It will be the perfect class if you know what you are looking for... just like in real life if you are looking for a particular word (ID) you can easily flip to the page in a dictionary to retrieve its meaning...

I am implementing them if I know exactly what item id I am looking for..

[Rezmason]

I never knew that about the E4X, Aquilonian. I'll check that out. :)

In my program, eudora, I do know exactly what to search for in the Dictionary. It just so happens that I'm using String objects as keys in my Dictionary, for now. But I can do a similar search in an Object, which uses conversion to String anyway:


// implementing Dictionary
var dict:Dictionary = new Dictionary();
var n:Node = new Node(); // don't worry about what Node is
n.index = "abc";
dict[n.index] = n;

// implementing Object
var obj:Object = new Object();
var n:Node = new Node();
n.index = "abc";
obj[n.index] = n;

The Dictionary uses strict equality to refer to an element of index n, while the Object first converts n to a String and then uses plain equality to refer to the element at that index. It's my guess that String conversion and plain equality are faster than strict equality, but again, I really don't know.

What I was gambling on when I first tried the Dictionary object, though, was binary searching. If Dictionary objects in AS3 are anything like maps in C++, an action performed with a Dictionary should have logarithmic performance (compared to an Array's linear performance). (Log is better than linear.) Does anybody know whether this is true?

[eudora]

Hmm my instinct would be that Dictionary objects will be more like maps in C++

Once I "store" the different elements into a Dictionary, there is an immediate 1-1 mapping thus no searching per say is needed... just like the word "apple" would immediately be stored in page 1 of a read dictionary. If thats the case, it should perform faster then an array in terms of searching...

For the Object vs Dictionary speed I wouldn't be sure... how about you run thru best/worse cast scenarios for all 3 classes and time their results? :)

Do let me know the result if you do so though.. hehe

[Rezmason]

Yeah, I probably will... though I was hoping that somebody else already has... I'll get back to you on that.

[senocular]

Objects - Use to create hashes with string keys (alpha-numeric).
Dictionaries - Like Objects but using any kind of key - doesn't have to be string; best use case is creating an object to store additional variables for instances provided to your class despite those instances not having definitions for those variables or for having a list of instances where each instance can be easily looked up.
Arrays - Like objects except using numeric keys and by such providing order to the elements. With arrays you can have your elements in a specific order based on their key (along with methods that work with that order) unlike objects whose order is mostly arbitrary.

With each you're basically just creating variables. Just like you would assign a variable to a movie clip, keys in these objects are the names of the variables stored in them.


If you're confused about Dictionaries, consider this example:
You have a class called ShapeCollection that takes a number of shapes and determine's their combined area. It has the methods
- addShape(shape:Shape);
- removeShape(shape:Shape);
and the property
- totalArea:Number;

Everytime you add a shape, you have to store the shape in a list so it can be accounted for when determning the total area of all the shapes in the collection. The shape would also need to be easily found when removeShape is called. Options:
List as Object: This is an idea, but what would you use as a key? There's no unique identifier for Shape instances that would be suitable for such a thing. You could make your own key with an incrementing value, but then you' be better off using...
List as Array: This makes more sense than object. You can easily add Shapes to a numerically indexed list and each will have their own spot. However, to remove a Shape, you have to loop through the entire list which, depending on how many shapes you have, could take a while.
List as Dictionary: This is your best option. As a Dictionary, the Shape instance itself is the key and since each instance is unique, you can never have the same key (otherwise its the same instance). When you need to remove the instance from the list, you simply delete it from the Dictionary, no looping is required.

For the area, you can start to see another problem of looping. As you get more shapes added to your collection, you would have to loop through more and more shapes. This, however, can be easily overcome by not looping through the shapes, but rather, just adding the area of an added shape to a saved total and then removing that area from the total when the shape is removed. But what if that calculation of area is costly in terms of performance, say, for example, if you are using BitmapData to determine a per-pixel area? Then you would want to calculate area as less as possible and not, as it is now, twice, once when adding the shape and once when removing it. What you can do is calculate the area once, and then just use that area for that shape whenever it is needed to be used (and we're under the assumption that the areas of these Shape instances is not dynamic and will not change). The problem here is that the shape class is closed and a new property like area can't just be defined within it. What you can do instead is save these values in the ShapeCollection. But how?
Use Object: Same issue of having a key that relates to your Shapes
Use Array: Same issue of needing to loop through a list of Shapes to find shapes.
Use Dictionary: Easily store the area for each Shape instance by keeping a Dictionary for the areas where each Shape key would represent the area for that Shape.

pseudo:

var shapeList:Dictionary = new Dictionary();
var shapeAreas:Dictionary = new Dictionary();
var totalArea:Number;

function addShape(shape:Shape) {
if (shape in shapeList) return;
shapeList[shape] = true;

var area;
if (shape in areaList) {
area = areaList[shape];
}else{
area = getArea(shape); // expensive calc
areaList[shape] = area;
}
totalArea += area;
}

function removeShape(shape:Shape) {
if (!(shape in shapeList)) return;
delete shapeList[shape];
totalArea -= areaList[shape];
}

[Aquilonian]

So, its like Dictionaryes put pseudo properties on sealed classes like isOnShapeList, area and things of the such
I dont understand however,how they can be a replacement for arrays, i mean,if i have a tank class and want to create 50 instances, inside a loop i can go
tank[i] = new tank();
but how i do that if i want to put the tanks inside a Dictionary? Cos with arrays tank[i] is the reference,and if with dictionaryes i use the same var as a reference how can i acecc the items later?
i mean
var a = new tank();
myDict[a] = a;
?

[senocular]

You would use a for..in or a for each..in (if the value is the same as the key) to loop through a dictionary.

If you need a key to reference an instance other than the instance itself (such as whatever i is), then you would use an object or array.

[eudora]

Yeah, I probably will... though I was hoping that somebody else already has... I'll get back to you on that.


any results to share abt this 3 classes? :hr:

[Rezmason]

Not yet, I've been really busy at my job. :) ...But also I'm worried that the benefits of using one data object over the others depends heavily on the implementation. A normal test procedure would be something like, "iterate over a million elements" or "cross-reference a million elements", but depending on what's being done to the elements, Flash might optimize your code one way and not another. It's all very shaky.

What I will do, though, is test each data type in my program ten times in each instance that I need a data object, and then I'll compare results and put them up here. They may have no value, but they'll be here.

[Rezmason]

HOLY SMOKES.

I've been indexing my elements with Strings! By switching them to int, and using the Dictionary, I'm seeing a ridiculous speed hike. Sweet Jesus. We're talking about an order of magnitude difference here.

This is an advantage that the Dictionary class has over the Object class– I can use any sort of object as a key. I'll compare the Dictionary next with Arrays, since they can also use numeric indexing... I'm betting the Dictionary will be faster still.

EDIT: turns out I the gargantuan Dictionary's still slower than a gargantuan Array. This goes to show that if you know how to structure your data well, you can get by with Flash's basic bits. This is also an indication of AS3's true power– I'm pretty sure I wouldn't be seeing this level of performance in AS2.

[CarlLooper]

:)

[Rezmason]

I should also add that I can only use Array for my giant data structure because my elements can have unique integer indices. I'm sure there are other situations where using Object and Dictionary are more useful. The gBlog (http://www.gskinner.com/blog/archives/2006/07/as3_dictionary.html) has something to say about that.

[CarlLooper]

You should try a gargatuan ByteArray - I found this astonishingly fast - and I'm a C++ programmer so I know what to compare it against.

Note that although a ByteArray is called such it can be used to store any size datatype.

If you test it out - use [] indexing rather than the available read/write functions - and code your own addressing (byteIndex = 4 * intIndex, etc)

Carl

[senocular]

be sure you are using int for your array indices; arrays will have better look up times using int (and if not using int, cast to int within the array access (myArray[int(index)])

[Rezmason]

I'm doing that, and I'm also using integers to store array lengths (so that my for loops' countervalues are direct comparisons like "i < arrayLength" and not referenced like "i < array.length").

I'm having some weird issues with the ByteArray, CarlLooper, but I'll give it another try.

[senocular]

ByteArrays are for holding integer data. You wouldn't use it to reference instances.

[Rezmason]

Ohhhhhhhhh. Alright, piece'o'cake; I can store my references in an Array, and store their indices in the ByteArray. Seems roundabout, though.

[senocular]

why do you need to do that?

[Dazzer]

So does that mean instead of creating a hashtable with object, you should use a dictionary using Strings to get a speed increase?

[CarlLooper]

I only mentioned ByteArray in the context of performance.

But working with ByteArray is only recommended if the boundary's of the problem to be solved are very well specified, ie. allowing you to hand code an optimised solution closer in style to assembly like instructions.

But if the problem is a moving target you are better off trading performance for better code management flexibility - ie. using the more dynamic (and therefore slower) functionality of the other classes.

Carl

[Rezmason]

I agree, Carl. In this context, I don't think I could benefit, but it's cool that the ByteArray allows for that low level of performance improvement.


So does that mean instead of creating a hashtable with object, you should use a dictionary using Strings to get a speed increase?

That's been hard to determine. The performance of a String-indexed Dictionary and an Object, as far as I can tell through testing, are very close. The same goes for an int-indexed Dictionary and an Array.

But if you can index your elements with integers rather than Strings, using an Array is way faster than using an Object.

[Rezmason]

UPDATE: You know what's even faster than an Array? A linked list. If your data has no order, iterating through a linked list with a while loop is rapid. I've cut the speed of my function from ~60ms to ~40ms, by changing one Array to a linked list.

[CarlLooper]

Yeah - linked lists don't have the overhead of recomputing an address for each node.

Carl

[Dazzer]

What do you mean... changing 1 array to a linked list? O.o

[CarlLooper]

The display list is an example of a linked list. Each element of the display list is a separate object ( a DisplayObjectContainer ) at an arbitrary location in memory. But each object is linked - not by their position in memory (which is arbitrary) but by the references (parent/getChildAt) each holds with respect to their neigbouring object in the list.

You run through the list by following these links rather than having to spend time looking up the address of each object in a lookup table of such addresses (an array of objects).

The beauty of such is that not only can such a list be iterated more efficiently - it can be re-organised more efficiently. Insertion and deletion does not incur the overhead of re-sorting a large lookup table of references (or table of table etc) - as all one needs to do is change a few references - where the changes occured.

Indeed arrays in Actionscript (as distinct from native arrays) will have this sort of infrastructure operating behind the scenes.

But by creating your own linked list you can tailor the behaviour of such to your own particular goal - ie. optimising it - because you know (which the compiler can't) what your particular goal is.

Carl

http://en.wikipedia.org/wiki/Linked_list (http://en.wikipedia.org/wiki/Linked_list)

[senocular]

Rezmason, do you have any comparisons you can provide from your testing? It'd be interesting to see how each approach stands up.

[Rezmason]

Since you asked nicely, I'll put something together soon. :-)

I've just replaced all my large and frequently-updated arrays with linked lists, and my updating function now runs at ~25ms (40fps). When I started the thread, I was iterating through String-indexed Dictionaries, and the same updating function ran at ~110ms (9fps). On more capable machines, I expect my program to run even faster.

I've got one more, small, frequently-accessed Array (or set of Arrays) that I'd like to swap with something faster. This last Array never exceeds a length of eight, and rarely exceeds a length of two. I just might unroll it, frankly. That's when you speed up a for loop by multiplying the elements you process, but also multiply the loop's step by the same amount:

//normal iteration
for (ike = 0; ike < a.length; ike++) {
trace(ike);
}

//unrolled iteration
for (ike = 0; ike < a.length; ike+=5) {
trace(ike);
trace(ike+1);
trace(ike+2);
trace(ike+3);
trace(ike+4);
}

In this case, I'd just unroll the entire eight-element Array. I haven't tried it yet, but I bet this will increase the speed again. I hope to chop off another ten milliseconds; getting 100fps out of a system that iterates through 62,000 nodes on a two-year-old iBook just might earn this project a spot in my portfolio. :-)

But yeah, linked lists. Hot damn. Expect a proof of concept soon.

[CarlLooper]

With apologys to Rez - I wrote this up in response to Dazzer's question - not to steal any thunder from Rez ...




package
{
public class Node
{
public var child:Node;
public var data:Number;
public var hasChild:Boolean;

public function Node()
{
hasChild = false;
}
}
}
Timeline code:



import Node;

var i:uint;
var t1,t2,t3:Number;
var numNodes = 1000000;
var dummy:Number;

// create a root node
var rootNode:Node = new Node();
// and a general purpose reference to any node
var node:Node;

// create an Array and populate with random numbers
var array:Array = new Array()
for(i=0; i<numNodes; i++)
{
array[i] = Math.random();
}

// create a linked list version of the array
node = rootNode;
for(i=0; i<numNodes; i++)
{
node.data = array[i];
node.hasChild = true; // not yet but will be in next line
node = node.child = new Node();
}
node.hasChild = false;

//======================
// demo that linked list
// and array have the same
// data for first 10 elements
//=======================

node = rootNode;
for(i=0;i<10;i++)
{
trace(String(node.data) + " == " + String(array[i]) );
node = node.child;
}

//======================
// performance test
//======================

trace("");
trace("perfromance test")

t1 = getTimer();
//---------------------------
// traverse linked list
node = rootNode;
dummy = node.data;
//trace(dummy)
while(node.hasChild)
{
dummy = node.data;
node = node.child;

//trace(dummy);
}
//---------------------------
t2 = getTimer()
//---------------------------
// traverse array
for(i=0; i<numNodes; i++)
{
dummy = array[i];
//trace(dummy);
}
//---------------------------
t3 = getTimer();

trace(t2-t1);
trace(t3-t2);

And results:



0.7603113758377731 == 0.7603113758377731
0.01426431443542242 == 0.01426431443542242
0.10728629864752293 == 0.10728629864752293
0.11245068861171603 == 0.11245068861171603
0.6708445260301232 == 0.6708445260301232
0.3448709724470973 == 0.3448709724470973
0.3217642526142299 == 0.3217642526142299
0.6300622676499188 == 0.6300622676499188
0.7570899371057749 == 0.7570899371057749
0.47874040994793177 == 0.47874040994793177

perfromance test
67
112

[Rezmason]

Hey, whatever works. :D Thanks, Carl!

[CarlLooper]

:)

[eudora]

Thanks Carl and Rez for the detail explanation.. I HAVE to find time to go through my existing code and improve on its efficiency.. if only I have more time away from work... ;(

[Rezmason]

I've just put up the latest working version of my project. You can find it here (http://www.rezmason.net/wireworld/index.html). :-) It's the Wireworld computer, which you can read about here (http://www.quinapalus.com/wi-index.html). It'll get a few more features soon, to start/pause/step through the system and to slow down the rate that it updates. And there'll be some other nice features.

Thanks again for all the data structure-related help! Let me know how fast it runs; the FPS counter is in the bottom-right corner.

[CarlLooper]

About 60 fps on my rust bucket.

Nice work by the way.

Carl

[Aquilonian]

Can someone please explain one thing?
I dont understand how to iterate through all the items on the linked list
I mean,


while(node.hasChild)
{
dummy = node.data;
node = node.child;

//trace(dummy);
}


how can
node.hasChild
work as a loop?Isnt hasChild just one propertie?
Owww...my bad i think i see now...each iteration node will be the child of the node...
But anyway, how do you remove or add items in a liknked list like that one?I mean, how if you want to remove an item in the middle of the list?
Tankz

[senocular]

But anyway, how do you remove or add items in a liknked list like that one?I mean, how if you want to remove an item in the middle of the list?
Tankz

You need a method that will facilitate that.

Lets say you have a list of three items A through C where the linking is:
A -> B -> C

If you want to remove B, you would remove set A.child = B.child and set B.chils = null (and if using hasChild, set it to false as well, though the child reference's existence in itself can alternatively function as hasChild here without the need for the extra property). Then the list becomes
A -> C

With B floating off in memory somewhere, either retained through another reference or ready for the GC.

[Aquilonian]

Ok, thanks
SO, it is possible to remove an item without have to loop through the entire list, isnt it?
Yeas it is, im dumb asking such dumb things

[senocular]

Ok, thanks
SO, it is possible to remove an item without have to loop through the entire list, isnt it?
Yeas it is, im dumb asking such dumb things

Well, that depends on the set up of your list. My usage of link lists typically include not just a child link, but prev and next links refering to both the previous and next objects in the list
A <-> B <-> C

Then, if you have a reference to B, and you need to remove it from the list, all you need to do is reference A from B.prev, change A.next to C, and reference C from B.next and change C.prev to A.

Using just a child reference would require a loop through the list until you find the object that has a child property that references B then changing it to reference B.child instead of B

[Albright]

Currently I'm using for loops to iterate through several arrays of objects in my project (each array's objects are of the same type), and I've been trying to find a more elegant way. The linked list thing looks handy, and if it's faster too, all the better.

So if I have A -> B -> C, and I want to remove B, just setting C as A's child will work. I get that. But what if I want to remove A? Would A=B do it?

Or what if I wanted to do all this in a function of the class that A, B and C belong to? How would a node remove itself then? I haven't tried it yet, but would this=this.childNode work? Or would parent.childNode=this.childNode be better? On second thought, would having A call B.classFunction call C.classFunction call D.classFunction, etc, cause overhead which would make doing it this way a bad idea?

Thanks in advance.

[Rezmason]

I wouldn't rely on parent, because linked lists rely on references that are not based on the display list.

The way I implement linked lists is, each list begins with a node called a startNode, which is never used but links to the first Node in the list. There's also an endNode, which is originally equal to startNode. So at first, startNode->null (an empty list). To add a Node to the list, I go
endNode.next = newNode;
endNode = newNode;[code]

Note that the startNode reference never changes, but the startNode.next reference does. Eventually, startNode->A->B->C->D--->N, endNode=N, and endNode.next=null. Splicing B out of the list is as easy as [code]A.next=C; To wipe out the end of the Array,
A.next=null, endNode=A; And To wipe the Array entirely,
startNode.next=null, endNode=startNode;

[Albright]

I wouldn't rely on parent, because linked lists rely on references that are not based on the display list.

Yeah, you're right, that doesn't make any sense. I was getting my mental lines crossed.


Eventually, startNode->A->B->C->D--->N, endNode=N, and endNode.next=null.

So you have a separate endNode variable which is always set to reference the last node? This isn't necessary if you only intend to iterate in one direction, as I do, right?

Thanks for your help. Still hoping for some info with regards to doing all this through functions of the class that the objects are instantiated from.

[Aquilonian]

nevermind

[Rezmason]

So you have a separate endNode variable which is always set to reference the last node? This isn't necessary if you only intend to iterate in one direction, as I do, right?

Thanks for your help. Still hoping for some info with regards to doing all this through functions of the class that the objects are instantiated from.

The endNode isn't used to iterate backwards. It could be if we were talking about a double-linked list, but it isn't. The endNode allows you to add new objects to the end of the linked list.

As for the functions you're looking for help with– you've got two classes, one that you instantiate your linked objects from (let's call it Node), and one that does the linking (let's call it LinkedList). LinkedList is the class that contains startNode, endNode, and all the helper functions. The Node class contains a Node reference that (at first) equals null, and some other properties. The Node class has no helper functions, only the LinkedList.

[Albright]

Okay, thanks for your help. I think I'm starting to get my brain wrapped around this now. I was going to try implementing this in my app today, but it didn't happen… I'll definitely pound away at it tomorrow.

[Aquilonian]

.

As for the functions you're looking for help with– you've got two classes, one that you instantiate your linked objects from (let's call it Node), and one that does the linking (let's call it LinkedList). LinkedList is the class that contains startNode, endNode, and all the helper functions. The Node class contains a Node reference that (at first) equals null, and some other properties. The Node class has no helper functions, only the LinkedList.
I was wondering how i could put all those functions in the LinkedList class and iterate through all the nodes with just one method call from the LinkedList class
Maybe senidng a function as parameter like this
public function iterateThroughAll(mf:Function){
//loop through all the list,get a ref of currentNode
mf(currentNode)
}
would that make things slow?
I want to make a class kind of array with push, remove, but im stuck when cames to put a function to iterate through all the nodes...cos with arrays its just a matter of using the index...

[Rezmason]

I want to make a class kind of array with push, remove, but im stuck when cames to put a function to iterate through all the nodes...cos with arrays its just a matter of using the index...

Precisely. So make a property of your linked list that always refers to the currently active data:


public class LinkedList {
public var currentData:Object;
private var startNode = new Node, endNode = startNode;
private var length:int = 0;
private var currentNode:Node;

public function pushNode(data:Object=null):void {
endNode.next = new Node(data);
if (endNode == startNode) {
currentNode = startNode.next;
currentData = currentNode.data;
}
endNode = endNode.next;
}

public function nextNode():void {
if (currentNode.next) {
currentNode = currentNode.next;
currentData = currentNode.data;
}
}
}

You know, maybe I should just make a LinkedList class. :D It'd save us all a heap of trouble.

[Aquilonian]

What i mean is, i want to put all that:
currentNode = firstNode;
while(currentNose.next){
//blablabla do things
currentNode = currentNode.next;
}
inside just a function of the LinkedList class but i dont know how
But by the other hand...is that the case of use a class?Just to save 3 lines of code?Im i overcomplicationg it?

[senocular]

while(currentNose.next){
hehe


... there are a couple of libraries out there with linked lists for AS3; if you want to see one, I'm sure you can google it.

[Aquilonian]

currentNose...lol
havent noticed that

[Rezmason]

There are a couple of libraries out there with linked lists for AS3; if you want to see one, I'm sure you can google it.

I should've done that. :/

I've put something together, though. If anyone wants a LinkedList class, I'll wrap it up nicely and post a link.

[smizzle]

I wrote myself a hash class since I also code in ruby and have gotten used to it. Basically it works like an object, but has a lot of the nice iterative methods that arrays have. I'll post the class if every one wants it.

[Rezmason]

Yeah, I'd like to see that. :-)

[smizzle]

Here ya go. It's pretty simple takes and object as a constructor extends proxy so you can dynamically access its properties then implements a lot of the array functionality, some of the method names are different. I usually just pass an inline function (ala js style)

[senocular]

Is this a finished class? At quick glance, it seems sortBy is incomplete.

[smizzle]

Ya things came up at work. I ran out of time, but I have some time today. I'll get that and a few other methods I wanted to implement done.

[smizzle]

Here's a new version. Also added a test file so you can see the syntax of each method and a bit of doco. Took out the sortBy method, didn't see a real use for it. Also added a toString method so it works with trace statements.

[Rezmason]

Thanks, smizzle! I'll check this out tonight.