[yt-dev] Matching points to grids

[John ZuHone]

Hi Chris,

I would point out that the code I wrote is so far only written in Python, so before we make a judgment call on the speed it should be converted to Cython. 

Here's where it is right now. I'm actually going to hold off on issuing a PR probably until I hear some more of Matt's thoughts and convert it to Cython (as much of it as possible, anyway). 

https://bitbucket.org/jzuhone/yt/changeset/d00afdd643c65062f357dbbe31fbfbd4

Best,

John

On Nov 17, 2012, at 6:09 PM, Christopher Moody <cemoody at ucsc.edu> wrote:

> Hi John,
> That speed is similar to what I found. Brute force collision check would make (3x2x7000x10^6) ~ 10^10 floating point operations, which should take a few seconds on a modern single core (3Ghz*10seconds). Making an actually intelligent depth-first search should drop the number of grids to check for every particle by an order of magnitude. So we should really be able to beat a 4-minute gridding time, we just need to figure out what the bottleneck is. And of course this is applicable to particles in yt-3.0.
> 
> chris
> 
> 
> On Sat, Nov 17, 2012 at 6:30 AM, John ZuHone <jzuhone at gmail.com> wrote:
> Chris,
> 
> Since last night I've developed a working depth-first approach which is *reasonably* fast, but I think it depends on your definition of reasonable. :) It just did a FLASH dataset with ~7000 blocks and 10^6 points in about 4 minutes. 
> 
> I'm going to try it out on a few more datasets, and I'm hoping to issue a PR for it today or tomorrow. 
> 
> Best,
> 
> John
> 
> On Nov 16, 2012, at 6:21 PM, Christopher Moody <cemoody at ucsc.edu> wrote:
> 
>> Hi John, 
>> I tried writing a cython routine that matched particles to grids a while back. It works in the opposite order as a recursive octree-like gridding. It starts with the highest-level most-refined grids, recording the grid ID that each particle belongs to. It skips previously gridded particles as it progresses to coarser grids. It's likely not faster than depth-first approach.
>> 
>> It could be helpful, but it's terribly slow, despite several attempts to speed it up. 
>> Check out  assign_particles_to_cell_lists() in yt-hg/yt/utilities/lib/CICDeposit.pyx
>> 
>> chris  
>> 
>> 
>> On Fri, Nov 16, 2012 at 11:30 AM, Matthew Turk <matthewturk at gmail.com> wrote:
>> Hi John,
>> 
>> I think that would work fine for Enzo, we'd just need to iterate over
>> root grids.
>> 
>> -Matt
>> 
>> On Fri, Nov 16, 2012 at 2:28 PM, John ZuHone <jzuhone at gmail.com> wrote:
>> > Hi Matt,
>> >
>> > Would it work just to start at the top-level grids and then work down the tree, checking the children as you go? I know this would work for FLASH, but I'm not certain it would work for Enzo.
>> >
>> > John
>> >
>> > On Nov 16, 2012, at 2:14 PM, Matthew Turk <matthewturk at gmail.com> wrote:
>> >
>> >> Hi John,
>> >>
>> >> That's the ideal way, but we don't yet have the code to do that.  I
>> >> would like to do that.  The fastest method would be to create a new
>> >> version of find_values_at_points (which accepts an array) and make itj
>> >> ust return grid indices.  This would do the NxM collision check of
>> >> particles in grids.
>> >>
>> >> Writing an octree-aware particle finder would be a good idea.
>> >> Necessary, even...
>> >>
>> >> -Matt
>> >>
>> >> On Fri, Nov 16, 2012 at 1:07 PM, John ZuHone <jzuhone at gmail.com> wrote:
>> >>> I did know about that, but given, say, a million points, would that be
>> >>> *fast*? I need to look at what it does I guess.
>> >>>
>> >>> In FLASH, what'd we'd normally do is start at the top level and traverse
>> >>> down the octree until we found the block.
>> >>>
>> >>> On Nov 16, 2012, at 1:02 PM, Nathan Goldbaum <nathan12343 at gmail.com> wrote:
>> >>>
>> >>> Hi John,
>> >>>
>> >>> Yes, you can use pf.h.find_point() to do that.  There's some documentation
>> >>> on it here:
>> >>> http://yt-project.org/doc/analyzing/low_level_inspection.html#finding-data-at-fixed-points
>> >>>
>> >>> -Nathan
>> >>>
>> >>> On Nov 16, 2012, at 10:00 AM, John ZuHone wrote:
>> >>>
>> >>> Hi all,
>> >>>
>> >>> Do we have anything in yt right now that, given a set of points, *quickly*
>> >>> finds out which grids they belong to?
>> >>>
>> >>> Best,
>> >>>
>> >>> John Z
>> >>> _______________________________________________
>> >>> yt-dev mailing list
>> >>> yt-dev at lists.spacepope.org
>> >>> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
>> >>>
>> >>>
>> >>> _______________________________________________
>> >>> yt-dev mailing list
>> >>> yt-dev at lists.spacepope.org
>> >>> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
>> >>>
>> >>>
>> >>>
>> >>> _______________________________________________
>> >>> yt-dev mailing list
>> >>> yt-dev at lists.spacepope.org
>> >>> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
>> >>>
>> >> _______________________________________________
>> >> yt-dev mailing list
>> >> yt-dev at lists.spacepope.org
>> >> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
>> >
>> > _______________________________________________
>> > yt-dev mailing list
>> > yt-dev at lists.spacepope.org
>> > http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
>> _______________________________________________
>> yt-dev mailing list
>> yt-dev at lists.spacepope.org
>> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
>> 
>> _______________________________________________
>> yt-dev mailing list
>> yt-dev at lists.spacepope.org
>> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
> 
> 
> _______________________________________________
> yt-dev mailing list
> yt-dev at lists.spacepope.org
> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
> 
> 
> _______________________________________________
> yt-dev mailing list
> yt-dev at lists.spacepope.org
> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.spacepope.org/pipermail/yt-dev-spacepope.org/attachments/20121117/01822b5a/attachment.html>