(x,y) Array? (solved)
Monkey Forums/Monkey Programming/(x,y) Array? (solved)
| ||
hello, i convert a old source code (path finding algorithms). i want have a object in a x,y grid because i need to find the nearest neighbours with +1 -1 Class Pos Field w:Int End Class Area Field grid:Pos[50,50] <??? i need grid[x+1,y-1].w=123 |
| ||
Array syntax is like this: (A two-dimensional array in Monkey is an array of one-dimensional arrays.) |
| ||
ok,thank you :-) i wonder why the compiler have a problem with this Field a:Pos[][] ok Field ab:Pos[50] ok Field abc:Pos[50][50] error? Field abcd:Pos[50][] ok |
| ||
As an alternative method: (I think this one is faster at allocating the array, as it is done in one single pass)Function Main() Local td:= New TwoDimensionalMatrix<String> td.Dim(100, 100) td.SetItem(50, 50, "Hello!") Print td.GetItem(50, 50) End Class TwoDimensionalMatrix<T> Method Dim(width, height) Self.width = width Self.height = height data = New T[width * height] End Method ReDim(width, height) Self.width = width Self.height = height data = data[ .. width * height] End Method GetWidth() Return width End Method GetHeight() Return height End Method GetLength() Return data.Length End Method GetItemByOffset:T(item:Int) Return data[item] End Method GetItem:T(x:Int, y:Int) Local val:Int = y * width + x Return data[val] End Method SetItem(x:Int, y:Int, value:T) Local val:Int = y * width + x data[val] = value End Private Field data:T[] Field width:Int = 0, height:Int = 0 End |
| ||
@ziggy cool!, thanks :) |
| ||
@ziggy - that's a nice implantation that I am going to steal... yonk! |
| ||
I like that approach, Ziggy. I will be stealing it too! |
| ||
Markus: Field abc:Pos[50][50] error? This is because you are trying to define too much at once. Field abc:Pos[50][] is fine, it says "make an array with 50 spaces for 1D arrays of Pos" But (although it is rarely used) all those 1D arrays could be different lengths. You need to specify that each one is a Pos[50]. I guess since they are nearly always the same length, it could be added as syntactic sugar sometime. On the other hand, that would mean a lot of object allocations were going on behind the scenes, which might be confusing. Personally I use a generic allocator: So to make a 50x50 array of new Pos objects, I can just write: grid = Generic< Pos >.AllocateArray( 50, 50 ) Generic< Pos >.FillObjectArray( grid ) If it were a 50x50 array of ints rather than objects, only the first line would be needed. The 1D array has its merits too, though - if you are doing intense calculations such as pathfinding, it should be faster than multidimensional arrays. |
| ||
@Gerry interesting, thank you very much. |
| ||
I was a bit bored and made an arbitrary-array size implementation of the above. It seems to work very fast. That's it: Usage example: 'USAGE EXAMPLE: Function Main() 'We create a multidimensional array: Local myArray:= New MultiArray<String> 'We set it to be three dimensions: myArray.Dim([3, 5, 7]) Print "Length of the array: " + myArray.Length Print "Number of dimensions: " + myArray.GetNumberOfDimensions() For Local i:Int = 0 Until myArray.GetNumberOfDimensions Print "Dimension " + i + " has a size of " + myArray.GetDimensionSize(i) Next 'Just a counter to set be used later: Local i:Int = 0 'We iterate the array using its x, y, and z indexes, and set and get values from/to it: For Local z:Int = 0 Until myArray.GetDimensionSize(2) For Local y:Int = 0 Until myArray.GetDimensionSize(1) For Local x:Int = 0 Until myArray.GetDimensionSize(0) 'We set the value "Value of 1, 2, 3, etc... to each item of the array: myArray.Set([x, y, z], "Value of " + i) 'We get the value of each item of the array, once set: Print "Iterating item (" + x + ", " + y + ", " + z + ") = " + myArray.Get([x, y, z]) 'We increase the counter: i += 1 Next Next Next 'This should generate an error in debug mode, wrong number of dimensions, as it's a x,y,z array: 'Print myArray.Get([3, 3]) EndNow if we could get some syntactic sugar to make this a bit better (somethinf like paramarrays) it would be very sexy. EDITED with a small fix. |
| ||
Ziggy, If I only understood a fraction of what you know... It is like my brain can only take in so much before it pushes something else out. Lol. Still I will study this and try to understand it. |
| ||
It's very very easy to use. See a small example that covers mostly anything: (latest edit of the above required) Function Main() 'Example 1: Creating a 3 dimensions array: Local myArray:= New MultiArray<MyClass> 'We set the number of dimensions, and the size of each dimension in one go: myArray.Dim([255, 100, 24]) 'We set a value at a given position of the array: '1.- Create Then item: Local myItem:= New MyClass myItem.name = "George" myItem.age = 24 '2.- Put it on a array position: myArray.Set([23, 45, 12], myItem) 'We get a value at a given position of the array: Local myItem2:= myArray.Get([23, 45, 12]) Print "The name of the item at 23, 45, 12 is " + myItem2.name 'Get the length of the array: Print "size= " + myArray.Length 'Get the number of dimensions Print "dimensions= " + myArray.GetNumberOfDimensions() 'Get the size of the first dimension: Print "size of first dimension= " + myArray.GetDimensionSize(0) 'Get the size of the second dimension: Print "size of second dimension= " + myArray.GetDimensionSize(1) 'Iterate the array: For Local myc:= EachIn myArray If myc <> Null Then Print myc.name Next 'Resize the array keeping items: myArray.ReDim([128, 128, 128]) Print "Size of the array after resizing= " + myArray.Length End Class MyClass Field name:String, age:Int End |
| ||
That might be convenient but I doubt very much that it's fast except for the initial allocation. Using a 1D array in pursuit of speed and then wrapping it with accessor functions seems to have some fatal attraction. The call overhead by itself likely wipes out any advantage from using 1D. A call that involves constructing an array to pass in is going to be far worse. |
| ||
The call overhead by itself likely wipes out any advantage from using 1D. A call that involves constructing an array to pass in is going to be far worse. Well... it should not. Calling a function is not *that* slow, and also, creating an array to call a method is a bad idea. That's true, but you can just not do it.Of couse accesing a 1D array is faster. Not sure comparing my method to calling an array of arrays of arrays, and also this allows for other things like resizing, iteration, etc. I think it is handy but, as with any collection-like abstraction, it has some drawbacks and the thing is to choose the right one on each stituation. |
| ||
It doesn't have to be *that* slow, whatever value for "that" you're imagining. It just has to be slower than the advantage you gain from the 1D access, which is somewhere between 0 and not a lot. As I said, it's convenient, but you made a claim that it is also "very fast" when it seems likely to be anything but if someone uses the accessors you have provided. I'm just flagging that fact to maybe avoid someone taking your claim at face value and then wondering why they've got performance issues. |
| ||
Yes, I see your point! I was expecting it to be slower than what I got after some testing, so that's why I said it was very fast, becouse it looked like it could be slow and, to my surprise, it was "very fast" at last on chrome using JavaScript. I haven't realy spent any efforts on benchmarking it or anything, and I don't expect anything like this to be as fast as direct 1D array. That's obvious! EDIT: After making some changes such as making the methods Final (they're pure, so they could be inlined by the compiler), on a small test I've done, on release mode, it's a bit faster to use the multidim class than to use an array of arrays to access 3 dimensions indexed item. The more dimensions you add, the better the class behaves, but the diference is almost negligible. On JavaScript, accesing arrays of arrays is always slightly faster than using the MultimDim class, but the difference is again very little. Haven't tested Flash or Objective-C, but I would say it's not bad! |
| ||
I've experimented with this in the past, and if you want to do straight Dijkstra pathfinding,the 1D array is 2X faster than the native Monkey 2D array. 99% of the time, this will make no difference whatsoever. |
| ||
That's very interesting. Using this version of the Multidim array: And running this benchmark that measures random access to elements, comparing the multidim array with an array of arrays of arrays (3 dimensions) it seems that the multidim array is faster in HTML5, and the same on C++ (release mode) Import lemongames.collections.multiarray Import mojo Global data:String Function Main() Const ArrSize:Int = 200 Const Iterations:Int = 500000 Const cycles:Int = 10 Print "Filling a 3 dim array of array" Local ms:= Millisecs() 'We create a 3 dim array using monkey array of arrays method: Local a:= New MyClass[ArrSize][][] For Local i:Int = 0 Until ArrSize a[i] = New MyClass[ArrSize][] For Local j:Int = 0 Until ArrSize a[i][j] = New MyClass[ArrSize] For Local k:Int = 0 Until ArrSize a[i][j][k] = New MyClass Next Next Next Print "Done in " + (Millisecs - ms) Print "Filling a 3 dim multidim array" ms = Millisecs() 'We create a 3 dimensional array using Multarray Local b:= New MultiArray<MyClass> b.Dim([ArrSize, ArrSize, ArrSize]) For Local i:= 0 Until b.Length b.Set(i, New MyClass) Next Print "Done in " + (Millisecs - ms) For Local c:= 0 Until cycles ms = Millisecs For Local i:= 0 Until Iterations Local x:Int = Rnd(0, ArrSize) Local y:Int = Rnd(0, ArrSize) Local z:Int = Rnd(0, ArrSize) data = a[x][y][z].name Next Print "Arrray of arrays took: " + (Millisecs - ms) ms = Millisecs Local arr:= New Int[3] For Local i:= 0 Until Iterations arr[0] = Rnd(0, ArrSize) arr[1] = Rnd(0, ArrSize) arr[2] = Rnd(0, ArrSize) data = b.Get(arr).name Next Print "Multidim array took: " + (Millisecs - ms) Next End Class MyClass Field name:String = "Monkey!" End I got this results on GLFW: Filling a 3 dim array of array Done in 1778 Filling a 3 dim multidim array Done in 1830 Arrray of arrays took: 208 Multidim array took: 200 Arrray of arrays took: 201 Multidim array took: 208 Arrray of arrays took: 208 Multidim array took: 198 Arrray of arrays took: 204 Multidim array took: 199 Arrray of arrays took: 213 Multidim array took: 200 Arrray of arrays took: 206 Multidim array took: 200 Arrray of arrays took: 207 Multidim array took: 205 Arrray of arrays took: 206 Multidim array took: 199 Arrray of arrays took: 204 Multidim array took: 195 Arrray of arrays took: 206 Multidim array took: 202 And I got this output on chrome HTML5: Filling a 3 dim array of array Done in 2563 Filling a 3 dim multidim array Done in 4437 Arrray of arrays took: 266 Multidim array took: 187 Arrray of arrays took: 235 Multidim array took: 203 Arrray of arrays took: 219 Multidim array took: 187 Arrray of arrays took: 219 Multidim array took: 203 Arrray of arrays took: 219 Multidim array took: 203 Arrray of arrays took: 219 Multidim array took: 187 Arrray of arrays took: 219 Multidim array took: 203 Arrray of arrays took: 219 Multidim array took: 203 Arrray of arrays took: 219 Multidim array took: 203 Arrray of arrays took: 219 Multidim array took: 203 Thhis is on FireFox, and the difference is even higer Filling a 3 dim array of array Done in 2715 Filling a 3 dim multidim array Done in 2967 Arrray of arrays took: 250 Multidim array took: 162 Arrray of arrays took: 247 Multidim array took: 160 Arrray of arrays took: 278 Multidim array took: 183 Arrray of arrays took: 278 Multidim array took: 159 Arrray of arrays took: 251 Multidim array took: 160 Arrray of arrays took: 248 Multidim array took: 160 Arrray of arrays took: 245 Multidim array took: 161 Arrray of arrays took: 249 Multidim array took: 160 Arrray of arrays took: 245 Multidim array took: 157 Arrray of arrays took: 251 Multidim array took: 160 So the MultiDim array class seems to be |