Paul and esteemed forum users,
I try to implement an algorithm (optimal location of wireless sensors on a grid) in eBasic (porting over from yabasic which is very slow when doing math computations) and have run across an eBasic issue that, I think, is unduly restrictive.
In my programming I need to use an array of integers that has 5 (FIVE) dimensions, say a[i,j,k,l,m]. Declaring such an array was not a problem in yabasic but arrays of more than 3 dimensions are NOT allowed in eBasic.
Since eBasic is NOT object oriented (thank God) and does not allow for array custom types, I cannot get around that by declaring, say, a 2 dimensional array aa[i,j] each cell of which would be a three dimensional array a[k,l,m].
Having the capability of using arrays of arbitrarily many dimensions or, at least, more than 3 (say up to 9) would be a great boon. Would Paul please consider adding this capability?
Also am I correct in understanding that I CANNOT use TYPE to declare an array of arrays?
Friendly regards from Greece,
John Paravantis
University of Piraeus
Sure you can use a type.
Would this be the way to declare an array of arrays?
type aaa
def a3[10,10,10]:int
endtype
type aaaaa
def a5[10,10]:aaa
endtyp
so that aaaaa may now be used as an array of (essentially) 5 dimensions? Can I NEST types this way?
Would this be equally FAST to being able to directly declare arrays of 5 dimensions?
John
I haven't done this in many years, but we used to only have single dimensioned arrays and were still able to do Multi's.
The trick is: define array with enough elements as required by your dimensions. (5,4) = 20 elements. To directly address it within this frame work was to:
Array(Index1 + ((Index2-1)*5)) = Array2(Index1, Index2)
This can be expanded to any number of dimensions with a little work.
Bill
John,
Yes that is one way to do it, speed isn't an issue as it is all machine code once compiled and the reference to a type is actually a bit faster than the additional calculation that would be needed for each dimension index.
OK, thank both of you for responding.
In regards to Paul observing "this is ONE way of doing it", is there a better/more elegant way of doing it? Could you provide a brief code example?
In the meantime, I will complete the translation of my yabasic program into eBasic and will report the speed increase to the forum.
I don't have a brief code example, but I'll write one for you.
An array in memory isn't comprised of cells, or indexes. It is just a continuous block of memory. You see it as an array because of how that memory is indexed by a calculation. So you can create an array of any dimension if you know how to translate the indexes into the correct memory location.
So the calculations for accessing an element of a two and three dimension array are as follows:
'two dimensions
address = base + (index2 * dim1 + index1) * datasize
'three dimensions
address = base + ((index3 * dim1 * dim2) + (index2 * dim1) + index1) * datasize
Where base is the starting address of the memory the array is stored in, and datasize is the size of an array element in bytes i.e 4 for an integer. I am sure you can see the pattern, the calculations of a 4 dimension array access would be:
'four dimensions
address = base + ((index4 * dim1 * dim2 * dim3) + (index3 * dim1 * dim2) + (index2 * dim1) + index1) * datasize
The calculations assume zero based indicies. Knowing the formula for accessing the array elements you can create an array with allocated memory of any size, and a subroutine to access that array for storage and retrieval. I will write a group of subs you can use for n dimensioned arrays. The speed of access is determined by how fast you can calculate the element address.
Paul.
Sorry, I meant providing a TYPE example.
Simulating a multidimensional array with an array of one dimension should be straightforward ALTHOUGH because my code runs for 40 MINUTES in yabasic I am concerned with the issue of speed: as you point out, indexing WILL take time.
John
It is not simulating. It is how the compiler does the calcuations for arrays, in assembly of course.
Based on Paul's example, I would think that the calculation of the index into a single dimensioned array would be pretty quick. Since it would result in an integer, which should be very quick to calculate. Integer math is usually very quick in assembly.
You could create a subroutine which would be passed the indexes and returns the single index, which could then be used as a direct index into the single dimensioned array.
sub indexer(index1:int, index2:int, index3:int, index4:int, index5:int),int
....
return index
endsub
usage: array(indexer(i1,i2,i3,i4,i5)) = value
This would make your code changes some what smaller.
Bill
Many thanks to all.
Incidentally, I find it annoying that array indexes start at 0 and end at (n-1), e.g. a[8] contains a[0] ... a[7].
Would Paul consider adding an OPTION BASE command (or the like) that would allow the user to choose between 0 and 1?
Why don't you just dimension the arrays as n+1 and use 1..n range in your programs? Problem solved.
However, having said that I'd like to add that it would be nice to have something more powerful than a simple option base. For example if we are using years in our calculations we could use:
DIM aYears[1914:1918]
and later in the program we can access the array like this:
xyzzy=aYears[1915]
Pretty neat and easy to understand what the code does when we look at it few months later. I know this can be done fairly easily by creating an appropriate indexing function but I prefer the compiler to take care of such calculations.
Barney
Barney,
Quite obviously, I DO dimension them as n+1. BUT this is not a good way to achieve what I want.
You very correctly point out the a[first:last] syntax as the BEST possible improvement and I enthusiastically second your motion.
Paul, would you kindly consider such an enhancement?
John
Quote from: Barney on December 08, 2006, 03:51:26 AM
...I know this can be done fairly easily by creating an appropriate indexing function but I prefer the compiler to take care of such calculations.
Quoting myself. I must be getting old. ::)
After reading it once again I realized that compiler would, of course, have problems with it. Such calculations belong to some sort of run time package and thus are much easier to do in interpreter environment. But there should still be a way of doing it, perhaps through the use of extra support functions...
Barney
For many such applications, a hash (dictionary or associative array) solves the problem quite neatly. ;)
Yes, Jerry, I know but I've been using the a[100:122] approach in HP BASIC for years and got used to it so much I always wish I can have it in other languages. :)
Barney
Compiled languages use zero based indexes because the processor uses zero based memory. A varaible in a compiled program is just memory, no types, no other information, just an address. So there isn't any place to store an array 'offset' and remain compatible with all other compiled languages.
Having subscripts begin at 0 is an advantage far more often than it is a drawback, in my opinion. And having an option so you can choose that introduces a lot of room for confusion and potential for bugs.
I like that as it is.
Barry
Quote from: barry on December 08, 2006, 11:19:45 AM
Having subscripts begin at 0 is an advantage far more often than it is a drawback, in my opinion.ÂÃ, And having an option so you can choose that introduces a lot of room for confusion and potential for bugs.
I agree. In mathematics (my background) indices start with zero.
The problem with varying array bounds is that you have to add in a bunch of helper functions. For example, in FreeBASIC you can say dim array(10 to 20) as integer, but then every time you access an array element, or assign one, or do anything else it has to call a function that works on the array. And the array isn't really a true array, because it is actually a UDT that describes it.
However, if you prefer this behaivor, you can write code to set it up. I have neither IBasic Pro nor EBASIC on my computer, but this should help you:
declare cdecl extern memcpy alias "_memcpy" ( dest:pointer, src:pointer, num:uint ),pointer
declare cdecl extern memset alias "_memset" ( buffer:pointer, c:int, num:uint ),pointer
declare import, GlobalReAlloc( hMem:pointer, dwBytes:uint, flags:uint ),pointer
type array
int lbound
int ubound
uint elemsize
pointer elems
endtype
global sub arrayDim( lbound:int, ubound:int, size:uint ), pointer
pointer a
a = new(array, 1)
settype a,array
*a.lbound = lbound
*a.ubound = ubound
*a.elemsize = size
if ubound > lbound then *a.elems = new(char, ( ubound - lbound + 1 ) * size)
return a
endsub
global sub arrayDelete( a:pointer )
delete *<array>a.elems
delete a
endsub
global sub arrayRedim( a:pointer, lbound:int, ubound:int ),pointer
if ubound <= lbound then return a
*<array>a.elems = GlobalReAlloc( *<array>a.elems, (ubound - lbound + 1) * *<array>a.elemsize, 0x0040 )
*<array>a.lbound = lbound
*<array>a.ubound = ubound
return a
endsub
global sub arrayRedimClear( a:pointer, lbound:int, ubound:int ),pointer
a = arrayRedim( a, lbound, ubound )
arrayClear( a )
return a
endsub
global sub arrayClear( a:pointer )
if *<array>a.elems <> 0 then memset( *<array>a.elems, 0, (*<array>a.ubound - *<array>a.lbound + 1) * *<array>a.elemsize )
endsub
global sub arraySet( a:pointer, index:int, elem:pointer )
if index < *<array>a.lbound or index > *<array>a.ubound then return
index -= *<array>a.lbound
memcpy( *<array>a.elems + (*<array>a.elemsize * index), elem, *<array>a.elemsize )
endsub
global sub arrayGet( a:pointer, index:int ),pointer
if index < *<array>a.lbound or index > *<array>a.ubound then return 0
index -= *<array>a.lbound
return *<array>a.elems + (*<array>a.elemsize * index)
endsub
Obviously this is untested since I don't have a tool installed to compile it. But I hope it works. This is an example usage:
pointer arr
int quit : quit = 0
int ind
pointer elem
'' Store integers (4 byte size) from 10 to 20 inclusive.
arr = arrayDim( 10, 20, 4 )
for i = 10 to 20
elem = new(int, 1)
*<int>elem = i - 10
arraySet( arr, i, elem )
next i
do
print "index from 10 to 20 (out of bounds = done)? ",
input ind
elem = arrayGet( arr, ind )
if elem = 0 then quit = 1 else print "arr[" + ltrim$(str$(ind)) + "] =", *<int>elem
until quit = 1
arrayDelete( arr )
Again, please let me know if there are any errors.
Hope it helps,
Parker
P.S. Though this only supports one dimension, it could easily be modified to support any number of dimensions using variable arguments. Arrays are redim-able, where arrayRedimClear is the same as REDIM in BASIC, and arrayRedim is the same as REDIM PRESERVE. arrayClear sets all elements to zero (this works on UDTs too, so be careful). Boundaries are inclusive.
I give my permission for anyone to distribute this code, along with any modifications, provided the source code is made available to anyone who wants it, that people know this, and that it is not sold.
P.P.S. I've fixed the errors. It should work now. Sorry I couldn't test it before.
Apart from the obvious typo where you are using "a" instead of "arr"
elem = arrayGet( a, ind )
shouldl be
elem = arrayGet( arr, ind )
everything compiles nicely but bombs out with the usual "send error..." to Microsoft message. Will check it again tomorrow because it's rather late here and I'd rather hit the bed than stare at the screen. :)
Barney
The typo is fixed. I would debug it and fix it myself, but unfortunately I can't :-\
If someone could compile a debug build and tell me which line it's crashing on I could probably fix it.
Thanks for trying it though. Sorry it crashes.
Parker
Well... I did not go to bed so here's the debug message:
Call stack:
CRTDLL! memcpy + 46
ArrayBounds! arraySet + 243 File: ArrayBounds.inc, Line: 53
ArrayBounds! arrayGet + 338 File: ArrayBounds.eba, Line: 13
kernel32! RegisterWaitForInputIdle + 73
Line 53 in ArrayBounds.inc is:
memcpy( *<array>a.elems + (*<array>a.elemsize * index), elem, *<array>a.elemsize )
Barney
Oops :-[
That's because the arraySet function requires a pointer and I gave it an int. memcpy is trying to read from memory locations 0-10 and obviously it can't. I'll fix it in the original post.
So after that, I have to say that having arrays start at 0 and string functions start at 1 really throws me off. I personally would rather have both start at 0 how it is in C and Java. However, I know this discussion has been brought up before and I don't think it's going to change.
It is for compatibility with string functions of other basics. And they are character positions, not indexes, when you are dealing with strings. When you think of a unicode string the 3rd character position isn't the 3rd byte, or even the 6th byte depending on the character itself.
I am just about finished modifying the parser to allow 5 dimensions. After that it's up to you ;)
Quote from: Paul Turley on December 08, 2006, 09:36:33 PM
I am just about finished modifying the parser to allow 5 dimensions. After that it's up to you ;)
What about Aurora?
Of course all of these changes will be in Aurora too.
OK it is done and will be in the next update. This now compiles and works as expected.
int a[5,5,5,5,5]
count = 0
for i = 0 to 4
for j = 0 to 4
for k = 0 to 4
for l = 0 to 4
for m = 0 to 4
a[i,j,k,l,m] = count
count+=1
next m
next l
next k
next j
next i
for i = 4 to 0 step -1
for j = 4 to 0 step -1
for k = 4 to 0 step -1
for l = 4 to 0 step -1
for m = 4 to 0 step -1
print a[i,j,k,l,m],
next m
next l
next k
next j
next i
do:until inkey$ <> ""
Quote from: Barney on December 08, 2006, 03:51:26 AM
However, having said that I'd like to add that it would be nice to have something more powerful than a simple option base. For example if we are using years in our calculations we could use:
DIM aYears[1914:1918]
and later in the program we can access the array like this:
xyzzy=aYears[1915]
Pretty neat and easy to understand what the code does when we look at it few months later. I know this can be done fairly easily by creating an appropriate indexing function but I prefer the compiler to take care of such calculations.
I would argue that an associative array would be much more appropriate for something like that. It would be nice to have that integrated into the language, rather than using functions as it is now. In other words, something like:
Def strAddress[] As String Array
strAddress["John Doe"] = "john@bigcorp.com"
strAddress["Jane Doe"] = "jane@bigcorp.com"
ForEach strKey, strValue In strAddress
Print strKey, strValue
Next
I agree, Mike, that would be nice.
You just need hashtables.
Otherwise, the cheat to hashtables is simply an array of structures.
Call me lazy...
Here is a structure with 2x2 dimensional arrays with 4 elements each.
This structure is party to a 2 dimensional array with 64 elements, each element is the structure.
Confusing?
Not really. Its a basic hashtable in the generic of terms.
Compile this as console and see the results.
edit: updated to make it the tower of numbers :)
OPENCONSOLE
type myStuff
def numbers[2,2] as int
def ages[2,2] as int
endtype
def array[8,8] As myStuff
def a,b,c,d as int
for a = 0 to 1
for b = 0 to 1
for c = 0 to 7
for d = 0 to 7
array[c,d].numbers[a,b]=rand(1,20)
array[c,d].ages[a,b]=rand(1,10)
next d
next c
next b
next a
print "Arrays"
for a = 0 to 1
print "+--------------------------+"
for b = 0 to 1
print "|--+--------------------+--|"
for c = 0 to 7
print "|----+----------------+----|"
for d = 0 to 7
print "|--------+--------+--------|"
if (array[c,d].numbers[a,b]) < 10 then
print "|--------+"+STR$(array[c,d].numbers[a,b])+" +--------|"
else
print "|--------+"+STR$(array[c,d].numbers[a,b])+" +--------|"
end if
if (array[c,d].ages[a,b]) < 10 then
print "|--------+"+STR$(array[c,d].ages[a,b])+" +--------|"
else
print "|--------+"+STR$(array[c,d].ages[a,b])+" +--------|"
end if
print "|--------+--------+--------|"
next d
print "|----+----------------+----|"
next c
print "|--+--------------------+--|"
next b
print "+--------------------------+"
next a
DO:UNTIL INKEY$ <> ""
CLOSECONSOLE
END
General result, results may vary since its all random:
Added some spacing, lol.. ok I am done with this now.. looks cooler in console cause everything lines up..
its this font...
Arrays
+--------------------------+
|--+--------------------+--|
|----+----------------+----|
|--------+--------+--------|
|--------+ 5 +--------|
|--------+ 4 +--------|
|--------+--------+--------|
|--------+--------+--------|
|--------+ 16 +--------|
|--------+ 3 +--------|
|--------+--------+--------|
|--------+--------+--------|
|--------+ 12 +--------|
|--------+ 5 +--------|
|--------+--------+--------|
etc.