Recent

Author Topic: matrix row exchange  (Read 540 times)

Paolo

  • Sr. Member
  • ****
  • Posts: 354
matrix row exchange
« on: December 04, 2022, 12:34:36 pm »
Hello,

in some code of mine I have to swap two rows of a matrix, and I am trying to increase the speed of such operation
Here the initial code fragment

Code: Pascal  [Select][+][-]
  1. Code-n.1
  2. Type
  3.    TMat = array of array of double;
  4. var
  5.    AMat : TMat;
  6.    Tmp : double;
  7. ..
  8.     for k:=0 to ADim-1 do begin
  9.       Tmp:=MatA[Row1,k];
  10.       MatA[Row1,k]:=MatA[Row2,k];
  11.       MatA[Row2,k]:=Tmp;
  12.     end;
  13.  

But taking advantage of TMat Type declaration I can write

Code: Pascal  [Select][+][-]
  1. Code-n.2
  2. Type
  3.    TMat = array of array of double;
  4. var
  5.    AMat : TMat;
  6. …TmpRow : array of Double;
  7.   for k:=0 to ADim-1 do begin
  8.     TmpRow:=AMatA[i];
  9.     AMatA[i]:=AMatA[imax];
  10.     AMatA[imax]:=TmpRow;
  11. end;
  12.  

But it is still not satisfactory in terms of speed (true copy), then I wrote

Code: Pascal  [Select][+][-]
  1. Code-n.3
  2. Type
  3.    TMat = array of array of double;
  4. .
  5. var
  6.    AMat : TMat;
  7.    Tmp1 : Pointer;
  8. .
  9.     Tmp1:=Pointer(AMatA[i]);
  10.     Pointer(AMatA[i]):=Pointer(AMatA[imax]);
  11.     Pointer(AMatA[imax]):=Tmp1;
  12.  

This seems the fastest !

Questions:

Q1: the code n.3 can be better written? in particular about the implemented type casting.
Q2: missed something that makes code n.3 more fragile ? NB: in the code above all rows of A have the same size, this is given as pre-condition.

Thank you in advance.

jamie

  • Hero Member
  • *****
  • Posts: 5046
Re: matrix row exchange
« Reply #1 on: December 04, 2022, 12:55:25 pm »
U could look at the MOVE procedure where u can pass address and size to source and destination .
De phone jamie
The only true wisdom is knowing you know nothing

MarkMLl

  • Hero Member
  • *****
  • Posts: 5860
Re: matrix row exchange
« Reply #2 on: December 04, 2022, 01:27:27 pm »
So what you're doing is relying on the implementation-specific assumption that a dynamic array is represented by a pointer. I /think/ it's safe, particularly since some of the core developers have IIRC told us that a SetLength(... 0) and ... := nil are equivalent.

However I think that I'd (a) explore whether there's some way of getting your second example to compile to a pointer exchange (i.e. by searching for some magic way to make a row-copy to be a reference copy, at least until written... I don't know whether FPC can do that) and (b) in any case have some test code in your app's startup to check that your idea of how an array is stored is correct (in case e.g. you change the inner array to be fixed-size at some point).

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Paolo

  • Sr. Member
  • ****
  • Posts: 354
Re: matrix row exchange
« Reply #3 on: December 04, 2022, 04:39:16 pm »
Thanks jamie and MarkMLI.

I didn't find any specific "magic" for such purpose  :(

GetMem

  • Hero Member
  • *****
  • Posts: 3917
Re: matrix row exchange
« Reply #4 on: December 04, 2022, 06:50:40 pm »
Hi Paolo,

Use the Move method to swap two rows. I attached a small demo application, you can play with different options.

Paolo

  • Sr. Member
  • ****
  • Posts: 354
Re: matrix row exchange
« Reply #5 on: December 04, 2022, 07:12:16 pm »
Thank you very much, GetMem,

I see that you and jamie suggested to use MOVE, but my code n.3 is not easier and faster ? just swap pointers...
the main goal here is speed, missed something ?

in my case, very large matrix, such swap can happen very frequently, and inside an iterative procedure of several loops.

MarkMLl

  • Hero Member
  • *****
  • Posts: 5860
Re: matrix row exchange
« Reply #6 on: December 04, 2022, 07:21:00 pm »
I agree, but I'd like to see a comment from somebody like PascalDragon.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

howardpc

  • Hero Member
  • *****
  • Posts: 4098
Re: matrix row exchange
« Reply #7 on: December 04, 2022, 07:31:49 pm »
This little program shows you don't need to use casting to pointers, or Move (though you can), since standard syntax is just as fast.
Code: Pascal  [Select][+][-]
  1. program rowSwap;
  2.  
  3. {$IfDef MSWINDOWS} {$apptype console} {$EndIf}
  4.  
  5. uses
  6.   SysUtils;
  7.  
  8. type
  9.    TDoubleArray = array of Double;
  10.  
  11.    TMatrix = array of TDoubleArray;
  12.  
  13. const
  14.   RowLength = 30;
  15.   RowCount = 10000;
  16.   HighValue = 1000;
  17.  
  18.   procedure InitialiseMatrix(aRowLength, aRowCount: SizeInt; out matrix: TMatrix);
  19.   var
  20.     r, c: SizeInt;
  21.   begin
  22.     {$R-}
  23.     Randomize;
  24.     matrix := Nil;
  25.     SetLength(matrix, aRowCount, aRowLength);
  26.     for r := 0 to aRowCount-1 do
  27.       for c := 0 to aRowLength-1 do
  28.         matrix[r, c] := Random * HighValue;
  29.   end;
  30.  
  31.   function SwappedRowsClassic(aRow1, aRow2: SizeInt; var aMatrix: TMatrix): Boolean;
  32.   var
  33.     tmpRow : TDoubleArray;
  34.   begin
  35.     if (aRow1 > High(aMatrix)) or (aRow1 < 0) or
  36.        (aRow2 > High(aMatrix)) or (aRow2 < 0) or
  37.        (aRow1 = aRow2) then
  38.       Exit(False);
  39.  
  40.     tmpRow := aMatrix[aRow1];  // no need to cast tmpRow as a pointer - the fact that it may be a pointer is an implementation detail the programmer does not need to know
  41.     aMatrix[aRow1] := aMatrix[aRow2];
  42.     aMatrix[aRow2] := tmpRow;
  43.     Result := True;
  44.   end;
  45.  
  46.   procedure ShowRow(aRow: SizeInt; aMatrix: TMatrix);
  47.   var
  48.     i: Integer;
  49.   begin
  50.     if aRow > High(aMatrix) then
  51.       Exit;
  52.     WriteLn('Row: ',aRow);
  53.     for i := 0 to High(aMatrix[aRow]) do
  54.       Write(aMatrix[aRow][i]: 2:8);
  55.     WriteLn;
  56.   end;
  57.  
  58. var
  59.   mat: TMatrix;
  60.   start: TTime;
  61.  
  62. begin
  63.   start := Time;
  64.   InitialiseMatrix(RowLength, RowCount, mat);
  65.   WriteLn('Time to initialise matrix is ',DateTimeToTimeStamp(Time - start).Time,' ms'#10);
  66.   ShowRow(0, mat);
  67.   ShowRow(RowCount-1, mat);
  68.  
  69.   start := Time;
  70.   if SwappedRowsClassic(0, RowCount-1, mat) then
  71.     begin
  72.       WriteLn(#10'Time to swap rows is ',DateTimeToTimeStamp(Time - start).Time,' ms'#10);
  73.       ShowRow(0, mat);
  74.       ShowRow(RowCount-1, mat);
  75.     end;
  76.   WriteLn(#10'Press Enter to finish');
  77.   ReadLn;
  78. end.

Paolo

  • Sr. Member
  • ****
  • Posts: 354
Re: matrix row exchange
« Reply #8 on: December 04, 2022, 07:37:59 pm »
this is my cone n.2 ! but in this case a real copy of the whole array takes place, not only pointer assignement, at least was my understanding ... am I wrong ?

GetMem

  • Hero Member
  • *****
  • Posts: 3917
Re: matrix row exchange
« Reply #9 on: December 04, 2022, 07:45:36 pm »
@Paolo

Quote
I see that you and jamie suggested to use MOVE, but my code n.3 is not easier and faster ? just swap pointers...
the main goal here is speed, missed something ?
Yes your method is faster and perfectly safe while swapping rows inside the same matrix. However if you work with two or more matrices, it will become evident that you cannot switch rows without physically switch the elements, especially if one of the matrix is "freed"(MatA = nil) at some point. So my solution is a more generic one, besides move is incredibly fast too. 

Paolo

  • Sr. Member
  • ****
  • Posts: 354
Re: matrix row exchange
« Reply #10 on: December 04, 2022, 07:54:38 pm »
ok, thanks again.

the fragment of code I show is as an example. Obviously in real scenario the implementation shall include matrix size control, etc... 
At the begin, the code is just to be used inside the same matrix (reagular matrix ie rectangular), but now you have mentioned the row swap between different matrix, I did not check, but the pointer mechanism, with the needed controls, should be still applicable, I'll give a look at this case as soon as possible.





MarkMLl

  • Hero Member
  • *****
  • Posts: 5860
Re: matrix row exchange
« Reply #11 on: December 04, 2022, 07:55:36 pm »
Yes your method is faster and perfectly safe while swapping rows inside the same matrix. However if you work with two or more matrices, it will become evident that you cannot switch rows without physically switch the elements, especially if one of the matrix is "freed"(MatA = nil) at some point. So my solution is a more generic one, besides move is incredibly fast too.

I'm scraping the bottom of my mathematical barrel here, but I seem to recall that there are times when it is recommended to transpose (⍉) rows and columns in the middle of a big calculation for the sake of efficiency.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Paolo

  • Sr. Member
  • ****
  • Posts: 354
Re: matrix row exchange
« Reply #12 on: December 04, 2022, 07:57:44 pm »
Yes if you do C=A*B if B is BTrasp, you accessing both by rows

 

TinyPortal © 2005-2018