forums.silverfrost.com Forum Index forums.silverfrost.com
Welcome to the Silverfrost forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

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

 
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> General
View previous topic :: View next topic  
Author Message
johannes



Joined: 21 Jan 2011
Posts: 65
Location: Leimen, Germany

PostPosted: Tue Apr 08, 2014 9:04 am    Post subject: Find any .true. in a 3D array as fast as possible Reply with quote

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 arbitrary true array element without searching the array through all dimensions?
BR, Johannes
Back to top
View user's profile Send private message
LitusSaxonicum



Joined: 23 Aug 2005
Posts: 2074
Location: Yateley, Hants, UK

PostPosted: Tue Apr 08, 2014 1:06 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
DanRRight



Joined: 10 Mar 2008
Posts: 2154
Location: South Pole, Antarctica

PostPosted: Tue Apr 08, 2014 11:27 pm    Post subject: Reply with quote

Parallelize.
Back to top
View user's profile Send private message
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6222
Location: Salford, UK

PostPosted: Wed Apr 09, 2014 7:32 am    Post subject: Reply with quote

Parallelize?! Surely that needs a smiley face. Neutral
Back to top
View user's profile Send private message
DanRRight



Joined: 10 Mar 2008
Posts: 2154
Location: South Pole, Antarctica

PostPosted: Wed Apr 09, 2014 10:52 am    Post subject: Reply with quote

I am dead seriousss! Very Happy 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"

http://forums.silverfrost.com/viewtopic.php?t=2534&highlight=paralell+parallel


Last edited by DanRRight on Wed Apr 09, 2014 9:19 pm; edited 2 times in total
Back to top
View user's profile Send private message
LitusSaxonicum



Joined: 23 Aug 2005
Posts: 2074
Location: Yateley, Hants, UK

PostPosted: Wed Apr 09, 2014 1:49 pm    Post subject: Reply with quote

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 INTEGER*4 or 64 in an INTEGER*8 (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) + 2*value_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_LOGICAL*1 you could have a scale of 1 ... 255 of truthfulness. Using RELATIVE_LOGICAL*16 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!
Back to top
View user's profile Send private message
davidb



Joined: 17 Jul 2009
Posts: 557
Location: UK

PostPosted: Thu Apr 10, 2014 9:38 am    Post subject: Reply with quote

This is what the intrinsic function ANY is for!

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

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.
_________________
Programmer in: Fortran 77/95/2003/2008, C, C++ (& OpenMP), java, Python, Perl
Back to top
View user's profile Send private message
LitusSaxonicum



Joined: 23 Aug 2005
Posts: 2074
Location: Yateley, Hants, UK

PostPosted: Thu Apr 10, 2014 11:17 am    Post subject: Reply with quote

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 INTEGER*8s of total length (Nx*Ny*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
Back to top
View user's profile Send private message
JohnCampbell



Joined: 16 Feb 2006
Posts: 2160
Location: Sydney

PostPosted: Thu Apr 10, 2014 1:53 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
davidb



Joined: 17 Jul 2009
Posts: 557
Location: UK

PostPosted: Thu Apr 10, 2014 6:53 pm    Post subject: Reply with quote

Why not just use:

Code:

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.
_________________
Programmer in: Fortran 77/95/2003/2008, C, C++ (& OpenMP), java, Python, Perl
Back to top
View user's profile Send private message
LitusSaxonicum



Joined: 23 Aug 2005
Posts: 2074
Location: Yateley, Hants, UK

PostPosted: Thu Apr 10, 2014 10:48 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
johannes



Joined: 21 Jan 2011
Posts: 65
Location: Leimen, Germany

PostPosted: Fri Apr 11, 2014 3:14 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
LitusSaxonicum



Joined: 23 Aug 2005
Posts: 2074
Location: Yateley, Hants, UK

PostPosted: Fri Apr 11, 2014 3:25 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
johannes



Joined: 21 Jan 2011
Posts: 65
Location: Leimen, Germany

PostPosted: Sat Apr 12, 2014 7:48 am    Post subject: Reply with quote

Hi Eddie,
here I have an ALLOCATABLE array.
BR, johannes
Back to top
View user's profile Send private message
davidb



Joined: 17 Jul 2009
Posts: 557
Location: UK

PostPosted: Sat Apr 12, 2014 1:38 pm    Post subject: Reply with quote

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 Wink . 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.
_________________
Programmer in: Fortran 77/95/2003/2008, C, C++ (& OpenMP), java, Python, Perl
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> General All times are GMT + 1 Hour
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group