Fortran templates
in [Fortran]
|
From: Charles Coldwell on 23 Apr 2008 18:43 glen herrmannsfeldt <gah(a)ugcs.caltech.edu> writes: > Charles Coldwell wrote: > (snip) > >> In C, I would write this > >> int compare(int i, int j) >> { >> double r = data[i] - data[j]; >> return (2*(r>0) - 1) & -(r != 0); >> } > > I think I more often see: > > return (r>0)-(r<0); Oooh. I like that. > Otherwise, how about > > compare=count((/ data[i].ge.data[j], data[i].gt.data[j] /))-1 Very cute, I like it, too. I have more confidence in the compiler's ability to generate tight code for the C version, above, though. Chip -- Charles M. "Chip" Coldwell "Turn on, log in, tune out" GPG Key ID: 852E052F GPG Key Fingerprint: 77E5 2B51 4907 F08A 7E92 DE80 AFA9 9A8F 852E 052F
From: relaxmike on 24 Apr 2008 04:01 On 23 avr, 12:06, Charles Coldwell <coldw...(a)gmail.com> wrote: > I don't see any code duplication in the client. The implementations > of "compare" and "exchange" must be different for different types. > It's like in C++, where "operator<" (the analog of "compare") must be > defined for any type in an STL container. I think I now understand what you mean, and let me explain what I mean : there is no duplication in the client, simply because there is only one client, of course ! This is because you transformed the problem of "having a method which sorts whatever type of array" into "having a method which sorts the client-side array". The consequence is that you define only one "compare" method, and you conclude that there is no duplication. Now let's define what should be to do to have a method to sort arrays of logical, integers, real and double : you, of course, have to define a "compare_logical" , "compare_integer", "compare_real", "compare_double". This is because the compare method have to explicitly define the type of data to compare. In the end, there are 4 implementations of the same "template" compare, all using the same (and basic) "<". That is true that if you want to compare characters, you may have to define "<" (but I am not sure). Isn'it duplication ? I looked in the internet to search for how the C++ STL solved that problem. I found a web page, but I do not known if it is of high quality : http://www.cppreference.com/cppalgorithm/sort.html See how the sort of an array of integers is solved : vector<int> v; v.push_back( 23 ); v.push_back( -1 ); v.push_back( 9999 ); v.push_back( 0 ); v.push_back( 4 ); sort( v.begin(), v.end() ); I don't pretend that fortran can achieve such a level of simplicity, but that's the goal isn't it ? I think that callbacks are a good and efficient way to uncouple the sorting algorithm from the type of data to sort, but that is only half of the work to do to have a routine which can sort <whatever> type of array. Regards, Michaël
From: Greg Lindahl on 24 Apr 2008 04:14 In article <9b4f7b86-02ae-4717-b375-e7314e1798c0(a)l64g2000hse.googlegroups.com>, relaxmike <michael.baudin(a)gmail.com> wrote: >See how the sort of an array of integers is solved : > > vector<int> v; > v.push_back( 23 ); > v.push_back( -1 ); > v.push_back( 9999 ); > v.push_back( 0 ); > v.push_back( 4 ); > sort( v.begin(), v.end() ); > >I don't pretend that fortran can achieve such a level of >simplicity, but that's the goal isn't it ? You've got to be kidding! Variables that lack a constructor syntax are not that simple. And the STL is well known to have a pretty steep learning curve. -- greg
From: Charles Coldwell on 24 Apr 2008 06:36 relaxmike <michael.baudin(a)gmail.com> writes: > On 23 avr, 12:06, Charles Coldwell <coldw...(a)gmail.com> wrote: >> I don't see any code duplication in the client. The implementations >> of "compare" and "exchange" must be different for different types. >> It's like in C++, where "operator<" (the analog of "compare") must be >> defined for any type in an STL container. > > I think I now understand what you mean, and let me explain what > I mean : there is no duplication in the client, simply because there > is only one client, of course ! This is because you transformed > the problem of "having a method which sorts whatever type of array" > into "having a method which sorts the client-side array". > The consequence is that you define only one "compare" method, and > you conclude that there is no duplication. > > Now let's define what should be to do to have a method to > sort arrays of logical, integers, real and double : > you, of course, have to define a "compare_logical" , > "compare_integer", > "compare_real", "compare_double". This is because the compare method > have to explicitly define the type of data to compare. > In the end, there are 4 implementations of the same "template" > compare, all using the same (and basic) "<". > That is true that if you want to compare characters, you may have to > define "<" (but I am not sure). > Isn'it duplication ? Yes and no. It's more duplication than what you find in C++. For example, to use an ordered STL container, a class must define "operator<". For POD types (int, long, double, float), you can use the built-in compiler provided operator, you don't have to write any code, whereas in my Fortran quicksort-with-callbacks, you must define "compare", even for the built-in types (e.g. INTEGER, REAL, LOGICAL). However, if you want to sort *strings*, you will have to define "operator<" for the string class. Similarly for any user-defined types. Now, admittedly, "operator<" for std::string comes with the standard library, so you would be crazy to actually write it yourself, but you still have to define it for all the types you design yourself. > I looked in the internet to search for how the C++ STL solved that > problem. I found a web page, but I do not known if it is of high > quality : > http://www.cppreference.com/cppalgorithm/sort.html > See how the sort of an array of integers is solved : > > vector<int> v; > v.push_back( 23 ); > v.push_back( -1 ); > v.push_back( 9999 ); > v.push_back( 0 ); > v.push_back( 4 ); > sort( v.begin(), v.end() ); > > I don't pretend that fortran can achieve such a level of > simplicity, but that's the goal isn't it ? Sure. What I wrote is a Fortran function that implements the "sort" that comes with the C++ standard library. You could argue that Fortran should supply a sort intrinsic so that the code isn't duplicated by many implementors, but that's different from generic programming. In terms of simplicity, if I wrote a module implementing compare and exchange for integers, the C++ code above in Fortran would read use my_module data(1) = 23 data(2) = -1 data(3) = 9999 data(4) = 0 data(5) = 4 call quicksort(5, compare, exchange) The difference with C++ in this example is that the standard library is supplying the sort routine, the vector<> template and it's associated "operator<" (which in this case is just the built-in "operator<" for type int). The quicksort routine I posted previously is almost as general as the one that the C++ standard library supplies: it can work on an array of any type, including user-defined types, hence my claim that it demonstrates "generic programming" in Fortran. The C++ STL sort is more generic because it works on containers of any type, including lists, deques, arrays, vectors, maps and multimaps. > I think that callbacks are a good and efficient way > to uncouple the sorting algorithm from the type of > data to sort, Hence my claim that it is "generic". > but that is only half of the work to do to have a routine which can > sort <whatever> type of array. Fair enough, but at least for user-defined types, you have to do the other half of the work yourself whether you use C++ or Fortran. Chip -- Charles M. "Chip" Coldwell "Turn on, log in, tune out" GPG Key ID: 852E052F GPG Key Fingerprint: 77E5 2B51 4907 F08A 7E92 DE80 AFA9 9A8F 852E 052F
From: relaxmike on 24 Apr 2008 07:28
On 24 avr, 12:36, Charles Coldwell <coldw...(a)gmail.com> wrote: > Yes and no. It's more duplication than what you find in C++. For > example, to use an ordered STL container, a class must define > "operator<". For POD types (int, long, double, float), you can use > the built-in compiler provided operator, you don't have to write any > code, whereas in my Fortran quicksort-with-callbacks, you must define > "compare", even for the built-in types (e.g. INTEGER, REAL, LOGICAL). > However, if you want to sort *strings*, you will have to define > "operator<" for the string class. Similarly for any user-defined > types. Now, admittedly, "operator<" for std::string comes with the > standard library, so you would be crazy to actually write it yourself, > but you still have to define it for all the types you design yourself. Yes of course, you are right. I cannot consider that defining three compare routines is such a big deal that one should use a template for that. We agree that the callback method is more closed to generic programming that it is to templates. > The difference with C++ in this example is that the standard library > is supplying the sort routine, the vector<> template and it's > associated "operator<" (which in this case is just the built-in > "operator<" for type int). The quicksort routine I posted previously > is almost as general as the one that the C++ standard library > supplies: it can work on an array of any type, including user-defined > types, hence my claim that it demonstrates "generic programming" in > Fortran. The C++ STL sort is more generic because it works on > containers of any type, including lists, deques, arrays, vectors, maps > and multimaps. Obviously, I don't know the STL sufficiently to compare fortran and C++ at that level. And I do not master the C++ iterators. > Fair enough, but at least for user-defined types, you have to do the > other half of the work yourself whether you use C++ or Fortran. You are right and there is no other way to do it. Anyway, the algorithm you provided is an interesting solution for the generic sorting problem. Michaël |