I encountered the following bug:
D:\gfortran\james\cheby2>type bug1.f90
function insert(lower,mi)
implicit none
integer, intent(in) :: lower(:)
integer, intent(in) :: mi
integer(size(lower)+1) insert
integer loc
loc = maxloc(lower,mask = mi > lower,dim = 1)
insert = [lower(1:loc),mi,lower(loc+1:)]
end function insert
D:\gfortran\james\cheby2>gfortran -c bug1.f90
bug1.f90:5:22:
integer(size(lower)+1) insert
1
Error: Deferred array 'lower' at (1) is not permitted in an initialization expre
ssion
integer :: insert(size(lower)+1)
"Thomas Koenig" wrote in message news:tjp54r$2il75$1...@newsreader4.netcologne.de...
integer :: insert(size(lower)+1)
Thanks. I was translating code from Matlab to Fortran and sort
of forgot the syntax rules. This was indeed my mistake.
I do hope you don't use this too much. If I understand it, it
allocates a whole new array each time. I am not sure what
happens to the old one.
When it goes out of scope, it no longer uses memory. (I was
going to say it is deallocated, but that has a precise meaning
in Fortran, so I didn't).
There are ways to create memory leaks in Fortran, but they
all involve pointers.
On Monday, October 31, 2022 at 12:40:13 PM UTC-7, James Van Buskirk wrote:
"Thomas Koenig" wrote in message
news:tjp54r$2il75$1...@newsreader4.netcologne.de...
integer :: insert(size(lower)+1)
Thanks. I was translating code from Matlab to Fortran
and sort
of forgot the syntax rules. This was indeed my mistake.
And, reading along, I knew what it was supposed to do, and didn't notice.
Or, maybe, it is time for lunch.
I do hope you don't use this too much. If I understand it, it
allocates a whole new array each time. I am not sure what
happens to the old one.
y = insert(x,3)
"gah4" wrote in message
news:d604914b-d8a2-4857...@googlegroups.com...
y = insert(x,3)
This was close to my usage, which actually was:
lower_new = insert(lower,mi)
It replaced the Matlab code:
lower_new = sort([mi lower])
Both methods are highly efficient in that they reliably insert
the new element mi into the sorted array lower, while still
occupying perhaps a couple of ppm of overall CPU time.
Of course, I admit to having gotten a little cross-eyed in
composing the Fortran replacement :)
Replacing code like
And this was done for maybe 1,000,000 elements. (From 60 character lines.)
That is O(n**2), as is I believe yours.
(snip)
do i=1000000,1,-1
x=insert(x,i)
enddo
Any suggestions on how long it should take?
I will post when it is done.
On Tuesday, November 1, 2022 at 11:10:12 PM UTC-7, gah4 wrote:
(snip)
do i=1000000,1,-1
x=insert(x,i)
enddo
(snip)
Any suggestions on how long it should take?
I will post when it is done.
And the answer is 82 minutes.
And the answer is 82 minutes.
You should consider a different underlying data structure than a linear array. I suggest looking at a binary search tree (BST). You can code a
simple one in fortran in about the same number of lines as your posted example.
Your insertion step requires O(n) effort for each insertion where n is
the current number of data points. A BST insertion requires O(log(n))
effort for each insertion. There are some other data structures that
might be useful too, but this is simple and should get you started in
the right direction.
On Wednesday, November 2, 2022 at 7:44:12 AM UTC-7, Ron Shepard wrote:
(snip, I wrote)
And the answer is 82 minutes.
You should consider a different underlying data structure than a linear array. I suggest looking at a binary search tree (BST). You can code a simple one in fortran in about the same number of lines as your posted example.
Your insertion step requires O(n) effort for each insertion where n is
the current number of data points. A BST insertion requires O(log(n)) effort for each insertion. There are some other data structures that
might be useful too, but this is simple and should get you started in
the right direction.
Just to be sure, it is James data structure and not mine.
I was trying to see how to call insert, and this was my first time
with an INTERFACE for a function returning a variable number of
array elements.
There is a popular binary search tree using pointers, but there is
also the heap, and especially binary heap:
There is a popular binary search tree using pointers, but there is
also the heap, and especially binary heap:
For this particular data structure there was no impact on performance,
but there was another one where the results were accumulated in
arrays. That really did slow things down tremendously but I hadn't
noticed before because the rest of my program was too slow for
the arrays to get that large. Since the results were to be plotted,
their order of generation was what mattered so I dropped them into
a linked list and the longest-running cases sped up by an order of
magnitude.
In the original example the sorted arrays had to be swept through
in order several times after each update so only arrays made
sense.
The binary heap is an interesting data structure, and one well
designed for languages were arrays start at 1. (It is usual to
ignore the 0th element in C.)
If you consider a balanced binary tree, and read off the elements
row by row, and then store them in an array:
the root goes in element 1.
The next two in elements 10 and 11. (Binary addressing.)
The next four in elements 100, 101, 110, 111.
Because of the way the addressing works, you can go up the
tree, just shifting the address right one bit at a time.
There is a convenient algorithm to go through the elements
in sorted order, based on binary arithmetic. Maybe not quite
as fast as a sorted array, but pretty fast.
And it is O(log N) to add elements to the heap.
I think that I have previously post AVL tree code to this forum.
It is unfortunate that you have not fleshed your ideas out by
posting code like:
integer n
real(REAL64) harvest
call RANDOM_NUMBER(harvest)
n = HUGE(n)*harvest
! Now insert n into your data structure...
So as to compare performance between the example you posted
and your proposed data structure solution...
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 159 |
Nodes: | 16 (0 / 16) |
Uptime: | 100:05:27 |
Calls: | 3,209 |
Files: | 10,563 |
Messages: | 3,009,979 |