per9000 wrote:
Hi,
yes I could make a class that wraps my matrix, and that is pretty much
the situation I am in. The need to flatten the array comes from a
babel-problem, I need the values in external resources written in
languages that are not in the .NET family.
I did a small example in C/C# that illustrates a horribly ugly
solution, but that works and that answers one of my questions.
I pretty much create an array (in two dims) in C# and send it to C. C#
looks at the array as an int[,]. But somewhere underneath this it is
just a pointer. In the C level I receive a void* (by 'pure' luck it is
a match).
The from the below code is:
C# >Hello.
C# >calling printArr.
0 1 2 3 4 5 6 7 8 9
C# >Good night.
That means to me that C# orders its elements "row based" (assuming the
second index corresponds to rows).
// C# code
// ------------------
using System;
using System.Runtime.InteropServices;
using System.Collections.Generic;
using System.Text;
namespace PER9000
{
class ArrTest
{
[DllImport("ArrSub.dll")]
public static extern void printArr(int[,] A, int I, int J);
static void Main(string[] args)
{
Console.WriteLine("C# >Hello.");
int I = 2;
int J = 5;
int[,] A = new int[I, J];
int c = 0;
for (int i = 0; i < I; i++)
for (int j = 0; j < J; j++)
A[i, j] = c++;
Console.WriteLine("C# >calling printArr.");
printArr(A, I, J);
Console.WriteLine("C# >Good night.");
}
}
}
// ------------------
// C code
void __declspec(dllexport) __stdcall printArr(void* A, int I, int J);
void __declspec(dllexport) __stdcall printArr(void* A, int I, int J)
{
int c = 0;
int * B = (int *) A;
for (c = 0; c < I * J; c++)
printf(" %d", B[c]);
printf("\n");
}
// ------------------
This somehow answers part of my question. It seems that I have to use a
nested for-loop (I agree the complexity is O(number of elements)) to
hand-pick the elements one by one (I am afraid this will be a
bottleneck when it comes to speed).
So my conclusion is that there are no 'better' way to flatten an array
in two dims ordered by column.
Two points.
First, the only way faster than O(n) is something equivalent to C's
memcpy method that copies chunks of memory at a time. I think that this
is what you're looking for, but so far as I know C# doesn't allow you
to do things like this for security reasons. On modern CPUs the loop
operation should be fast enough anyway, as the whole row will likely
fit into on-board cache and the loop for copying a row (at least) will
not have to fetch from memory. I don't know about the writing of the
array to its new "flattened" structure... that may fit into cache as
well. Anyway, using pure C#, there's no "memcpy" any more, so there's
nothing faster than O(n).
Second, I think that you're thinking about the problem from a
too-low-level point of view. In situations like this, you have two
possible solutions:
1) Maintain the values in their most logical form (i.e. a
two-dimensional array) and whenever you need to read them in another
form (e.g. flattened into a column-then-row order) then do the
necessary calculations to fetch them in that order. This is the
solution I proposed. This solution makes sense if most of the time you
are manipulating / using the values as a 2-D array and only
occasionally do you need them in their row-major or column-major order.
>From a performance point of view, this solution works well if you spend
most of your time in the C# code, but only occasionally have to call
other languages and thus translate the array into column-major order.
(As you've seen, C# stores multidimensional arrays in row-major order
and so is compatible with C, for example, although I don't know if that
is guaranteed to be so into the future.)
If, however, you make repeated calls to other languages and you have to
transform the array each time, and you suspect that this will be a
performance problem, the solution is not to find a way to transform the
array faster, but to find a way to not transform the array at all.
2) One solution along those lines is to maintain the values in multiple
orders and use whichever order is most useful at any given moment. This
makes sense if the values are read much more than they are modified,
and the reads are as often in one order as another. The code for a
solution like that might look something like this:
public class MyMatrix<T>
{
private T[] _rowMajor;
private T[] _columnMajor;
private int _rowCount;
private int _columnCount;
public MyMatrix(int rows, int columns)
{
if (rows <= 0) throw new ArgumentException(...);
if (columns <= 0) throw new ArgumentException(...);
this._rowCount = rows;
this._columnCount = columns;
this._rowMajor = new T[rows * columns];
this._columnMajor = new T[rows * columns];
}
public T this[int row, int column]
{
get { return this._rowMajor[row * this._columnCount + column];
}
set
{
this._rowMajor[row * this._columnCount + column] = value;
this._columnMajor[column * this._rowCount + row] = value;
}
}
...etc...
}
As you can see, the cost here is writing to the structure, which is now
more expensive. The return on that investment is that you have row and
column-major order arrays constantly maintained for quick read-back. If
the C# program is constantly reading the values as a two-dimensional
array then you could add that as a third, constantly-maintained form
for the data. In other words, store the data in triplicate:
two-dimensional, row-major, and column-major orders.
This becomes more complicated, however, if the programs you call will
be modifying the arrays. In that case when you return from calling the
other language you have to synch any changes from the array you passed
back to the other copy or copies. So, if you pass a row-major array to
a program that makes changes to it, you then have to copy that back
into the column-major version (and potentially to the two-dimensional
version, if you're maintaining that) so that they remain in synch.
Since you can't know what the program changed, that would cost you at
least one entire array copy on every call, which would be the same cost
as the first solution.
So, if the other-language programs you're calling do nothing but read
the arrays, and you call them frequently, solution #2 is better. If
they update the arrays, or if they are called infrequently and your C#
program does frequent updates to the array then solution #1 is at least
no worse, and probably better. Finally, if the programs you call in
other languages update the arrays they're passed then you're going to
have performance problems no matter what you do.
