Recent

Author Topic: Reverse order of an array  (Read 16410 times)

justnewbie

  • Sr. Member
  • ****
  • Posts: 292
Reverse order of an array
« on: March 25, 2018, 01:12:37 pm »
Is there any built-in function in FP that is able to re-indexing an array in reverse order?
If not, can you show me a custom-made example with a fast solution?

This is my solution, but I'm sure there is something better:
Code: Pascal  [Select][+][-]
  1. procedure ReverseOrder(var origArray: array of double);
  2. var
  3.    tempArr: array of double;
  4.    i: integer;
  5. begin
  6.    SetLength(tempArr, Length(origArray));//Follow-up addition just for the sake of completeness
  7.    for i := High(origArray) downto Low(origArray) do
  8.       tempArr[i] := origArray[High(origArray) - i];
  9.    for i := High(tempArr) downto Low(tempArr) do
  10.       origArray[i] := tempArr[i];
  11. end;  
« Last Edit: March 25, 2018, 07:18:47 pm by justnewbie »

howardpc

  • Hero Member
  • *****
  • Posts: 4144
Re: Reverse order of an array
« Reply #1 on: March 25, 2018, 02:11:24 pm »
Did you actually try your "solution"?

I do not know of a built-in FPC routine to do what you ask.

The following should do, but there are doubtless faster implementations:
Code: Pascal  [Select][+][-]
  1. type
  2.  
  3. TDoubleDynArray = array of Double;
  4.  
  5. procedure ReverseOrder(var origArray: TDoubleDynArray);
  6. var
  7.   tempArr: TDoubleDynArray;
  8.   i, h: integer;
  9. begin
  10.   h := High(origArray);
  11.   SetLength(tempArr, Length(origArray));
  12.   for i := 0 to h do
  13.     tempArr[i] := origArray[h - i];
  14.   origArray := tempArr;
  15. end;
   

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: Reverse order of an array
« Reply #2 on: March 25, 2018, 02:12:38 pm »
This is my solution, but I'm sure there is something better:
Your decision is wrong. It is necessary to allocate storage under tempArr: SetLength(tempArr, Length(origArray)).
If you do not want to allocate memory for an array, you can do it with one temporary variable:
Code: Pascal  [Select][+][-]
  1. procedure ReverseInPlace(var A: array of Double);
  2. var
  3.   i: Integer;
  4.   Tmp: Double;
  5.   iMax: Integer;
  6. begin
  7.   iMax := High(A);
  8.   for i := 0 to iMax div 2 do
  9.   begin
  10.     Tmp := A[i];
  11.     A[i] := A[iMax - i];
  12.     A[iMax - i] := Tmp;
  13.   end;
  14. end;

justnewbie

  • Sr. Member
  • ****
  • Posts: 292
Re: Reverse order of an array
« Reply #3 on: March 25, 2018, 02:37:27 pm »
Yes, I guessed that array resizing is a must.
Thank you guys for the great examples!

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: Reverse order of an array
« Reply #4 on: March 25, 2018, 04:45:46 pm »
Also note that theoretically and technically you should not physically "reverse" an array: it makes no sense and is a waste of time. The language supports both top to bottom and bottom to top traversals.
(If you worked for me.. reason to get fired). But you ask good questions. Keep up the efforts.
Specialize a type, not a var.

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: Reverse order of an array
« Reply #5 on: March 25, 2018, 05:03:07 pm »
Serge does not address the case in which the range is not an event number..

I am not sure what is going to happen if the High(Array) is not an even number?
The only true wisdom is knowing you know nothing

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Reverse order of an array
« Reply #6 on: March 25, 2018, 05:05:02 pm »
I am not sure what is going to happen if the High(Array) is not an even number?

The middle number stays in its place.

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: Reverse order of an array
« Reply #7 on: March 25, 2018, 05:17:31 pm »
And it is a silly exercise..... Shame on you both: jamie and engkin. O:-) O:-) It is nonsense....

Forward or backward is a matter of definition - to a programmer - it does not matter in code efficiency. Memory layout can stay as is....
More "bright" idea's you two?.... :P
« Last Edit: March 25, 2018, 05:22:21 pm by Thaddy »
Specialize a type, not a var.

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Reverse order of an array
« Reply #8 on: March 25, 2018, 05:34:24 pm »
And it is a silly exercise..... Shame on you both: jamie and engkin. O:-) O:-) It is nonsense....

Forward or backward is a matter of definition - to a programmer - it does not matter in code efficiency. Memory layout can stay as is....
More "bright" idea's you two?.... :P

Your post motivated me to say that Serge's code does not check the length of the array. And using the word "efficiency" makes me suggest:
Code: Pascal  [Select][+][-]
  1. procedure ReverseInPlace(var A: array of Double);
  2. var
  3.   i: Integer;
  4.   Tmp: Double;
  5.   p1: pdouble;
  6.   p2: pdouble;
  7. begin
  8.   if Length(A)=0 then exit;
  9.   p1 := @A[0];
  10.   p2 := p1+High(A);
  11.   for i := High(A) div 2 downto 0 do
  12.   begin
  13.     Tmp := p1^;
  14.     p1^ := p2^;
  15.     p2^ := Tmp;
  16.     inc(p1);
  17.     dec(p2);
  18.   end;
  19. end;

Nitorami

  • Sr. Member
  • ****
  • Posts: 481
Re: Reverse order of an array
« Reply #9 on: March 25, 2018, 06:55:12 pm »
The myth that pointer arithmetics must be faster just doesn't die out.

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Reverse order of an array
« Reply #10 on: March 25, 2018, 07:08:37 pm »
The myth that pointer arithmetics must be faster just doesn't die out.

Like the myth that using assembly code is faster than pure pascal.

Nitorami

  • Sr. Member
  • ****
  • Posts: 481
Re: Reverse order of an array
« Reply #11 on: March 25, 2018, 07:12:08 pm »
Exactly. In most cases it isn't.
And to my experience, pointer arithmetics is really only a benefit with multi-dimensional arrays, where the compiler is not yet smart enough to optimise unnecessary address calculations. In the matter at hand, my machine is 5% faster with normal array access than when using pointers.
 

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Reverse order of an array
« Reply #12 on: March 25, 2018, 07:46:25 pm »
Exactly. In most cases it isn't.
And to my experience, pointer arithmetics is really only a benefit with multi-dimensional arrays, where the compiler is not yet smart enough to optimise unnecessary address calculations.
As you said, in most cases the compiler gives good enough code. That does not mean there is no space for improvement. A different method, SIMD, or code for a specific CPU.

In the matter at hand, my machine is 5% faster with normal array access than when using pointers.
Did you know before hand? I did not test before posting the code. Can you be sure it would be the same on my machine?

But just assume that the pointer arithmetic code were faster by some significant amount, then we know there is a possibility the compiler needs some adjustment. I would not discourage these tests.

rvk

  • Hero Member
  • *****
  • Posts: 6110
Re: Reverse order of an array
« Reply #13 on: March 25, 2018, 07:47:23 pm »
Your post motivated me to say that Serge's code does not check the length of the array. And using the word "efficiency" makes me suggest:
Code: Pascal  [Select][+][-]
  1. ...
  2.   if Length(A)=0 then exit;
  3.  
Well, if efficiency is the word  :D

Code: Pascal  [Select][+][-]
  1. //...
  2.   if Length(A)<2 then exit;
  3.  

engkin

  • Hero Member
  • *****
  • Posts: 3112
Re: Reverse order of an array
« Reply #14 on: March 25, 2018, 07:51:18 pm »
 @rvk,   :D  ;D

 

TinyPortal © 2005-2018