Link to home
Start Free TrialLog in
Avatar of CyberKnight
CyberKnight

asked on

Problem with Dynamic arrays

Hi there !

It's either that Im doing something incorrectly, or dynamic arrays function a little differently... ;-)

I have a graphic effect that is calcuated using a "fixed" 2D array. It works great.

But when I change the fixed array to a dynamic array, it screws up the effect.

Please try this code below.

The code below just fills a little rectangle, in a certain way.

Curently it is using a "fixed" array like...
"array [1..100,1..150] of integer;".
You can run it as is.
The effect that you see is a white line that fills the screen.

But when you change the code by commenting the fixed array declaration, show as {@} in the code, and then uncomment the dynamic array code, shown as {#},

... the effect gets messed up ..???


I require the code below to use the dynamic array, but it must produce the same effect, when run as is shown below.



(**************** Code Begin *********************)
{$R+}
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ExtCtrls;

type
  TForm1 = class(TForm)
    Timer1: TTimer;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Timer1Timer(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
Const MaxX=100;
      MaxY=50;
var
  Form1: TForm1;

{@}    B,OldB:array [0..MaxX, 0..MaxY] of Integer;
{#} //   B,OldB:array of array of Integer;
    BMP:TBitMap;
implementation

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);
Var j:Integer;
begin
 BMP:=TBitMap.Create;
 BMP.Width:=MaxX;
 BMP.Height:=MaxY;

(*    // Code to set the Length of the dynamic array
{#} SetLength(   B,MaxX);
{#} SetLength(OldB,MaxX);
{#} For j := 0 to MaxX-1 do
{#} Begin
{#}   SetLength(   B[j],MaxY);
{#}   SetLength(OldB[j],MaxY);
{#} End;
*)

// Just put some white dots on the BMP
 For j := 0+30 to MaxX-31 do
   B[J,MaxY div 2]:=255;
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
BMP.Free;
end;

procedure TForm1.Timer1Timer(Sender: TObject);
Var X,Y:Integer;
begin
  OldB:=B;
  for Y := 1 to MaxY-2 do
    for X := 1 to MaxX-2 do
    begin
      // Some effect that eventually fills the whole area.
      B[X,Y]:=
         (OldB[X-1,Y]+ OldB[X+1,Y]+
          OldB[X,Y-1]+ OldB[X,Y+1]) div 2;

      //Clips color
      If B[X,Y] > 255 then B[X,Y] :=255;
      //Set the color;
      BMP.Canvas.Pixels[X,Y]:=RGB(B[X,Y],B[X,Y],B[X,Y]);
    End;
  //Draw on form
  Form1.Canvas.Draw(0,0,BMP);
end;
end.
(***************** CODE END **************************)


Avatar of robert_marquardt
robert_marquardt

You can do a SetLength(B, MaxX, MaxY);
No need for a loop.
Avatar of Mohammed Nasman
Hello

  your declaration is not for dyanmic array, it's for fixed size array
if you want to declare a dyanmic array use it like:

 B,OldB:array of array of Integer;

then your code will work fine


Best regards
Mohammed Nasman
Avatar of CyberKnight

ASKER

Hmm...Yep Robert, I recently realized that U can declare a dynamic array...SetLength (Array, 100 , 100); (So there actually is no need for my loop.


Mohammed.. When I used a fixed array...the code works...but when I use a dynamic array..its doesnt..
If U look at the line after the "fixed" array declaration, U will see that Ive commented out the dynamic array declaration...


Anyway...I seem to have found the problem...

My problem is that

OldB:=B; // is actually incorrect
//the above works for fixed arrays, but not for dynamic arrays....






The problem was not related to the declaration...of the dynamic array.

Ive found the solution to the problem, which is actually...in my assignment from 1 dynamic array to the other.
This line is the guilty one:

OldB:=B;

When using static arrays, it copies the array content, but when using dynamic arrays, it only sets both pointers "OldB" and "B" to the same pointer. After you've done that, OldB and B have always the same content.

Replace the line with "OldB := Copy(B);", then your sources will work correctly.

Regards, Madshi.
I repost the same comment here, that I posted in the other question:

I'm sorry, I gave you wrong information. The function "b := Copy(a)" works fine on 1d arrays only. When being used on 2d arrays, it works like "b := a". That's not good, Borland...   :-(

Here comes the solution. I don't like it too much (because IMO Borland should do that for us), but it works.

type T2d = array of array of integer;

procedure Copy2d(const a1: T2D; var a2: T2D);
var i1 : integer;
begin
  i1 := Length(a1);
  for i1 := 0 to i1 - 1 do
    Move(pointer(a1[i1])^, pointer(a2[i1])^, Length(a1[i1]) * 4);
end;

P.S: When you call this function, both arrays must have be created already and must have exactly the same size(s).
How about that:

OldB:=B;
SetLength(B,MaxX,MaxY); //this line will make the dynamic array unique according to Delphi help

That is, by resetting the array's size (even if it is the size it already is) will make it a unique copy instead of a referenced array.
Madshi, it makes perfec sense that Copy() does not work as expected when two or more dimensions are used. Actually, it does work correctly; remember that we have an array of array. So, when we use Copy, it will makje a copy of the first array (the first dimension) and copy all the other arrays into it, so that the second dimension arrays are just reference-counted (A,B are our vars, 1 and 2 the dimensions):

A
  \
    1-2 (1 is referenced twice, 2 is unique)
  /
B

becomes when Copy()-ed:

A-1 (unique)
    \
      2 (referenced twice)
    /
B-1 (also unique)

I guess the SetLength approach will work (I did not test it) because it should reset all dimensions, the ones of the higher dimensional arrays also, and thus make it completely unique.
Hm, my ASCII graphics got broken by the font, I'll try a second time:

A
     \
           1-2 (1 is referenced twice, 2 is unique)
     /
B

becomes when Copy()-ed:

A-1 (unique)
          \
               2 (referenced twice)
          /
B-1 (also unique)
AvonWyss, you're absolutely right. I've checked the SetLength approach, it really works.

Then I also did a performance test:

Copy + SetLength: 3470ms
Copy2d: 200ms

So the Copy2d function is about 1700% faster.

Regards, Madshi.
Correction: We don't need to do Copy + SetLength, we can also do:

a1 := a2;
SetLength(a1, MaxX, MaxY);

In that case it doesn't take 3470ms, but only 3060ms.

Furthermore the difference to Copy2d is only that big, if you change the array very often without allocating/freeing it. But in CyberKnight's sources it's like that, so for him Copy2d should be the prefered solution.

Regards, Madshi.
Madshi, I think you did not do a really fair comparison of the two methods. Yours expects two already allocated arrays, while thr SetLength approach allocated the memory of the second array. So, if you measure the allocation of memory for the second array you're using also, both methods should end up being about the same in the means of speed: I believe that the memory manager is eating up most of the time, because 100+1 memory blocks are allocated during the SetLength.

The best method would be not to copy any data anyways. This can be easily achieved by adding a third dimension to the array:

instead of
    B,OldB: array of array of Integer;

declare
    B: array of array of array of Integer;

and use SetLength(B,1,100,150);

Lets say we use an Index, so we have:

B[Index,X,Y] -> current array
B[1-Index,X,Y] -> previous array

to switch arrays, just use Index:=1-Index;

In this case, no memory has to be copied, and thus the speed should be even better. Btw, CyberKnight, have a look at the ScanLine property of the bitmap...
>> Madshi, I think you did not do a really fair comparison of the two methods.

Hmmm... Let us see...

>> Yours expects two already allocated arrays, while thr SetLength approach allocated the memory of the second array. So, if you measure the allocation of memory for the second array you're using also, both methods should end up
being about the same in the means of speed: I believe that the memory manager is eating up most of the time, because 100+1 memory blocks are allocated during the SetLength.

You're absolutely right. *But* I explicitly said in my previous comment: "the difference to Copy2d is only that big, if you change the array very often without allocating/freeing it". So I already said quite exactly what you're saying here. Copy2d is only faster under special circumstances.

Now look, in CyberKnight's original sources the allocation was done in FormCreate already - so we *DO* have those special circumstances! CyberKnight does a "OldB := B" in the timer. This one line is the problem. It has to be replaced with something else. You can now either replace it with "Copy2d", or with "OldB := B; SetLength(OldB, MaxX, MaxY)". And in exactly this situation "Copy2d" is a whole lot faster. Don't you agree with that?

Would a 3d array really be faster? I'm not sure. Neither Copy2d nor a 3d array do any allocation (and that is the biggest time consumer). So the difference can not be that big. Copy2d does a move, which costs time for sure. But a 3d array has one index more. That means any access to the array's values has to resolve one pointer more. That also costs time, and that wich each access. I'm really not sure which one is faster in the end. That probably depends on the circumstances again...
Maybe the 3d array is faster in this situation, but then only a bit, and on the other side it consumes a lot more memory. So I think I would go with the 2d array.

Regards, Madshi.
Madshi, I completely agree with you. However, I felt that to people which do not have as much insight in Delphi's way of dealing with things, the comment I made could hold important information. Your speed comarison did make the SetLength approach look pretty slow, but it's important to understand that this slowness is due to the difference in the operation done. My only intention was to point this out. As for the 3D version, it will use pretty much exacly as much memory since we have one array with a second dimension instead of two separate 2D arrays (the OldB array is obsolete in the 3D version).

The 2D approach will be faster compared the shown 3D version indeed if you do a lot of access to fileds in the array since the 1st dimension is also a dynamic array. Instead of a dynamic 1st dimension, one could also use a static (if that's the word) dimension, thus making it even with the 2D performance:

type
    B: array[0..1] of array of array of Integer;

On the other hand, the 3D approach does not copy a single memory block to get the swapping done, thus making the switching new->old a matter of no time at all (compared to the memory copy used).

Hopefully we haven't confudes
(oops, hit the wrong button)
..confused everyone watching this discussion ;-)
ASKER CERTIFIED SOLUTION
Avatar of Madshi
Madshi

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Yeah, kids, listen to grandpa Madshi... ;-)
(O:
Wow....

This has certainly turned out into an interesting discussion....

AvonWyss, your a1:=a2; Setlength(a1,rows,cols); works fine...but is slow due to the de/re/allocation of memory for the array.

It seems that Madshi's Copy2D works faster because (in my case) the size of my arrays dont change.

The 3D array swaping pointer method would work fine, but Madshi has simplified it..... :-)

After some testing... it seems that I will be using the method suggested by Madshi.
All this does is swap the pointers of the 2 arrays.
When I looked at my code, I realized that I didnt really need to "copy" the array. Swapping it would be fine, as I perform calculations on 1 array, after a "save" a copy of my previous calculations in the other array.
So, by swapping array pointers, it works perfectly (and this doesnt really depend on array size either, therefore making it just as fast for a 1000X1000 array as it would be for a 10X10 array.

Ive done some "testing" on speeds.... (My"testing" program is below). I dont know of any other way to test speeds, but I think it is kind of reliably.)

Thanx to you all who have posted stuff.


(********************)
(* these tests performed on my PII 450, 128 ram*)
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Forms, Dialogs,
  StdCtrls, Classes, Controls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
type
  T2d = array of array of Integer;
var
  Form1: TForm1;
  H,W:Integer;
  a1,a2:T2d;
implementation

{$R *.DFM}

procedure Copy2d(const a1: T2D; var a2: T2D);
var i1 : integer;
begin
 i1 := Length(a1);
 for i1 := 0 to i1-1  do
   Move(pointer(a1[i1])^, pointer(a2[i1])^, Length(a1[i1]) * 4);
end;

procedure TForm1.Button1Click(Sender: TObject);
var swapVar : dword;
  k,j:integer;
  s:dword;
begin
  s:=Gettickcount;
  For j := 1 to 1000 do
  Begin
//    Copy2d(a1,a2); // 590 to 611ms
// Madshi's method

//    For k := 0 to H-1 do
//      a1[k]:=Copy(a2[k],0,W);      // 732 to 742
// My old method

//    a1:=a2; SetLength(a1,H,W);  // 2093 to 2113
// AvonWyss's Method
// Note: this method continuously deallocates and reallcoates memory, making it slow.

//    swapVar := dword(a1);
//    dword(a1) := dword(a2);    //0
//    dword(a2) := swapVar;
// Madshi's method
// Note : this method doesnt really copy, but just swap the array pointers. Therfore almost no overhead.
  End;
  Showmessage(inttostr((gettickcount-s)));
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  h:=200;   w:=200;
  SetLength(a1,h,w);
  SetLength(a2,h,w);
end;

end.