April 08, 2007
Graham wrote

> A floating point texture buffer - 3 floats per pixel, and (say)
> 640x480 pixels.

To me your remark does not explain the necessity of O(1) access to an element randomly choosen---sorry for letting that out in my previous question.

-manfred
April 08, 2007
A bit of confusion here:-)  Yes, it's a simple, static fixed size, multi-dimensional array.  I could use a 1D array, but I wanted to try out the 2D approach and was puzzled why I couldn't use the initialiser for the entire array if I had more than one dimension.  There's nothing more to this!

Thanks.

Daniel Keep wrote:
> 
> Chris Nicholson-Sauls wrote:
>> Daniel Keep wrote:
>>> Graham wrote:
>>>> A floating point texture buffer - 3 floats per pixel, and (say) 640x480
>>>> pixels.
>>>>
>>>> Manfred Nowak wrote:
>>>>> Graham wrote
>>>>>
>>>>>> several thousand elements large.
>>>>> In what domains do one need to represent dense multidimensional
>>>>> structures with O(1) time for accesses of elements?
>>>>>
>>>>> -manfred 
>>> Perhaps you shouldn't be using jagged arrays, then.  int[][] is *NOT* a
>>> multidimensional array.  It's basically equivalent to this:
>>>
>>> struct int_array
>>> {
>>>     int* ptr;
>>>     size_t length;
>>> }
>>>
>>> struct int_array_array
>>> {
>>>     int_array* ptr;
>>>     size_t length;
>>> }
>>>
>>> int_array_array buffer;
>>>
>>> Notice those nested pointers; that means that your texture is not
>>> necessarily contiguous in memory, which would make, for example, loading
>>> the texture into GL a pain in the behind.  Not sure if the cache would
>>> have problems...
>>>
>>> I think there's a few multidimensional array templates floating
>>> around... or if not, you can always write your own :)
>>>
>>>     -- Daniel
>>>
>> Actually, /IF/ he's using static/fixed-length arrays, then as I
>> understand it this ceases to be true.  That is, static arrays are solid
>> blocks of memory -- and I assume this stays the same for
>> multi-dimensional arrays.  Of course, /IF/ he's using dynamic-length
>> arrays, then you're absolutely correct about it being likely opposite.
>>
>> -- Chris Nicholson-Sauls
> 
> Ah yes, of course.  Sorry; bit dense today :P
> 
> 	-- Daniel
> 
April 08, 2007
I'm not sure why you're concentrating on O(1) random access.  I need a static buffer of fixed width & height.  As I mentioned in a previous post, I could use a 1D array, but wanted to try a multi dimensional array and was puzzled why the initialiser didn't work.  I'm passing this array to OpenGL, so I need a contiguous buffer.

Does that explain what I'm after?

Thanks.

Manfred Nowak wrote:
> Graham wrote
> 
>> A floating point texture buffer - 3 floats per pixel, and (say)
>> 640x480 pixels.
> 
> To me your remark does not explain the necessity of O(1) access to an element randomly choosen---sorry for letting that out in my previous question.
> 
> -manfred
April 08, 2007

Graham wrote:
> A bit of confusion here:-)  Yes, it's a simple, static fixed size, multi-dimensional array.  I could use a 1D array, but I wanted to try out the 2D approach and was puzzled why I couldn't use the initialiser for the entire array if I had more than one dimension.  There's nothing more to this!
> 
> Thanks.

You *don't* have more than one dimension; you're really nesting arrays.
 Strictly speaking, int[5][5] is an (albeit static) jagged array.

I realise that for your purposes, it's six of one, half a dozen of the other -- I'm just being pedantic :)

	-- Daniel

> Daniel Keep wrote:
>>
>> Chris Nicholson-Sauls wrote:
>>> Daniel Keep wrote:
>>>> Graham wrote:
>>>>> A floating point texture buffer - 3 floats per pixel, and (say)
>>>>> 640x480
>>>>> pixels.
>>>>>
>>>>> Manfred Nowak wrote:
>>>>>> Graham wrote
>>>>>>
>>>>>>> several thousand elements large.
>>>>>> In what domains do one need to represent dense multidimensional structures with O(1) time for accesses of elements?
>>>>>>
>>>>>> -manfred
>>>> Perhaps you shouldn't be using jagged arrays, then.  int[][] is *NOT* a multidimensional array.  It's basically equivalent to this:
>>>>
>>>> struct int_array
>>>> {
>>>>     int* ptr;
>>>>     size_t length;
>>>> }
>>>>
>>>> struct int_array_array
>>>> {
>>>>     int_array* ptr;
>>>>     size_t length;
>>>> }
>>>>
>>>> int_array_array buffer;
>>>>
>>>> Notice those nested pointers; that means that your texture is not
>>>> necessarily contiguous in memory, which would make, for example,
>>>> loading
>>>> the texture into GL a pain in the behind.  Not sure if the cache would
>>>> have problems...
>>>>
>>>> I think there's a few multidimensional array templates floating around... or if not, you can always write your own :)
>>>>
>>>>     -- Daniel
>>>>
>>> Actually, /IF/ he's using static/fixed-length arrays, then as I understand it this ceases to be true.  That is, static arrays are solid blocks of memory -- and I assume this stays the same for multi-dimensional arrays.  Of course, /IF/ he's using dynamic-length arrays, then you're absolutely correct about it being likely opposite.
>>>
>>> -- Chris Nicholson-Sauls
>>
>> Ah yes, of course.  Sorry; bit dense today :P
>>
>>     -- Daniel
>>

-- 
int getRandomNumber()
{
    return 4; // chosen by fair dice roll.
              // guaranteed to be random.
}

http://xkcd.com/

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP  http://hackerkey.com/
April 08, 2007
Graham wrote


> Does that explain what I'm after?

Yes. Thx. I am just searching for the more general pattern.

Now I can give up to find a foundation for your wish:
> I'd much rather treat it similarly to a 1D array in this case!

As you state it yourself it is just a single case, where you want to treat something differently from the general pattern, that arrays of type T[] are assigned to by mentioning a value of the type T.

You want to extend this general pattern by being able for all natural numbers n to initialize an array of type T[]^n by mentioning a value of type T.

But how to write a class that is able to mimic this behaviour?

-manfred




April 08, 2007
As I said before, I could use a normal 1D array.  My basic point is that as I was trying to initialise a static, rectangular array, there's no reason (that I can see) why the initialiser can't work for more than 1D.

(And to be pedantic, int[5][5] is a 2D rectangular array, which in memory is exactly the same as int[25] - a 1D array, of course - so six of one and half a dozen of the other perhaps, but int[5][5] does have > 1 dimension :-))

(Thanks for the previous recommendations though!)

g

Daniel Keep wrote:
> You *don't* have more than one dimension; you're really nesting arrays.
>  Strictly speaking, int[5][5] is an (albeit static) jagged array.
> 
> I realise that for your purposes, it's six of one, half a dozen of the
> other -- I'm just being pedantic :)
> 
> 	-- Daniel
April 09, 2007
Graham Wrote:
> (And to be pedantic, int[5][5] is a 2D rectangular array, which in memory is exactly the same as int[25] - a 1D array, of course - so six of one and half a dozen of the other perhaps, but int[5][5] does have > 1 dimension :-))

Actually, you're wrong sir.  An int[5][5] produces an array containing 5 structs, each of:

struct Array {
  size_t(or was it int?  uint?) length;
  void* ptr;
}

Each of those arrays then points to another array of 5 elements.

What I believe you want is a rectangular array:

int[5,5], which will produce a single Array struct that you can access via taking a multiple of the first index added to the second index (or is it vice versa?)

This notation tends to typically be inferior to int[25] for that very reason, each access requires math on two indices.  I might also note that it is typically more efficient to use a power of two for array sizes for indexing purposes - so long as the array size doesn't cause the OS you're working on to have difficulty allocating the space.

Some OS's allocate in 4kb units and then take 16 bytes for metadata, some allocate anything > 2kb in a "giant data" page-set which may be more inefficient than the smaller page-sets as it may allocate your data accross pages.
April 09, 2007
Graham, I was wondering if you were someone that I know.  Are you the Graham I am thinking of?

-Craig

"Graham" <grahamamacdonald@gmail.com> wrote in message news:ev7kdm$1p8e$1@digitalmars.com...
> Why will array setting work for a 1D array, but not a 2D?  If I enter:
>   int[5] buffer;
>   buffer[] = 5;
>
> It compiles, but if I enter:
>   int[5][5] buffer;
>   buffer[][] = 5;
>
> (I tried the variation buffer[] = 5, but that didn't work either.)
>
> It fails to compile (in gdc), with the warning:
>
>   MainLoop.d:56: Error: cannot implicitly convert expression (5) of type
> int to int[5]
>   Error: cannot cast int to int[5]
>   make: *** [build/MainLoop.o] Error 1
>
> To my untrained eye, it looks like it would like me to pass it an int[5] to initialize the array, but that's a bit odd - I'd much rather treat it similarly to a 1D array in this case!
>
> Thanks,
> graham


April 09, 2007
Dan wrote:
> Graham Wrote:
>> (And to be pedantic, int[5][5] is a 2D rectangular array, which in memory is exactly the same as int[25] - a 1D array, of course - so six of one and half a dozen of the other perhaps, but int[5][5] does have > 1 dimension :-))
> 
> Actually, you're wrong sir.  An int[5][5] produces an array containing 5 structs, each of:
> 
> struct Array {
>   size_t(or was it int?  uint?) length;
>   void* ptr;
> }
> 
> Each of those arrays then points to another array of 5 elements.

No, he was right. That struct is only used for dynamic arrays, not with static arrays. Static arrays are just a linear row of members stored in-place (but passed by reference).
You don't need to take my word for it, look at what the compilers do:
=====
$ cat test.d
import std.stdio;

int[5][5] matrix;

void main() {
    // Initialize
    foreach (r, inout row; matrix) {
        foreach (c, inout elt; row) {
            elt = r * 5 + c;
        }
    }

    // Access as a linear array:
    uint* p = cast(uint*) matrix.ptr;
        // (Note: ".ptr" is not actually stored but inserted as
        // a constant)
    for (size_t i = 0; i < 25; i++) {
        writef(p[i],' ');
    }
    writefln();
}
$ dmd -run test.d
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
$ gdc -o test test.d && ./test
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
=====

> What I believe you want is a rectangular array:
> 
> int[5,5], which will produce a single Array struct that you can access via taking a multiple of the first index added to the second index (or is it vice versa?)

Sorry, "int[5,5]" only compiles because of the obscure comma operator. The first 5 is evaluated and thrown away, what's left is a regular old int[5]. (Still stored in-place by the way)

> This notation tends to typically be inferior to int[25] for that very reason, each access requires math on two indices.  I might also note that it is typically more efficient to use a power of two for array sizes for indexing purposes - so long as the array size doesn't cause the OS you're working on to have difficulty allocating the space.

Providing two indices to a variable declared as "int[5,5]" will evaluate the first index and throw it away, only using the second. The comma operator strikes again.

> Some OS's allocate in 4kb units and then take 16 bytes for metadata, some allocate anything > 2kb in a "giant data" page-set which may be more inefficient than the smaller page-sets as it may allocate your data accross pages.
April 09, 2007
I think you have yourself confused. http://stumail.curry.edu/~dthibeau/Graham_Craig.jpg


> Graham, I was wondering if you were someone that I know.  Are you the Graham I am thinking of?
>
> -Craig