Position item in an array larger than 3D

General FreeBASIC programming questions.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Position item in an array larger than 3D

Code: Select all

`Question: How to find the position that has an element of an array / vector / multidimensional array, using a mathematical formula? For example, in a 2D array of 4 x 4 A B C D E F G H I J K L M N O P A 1D 2D array = Array = ABCDEFGHIJKLMNOP              Position = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16. Ok! Then, the position Rowx = 3, colx = 3, position = 11 & content = K Formula: ((Rowx -1) * col) + colx = ((3 - 1) * 4) + 3 = Position 11 = element = K :::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::: Now in a 3D array = 4 x 4 x 4 1D = 3D = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... 60 61 62 63 64                                                                POSITION 63 = CONTENT = 63 level 1  1 2 3 4  5 7 7 8  9 10 11 12 13 14 15 16 level 2 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 level 3 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 level 4 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Example: Row 4 x column 3 x Level 4 = 4x3x4 = 63 Position 63 = Element 3D position pa Formula: ((Rowx - 1) * col) + colx + ((rows * cols) * (level -1)) ((4 - 1) * 4 * 4) + 3 + ((4 * 4) * (4 - 1)) = POSITION 63 = content = 63 :::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::: So my question is: What is the formula to find the position within an array larger than 4 or 5 or 20?Thanks"`
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

This code finds the array descriptor in FB. I'm sorry it only finds one dimension, but it shows what information is available in the descriptor for computation of pointer addresses. You can expand it to more dimensions by adding lines.

Code: Select all

`'=======================================================================' Local Array Descriptor is in the stack '=======================================================================Dim As Integer j = 1, k = 8'=======================================================================' keep this block together because the relative positions of the array ' descriptor and ip, referenced by ebp in the stack frame, is critical.Dim As Double x(j To k)     ' creates  descriptor  in the stack frameDim As Integer Pointer ip   ' creates  ip  4 bytes below in the frameip = Cptr(Integer Ptr, @ip + 1) ' ip should now point at the descriptor' @ip is a "Ptr" to an "Integer Ptr" so it must be changed back'=======================================================================Print Hex(ip, 8); "  ip  address of descriptor in stack "Print'-----------------------------------------------------------------------Print Hex(@x(j), 8); "  @x(j)  address of lowest element  "Print Hex(@x(k), 8); "  @x(k)  address of highest element "Print '-----------------------------------------------------------------------Print "Descriptor " Print Hex(*(ip+0), 8); "  element(zero) address for indexing "Print Hex(*(ip+1), 8); "  base address of allocated memory "Print Hex(*(ip+2), 8); "  total allocated memory in bytes "Print Hex(*(ip+3), 8); "  element size in bytes "Print Hex(*(ip+4), 8); "  number of dimensions "PrintPrint Hex(*(ip+5), 8); "  number of elements in dimension "Print Hex(*(ip+6), 8); "  lower bound of dimension "Print Hex(*(ip+7), 8); "  upper bound of dimension "Print'-----------------------------------------------------------------------' if it passes these tests then it probably found the descriptor OK'-----------------------------------------------------------------------' test to detect position disagreement of lowest elementIf @x(j) <> *(ip+1) Then    Color 14    Print "Fault in descriptor position or values "    Print Hex(  @x(j), 8); "  base element "     Print Hex(*(ip+1), 8); "  base memory "     Print    SleepEnd If'-----------------------------------------------------------------------' test if  memory_allocated = element_size * number_elementsIf *(ip+2) <> (*(ip+3) * *(ip+5)) Then    Color 14    Print "Suspicious allocated memory space error "    Print    SleepEnd If'-----------------------------------------------------------------------' check that upper and lower bounds match the element(zero) address Dim As Integer z = Cint(@x(j)) - (j*(Cint(@x(k)) - Cint(@x(j))) \ (k - j))If z <> *ip Then    Color 14    Print " faulty bounds or zero index interpolation value "     Print Hex(  z, 8); "  interpolated "     Print Hex(*ip, 8); "  descriptor "     Print    SleepEnd If'=======================================================================' to align array elements Dim As Integer ByteAlign = 16Dim As Integer np = 1 + (((*ip) - 1) Or (ByteAlign - 1))Print  Hex( *ip, 8); "  old base "Print  Hex(  np, 8); "  new base "Dim As Integer Pointer upper_bound = ip + 7print hex(*upper_bound , 8); "  old upper bound "*ip = np            ' adjust the zero index pointer up a few bytes*(ip+7) = *(ip+7)-1 ' reduce upper bound to enable bounds checkingprint hex(*upper_bound , 8); "  new upper bound "'-----------------------------------------------------------------------PrintPrint "normal exit encountered "'=======================================================================Sleep'======================================================================= `
dodicat
Posts: 6637
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Position item in an array larger than 3D

Here's a formula method for arrays up to six dimensions, for more you can extend.

Code: Select all

`'=================================================#define ub ubound#define lb lbound #define _r(arr,n) (ub(arr,n)-lb(arr,n)+1)#define d1(a,i) (i-lb(a,1))#define d2(a,i,j) (_r(a,2)*d1(a,i)+(j-lb(a,2)))#define d3(a,i,j,k) (_r(a,3)*d2(a,i,j)+(k-lb(a,3)))#define d4(a,i,j,k,l) (_r(a,4)*d3(a,i,j,k)+(l-lb(a,4)))#define d5(a,i,j,k,l,m) (_r(a,5)*d4(a,i,j,k,l)+(m-lb(a,5)))#define d6(a,i,j,k,l,m,n) (_r(a,6)*d5(a,i,j,k,l,m)+(n-lb(a,6)))'Build more if needed'==================================================dim as string array(1 to 6,3 to 8,0 to 4,1 to 5,2 to 4,8 to 10)print d6(array,1,3,0,1,2,8),"Start"print d6(array,2,5,3,3,3,9),"Somewhere in the middle"print d6(array,6,8,4,5,4,10),"End"sleep  `
fxm
Posts: 9816
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

Yes dodicat. This is a good recursive calculation method using macros.
We can verify the result with:

Code: Select all

`Dim As String array(1 To 6,3 To 8,0 To 4,1 To 5,2 To 4,8 To 10)Print @array(1,3,0,1,2,8) - @array(1,3,0,1,2,8),"Start"Print @array(2,5,3,3,3,9) - @array(1,3,0,1,2,8),"Somewhere in the middle"Print @array(6,8,4,5,4,10) - @array(1,3,0,1,2,8),"End"Sleep`

Another algorithm, but very rustic:

Code: Select all

`Function offset6(array() As String, _                 Byval I1 As Integer, _                 Byval I2 As Integer, _                 Byval I3 As Integer, _                 Byval I4 As Integer, _                 Byval I5 As Integer, _                 Byval I6 As Integer) As Integer  Dim I As Integer  For K1 As Integer = Lbound(array,1) To Ubound(array,1)    For K2 As Integer = Lbound(array,2) To Ubound(array,2)      For K3 As Integer = Lbound(array,3) To Ubound(array,3)        For K4 As Integer = Lbound(array,4) To Ubound(array,4)          For K5 As Integer = Lbound(array,5) To Ubound(array,5)            For K6 As Integer = Lbound(array,6) To Ubound(array,6)              If I1 = K1 And I2 = K2 And I3 = K3 And I4 = K4 And I5 = K5 And I6 = K6 Then                Return I              Else                I = I + 1              End If            Next K6          Next K5        Next K4      Next K3    Next K2  Next K1End FunctionDim As String array(1 To 6,3 To 8,0 To 4,1 To 5,2 To 4,8 To 10)Print offset6(array(),1,3,0,1,2,8),"Start"Print Offset6(array(),2,5,3,3,3,9),"Somewhere in the middle"Print Offset6(array(),6,8,4,5,4,10),"End"Sleep`
fxm
Posts: 9816
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

Same principle as dodicat, but using a true recursive function.
This recursive function is applicable to any number of dimensions:
(the number of dimensions is the parameter 'N')

Code: Select all

`Function offset(array() As String,I() As Integer,Byval N As Integer) As Integer  If N = 0 Then    Return 0  Else    Return offset(array(),I(),N-1)*(Ubound(array,N)-Lbound(array,N)+1)+I(N)-Lbound(array,N)  End IfEnd FunctionDim As String array(1 To 6,3 To 8,0 To 4,1 To 5,2 To 4,8 To 10)Dim As Integer I1(1 To 6) = {1,3,0,1,2,8}Print offset(array(),I1(),6),"Start"Dim As Integer I2(1 To 6) = {2,5,3,3,3,9}Print Offset(array(),I2(),6),"Somewhere in the middle"Dim As Integer I3(1 To 6) = {6,8,4,5,4,10}Print Offset(array(),I3(),6),"End"Sleep`
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Hi all!

Richard, Dodicat, Fxm:

Firstly thank you for your interest in my question.

I have not had time to test your example.

All three are very interesting, but I think the example of Dodicat,

to me may be the most interesting, as it uses formulas and I have no loop "For / Next" or similar.

The application of a formula is faster than multiple loops.

I will try tonight to try the three examples.

Thank you very much everyone!

Regards
fxm
Posts: 9816
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

lrcvs wrote:The application of a formula is faster than multiple loops.

Why a great constraint on the execution speed of the offset computation?
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

I do not understand the question?
codeFoil
Posts: 255
Joined: Dec 22, 2011 4:45
Location: United States
Contact:

Re: Position item in an array larger than 3D

In other words, for what purpose is your calculation intended? As you can see, there are always several ways to approach a problem, but without knowing what your goal is, others may over look an obvious solution and steer you toward an "optimal" self defeating approach.
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

I assumed the array already existed and Ircvs wanted to use pointers or assembly code for access.
I once started to write a converter for “Row major” to “Column major” translation of any arity.
FB could support both systems since the difference is only the forward or reverse application of the indexes in the recursive solution.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Hi all!

Codefoil, Richard:

The ultimate goal of my question is to show that a possible mathematical formula, we can find any element in an array multideminsional, more efficiently than using loops "For / Next".

Richard:
My computer skills / Basic, sonlos of a child in a kindergarten, are very low.

Also, I am too old to learn assembler or machine code, for me, is unthinkable!

Regards
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

@Ircvs. I am sorry if we have taken over your thread.

Assembly code is fun! IA32 is much easier than the old x86 segment addressed code.
You can play with asm blocks inside an FB program. You are never too old to have fun.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Sure, you're never too old for anything important, and above all learn!

Regards
dodicat
Posts: 6637
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Position item in an array larger than 3D

Richard's and fxm's snippets very enlightening.
I've messed about here with some asm code I dug out from the forum.
The scenario:
Somebody gives you an array (string here), and you haven't a clue what it is.
How this could come about I couldn't imagine, but it has happened.
You must investigate the array and get it's range, then pick a point in the middle.
(Perhaps fxm could overload his function sometime)
This is just a bit of fun, not to be used for mission critical work, but you can do it at home.

Code: Select all

` '=================================================#macro getdim(d)    Asm        mov esi, [ebp+8]        mov eax, [esi+16]        mov [d], eax    End Asm#endmacroFunction DIMENSION overload (array() As Integer) As Integer    Dim d As Integer    getdim(d)    Return dEnd FunctionFunction DIMENSION overload (array() As single) As Integer    Dim d As Integer    getdim(d)    Return dEnd FunctionFunction DIMENSION overload (array() As double) As Integer    Dim d As Integer    getdim(d)    Return dEnd FunctionFunction DIMENSION overload (array() As string) As Integer    Dim d As Integer    getdim(d)    Return dEnd Function'===================================================== FXMFunction offset(array() As String,I() As Integer,Byval N As Integer) As Integer  If N = 0 Then    Return 0  Else    Return offset(array(),I(),N-1)*(Ubound(array,N)-Lbound(array,N)+1)+I(N)-Lbound(array,N)  End IfEnd Function'========================================function post(n as integer) as string'(for st,nd,rd etc)    dim as string d=" "+str(n),t    If Left(d,1)<>"1" Then        Select Case  Right(d,1)        Case "1":t="st"        Case "2":t="nd"        Case "3": t="rd"        Case Else:t="th"        End Select    Else        t="th"    End If    return tend function'========================================================='Some unknown string array:Dim As String array(1 To 6,3 To 8,0 To 4,1 To 5,2 To 4,8 To 10)'=========================================================dim as integer n=DIMENSION(array())dim as integer I1(1 to n),I3(1 to n)For x As Integer  = 1 To n    I1(x)=Lbound(array,x)    Print "Lowerbound of ";x & post(x);" dimension ";Lbound(array,x)    I3(x)=ubound(array,x)    Print "Upperbound of ";x & post(x);" dimension ";Ubound(array,x)      PrintNext xPrint "Dimension of array (as can be seen)= ";nprintPrint offset(array(),I1(),n),"Start"Print Offset(array(),I3(),n),"End"print "Now we can pick somewhere in the middle e.g 2,5,3,3,3,9"Dim As Integer I2(1 To 6) = {2,5,3,3,3,9}Print Offset(array(),I2(),6),"Somewhere in the middle"Sleep `
fxm
Posts: 9816
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

dodicat wrote:(Perhaps fxm could overload his function sometime)

Any terminal recursion can be easily converted into a loop (no more risk of stack overflow, faster, but a little less compact code).

- Compacted function using recursion:

Code: Select all

`Function offset(array() As String,I() As Integer,Byval N As Integer) As Integer  If N > 0 Then    Return offset(array(),I(),N-1)*(Ubound(array,N)-Lbound(array,N)+1)+I(N)-Lbound(array,N)  End IfEnd Function`

- Less compact function using loop:

Code: Select all

`Function offset(array() As String,I() As Integer,Byval N As Integer) As Integer  Dim K As integer  For J As Integer = 1 To N    K = K*(Ubound(array,J)-Lbound(array,J)+1)+I(J)-Lbound(array,J)  Next J  Return KEnd Function`

Return to “General”

Who is online

Users browsing this forum: Stonemonkey and 3 guests