* * *

Author Topic: Dynamic arrays ...  (Read 3306 times)

graemejc

  • New member
  • *
  • Posts: 17
Dynamic arrays ...
« on: June 10, 2018, 02:17:07 am »
(* The following code to read, save and print filenames works perfectly well. *) 
(* However if I use dynamic arrays by changing the definition of FN_Storage by
commenting out the current definition and de-commenting out the 2nd definition,
it doesn't work. The only filename that is stored is the last one because it
seems that everytime there is a call to

        setlength(filenames,no_of_filenames);

that complete new memory is allocated to the dynamic array, filenames, losing
the previous file names stored. In retrospect, that is perfectly understandable
behaviour. However, I am wondering how to use dynamic arrays to do this.

The only way that I can think to do this is to read the file names, count them,
create the dynamic array to the required size, then reread and store them. Seems
wasteful doing the 2 sets of reads. Is there a better way of doing this using
dynamic arrays? It seems to me at this stage that it would be easier to simply
not use arrays, rather create a linked list.

When I was regular computer programmer (1980s), neither VAX-VMS
Pascal or Turbo Pascal 4.0 used dynamic arrays, so I'm just learning these. *)

program Project1;
Uses
        Crt,
        Dos;  {FindFirst, FindNext}
type
        string255=string[255]; (* shortstring *)
        FN_Storage=array [1..10] of string255;   { Comment out to change
                                                   definition to dynamic
                                                   arrays.}
        (*FN_Storage=array of string255;*)       { De-comment out to change
                                                   definition to dynamic array}
var
        Dir            :SearchRec ;
        no_of_filenames:Integer   ;
        filenames      :FN_Storage;
        fnum           :integer   ;
        c              :char      ;
begin
        (* Read, store and write the files. *)
        WriteLn('FileName');
        FindFirst('*.GJC',archive,Dir);
        no_of_filenames:=0;
        while DosError=0 do begin
                no_of_filenames:=no_of_filenames+1;
                Writeln(Dir.Name);
                (*setlength(filenames,no_of_filenames);*) { Necessary if
                                                filenames was a dynamic array. }
                filenames[no_of_filenames]:=Dir.Name;
                dos.FindNext(Dir);
        end;
        dos.FindClose(Dir);

        (* Write the stored files, *)
        for fnum:=1 to no_of_filenames do begin
                writeln(filenames[fnum]);
        end;

        (* Keep screen till press a key. *)
        while keypressed do c:=readkey;
        c:=readkey;
end. 

josh

  • Hero Member
  • *****
  • Posts: 631
Re: Dynamic arrays ...
« Reply #1 on: June 10, 2018, 02:39:30 am »
Hi

Remember that the Array is zero element based.

ie SetLength(MyArrray,1) creates an array which has just the 0 element available

Code: [Select]
no_of_filenames:=no_of_filenames+1;
setlength(filenames,no_of_filenames);
filenames[no_of_filenames]:=Dir.Name;

In you code on initial loop, no_of_filenames=1, you then set then length of array to 1, but remember elelment 1 is not available; only element 0, however you set filenames[1]:= the name, this element is not available; I would have thought that a runtime error would occur if you have set it in debig options.

I have not tested but a small change might correct it, using as much of your code as is.

Code: Pascal  [Select]
  1.  WriteLn('FileName');
  2.  FindFirst('*.GJC',archive,Dir);
  3.  no_of_filenames:=0;
  4.  while DosError=0 do begin
  5.     no_of_filenames:=no_of_filenames+1;
  6.     Writeln(Dir.Name);
  7.     setlength(filenames,no_of_filenames);
  8.     filenames[no_of_filenames-1]:=Dir.Name; // array is zero based
  9.     dos.FindNext(Dir);
  10.  end;
  11.  dos.FindClose(Dir);
  12.  
  13.  (* Write the stored files, *)
  14.   for fnum:=0 to no_of_filenames-1 do begin  // array is zero based
  15.      writeln(filenames[fnum]);
  16.   end;
  17.  
« Last Edit: June 10, 2018, 02:41:01 am by josh »
Development Installation Lazarus 1.3, FPC 2.7.1,Windows 7/8 32/64, OSX, *nix

Test Environment Lazarus & FPC Trunk on Windows and OSX (Cocoa Mainly on OSX). Testing also Crosscompile windows to OSX.. 
Any posts made from 2015 will be based on Lazarus Trunk.

Nitorami

  • Sr. Member
  • ****
  • Posts: 344
Re: Dynamic arrays ...
« Reply #2 on: June 10, 2018, 11:06:25 am »
Dynamic arrays are incredibly convenient once you learned how to handle them  ;D

As Josh says, they always start at index zero, and you cannot change that. That is probably your mistake. Something like this
Code: Pascal  [Select]
  1. SetLength (FileNames,1);
  2. FileNames[1] := Something;
  3.  
should throw an access violation because only element zero is available in an array of length 1. With range checks on, this should throw a range check error.

Quote
that complete new memory is allocated to the dynamic array, filenames, losing
the previous file names stored.
No: Setting the length of a dynamic array only deletes the newly allocated memory ! If your array contains 5 elements, and you extend it to length 6, the first 5 elements will be remembered !


Zoran

  • Hero Member
  • *****
  • Posts: 1253
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: Dynamic arrays ...
« Reply #3 on: June 10, 2018, 11:59:16 am »

Quote
that complete new memory is allocated to the dynamic array, filenames, losing
the previous file names stored.
No: Setting the length of a dynamic array only deletes the newly allocated memory ! If your array contains 5 elements, and you extend it to length 6, the first 5 elements will be remembered !

Of course they will be remembered. However, the memory for whole array will be reallocated (for six elements), the first five elements will then be copied to the start of new memory, and you will be able to set the sixth element to something. This reallocating can be a costly operation, therefore, the better way is not to allocate one by one in each iteration, but do something like this:

Code: Pascal  [Select]
  1. no_of_filenames:=0;
  2. SetLength(filenames, 0);
  3. while DosError=0 do begin
  4.   Writeln(Dir.Name);
  5.  
  6.   no_of_filenames := no_of_filenames + 1;
  7.   // Now ask and allocate if necessary:
  8.   if no_of_filenames > Length(filenames) then
  9.     // Do not allocate one by one, but more, for example by half of what you already have:
  10.     SetLength(filenames, no_of_filenames * 3 div 2 + 2); // adding two is meaningful while numbers are small (initially it will grow to 2, whereas 0 * 3 div 2 will remain zero, leading to memory corruption!).
  11.  
  12.   filenames[no_of_filenames - 1] := Dir.Name; // NOTE -1 here, dinamyc array alway zero-based!
  13.                 dos.FindNext(Dir);
  14. end;
  15. SetLength(filenames, no_of_filenames); // finally cut it to what it actually should be.
  16.  
  17. dos.FindClose(Dir);
  18.  
« Last Edit: June 10, 2018, 12:01:53 pm by Zoran »

graemejc

  • New member
  • *
  • Posts: 17
Re: Dynamic arrays ...
« Reply #4 on: June 10, 2018, 03:40:41 pm »
Hi

Remember that the Array is zero element based.

Yep, that worked well. Thank you. :-[

graemejc

  • New member
  • *
  • Posts: 17
Re: Dynamic arrays ...
« Reply #5 on: June 10, 2018, 03:47:04 pm »

should throw an access violation because only element zero is available in an array of length 1. With range checks on, this should throw a range check error.

Quote

Thank you. Now I'll have to learn how to turn range checks on.  :-[  I think it's ...

{$R}

graemejc

  • New member
  • *
  • Posts: 17
Re: Dynamic arrays ...
« Reply #6 on: June 10, 2018, 03:48:49 pm »
Code: [Select]
[quote author=Zoran link=topic=41535.msg288342#msg288342 date=1528624756]
[quote author=Nitorami link=topic=41535.msg288338#msg288338 date=1528621585]

  filenames[no_of_filenames - 1] := Dir.Name; // NOTE -1 here, dinamyc array alway zero-based!
                dos.FindNext(Dir);
end;
SetLength(filenames, no_of_filenames); // finally cut it to what it actually should be.

dos.FindClose(Dir);
[/quote]

Fantastic. Thank you.

Nitorami

  • Sr. Member
  • ****
  • Posts: 344
Re: Dynamic arrays ...
« Reply #7 on: June 10, 2018, 08:43:54 pm »
Mind, if you want to add a few hundres filenames to a dynamic array, extending it one by one, performance is hardly an issue.
However if you read 10 million values from a file, it is, because the operating system will have to search for a larger memory space very often.
It depends on your application whether you extend the array one by one of rather in chunks.

Range check on is {$R+} when defined in the code
« Last Edit: June 10, 2018, 08:58:47 pm by Nitorami »

bytebites

  • Full Member
  • ***
  • Posts: 160
Re: Dynamic arrays ...
« Reply #8 on: June 10, 2018, 09:06:31 pm »
Instead of
Code: Pascal  [Select]
  1. FN_Storage=array [1..10] of string255;

use

Code: Pascal  [Select]
  1. FN_Storage=array [1..10] of ShortString;

User137

  • Hero Member
  • *****
  • Posts: 1748
    • Nxpascal home
Re: Dynamic arrays ...
« Reply #9 on: June 11, 2018, 01:21:22 am »
For peace of mind i just had to test what now happens with memory locations when resizing array. Code:
Code: Pascal  [Select]
  1. procedure TForm1.FormCreate(Sender: TObject);
  2. var a: array of integer;
  3.     p1, p2: PInteger;
  4. begin
  5.   setlength(a, 10);
  6.   a[4]:=99;
  7.   p1:=@a[4];
  8.   setlength(a, 20); // Resize existing dynamic array
  9.   p2:=@a[4];
  10.   edit1.Text:=format('%d : %d -> %d',[a[4], integer(p1), integer(p2)]);
  11. end;
Prints out: 99 : 22786224 -> 23170624
So the pointer is different, meaning entire array was copied. But if i swap 10 and 20 around, shrinking the array instead of making it larger:
Result: 99 : 21897504 -> 21897504
That's clearly cheaper operation.

Use TList, TObjectList or similar if you want to add elements 1 by 1. They're internally optimized better than you possibly could figure.

graemejc

  • New member
  • *
  • Posts: 17
Re: Dynamic arrays ...
« Reply #10 on: June 11, 2018, 03:08:34 am »
Instead of
Code: Pascal  [Select]
  1. FN_Storage=array [1..10] of string255;

use

Code: Pascal  [Select]
  1. FN_Storage=array [1..10] of ShortString;

Is there any advantage to that? I used string255 years ago when there was no such thing as shortstring (been out of programming for 30 years) and so just continued using it. When I started to read up to restart programming, I didn't know what a shortstring was. I discovered it was the same as string255 so kept the latter as it makes it clear what it is. If there is some sort of advantage to shortstring, I'll use it. Thanks for your advice.

Zoran

  • Hero Member
  • *****
  • Posts: 1253
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: Dynamic arrays ...
« Reply #11 on: June 11, 2018, 10:51:37 am »
Instead of
Code: Pascal  [Select]
  1. FN_Storage=array [1..10] of string255;

use

Code: Pascal  [Select]
  1. FN_Storage=array [1..10] of ShortString;

Is there any advantage to that? I used string255 years ago when there was no such thing as shortstring (been out of programming for 30 years) and so just continued using it. When I started to read up to restart programming, I didn't know what a shortstring was. I discovered it was the same as string255 so kept the latter as it makes it clear what it is. If there is some sort of advantage to shortstring, I'll use it. Thanks for your advice.

I don't think so. Even if there were some rational reason, saying just "use this instead of that" without a word of explanation can lead nowhere, but only makes confusion. >:(

I'd say this is just a misleading advice. Use what you prefer.

Maybe bytebits will explain what he meant after all.
« Last Edit: June 11, 2018, 10:53:43 am by Zoran »

ASBzone

  • Jr. Member
  • **
  • Posts: 78
  • Automation leads to relaxation...
    • BrainWaveCC Utilities
Re: Dynamic arrays ...
« Reply #12 on: June 12, 2018, 03:43:21 pm »
Mind, if you want to add a few hundres filenames to a dynamic array, extending it one by one, performance is hardly an issue.
However if you read 10 million values from a file, it is, because the operating system will have to search for a larger memory space very often.

I have a Prime Number List Generator that uses a dynamic array to store the list of prime numbers, and I start it with a size of 25 and then grow as needed.

I recompiled it to simply calculate the max number of prime numbers possible for a range of 1 to x [which, interestingly enough, is a little less than "x div (log10(x) * 2)"] and to set the size of the array to that size from the beginning.

I then compared the timing of both executables when checking for prime numbers in the range of 1-1000, 1-10000, 1-100000, 1-1000000 and 1-10000000 and I saw only milliseconds of difference in performance between the two executables.  I honestly expected more than that.

This on the following hardware:

Kernel version:            Windows 10 Enterprise, Multiprocessor Free
Kernel build number:   16299
Processors:                 4
Processor speed:         2.2 GHz
Processor type:           Intel(R) Core(TM) i5-5300U CPU @
Physical memory:        8 GB


Lazarus 1.8.4 w/FPC 3.0.4, Win32
-ASB: https://www.BrainWaveCC.com

Lazarus 1.8.4 + FPC 3.0.4 (32-bit w/64-bit cross-compile)
Occasional testing of NewPascal
Windows 10 Pro x64, Version 1803 (Build 17134.228)

(Technically, I logon to these forums from multiple versions of Windows Pro/Enterprise...)

Nitorami

  • Sr. Member
  • ****
  • Posts: 344
Re: Dynamic arrays ...
« Reply #13 on: June 12, 2018, 06:30:34 pm »
I guess that determining prime numbers itself is a costly operation, so memory reallocation may not have such a big impact. And the impact usually grows with array size.
In my application I am copying large amounts of floats, some 50 million values or  more, from one array to another, performing a simple filter operation; for instance, values outside a certain range are discarded. The target array will therefore be smaller than the original. I started with incrementing the size with each new element copied across, but that became very noticeably slower as the target array grew in size. Blockwise allocation speeded it up quite significantly.

ASBzone

  • Jr. Member
  • **
  • Posts: 78
  • Automation leads to relaxation...
    • BrainWaveCC Utilities
Re: Dynamic arrays ...
« Reply #14 on: June 13, 2018, 03:21:35 am »
I guess that determining prime numbers itself is a costly operation, so memory reallocation may not have such a big impact. And the impact usually grows with array size.

Good point...

In my application I am copying large amounts of floats, some 50 million values or  more, from one array to another, performing a simple filter operation; for instance, values outside a certain range are discarded. The target array will therefore be smaller than the original.

Hmmm...  Let me test with larger ranges for prime and see if that changes anything.  (I like code optimization)
-ASB: https://www.BrainWaveCC.com

Lazarus 1.8.4 + FPC 3.0.4 (32-bit w/64-bit cross-compile)
Occasional testing of NewPascal
Windows 10 Pro x64, Version 1803 (Build 17134.228)

(Technically, I logon to these forums from multiple versions of Windows Pro/Enterprise...)

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus