Recent

Author Topic: Dynamic arrays concatenation, insertion and deletion of elements  (Read 1037 times)

Kwadrum

  • New Member
  • *
  • Posts: 13
Dynamic arrays concatenation, insertion and deletion of elements
« on: September 28, 2020, 03:23:26 am »
Hi,
Reading Marco Cantu’s book on Object Pascal, I got to the description of dynamic arrays concatenation and adding unitary elements into them. It is probably nothing new for the most of people here, but I realized this also works in FPC 3.2:
Code: Pascal  [Select][+][-]
  1. program dyn_array_tricks;
  2.  
  3. {$mode objfpc} {$H+} {$modeSwitch arrayOperators+}
  4.  
  5. uses
  6. SysUtils;
  7.  
  8. var
  9. da: array of byte;
  10. i, k: byte;
  11.  
  12. BEGIN
  13.     da := [1, 2, 3];
  14.     da := da + da;             
  15.     //da := Concat(da,da); does the same as above
  16.     da := da + [4, 5]; 
  17.     k := 99;
  18.     da := da + [k];
  19.       for i in da do
  20.             Writeln(i.ToString);
  21.            //Writeln(IntToStr(i)); does the same as above
  22. END.

On the very first look it seems like a very cool feature, but then I tried to think of a possible application of it. This approach is probably not very fast as (I guess) it uses array resizing (like SetLength) at before addition of new elements and therefore there is not much sense in putting it into a loop. So far I have come up with only one example, when one needs to iteratively compute some value (an integral, etc) with a pre-set accuracy and would like to keep track of the whole trajectory. So at each iteration (of unknown number of course) it is possible to add the values of some parameters into an array to see later how the changed.

So I have two questions on this set of features:
1) What would be an “ideal”, but real life example of using these dynamic arrays features?
2) Isn’t this anything similar (or even based on) to the TVector type from RTL? As far as I can see it is capable of doing (almost?) exactly the same things.

Thank you.

Handoko

  • Hero Member
  • *****
  • Posts: 3902
  • My goal: build my own game engine using Lazarus
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #1 on: September 28, 2020, 04:21:52 am »
1) What would be an %u201Cideal%u201D, but real life example of using these dynamic arrays features?

For example, when writing a game you use TInventory to store player's items.

Code: Pascal  [Select][+][-]
  1. const
  2.   MaxItemID = 7;
  3.   HPBig     = 1; // big healing potion
  4.   HPSmall   = 2; // small healing potion
  5.   MPBig     = 3; // big mana potion
  6.   MPSmall   = 4; // small mana potion
  7.   Sw        = 5; // common sword
  8.   SwSmall   = 6; // small sword
  9.   SwLong    = 7; // long sword
  10.  
  11. type
  12.   TInventory = array of Byte;
  13.  
  14. var
  15.   Inventory = TInventory;
  16.    
  17. // Give some bonus items if player finish a quest
  18. procedure BonusItems;
  19. begin
  20.   Inventory := Inventory + [HPSmall, MPSmall] + [Random(MaxItemID)+1];
  21. end;

It just quickly written example. For better coding I probably will use enum type for the items' IDs.

Thaddy

  • Hero Member
  • *****
  • Posts: 10572
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #2 on: September 28, 2020, 08:15:35 am »
The feature is new in 3.2.0. See the release notes:
https://wiki.freepascal.org/FPC_New_Features_3.2.0#Dynamic_Arrays_have_built_in_.2B_operator_support


A side note regarding your code: write/writeln/writestr already supports integer - and many more -  formatting capabilities by default so:
Code: Pascal  [Select][+][-]
  1.       for i in da do
  2.             Writeln(i);// no string conversion necessary
This is Delphi compatible(apart from writestr).   
see the manual for the supported types and formatting options: https://www.freepascal.org/docs-html/rtl/system/write.html
« Last Edit: September 28, 2020, 08:31:02 am by Thaddy »

PascalDragon

  • Hero Member
  • *****
  • Posts: 2405
  • Compiler Developer
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #3 on: September 28, 2020, 09:22:34 am »
On the very first look it seems like a very cool feature, but then I tried to think of a possible application of it. This approach is probably not very fast as (I guess) it uses array resizing (like SetLength) at before addition of new elements and therefore there is not much sense in putting it into a loop. So far I have come up with only one example, when one needs to iteratively compute some value (an integral, etc) with a pre-set accuracy and would like to keep track of the whole trajectory. So at each iteration (of unknown number of course) it is possible to add the values of some parameters into an array to see later how the changed.

Using it in a loop to add single elements is indeed not a good idea, but that is also true for manually doing this. If you however concatenate larger arrays then it will pay off, because the RTL uses Move to copy the elements (of course it also adjusts reference counts of managed types).

2) Isn’t this anything similar (or even based on) to the TVector type from RTL? As far as I can see it is capable of doing (almost?) exactly the same things.

Dynamic arrays are more low level than any class type and in addition to that they are managed automatically. More often than not using an array is simpler than using a class based container.

Kwadrum

  • New Member
  • *
  • Posts: 13
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #4 on: October 01, 2020, 03:38:14 am »
Using it in a loop to add single elements is indeed not a good idea, but that is also true for manually doing this. If you however concatenate larger arrays then it will pay off, because the RTL uses Move to copy the elements (of course it also adjusts reference counts of managed types).

Thanks a lot for explanations!

Do I understand it correctly, that at each addition of a new element (to the end or insertion in the middle) the array is resized by making a new N+1 array and copying all the N elements of the original array + one new into it? If so, I guess, the same applies to deletions within arrays and concatenations.
Therefore, the bigger the array the longer it takes to add/remove a new element?
Isn't that what is estimated as O(N)?

Thaddy

  • Hero Member
  • *****
  • Posts: 10572
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #5 on: October 01, 2020, 06:47:34 am »
Deletion is on average O(N/2) because the same space is used. I.e. on average there is less to copy.

PascalDragon

  • Hero Member
  • *****
  • Posts: 2405
  • Compiler Developer
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #6 on: October 01, 2020, 09:19:33 am »
Using it in a loop to add single elements is indeed not a good idea, but that is also true for manually doing this. If you however concatenate larger arrays then it will pay off, because the RTL uses Move to copy the elements (of course it also adjusts reference counts of managed types).

Thanks a lot for explanations!

Do I understand it correctly, that at each addition of a new element (to the end or insertion in the middle) the array is resized by making a new N+1 array and copying all the N elements of the original array + one new into it? If so, I guess, the same applies to deletions within arrays and concatenations.
Therefore, the bigger the array the longer it takes to add/remove a new element?
Isn't that what is estimated as O(N)?

In principle it is O(N), but there is an optimization the RTL does: it uses ReallocMem to allocate the new memory, so if the memory manager determines that it can reuse the space directly behind the array there won't be a completely new allocation, thus no need to move the whole array over. If you added an element at the end that that will be it. If you added an element in the middle you'll of course have another Move. Concat also does a ReallocMem and if everything fits there will only be the Move of the second (third, fourth, ...) array.

Also when shrinking the array this works out as well, especially if non-managed types are used. Of course deleting an element inside the array is more involved again.

Thaddy

  • Hero Member
  • *****
  • Posts: 10572
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #7 on: October 01, 2020, 09:23:28 am »
Of course deleting an element inside the array is more involved again.
Yes, but it should be O(N/2)?

PascalDragon

  • Hero Member
  • *****
  • Posts: 2405
  • Compiler Developer
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #8 on: October 01, 2020, 09:28:20 am »
O(N/2) is still linear, thus the same as O(N). It would be more interesting if it would be O(N log N) or something like that. A simple factor is irrelevant.

Thaddy

  • Hero Member
  • *****
  • Posts: 10572
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #9 on: October 01, 2020, 09:35:56 am »
I stand corrected. I forgot about some of the theory.

egsuh

  • Hero Member
  • *****
  • Posts: 503
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #10 on: October 01, 2020, 12:06:15 pm »
I did not know this feature, but this is really useful. I can treat it as if set (still they are not exactly the same, but I can manage it).  I use dynamic arrays very frequently. I don't think the performance is important as I'm not dealing with hundreds of thousand items. Thank you for the information. I'll try myself.


egsuh

  • Hero Member
  • *****
  • Posts: 503
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #11 on: October 01, 2020, 12:12:32 pm »
I tried this, but this is applicable only to array of byte. Is there any way that I can do the similar thing with array of integer?

PascalDragon

  • Hero Member
  • *****
  • Posts: 2405
  • Compiler Developer
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #12 on: October 01, 2020, 01:16:15 pm »
I tried this, but this is applicable only to array of byte. Is there any way that I can do the similar thing with array of integer?

What do you mean? It should work with any array. Or are you using FPC 3.0.4? The array features are new in 3.2.0.

egsuh

  • Hero Member
  • *****
  • Posts: 503
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #13 on: October 02, 2020, 10:40:01 am »
Quote
What do you mean? It should work with any array. Or are you using FPC 3.0.4? The array features are new in 3.2.0.

You are right... I tested it on PC with 3.0.4.  This works fine on 3.2.0 (Lazarus 2.0.10).

Kwadrum

  • New Member
  • *
  • Posts: 13
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #14 on: October 03, 2020, 02:10:51 am »
In principle it is O(N), but there is an optimization the RTL does: it uses ReallocMem to allocate the new memory, so if the memory manager determines that it can reuse the space directly behind the array there won't be a completely new allocation, thus no need to move the whole array over. If you added an element at the end that that will be it. If you added an element in the middle you'll of course have another Move. Concat also does a ReallocMem and if everything fits there will only be the Move of the second (third, fourth, ...) array.
Also when shrinking the array this works out as well, especially if non-managed types are used. Of course deleting an element inside the array is more involved again.
Ah, so it is where that O(N/2) comes from... for an addition of one element to the end of the array I guess.
So as far as I understand it now these features are mostly useful for handling a rather small array which size fluctuates a bit around an average. An Inventory list by Handoko indeed seems to be a perfect example. But I'm still thinking if and how I could use for my own purposes.  :)

 

TinyPortal © 2005-2018