Maxval(array)

I want to know the 3 biggest values inside an array using Maxval(array).

The biggest value I know how to get it like this:

Biggest(1) = Maxval(array)

Now, I'd like to consider the remaining array, without biggest(1); do you know if it's possible to get the second biggest value, using

WHERE (array < biggest(1))

biggest(2) = MAXVAL(array)

ENDWHERE

I'v yet tried and it doesn't function, or I'm making some error ...

Thanks

F

WHERE is rather like an IF construct applied to each array element in turn. This means that your code is logically incorrect on two counts.

Try

b1 = maxval(array) b2 = maxval(array, mask = array < b1)

Or you could use a FORALL construct in the form...

b1 = 0 !(or a large negative value if all the elements might be negative) b2 = 0

FORALL(i=1,n) IF(array(i) > b1)THEN b2 = b1 b1 = array(i) ENDIF END FORALL

This assumes your array is one dimensional. Using DO constructs instead of FORALL is a little more direct. This second approach needs improving because you could end up with b2 = b1 when the largest value is repeated.

I would suggest you have 2 alternatives:-

If you realy want to use MAXVAL (MAXLOC) then the following could work.

x = minval(array)
!
i1 = maxloc(array)
x1 = array(i1) ; array(i1) = x
!
i2 = maxloc(array)
x2 = array(i2) ; array(i2) = x
!
i3 = maxloc(array)
x3 = array(i3) ; array(i3) = x

Alternatively, you could sort the array once using DSORT@, RSORT@ or ISORT@ then use the supplied index to locate the values.

I would expect that one call to sort might be quicker than 4 search calls to minval and maxloc. It would depend on the size of the array and what further use you could make of the sort index.

Thank you Paul and John, I've been working around following your posted ideas, using MAXVAL and MAXLOC.

Although my first intention was to get 3 biggest values of an array, now I can get all the array sorted, even with repeated values (e.g. a(1) = 5 and a(22) = 5).

I don't know if it can be done faster using another code or by means of ISORT routine.

Meanwhile, I post here the code I got waiting for your comments to turn it faster.

PROGRAM SORT_ARRAY
implicit none
!ARRAY IS THE ORIGINAL ARRAY
!MAX IS AN INTERMEDIATE ARRAY
!B IS THE FINAL ARRAY SORTED, THAT WILL BE USED

INTEGER ARRAY(1000), MAX(1000), B(1000), G, I, T

DO I = 1, 1000
  ARRAY(I) = I
  END DO

  
I = MAXVAL(ARRAY)

DO T = 1, 1000
MAX = MAXVAL(ARRAY, MASK = ARRAY <= I)
B(T) = MAX(T)
G = MAXLOC(ARRAY, DIM = 1, MASK = ARRAY .LE. I)

I = ARRAY(G)
! ... because it's possible that some values are repeated in ARRAY
! we need to change it to catch other equal values:

ARRAY(G) = ARRAY(G) + 1 

!  that means that ARRAY is no longer the same as at the beginning

END DO

 PRINT *, B(1), B(2), B(3), B(4), B(5), B(6) 

  END PROGRAM

Your program example could be improved substantially, as you have done a masked search 2,000 times.

I have modified your code to:

1. use a parameter NUM rather than 1000 for a test.
2. included a use of ISORT@ to show an alternative solution.
3. I do not know why you used the line 'MAX = MAXVAL(ARRAY, MASK = ARRAY ⇐ I)' as MAXVAL returns a scalar.
4. MAXVAL can be replaced by MAXLOC as it does the same search.
5. included some timing to see how long both approaches take.

You should try a larger value of num to see how dramatically different the run time is between the 2 approaches, say a value of num = 100,000 or 1,000,000 will show a big difference, if you have the time to wait.

Intrinsic procedures for searching still have to do similar searching operations as a procedure you could write yourself. They are not much faster.

I hope this example is of use.

PROGRAM SORT_ARRAY 
!
!  ARRAY IS THE ORIGINAL ARRAY 
!  MM    IS AN INTERMEDIATE ARRAY 
!  B     IS THE FINAL ARRAY SORTED, THAT WILL BE USED 
!
   implicit none 
!
   integer, parameter :: num = 100000
!
   INTEGER ARRAY(num), MM(num), B(num), G, I, T, NT, i0,i1,i2,i3, k
   real*8  x
!
                                                      call system_clock (i0)
   DO I = 1, num 
     call random_number (x)
     ARRAY(I) = int ( x * real(num) ) 
   END DO 
!  
! This is a much faster solution, if many ordered values are required
                                                      call system_clock (i1)
   call isort@ (mm, array, num)
   write (*,1000) (array(mm(num-i)),i=0,9)
!
! Now proceed with original scan
                                                      call system_clock (i2)
   I = MAXVAL (ARRAY) 
!
! determine number of scans to make ( = num takes too long )
   NT = sqrt (real(num))
    if (NT <  20) NT =  20
    if (NT > 100) NT = 100
!
   DO T = 1, NT !  was 'num'
      if (mod(t,num/10) == 0) write (*,*) 'At',T
!
! Why the use of array MM ?, as MAXVAL returns a scalar (rank 1 less than ARRAY)
!!   MM   = MAXVAL (ARRAY, MASK = ARRAY <= I) 
!!   B(T) = MM(T) 
!
     B(T) = MAXVAL (ARRAY, MASK = ARRAY <= I) 
!
      G = MAXLOC (ARRAY, DIM = 1, MASK = ARRAY .LE. I) 
!
      I = ARRAY(G) 
!
! NOTE: ARRAY(G) could also be used to set B(T)
!zz      B(T) = I
!
! ... because it's possible that some values are repeated in ARRAY 
! we need to change it to catch other equal values: 

      ARRAY(G) = ARRAY(G) + 1 

!  that means that ARRAY is no longer the same as at the beginning 

   END DO 

   write (*,1000) (B(i), i=1,10)
                                                      call system_clock (i3)
!
! estimate of equivalent number of scan operations to a full sort
   k = nint ( real(I2-I1)/real(i3-i2) * real(NT) )   
   write (*,1002)                                 &
               'Set Up data ', (i1-i0),' ticks',  &
               'Sort search ', (i2-i1),' ticks',  &
               'Scan search ', (i3-i2),' ticks',  &
               'Array Size  ', num,    ' ',       &
               'Num scans   ', NT,     ' ',       &
               'Scans = Sort', k,      ' scans'       
1000 format (10i8)
1002 format (1x,a,i8,a)
END PROGRAM

You are right John!

The first code I posted is very slow when sorting more than 1000 array elements.

The code you posted as 'Scan' is much, much... faster than mine too.

To sort 10000 elements with my code takes more than 5 min!!! Your 'scan' code takes some seconds to sort 100000!

But ISORT routine it's a thunder light; although I've met it in the net, I didn't know how to use it, namely its parameters (mm, array, num). Now I know how to use it. You don't imagine how grateful I am with your help. I searched a lot to make that piece of code and it has been worth, not by its performance, but by the problems I've to solve ... learning a little more.

Your code has a lot of new information for me and I need some more time to digest it all.

It's a marvelous work that will be a good reference for all fortran beginners like me.

Thanks a lot John.

Frank

I've tried to sort an array with dimension = 2, by each dimension, but I didn't get to.

I'm supposing that ISORT subroutine has no other parameters to sort by each dimension of the array. I didn't met that in FTN95 help files.

Perhaps using Maxloc/Maxval and specifying DIM = 1 or 2, is better here, although slower.

The other way is to pass all values of one selected dimension of the original array to one dimension array and to use ISORT subroutine after :idea:

ISORT@ will probably work just as well with 2-dimensional arrays provided that you pass the size of the whole array. You could use an EQUIVALENCE statement to cast it to a 1-dimensional array but I doubt if you will need to do this even in /check mode.

In other words the array will be stored as a contiguous block that internally looks like a 1-dimensional array.

Paul, I don't know if I'm understanding what you mean.

Supposing this is the array I want to sort:

Array(1,1) = 10 Array(1,2) = 15 Array(1,3) = 20 Array(2,1) = 1 Array(2,2) = 5 Array(2,3) = 6

Call isort@ (Array2, Array, N)

will make Array2 to look like this:

Array2(1) pointed to Array(1,3) Array2(2) pointed to Array(1,2) Array2(3) pointed to Array(1,1) Array2(4) pointed to Array(2,3) Array2(5) pointed to Array(2,2) Array2(6) pointed to Array(2,1)

I want only to work with 3 elements of Array: Array(2,1), Array(2,2) and Array(2,3).

I´m afraid that it's not possible to specify that in 'Call Isort@ (Array2, Array, N)'.

Meanwhile I'm not seeing how to make an Equivalence Statement in this example; can you give me a hint, using If ... Then... End If?

Thanks, Frank

ISORT@ should work OK with 2 dimensional arrays in the sense that the columns of the matrix follow one after another in a linear order. It becomes one dimensional by going down the first column and then continuing at the top of the second column etc.

Ignore what I wrote about EQUIVALENCE statements.

If you only want to sort selected elements from the array then you will need to extract them from the array first.

sorry for my ignorance, but...is it possible to use ISORT with arrays of derived data type? For instance, if my array contains elements with coord%x and coord%y data. Can ISORT sort the array according to coord%x values? I wrote my own routine for that, but I wonder if there is anything faster...

Agustin

Paul,

Further to this latest question, can we assume any implied variable order for a Type array, when supplying an 'address' for a F77 style routine, such as ISORT@. Can any variable order be assumed for the following data TYPE ?

TYPE Coordinate_Record
   real*8 X
   real*8 Y
   real*8 Z
   integer*4 fixity(6)
END TYPE Coordinate_Record

type (Coordinate_record) nodes(1000)

If the array 'fixity' was not included, would that give any better assumptions on variable order ?

For example, if I call a routine, like 'call average_height (nodes%Z)', or even call DSORT@ (index, nodes%Z, n), does this require a temporary array to be provided by the compiler, which is used to update the Z values on return, or does it use the actual Z values in the TYPE data structure ? It could get confusing/illegal if I also addressed nodes(i)%Z in average_height, if nodes was defined in a module.

thanks John

Fortran 95 has the SEQUENCE attribute which I assume is appropriate here. FTN95 also appears to accept the form SEQUENCE(num). This may relate to the padding. I can check this out if you need to know.

Paul, would you suggest to use SEQUENCE in the following subroutine to make faster the sorting of the data? I believed that it was better to leave the compiler to allocate derived data type. I am currently using this code for ordering an array with x and y coordinates of particles according the x values.

Agustin

SUBROUTINE order_array(n,lista) use my_data implicit none real tmp,tmp2 integer swap_index,length,n type(coordenate),dimension(n) :: lista length = size(lista) do j=1,length-1 swap_index = MAXLOC(lista(j:length)%x,DIM=1) tmp = lista(j)%x tmp2=lista(j)%y lista(j)%x = lista((j-1)+swap_index)%x lista(j)%y = lista((j-1)+swap_index)%y lista((j-1)+swap_index)%x = tmp lista((j-1)+swap_index)%y = tmp2 end do END SUBROUTINE order_array

I have just tested DSORT@ with derived type data arrays and works great and incredibly faster than my code! and apparently there is no need of using SEQUENCE in the declaration of the derived type. Just my 0.2 cents Agustin