(x,y) Array? (solved)

Monkey Forums/Monkey Programming/(x,y) Array? (solved)

Markus(Posted 2013) [#1]
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


Gerry Quinn(Posted 2013) [#2]
Array syntax is like this:



(A two-dimensional array in Monkey is an array of one-dimensional arrays.)


Markus(Posted 2013) [#3]
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


ziggy(Posted 2013) [#4]
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



Markus(Posted 2013) [#5]
@ziggy
cool!, thanks :)


Supertino(Posted 2013) [#6]
@ziggy - that's a nice implantation that I am going to steal... yonk!


Why0Why(Posted 2013) [#7]
I like that approach, Ziggy. I will be stealing it too!


Gerry Quinn(Posted 2013) [#8]
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.


Markus(Posted 2013) [#9]
@Gerry
interesting, thank you very much.


ziggy(Posted 2013) [#10]
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])
End

Now 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.


Loofadawg(Posted 2013) [#11]
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.


ziggy(Posted 2013) [#12]
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



muddy_shoes(Posted 2013) [#13]
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.


ziggy(Posted 2013) [#14]
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.


muddy_shoes(Posted 2013) [#15]
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.


ziggy(Posted 2013) [#16]
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!


Gerry Quinn(Posted 2013) [#17]
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.


ziggy(Posted 2013) [#18]
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 marginaly faster than an array of arrays for 3 dimensional arrays but the diference is very very little, but the class provides some additional functionalities.