
forums.silverfrost.com Welcome to the Silverfrost forums

View previous topic :: View next topic 
Author 
Message 
johannes
Joined: 21 Jan 2011 Posts: 65 Location: Leimen, Germany

Posted: Tue Apr 08, 2014 9:04 am Post subject: 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 arbitrary true array element without searching the array through all dimensions?
BR, Johannes 

Back to top 


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

Posted: Tue Apr 08, 2014 1:06 pm Post subject: 


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 


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

Posted: Tue Apr 08, 2014 11:27 pm Post subject: 


Parallelize. 

Back to top 


PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 6222 Location: Salford, UK

Posted: Wed Apr 09, 2014 7:32 am Post subject: 


Parallelize?! Surely that needs a smiley face. 

Back to top 


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

Posted: Wed Apr 09, 2014 10:52 am Post subject: 


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"
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 


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

Posted: Wed Apr 09, 2014 1:49 pm Post subject: 


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 nonzero integers. If they were coded into INTEGER*8s, then you are in effect finding the block of 64 equivalentlogicals 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 


davidb
Joined: 17 Jul 2009 Posts: 557 Location: UK

Posted: Thu Apr 10, 2014 9:38 am Post subject: 


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 subarrays with an exit when a .true. is found. _________________ Programmer in: Fortran 77/95/2003/2008, C, C++ (& OpenMP), java, Python, Perl 

Back to top 


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

Posted: Thu Apr 10, 2014 11:17 am Post subject: 


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 


JohnCampbell
Joined: 16 Feb 2006 Posts: 2160 Location: Sydney

Posted: Thu Apr 10, 2014 1:53 pm Post subject: 


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 1dimensional 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 


davidb
Joined: 17 Jul 2009 Posts: 557 Location: UK

Posted: Thu Apr 10, 2014 6:53 pm Post subject: 


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 


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

Posted: Thu Apr 10, 2014 10:48 pm Post subject: 


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 


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

Posted: Fri Apr 11, 2014 3:14 pm Post subject: 


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 


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

Posted: Fri Apr 11, 2014 3:25 pm Post subject: 


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 


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

Posted: Sat Apr 12, 2014 7:48 am Post subject: 


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

Back to top 


davidb
Joined: 17 Jul 2009 Posts: 557 Location: UK

Posted: Sat Apr 12, 2014 1:38 pm Post subject: 


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. _________________ Programmer in: Fortran 77/95/2003/2008, C, C++ (& OpenMP), java, Python, Perl 

Back to top 




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
