Hi John,<div>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.<span></span></div>
<div><br></div><div>chris</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Nov 17, 2012 at 6:30 AM, John ZuHone <span dir="ltr"><<a href="javascript:_e({}, 'cvml', 'jzuhone@gmail.com');" target="_blank">jzuhone@gmail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Chris,<div><br></div><div>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. </div>

<div><br></div><div>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. </div><div><br></div><div>Best,</div><div><br></div><div>John</div><div><div><div>
<br><div><div>On Nov 16, 2012, at 6:21 PM, Christopher Moody <<a href="javascript:_e({}, 'cvml', 'cemoody@ucsc.edu');" target="_blank">cemoody@ucsc.edu</a>> wrote:</div><br><blockquote type="cite">Hi John, <div>
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.</div>


<div><br></div><div>It could be helpful, but it's terribly slow, despite several attempts to speed it up. </div><div>Check out  assign_particles_to_cell_lists() in yt-hg/yt/utilities/lib/CICDeposit.pyx</div><div><br>

</div>
<div>chris  </div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Nov 16, 2012 at 11:30 AM, Matthew Turk <span dir="ltr"><<a href="javascript:_e({}, 'cvml', 'matthewturk@gmail.com');" target="_blank">matthewturk@gmail.com</a>></span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi John,<br>
<br>
I think that would work fine for Enzo, we'd just need to iterate over<br>
root grids.<br>
<br>
-Matt<br>
<div><div><br>
On Fri, Nov 16, 2012 at 2:28 PM, John ZuHone <<a href="javascript:_e({}, 'cvml', 'jzuhone@gmail.com');" target="_blank">jzuhone@gmail.com</a>> wrote:<br>
> Hi Matt,<br>
><br>
> 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.<br>
><br>
> John<br>
><br>
> On Nov 16, 2012, at 2:14 PM, Matthew Turk <<a href="javascript:_e({}, 'cvml', 'matthewturk@gmail.com');" target="_blank">matthewturk@gmail.com</a>> wrote:<br>
><br>
>> Hi John,<br>
>><br>
>> That's the ideal way, but we don't yet have the code to do that.  I<br>
>> would like to do that.  The fastest method would be to create a new<br>
>> version of find_values_at_points (which accepts an array) and make itj<br>
>> ust return grid indices.  This would do the NxM collision check of<br>
>> particles in grids.<br>
>><br>
>> Writing an octree-aware particle finder would be a good idea.<br>
>> Necessary, even...<br>
>><br>
>> -Matt<br>
>><br>
>> On Fri, Nov 16, 2012 at 1:07 PM, John ZuHone <<a href="javascript:_e({}, 'cvml', 'jzuhone@gmail.com');" target="_blank">jzuhone@gmail.com</a>> wrote:<br>
>>> I did know about that, but given, say, a million points, would that be<br>
>>> *fast*? I need to look at what it does I guess.<br>
>>><br>
>>> In FLASH, what'd we'd normally do is start at the top level and traverse<br>
>>> down the octree until we found the block.<br>
>>><br>
>>> On Nov 16, 2012, at 1:02 PM, Nathan Goldbaum <<a href="javascript:_e({}, 'cvml', 'nathan12343@gmail.com');" target="_blank">nathan12343@gmail.com</a>> wrote:<br>
>>><br>
>>> Hi John,<br>
>>><br>
>>> Yes, you can use pf.h.find_point() to do that.  There's some documentation<br>
>>> on it here:<br>
>>> <a href="http://yt-project.org/doc/analyzing/low_level_inspection.html#finding-data-at-fixed-points" target="_blank">http://yt-project.org/doc/analyzing/low_level_inspection.html#finding-data-at-fixed-points</a><br>



>>><br>
>>> -Nathan<br>
>>><br>
>>> On Nov 16, 2012, at 10:00 AM, John ZuHone wrote:<br>
>>><br>
>>> Hi all,<br>
>>><br>
>>> Do we have anything in yt right now that, given a set of points, *quickly*<br>
>>> finds out which grids they belong to?<br>
>>><br>
>>> Best,<br>
>>><br>
>>> John Z<br>
>>> _______________________________________________<br>
>>> yt-dev mailing list<br>
>>> <a href="javascript:_e({}, 'cvml', 'yt-dev@lists.spacepope.org');" target="_blank">yt-dev@lists.spacepope.org</a><br>
>>> <a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org" target="_blank">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a><br>
>>><br>
>>><br>
>>> _______________________________________________<br>
>>> yt-dev mailing list<br>
>>> <a href="javascript:_e({}, 'cvml', 'yt-dev@lists.spacepope.org');" target="_blank">yt-dev@lists.spacepope.org</a><br>
>>> <a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org" target="_blank">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a><br>
>>><br>
>>><br>
>>><br>
>>> _______________________________________________<br>
>>> yt-dev mailing list<br>
>>> <a href="javascript:_e({}, 'cvml', 'yt-dev@lists.spacepope.org');" target="_blank">yt-dev@lists.spacepope.org</a><br>
>>> <a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org" target="_blank">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a><br>
>>><br>
>> _______________________________________________<br>
>> yt-dev mailing list<br>
>> <a href="javascript:_e({}, 'cvml', 'yt-dev@lists.spacepope.org');" target="_blank">yt-dev@lists.spacepope.org</a><br>
>> <a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org" target="_blank">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a><br>
><br>
> _______________________________________________<br>
> yt-dev mailing list<br>
> <a href="javascript:_e({}, 'cvml', 'yt-dev@lists.spacepope.org');" target="_blank">yt-dev@lists.spacepope.org</a><br>
> <a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org" target="_blank">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a><br>
_______________________________________________<br>
yt-dev mailing list<br>
<a href="javascript:_e({}, 'cvml', 'yt-dev@lists.spacepope.org');" target="_blank">yt-dev@lists.spacepope.org</a><br>
<a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org" target="_blank">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a><br>
</div></div></blockquote></div><br></div>
_______________________________________________<br>yt-dev mailing list<br><a href="javascript:_e({}, 'cvml', 'yt-dev@lists.spacepope.org');" target="_blank">yt-dev@lists.spacepope.org</a><br><a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org" target="_blank">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a><br>

</blockquote></div><br></div></div></div></div><br>_______________________________________________<br>
yt-dev mailing list<br>
<a href="javascript:_e({}, 'cvml', 'yt-dev@lists.spacepope.org');" target="_blank">yt-dev@lists.spacepope.org</a><br>
<a href="http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org" target="_blank">http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org</a><br>
<br></blockquote></div><br></div>