Find any .true. in a 3D array as fast as possible

Hi all, I have a large 3D logical array Llogic(Nx,Ny,Nz), say. Initially all elements are .false. and within some loops more elements get .true. and some return to .false. - more or less in unpredictable order.

My question: is there a fast way to find one [u:6cf68ac207]arbitrary[/u:6cf68ac207] true array element without searching the array through all dimensions? BR, Johannes

How may .true. values are there at any one time? If Nx, Ny and Nz are big, and the number of .true. values is small, then it might be worth dispensing with the 3D array and just keeping the indices for the .true. values.

Eddie

Parallelize.

Parallelize?! Surely that needs a smiley face. 😐

I am dead seriousss! 😄 All depends on problem size. If you are searching in huge arrays many times during run which becomes the bootleneck and the trick Eddie suggested is by some reason not applicable then what else is left? Parallelization. It works great as we tested it in the thread called 'Two multithreading programs'

https://forums.silverfrost.com/Forum/Topic/2239&highlight=paralell+parallel

It seems to me that it should be possible somehow to make use of the fact that .true. is stored as 1, and .false. as 0. Accordingly using any LOGICAL of more than an eighth of a byte is wasting space! Or, encoding the logicals as consecutive bits in an INTEGER, one could code in 32 of them in an INTEGER4 or 64 in an INTEGER8 (or whatever, and completely forgetting about the sign bit for simplicity of argument). Let's suppose that you stored your initial .false. values as zeroes, then your integers would all simply come out as zero. It might be a bit of a rigmarole to set one of the bits in the appropriate INTEGER to 1 or reset it to zero, but you would reduce the problem of finding a .true. to testing for non-zero integers. If they were coded into INTEGER*8s, then you are in effect finding the block of 64 equivalent-logicals in which there is a .true., which reduces the testing by a huge factor, although every time one wants to flip a value from .true. to .false. or vice versa there is an overhead, plus even finding the nearest block of 64 values you still need to determine which one is it.

It certainly boils down to what is the expected range of Nx, Ny and Nz, and indeed, how many .true.s there are likely to be, and how adept Johannes is at manipulating bits as distinct from the simplicity of LOGICALs.

My INTEGER would be composed from

value_of_Llogical(I,J,K) + 2value_of_Llogical(I,J, K+1) + 4 ...

(and don't forget the sign bit, which might make it better to encode just 63 in an INTEGER*8 etc).

Alternatively spend the next decade becoming an expert in searching algorithms, which I am certainly not!

Eddie

PS. It ought to be possible to store relative truth in a LOGICAL, and I offer this as a tongue in cheek suggestion for a future Fortran standard. Even in a RELATIVE_LOGICAL1 you could have a scale of 1 ... 255 of truthfulness. Using RELATIVE_LOGICAL16 it might even be possible to discriminate the level of truthfulness in a politician's promise, and thus open up unimagined possibilities for programming fields in the future!

This is what the intrinsic function ANY is for!

Perhaps Paul will parallelise this for us using SSE or AVX 😄.

If ANY is inefficient on large arrays, you can use ANY with a divide and conquer strategy on smaller sub-arrays with an exit when a .true. is found.

See, I said you needed an expert on searching algorithms, and there is one at hand!

I did have a quick scan of standard functions in Fortran 95, and ANY didn't catch my eye. I suspect that it needs at some point to examine every value, which isn't the case with either of my my first or second suggestions. The first would be fastest with a small number of .true.s and my second suggestion probably needs at least one of Nx, Ny and Nz to be large before it makes sense, but checking the bits sixty three at a time must beat checking each one singly.

Having thought more about my second suggestion, it is probably worth some deep thought about the best way to get the minimum number of items to search, and that may well require mapping to a linear array of INTEGER8s of total length (NxNy*Nz)/63+1.

Finally, I had a quick go with ANY. It's a new trick for this old dog. It doesn't tell you where the .true. is, and I suspect that the original poster wanted to extract the position and probably already knew that there was at least one .true. in hiding. Knowing that a needle lies in a haystack is useful, but knowing where it is represents a different problem. I may be wrong of course.

Although the Fortran 95 standard requires that certain functions exist, it does not demand that they are optimised or even reasonably efficient in all or any circumstances - a missed opportunity.

Eddie

I agree with Eddie, If you keep a list of true values, then work on the true list. You can keep a list of the addresses of (Nx,Ny,Nz) that are true in an integer vectior, with a count num_true. These is a simple transformation from (Nx,Ny,Nz) to the 1-dimensional array offset. It all depends on the % true in the large 3D array, to confirm if this approach is effective. If % < 10% then it is probably useful. There is also the consideration on the order of the index array, being address order, FIFO order or other, which can provide a useful ordering strategy for using .true. values.

John

Why not just use:

is_true = .false.
outer: do k=1, Nz
       do j=1, Ny
       do i=1, Nx
           if (Llogic(i,j,k)) then
              is_true = .true.
              exit outer
           end if
       end do
       end do
       end do outer

! is_true is .true. if a .true. value exists
! if is_true .eq. .true. then i,j,k contains the location of the first .true. value

You only search until the first .true. is found. The only time you search every element is when there isn't a .true. value (or when there is one .true. value in the last element).

If you don't like the labelled outer do and the exit, you can of course use goto.

BTW: ANY doesn't need to look at every value. ALL does need to. But you are at the mercy of how efficiently the compiler writers have written these functions.

We are all answering different questions!

Davidb is answering the question (firstly) is any element .true.? and (secondly) what are the indices of the first .true. element? David, if the very last element is .true. you have to scan through all of them, and indeed, if there are no .true. values the same.

Having a vector of .true. values with their indices allows us to very quickly find every .true. value, and never search through the whole set. My second suggestion scans through the lot, but lots at a time.

Does Johannes's question mean that he is happy to find the location of just one of the .true. values?

Eddie

Hi all, thank you for so much of ideas. If there was a command like maxloc but for Logical just one statement would have done it.

Finally I've chosen to do some indexing and searching in a subdomain around the last few .true. findings. If this is not successful I search in the complete array. This considerably reduces the number of big sweeps. Fortunately the .true.'s are not perfectly random distributed, but bit of clustered.

best regards, Johannes

BTW: the dimension is of the order of 1000x1000x10

Johannes,

If your logical array is in a named common block then in another subprogram it could be declared as an integer array (as long as the logicals and integers are of the same length) and then MAXLOC would work on it! This makes use of the .true. = 1 and .false. = 0 equivalence.

David's caution about how the intriniscs work applies here too.

Eddie

Hi Eddie, here I have an ALLOCATABLE array. BR, johannes

Be careful associating .true. with 1.

Some compilers store .true. as -1 (e.g. PGI/Nvidia Fortran) so you have to use MINLOC with that compiler 😉 . Of course, this is only a problem if you need portability.

As you know your data and the likely locations of the .true. values it makes sense to search those locations first. One strategy that sometimes helps is to look first in the place where a .true. was found last time you looked. Or, indeed, to build up a table of locations where previous .true. values were found.