experchange > fortran

Paul Wenk (02-26-19, 11:20 PM)
Am Dienstag, 26. Februar 2019 07:54:05 UTC+1 schrieb Arjen Markus:
> On Monday, February 25, 2019 at 11:09:08 PM UTC+1, Paul Wenk wrote:
> You might also have a look at ORDERPACK -
> Regards,
> Arjen


Very useful indeed, thanks!
Wolfgang Kilian (02-27-19, 09:33 AM)
On 26.02.2019 22:15, Paul Wenk wrote:
> Am Dienstag, 26. Februar 2019 18:16:15 UTC+1 schrieb FortranFan:
> Thanks a lot for this solution!
> But shouldn't this be part of a lib where the different types are covered using an interface? One could always say: Well, you can write it yourself. But sometimes there are this little tweaks and tricks which were found over the years of language use which you are not aware of.
> Cheers,
> Paul


You are asking for a library analogous to the STL in C++. Such a
facility has been on the wishlist of many Modern-Fortran users for a
long time, and finally it appears as if the next revision of the
standard (Fortran 202X) may enable the creation of such libraries.

At present, this is not possible. The difficult part is the 'different
types are covered' bit. It is straightforward to implement algorithms
for the finite set of intrinsic types (others have pointed to examples).
A satisfactory solution that supports any (derived) type, without
major inconveniences for the user, is not possible within the scope of
present Fortran.

-- Wolfgang
Ron Shepard (02-27-19, 06:45 PM)
On 2/27/19 1:33 AM, Wolfgang Kilian wrote:
> At present, this is not possible.  The difficult part is the 'different
> types are covered' bit.  It is straightforward to implement algorithms
> for the finite set of intrinsic types (others have pointed to examples).
>  A satisfactory solution that supports any (derived) type, without
> major inconveniences for the user, is not possible within the scope of
> present Fortran.


There is a straightforward way to achieve this goal in current fortran
(or f90, or f77 for that matter) for the requested task and for similar
sorting and ordering tasks.

The general approach is that the sort/ordering program always works with
the integer indexing array. One argument to the sort routine is a dummy
function, written by the programmer, that returns the result of
comparisons between two array elements given their integer indices. The
sort routine never needs to see or declare the user defined type that is
being compared, so there is no problem with allowing it to work on any
intrinsic or user defined type. Also, elements of those derived types
are never copied or swapped, it is only the elements of the integer
index array that are swapped. This is a nice feature of this approach
for complicated derived types that have, for example, big memory
footprints or allocatable members of arbitrary size. This approach also
works well when arbitrary subsets of the underlying data are sorted.

I remember a similar discussion to this a few years ago here in CLF, and
I think I posted an example of a heap sort that worked this way. If what
I'm explaining isn't obvious, I can try to dig out that routine and
repost it. I personally like heap sort over the other alternatives for
these kinds of sorting tasks. It sorts in-place with no extra memory
requirements, it is O(N*log(N)) scaling, and that is also its worst-case
behavior. Also, heap sort is easy to understand and implement in
fortran, it can be done with loops rather than recursion, and so on.

A previous post referred to a library that was mostly based on merge
sorts. Merge sorts are also easy to understand and implement in fortran,
but they are not in-place, they require intermediate work arrays. Qsort
was also mentioned. Its downside is that its worst case behavior is N^2
rather than N*log(N). And someone also posted a brute force N^2
selection sort, which is easy to implement, but has no place in an
efficient library of sort and order routines. There are special
situations in which all of those algorithms are appropriate, of course,
but heap sort is a nice general purpose approach particularly when used
with an index vector to order arbitrary elements of arbitrary types.

$.02 -Ron Shepard
gah4 (02-28-19, 04:36 AM)
On Wednesday, February 27, 2019 at 8:45:24 AM UTC-8, Ron Shepard wrote:

(snip)

> A previous post referred to a library that was mostly based on merge
> sorts. Merge sorts are also easy to understand and implement in fortran,
> but they are not in-place, they require intermediate work arrays. Qsort
> was also mentioned. Its downside is that its worst case behavior is N^2
> rather than N*log(N). And someone also posted a brute force N^2
> selection sort, which is easy to implement, but has no place in an
> efficient library of sort and order routines. There are special
> situations in which all of those algorithms are appropriate, of course,
> but heap sort is a nice general purpose approach particularly when used
> with an index vector to order arbitrary elements of arbitrary types.


Some object-oriented languages have libraries of general routines
that can work with appropriate data structures. Java has an inteface
(Java term) called List, which is implemented (again, Java term) by
list-like classes, such as LinkedList and ArrayList.

This allows one to use the appropriate methods, without needing
to know the underlying class details. List has a sort() method,
which well either sort based on the comparator of the class of
the list elements, or a supplied comparator.

As for specific details, it seems that List.sort() copies the data
to an array, sorts the array, and then copies it back. That is much
more efficient than sorting a list in place.

As noted previously, C has a qsort routine (which may or may not
implement quicksort) to sort an array of arbitrary sized elements,
including structs. C has the ability to copy a struct knowing
only its size, and not its contents.

On the other hand, there is no data structure in Java similar
to an array of struct. Non-primitive data in Java is always
handled indirectly through a reference. Instead of an array of
structures, Java will have an array of references to arbitrary
objects. I don't know that one can find list positions,
after sorting a list, other than putting index numbers in to the
list elements before sorting.

As well as I know it, the OO features of Fortran can implement
something like a Java List. I don't know that there is anything
like the Java interface, to generalize some things, but one should
be able to implement a LinkedList in Fortran, with a sort method.

It is still an inconvenience of Fortran not to have arrays
of pointers.
Ron Shepard (02-28-19, 08:34 AM)
On 2/27/19 8:36 PM, gah4 wrote:
> It is still an inconvenience of Fortran not to have arrays
> of pointers.


One can have an array of a derived type in fortran whose only member is
a pointer. Is there anything that could be done with an array of
pointers that cannot be done with the derived type array? Is there any
loss of efficiency with the fortran approach? Is there any loss of clarity?

Sorting the members of a linked list efficiently requires something like
the indexed sort mentioned by the original poster. Swapping elements of
a linked list is problematic, as is referencing some arbitrary element
somewhere in the middle, so performing the sort through the integer
index array solves both of those problems.

$.02 -Ron Shepard
gah4 (02-28-19, 09:25 AM)
On Wednesday, February 27, 2019 at 10:34:56 PM UTC-8, Ron Shepard wrote:

(I wrote)

> > It is still an inconvenience of Fortran not to have arrays
> > of pointers.


> One can have an array of a derived type in fortran whose only member is
> a pointer. Is there anything that could be done with an array of
> pointers that cannot be done with the derived type array? Is there any
> loss of efficiency with the fortran approach? Is there any loss of clarity?


Slightly less convenient, slightly more ugly, but probably no difference
in efficiency.

PL/I, I believe inherited from COBOL, has partial qualification
where you can reference a structure member leaving out some qualifiers
if the result uniquely identifies one member.

I believe one reason for this in COBOL is that COBOL doesn't
directly allow multidimensional arrays, but instead array of
structure of array of ..., so partial qualification allows for
something that looks like a multidimensional array.

Partial qualification would remove the ugliness and increase
the convenience.

> Sorting the members of a linked list efficiently requires something like
> the indexed sort mentioned by the original poster. Swapping elements of
> a linked list is problematic, as is referencing some arbitrary element
> somewhere in the middle, so performing the sort through the integer
> index array solves both of those problems.


Or an array of pointers (or references).

Java will pass the reference for two elements to the comparator
method (almost wrote function), which then, as with qsort, returns
a negative, zero, or positive value.

I think what Java does is to allocate an array of Object, the
superclass of all classes, copy all the references, sort the array,
then copy them back, or recreate the list. Since all references
to a List should be through the appropriate methods, the actual
internal structure is hidden from the user.

I haven't tried OO Fortran enough to know how easy it is to do.
Alberto Ramos (02-28-19, 12:00 PM)
In the numeric library



you have a qsort routine for the basic data types (int,real,double
precision). This routine sorts in place the array and optionally
returns an index with the positions.

It would be easy for you to copy the array before the call, and just
get the index.

Example code follows:

program foo

use nonnumeric

implicit none

real :: data(10)

call random_number(data)
write(*,*)data

call qsort(data)
write(*,*)data

write(*,*)
call random_number(data)
write(*,*)data

call qsort(data,ipt)
write(*,*)data
write(*,*)ipt

stop
end program foo
spectrum (03-05-19, 06:14 PM)
Although this may be already mentioned in the above replies, *lasrt() routine
may also be a possible candidate, if the list of interest is of primitive type?
(But I've never used these routines so far, so not sure about the performance...)

Lapack


MKL
Dominik Gronkiewicz (03-09-19, 05:55 PM)
W dniu wtorek, 26 lutego 2019 22:15:38 UTC+1 użytkownik Paul Wenk napisał:
> Thanks a lot for this solution!
> But shouldn't this be part of a lib where the different types are coveredusing an interface? One could always say: Well, you can write it yourself.But sometimes there are this little tweaks and tricks which were found over the years of language use which you are not aware of.


This is one of many things that are wrong with Fortran. Almost no libraries(besides outdated 40 years old codes), you have to write everything yourself or use C interfaces. And this is unlikely to change since distribution of Fortran libraries is a nightmare, there are no generics in the language so everyone just moves to C++.
Ron Shepard (03-09-19, 11:10 PM)
On 3/9/19 9:55 AM, Dominik Gronkiewicz wrote:
> This is one of many things that are wrong with Fortran. Almost no libraries (besides outdated 40 years old codes), you have to write everything yourself or use C interfaces.


What kind of libraries? Numerical libraries? Many of those used in other
languages are based on those written in fortran 40 years ago: LAPACK, etc.

> And this is unlikely to change since distribution of Fortran libraries is a nightmare,


How is this different from any other language, C, C++, etc.? You take
the source, compile it, and link it with your application, same as any
other language.

> there are no generics in the language so everyone just moves to C++.


There were generics in fortran before they were in C, C++, etc. It is
true that in the 80s there was a long delay in getting that
functionality from intrinsics up to the user-written code, but it did
make it. However, as I pointed out in this thread a few weeks ago, there
is no need for generics in the language to implement the requested task,
it could be implemented in f77 for any intrinsic type, and it can easily
be implemented in f90 and later for any user defined type.

$.02 -Ron Shepard
Ian Harvey (03-10-19, 05:43 AM)
On 2019-03-10 06:40, Ron Shepard wrote:
[..]
> is no need for generics in the language to implement the requested task,
> it could be implemented in f77 for any intrinsic type, and it can easily
> be implemented in f90 and later for any user defined type.


The intrinsic or user-written generics being discussed in the last
paragraph are different from the meaning of "generics" (generic
programming, really) as discussed in the earlier paragraph.

The integer indexing array approach discussed in the other post places
requirements on the client source code that are above a generic
programming approach.
robin.vowels (03-10-19, 11:52 AM)
On Sunday, March 10, 2019 at 2:55:52 AM UTC+11, Dominik Gronkiewicz wrote:
> W dniu wtorek, 26 lutego 2019 22:15:38 UTC+1 użytkownik Paul Wenk napisał:
> > Thanks a lot for this solution!
> > But shouldn't this be part of a lib where the different types are covered using an interface? One could always say: Well, you can write it yourself. But sometimes there are this little tweaks and tricks which were found over the years of language use which you are not aware of.

> This is one of many things that are wrong with Fortran. Almost no libraries (besides outdated 40 years old codes),


Try Numerical Recipes.

> you have to write everything yourself or use C interfaces.
> And this is unlikely to change since distribution of Fortran
> libraries is a nightmare, there are no generics in the language
> so everyone just moves to C++.


Generic functions were introduced in FORTRAN 77, while generic procedures
were introduced in Fortran 90.
spectrum (03-10-19, 10:50 PM)
On Sunday, March 10, 2019 at 6:52:04 PM UTC+9, robin....@gmail.com wrote:
> Generic functions were introduced in FORTRAN 77, while generic procedures
> were introduced in Fortran 90.


Dear Robin,
As Ian suggested above, I believe the meaning of "generic" is somewhat (or rather
greatly) different here - it is more like this one. The key point is that a library routine
can be used for types that are developed *after* the routine was written.



# I haven't read the above Wiki in detail, but it is interesting to see that
Ada has it even from 1970's (??) and has made generic container libraries in 2005.
spectrum (03-10-19, 11:00 PM)
On Sunday, March 10, 2019 at 12:55:52 AM UTC+9, Dominik Gronkiewicz wrote:

> This is one of many things that are wrong with Fortran. Almost no libraries (besides outdated 40 years old codes), you have to write everything yourself or use C interfaces. And this is unlikely to change since distributionof Fortran libraries is a nightmare, there are no generics in the languageso everyone just moves to C++.


Though the lack of various things (including generics) is certainly a factor, I also think
that another critical factor is the lack of popular "ecosystem(s)" or repositories
for efficient reuse of libraries and communication about the usage etc. So,new users
need to search for available tools by themselves, learn the installation method (sometimes
very time-consuming), validate them (this is crucial!), and finally use them.
(Sometime before, I need to find some special function codes, but it took really a lot of
time to find a good one. Some initial libraries I tried were almost useless....)
Ron Shepard (03-11-19, 08:44 AM)
On 3/10/19 4:00 PM, spectrum wrote:
> On Sunday, March 10, 2019 at 12:55:52 AM UTC+9, Dominik Gronkiewicz wrote:
>> This is one of many things that are wrong with Fortran. Almost no libraries (besides outdated 40 years old codes), you have to write everything yourself or use C interfaces. And this is unlikely to change since distribution of Fortran libraries is a nightmare, there are no generics in the language so everyone just moves to C++.

> Though the lack of various things (including generics) is certainly a factor, I also think
> that another critical factor is the lack of popular "ecosystem(s)" or repositories
> for efficient reuse of libraries and communication about the usage etc.


Yes, such as netlib, which is about 30 years old. Netlib distributes
AMPL, BLAS, EISPACK, LAPACK, LINPACK, MINPACK, QUADPACK, and SLATEC.

In my field of quantum chemistry, we have done this even longer with
such things as QCPE at Indiana University, which dates back to 1963, and
the NRCC which was active in the early 1980s. Other scientific areas
such as astronomy and high energy physics also have had code
repositories. Of course, that all started before the internet, so things
can be done differently now.

I am one of the COLUMBUS developers, and we began distributing our codes
with anonymous FTP in the 1980s. I think we were the first quantum
chemistry code to do this. Now, there are several open source
programming projects, NWChem, DALTON, MOLCAS, and many others.

> So, new users
> need to search for available tools by themselves,


Yes, but the same is true for any language.

> learn the installation method (sometimes
> very time-consuming),


Same for any language.

> validate them (this is crucial!),


Yes, the same for any language.

> and finally use them.
> (Sometime before, I need to find some special function codes, but it took really a lot of
> time to find a good one. Some initial libraries I tried were almost useless...)


This will always be a problem for any kind of library in any language,
and especially for open-source projects where anyone can contribute or
modify the source code.

$.02 -Ron Shepard

Similar Threads