A Flash Developer Resource Site

Page 1 of 2 12 LastLast
Results 1 to 20 of 23

Thread: Flat Array vs Multidimensional Array

  1. #1
    Developer
    Join Date
    Apr 2007
    Location
    UK
    Posts
    324

    Flat Array vs Multidimensional Array

    For a game I'm making with AS3 I've tried to stick with using flat arrays as much as possible because I read somewhere that its faster than using multidimensional arrays. I just need to know if anyone knows or can point me to any place which discusses the speed difference (if there is any).

    Using multidimensional arrays would make my coding much easier but if its slower than flat arrays I'm willing to persevere for the better execution time.

    Any thoughts?

  2. #2
    Hype over content... Squize's Avatar
    Join Date
    Apr 2001
    Location
    Lost forever in a happy crowd...
    Posts
    5,926
    multi-dim arrays are slower, but not enough to make your life harder by not using them.

    It's been years since I've got hung up about speed to the point that I spite myself and make my job harder to save a few ms here and there ( When just plotting image to the screen will take more of your cpu time than 95% of your running code anyway ).

    Squize.

  3. #3
    Untitled-1.fla strille's Avatar
    Join Date
    Mar 2001
    Location
    Sweden
    Posts
    1,626
    I agree with Squize, and since you are using AS3 it's a no-brainer: use multidim arrrays. The reason? AS3 is MUCH faster than previous versions. So the access time to the item in the array won't be a problem.

  4. #4
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    Quote Originally Posted by Cortana
    For a game I'm making with AS3 I've tried to stick with using flat arrays as much as possible because I read somewhere that its faster than using multidimensional arrays. I just need to know if anyone knows or can point me to any place which discusses the speed difference (if there is any).

    Using multidimensional arrays would make my coding much easier but if its slower than flat arrays I'm willing to persevere for the better execution time.

    Any thoughts?
    not sure, i'd say a flat array will always win because you only need one lookup. But i'd say the speed will be unnoticable. So go with whatever makes programming easier.

    Arrays are faster than objects in AS3 as well.

    EDIT - what those guys said.
    lather yourself up with soap - soap arcade

  5. #5
    Developer
    Join Date
    Apr 2007
    Location
    UK
    Posts
    324
    Excellent! Thanks a lot guys

  6. #6
    Pumpkin Carving 2008 ImprisonedPride's Avatar
    Join Date
    Apr 2006
    Location
    Grand Rapids MI
    Posts
    2,378
    Hmm... I've often weighed the possibilities of using a single dimension array, but always dismissed it. My bug was targeting. How does someone target the nth element, n being prime? I would have thought finding the element would be an array[x*y] thing, but I'm starting to think it's more of an array[x*a+y]; 'a' being a set amount that the total number of elements (minus the max value of y) is divisible by. It could be that it's pretty early and I'm tired, but this has always been my beef with 1d arrays.
    The 'Boose':
    ASUS Sabertooth P67 TUF
    Intel Core i7-2600K Quad-Core Sandy Bridge 3.4GHz Overclocked to 4.2GHz
    8GB G.Skill Ripjaws 1600 DDR3
    ASUS ENGTX550 TI DC/DI/1GD5 GeForce GTX 550 Ti (Fermi) 1GB 1GDDR5 (Overclocked to 1.1GHz)
    New addition: OCZ Vertex 240GB SATA III SSD
    WEI Score: 7.6

  7. #7
    Developer
    Join Date
    Apr 2007
    Location
    UK
    Posts
    324
    Yep, using code like array[x*loopIndex+somethingElse] to reference arrays is what I'm doing a lot and its sometimes a pain in the buttocks.

    Multidimensional it is!

  8. #8
    Heli Attack! iopred's Avatar
    Join Date
    Jun 2003
    Location
    Sydney, Australia
    Posts
    923
    Quote Originally Posted by mr_malee
    Arrays are faster than objects in AS3 as well.
    Yes, but not Dictionaries, sweet, sweet delicious Dictionaries.
    Christopher Rhodes
    squarecircleco.

  9. #9
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    what are these dictionaries you speak of?

    intriguing.
    lather yourself up with soap - soap arcade

  10. #10
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    I tried to understand the point in new dictionary object, but it has so far escaped me. Maybe some day I will find out what they are good for.

  11. #11
    Heli Attack! iopred's Avatar
    Join Date
    Jun 2003
    Location
    Sydney, Australia
    Posts
    923
    Dictionaries are just like objects.

    dict["string"] = "blah";
    trace(dict["string"]);

    and:

    for each(var i:* in dict)
    {
    trace(i);
    }

    So a use for them, say we want to load resources and grab them fast, like some kind of linked list, we can use an array and search through from 0 -> n every time we look for something, or give each resource an 'id' and look it up in a Dictionary.
    Christopher Rhodes
    squarecircleco.

  12. #12
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    i'm reading the docs right now. It looks just like an object expect you can pass a reference as an id, and return a value by using the reference.

    And you say these are the fastest way to store and retrieve data? testing time
    lather yourself up with soap - soap arcade

  13. #13
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    it still looks like array wins. Compared with object and dictionary. I know this is a case where array can exist because they key is a number. So i suppose if you had to decide between object and dictionary then i'd go dictionary.
    Code:
    import flash.utils.Dictionary
    import flash.utils.getTimer;
    
    var dic:Dictionary = new Dictionary()
    var arr:Array = []
    var obj:Object = {}
    
    //populate all objects with same data
    
    var len:int = 900000
    var i:int = len
    var v:String;
    
    while(--i >= 0){
    	
    	dic[i] = "hello"
    	arr[i] = "hello"
    	obj[i] = "hello"
    }
    
    //run dictionary
    
    var t:Number = getTimer()
    
    for(i in dic){
    	
    	v = dic[i]
    }
    
    trace(getTimer() - t)
    
    //run array
    
    i = len
    t = getTimer()
    
    while(--i >= 0){
    	
    	v = arr[i]
    }
    
    trace(getTimer() - t)
    
    //run object
    
    t = getTimer()
    
    for(i in obj){
    	
    	v = obj[i]
    }
    
    trace(getTimer() - t)
    i'll try out a 2 dimensional array. With dictionary having keys as x+y

    edit - 2D array, dictionary wins when it uses a 1D loop, however Array is by far the fastest when using a 2D loop
    Code:
    import flash.utils.Dictionary;
    import flash.utils.getTimer;
    
    var dic:Dictionary = new Dictionary();
    var arr:Array = []
    var obj:Object = {}
    
    //populate all objects with same data
    
    var lenX:int = 200
    var lenY:int = 200
    
    var px:int = 0
    var py:int = 0
    var i:int;
    
    var v:Array;
    
    for(x = 0; x<lenX; x++){ arr[x] = []
    for(y = 0; y<lenY; y++){
    	
    	dic[x+"-"+y] = ["hello", "goodbye", 0, 1, 2, true]
    	arr[x][y] = ["hello", "goodbye", 0, 1, 2, true]
    	obj[x+"-"+y] = ["hello", "goodbye", 0, 1, 2, true]
    }}
    
    //run dictionary
    
    var t:Number = getTimer()
    
    for(i in dic){
    	
    	v = dic[i]
    }
    
    trace("dictionary var i in", getTimer() - t)
    
    //run dictionary
    
    t = getTimer()
    
    for(x = 0; x<lenX; x++){
    for(y = 0; y<lenY; y++){
    	
    	v = dic[x+"-"+y]
    }}
    
    trace("dictionary x y", getTimer() - t)
    
    //run array
    
    t = getTimer()
    
    for(x = 0; x<lenX; x++){
    for(y = 0; y<lenY; y++){
    	
    	v = arr[x][y]
    }}
    
    trace("array x y", getTimer() - t)
    
    //run object
    
    t = getTimer()
    
    for(i in obj){
    	
    	v = obj[i]
    }
    
    trace("object var i in", getTimer() - t)
    
    //run object
    
    t = getTimer()
    
    for(x = 0; x<lenX; x++){
    for(y = 0; y<lenY; y++){
    	
    	v = obj[x+"-"+y]
    }}
    
    trace("object x y", getTimer() - t)
    Last edited by mr_malee; 06-07-2007 at 08:12 AM.
    lather yourself up with soap - soap arcade

  14. #14
    Heli Attack! iopred's Avatar
    Join Date
    Jun 2003
    Location
    Sydney, Australia
    Posts
    923
    Ah nice to see, Dictionaries were faster in the Beta, I hadn't thought to retest.

    Either way, they are handy in their own situations.

    I think you should try a test with dict[Math.random()*10000] looped a few times though. Iterating is pretty standard.

    Also Dictionaries have the insertion/removal cost of next to nothing:
    dict[index] = null
    vs
    Array.splice();
    Christopher Rhodes
    squarecircleco.

  15. #15
    ....he's amazing!!! lesli_felix's Avatar
    Join Date
    Nov 2000
    Location
    London UK
    Posts
    1,506
    AFIAK, a dictionary has the combined functionality of a numerical array and an associative array. That alone makes it very useful.

    If we're going for speed, has anyone tried numerically-named variables:
    I seem to remember they're pretty quick too

    var1
    var2
    var3

    this["var" + x] to retrieve data.

  16. #16
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    yeah, i think i will have some use for a dictionary array, but just for data that i need keys for.

    is the dictionary something special for AS? or do other languages feature such things. Sometimes i wonder why certain structures have not been made accessible for us. Like the linked list in C
    lather yourself up with soap - soap arcade

  17. #17
    Senior Member
    Join Date
    Jan 2006
    Location
    USA
    Posts
    383
    Never heard of a Dictionary struct.. interesting.

    I'm curious of what you meant, malee.. linked lists are accessible to any programming language, to my knowledge.

    You just have to create a Node class and a LinkedList class. And there you have a linked list. I find them very useful when I have a map/array full of empty slots.

  18. #18
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    Dictionary is an odd duck in AS3. I find it really interesting that it even supports weak references.

  19. #19
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    Quote Originally Posted by AfternoonDelite
    I'm curious of what you meant, malee.. linked lists are accessible to any programming language, to my knowledge.
    sorry, thought that C, C++ came with a native linked list array.
    lather yourself up with soap - soap arcade

  20. #20
    Feeling adventurous? T1ger's Avatar
    Join Date
    Mar 2004
    Posts
    850
    How about if you use a onedimensional-array, and save the "width" in another variable..
    PHP Code:
    //Instead of this:
    map1 = [[0,0,1],[0,1,0],[1,0,0]];
    //this:
    map2 = [0,0,1,0,1,0,1,0,0];
    3;
    //how to access it:
    trace(map1[0][2]); // 1
    trace(map2[0*w+2]); // 1 
    I actually made a test to compare them... http://www.straleks.com/flash/arraytest/
    With 10000 cycles i get that flat arrays are about 25 % faster than multidimensional.. Source is available as a link on the page. Could these test-results be reliable?
    I don't have a photograph, but you can have my footprints. They're upstairs in my socks.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center