StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>Histograms</strong></p> <p>The histogram way is not the fastest, and can't tell the difference between an arbitrarily small separation of points and <code>2 * sqrt(2) * b</code> (where <code>b</code> is bin width).</p> <p>Even if you construct the x bins and y bins separately (O(N)), you still have to perform some ab convolution (number of bins each way), which is close to N^2 for any dense system, and even bigger for a sparse one (well, ab >> N^2 in a sparse system.)</p> <p>Looking at the code above, you seem to have a loop in <code>grid_density()</code> which runs over the number of bins in y inside a loop of the number of bins in x, which is why you're getting O(N^2) performance (although if you are already order N, which you should plot on different numbers of elements to see, then you're just going to have to <a href="http://asserttrue.blogspot.com/2009/03/how-to-write-fast-code.html" rel="nofollow">run less code</a> per cycle).</p> <p>If you want an actual distance function then you need to start looking at contact detection algorithms.</p> <p><strong>Contact Detection</strong></p> <p>Naive contact detection algorithms come in at O(N^2) in either RAM or CPU time, but there is an algorithm, rightly or wrongly attributed to Munjiza at St. Mary's college London, which runs in linear time and RAM.</p> <p>you can read about it and implement it yourself from <a href="http://onlinelibrary.wiley.com/doi/10.1002/0470020180.fmatter/summary" rel="nofollow">his book</a>, if you like.</p> <p><strong>I have written this code myself, in fact</strong></p> <p>I have written a python-wrapped C implementation of this in 2D, which is not really ready for production (it is still single threaded, etc) but it will run in as close to O(N) as your dataset will allow. You set the "element size", which acts as a bin size (the code will call interactions on everything within <code>b</code> of another point, and sometimes between <code>b</code> and <code>2 * sqrt(2) * b</code>), give it an array (native python list) of objects with an x and y property and my C module will callback to a python function of your choice to run an interaction function for matched pairs of elements. it's designed for running contact force DEM simulations, but it will work fine on this problem too.</p> <p>As I haven't released it yet, because the other bits of the library aren't ready yet, I'll have to give you a zip of my current source but the contact detection part is solid. The code is LGPL'd.</p> <p>You'll need Cython and a c compiler to make it work, and it's only been tested and working under *nix environemnts, if you're on windows you'll need <a href="http://wiki.cython.org/InstallingOnWindows" rel="nofollow">the mingw c compiler for Cython to work at all</a>.</p> <p>Once Cython's installed, building/installing <a href="http://dl.dropbox.com/u/18178598/pynet-0.0.1.zip" rel="nofollow">pynet</a> should be a case of running setup.py.</p> <p>The function you are interested in is <code>pynet.d2.run_contact_detection(py_elements, py_interaction_function, py_simulation_parameters)</code> (and you should check out the classes Element and SimulationParameters at the same level if you want it to throw less errors - look in the file at <code>archive-root/pynet/d2/__init__.py</code> to see the class implementations, they're trivial data holders with useful constructors.)</p> <p>(I will update this answer with a public mercurial repo when the code is ready for more general release...)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload