Hi John,<div><br></div><div>I think this looks pretty good for now, certainly for 2.x.</div><div><br></div><div>In 3.0 I want to eventually transition FLASH to the Octree geometry structure, which would mean that particle location could all occur directly inside Cython. We'd also have a number of much faster particle selection routines, which could eventually make it not necessary to directly sort or select particles too strongly in advance, as long as a coarse index could be built.</div>
<div><br></div><div>I say push it and we can move on from there. If you want, one thing you could absolutely do right now is construct a Cython routine that accepted:</div><div><br></div><div>x,y,z</div><div>left_edges, right_edges, parent_index</div>
<div><br></div><div>and then construct an octree from that, assigning particles as they came.</div><div><br></div><div>-Matt</div><div><br>On Saturday, November 17, 2012, John ZuHone 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">By the way, I certainly think that there is much room for improvement, so anyone that would like to take a look at it and make suggestions is most welcome. <div><br><div><div>On Nov 17, 2012, at 6:09 PM, Christopher Moody <<a>cemoody@ucsc.edu</a>> wrote:</div>
<br><blockquote type="cite">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><br><br><div>On Sat, Nov 17, 2012 at 6:30 AM, John ZuHone <span dir="ltr"><<a>jzuhone@gmail.com</a>></span> wrote:<br>
<blockquote 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>
<br><div><div>On Nov 16, 2012, at 6:21 PM, Christopher Moody <<a>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><br><br><div>On Fri, Nov 16, 2012 at 11:30 AM, Matthew Turk <span dir="ltr"><<a>matthewturk@gmail.com</a>></span> wrote:<br>
<blockquote 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><br>
On Fri, Nov 16, 2012 at 2:28 PM, John ZuHone <<a>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>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>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>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></div></blockquote></div></div></blockquote></div></div></div></blockquote></div></div></blockquote></div></div></div></blockquote></div>