Sure... J is designed for working with regular data structures. Trees -- or at least binary trees -- are irregular. Specifically, in the context of the KD tree, to properly interpret the significance of a child node, you must include information which is not represented at the node, but which must be extracted during the traversal from the root.
That said, yes... the data structures that work in J, for algorithmic cases which are traditionally addressed by trees, tend to have tree-like characteristics. They can often be thought of as variants on the tree structures, if you are in the right frame of mind. The perspective offered in Henry Rich's introduction to his "J for C Programmers" book (http://www.jsoftware.com/help/jforc/introduction.htm) might be relevant here. Put differently: J's operations have significant O(1) interpreter overhead. However, when an operation can be applied to a large sequence of data this cost will tend to be much smaller than the O(n) [or whatever] cost of applying that primitive to that large chunk of data. In other words, large, regular operations tend to be (relatively speaking) much cheaper in J than small, step-by-step operations. So when you can use them, it's usually a good idea to do so. (As a result, successful J programmers tend to focus on large-scale algorithmic issues.) I hope this made sense, -- Raul On Thu, Sep 13, 2012 at 6:53 PM, slocklin <scott_lock...@yahoo.com> wrote: > > Raul: > > Can you expand on why trees are bad in J? Coming from a C and Lisp > mentality, tree search wins a lot of problems. kd-trees break down in higher > dimensions (aka, for things like image databases, where I guess locality > hashing will beat a brute force search), but for modest dimensionality > (~10), they seem to do well, with cache misses and everything. > Your technique works, if I understand it correctly, and I'm guessing it > doesn't keep extra copies of the data around to fill up the memory, making > it effectively a sort of tree. > > It is going to take me a while to digest the code you and Marshall wrote, > thank you both very kindly for taking the time! > > -Scott > > > Raul Miller-4 wrote: >> >> Tree structures -- especially binary tree structures -- are frequently >> a bad choice in J. >> >> Personally, if I were working with spatial data in J, I'd probably >> start with something like this: >> >> NB. example arbitrary set of points: >> points=: ?.20 3$0 >> prepad=: $&__@,~@{:@$, ], $&_@,~@{:@$ >> searchable=: /:~@:((|."0 1) ,:^:(2 - #@$))"0 2~ i.@{:@$ >> SP=: searchable prepad points >> >> In other words: make n copies of the list of points (where n is the >> number of dimensions) and sort each list so that it can be binary >> searched along one of those dimensions. >> >> Of course, it's not that simple. To find the nearest point, you need >> to search a volume which includes your candidate points. So, in the >> worst case (most points equidistant from the point you are checking) >> you wind up searching the entire data structure. >> >> I've assumed, here, that once we've done a binary search to find a >> close match to the point we are looking for that it's worth searching >> the n nearest points in each direction from that match (where n is the >> number of dimensions). So this means an initial search of n*(1+n) >> points (n lists of candidates each containing 1+n points). We need to >> extend our search if any of the 2n points bounding each of the n lists >> of candidates has a coordinate distance from the point we are looking >> for which is closer than our closest candidate. >> >> This might sound significantly less efficient than a kd-tree, but we >> need to keep in mind that the kd-tree (or r* tree) has significant >> costs from cache misses and from pipeline busting. >> >> That said, there are a few other tricks that might be needed. For >> example, if you are incrementally building the structure, adding to >> sorted lists is inefficient. You can work around this issue by >> maintaining multiple instances of the logical structure and searching >> both (or all) of them and then picking the best result (for example). >> Then occasionally you find some time to merge them together. >> >> That said, I have not had time to draft up a real sample. (The >> project I am currently working on releases this weekend, and in my >> "spare" time I'm taking a class, which leaves me without much time for >> fun stuff like this.) >> >> I hope this helps, >> >> -- >> Raul >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> >> > > -- > View this message in context: > http://old.nabble.com/Spatial-trees-tp34422178s24193p34429335.html > Sent from the J Programming mailing list archive at Nabble.com. > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
