-
Notifications
You must be signed in to change notification settings - Fork 13
/
README.txt
131 lines (99 loc) · 4.49 KB
/
README.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
SciPy-based kd-tree with periodic boundary conditions
Copyright 2012 Patrick Varilly.
Released under the scipy license
Rationale
---------
When running and/or analyzing molecular simulations, finding the closest
neighbors of a particles is a very common operation. Usually, Verlet lists
and/or cell lists are used for this, but these usually work well when the
maximum neighbor distance is fixed and not too large. kd-trees are the
general answer to the problem of finding nearest neighbors, and SciPy
implements kd-trees quite well. However, molecular simulations are usually
run in periodic boxes, not open boxes, so the act of finding "close"
neighbors must take the periodic boundary conditions into account.
This module implements two classes, PeriodicKDTree and PeriodicCKDTree,
that work as drop-in replacements for scipy.spatial.KDTree and
scipy.spatial.cKDTree, respectively (the latter of these is a Cython-optimized
version of a kd-tree but with more limited functionality).
For the moment, only the query and query_ball_point methods are implemented.
These should see you through most situations in analyzing molecular
simulations.
Installation
------------
The uwham package relies on NumPy and SciPy to do its work. Make sure
these are installed (for Mac OS X users, see note below). Then run the
following command inside the uwham directory:
python setup.py install --user
The query_ball_point method in PeriodicCKDTree relies on the extension to
cKDTree I recently wrote for SciPy. See
https://github.com/scipy/scipy/pull/262
Basic usage
-----------
from periodic_kdtree import PeriodicCKDTree
import numpy as np
# Boundaries (0 or negative means open boundaries in that dimension)
bounds = np.array([30.0, 30.0, -1]) # xy periodic, open along z
# Points
n = 10000
data = 30.0 * np.random.randn(n, 3)
# Build kd-tree
T = PeriodicCKDTree(bounds, data)
# Find 4 closest neighbors to a random point
# (d[j], i[j]) = distance and index of jth closest point
d, i = T.query([45.0, 10.0, 10.0], k=4)
# Find neighbors within a fixed distance of a point
neighbors = T.query_ball_point([45.0, 10.0, 10.0], r=3.0)
Tests and benchmarks
--------------------
See test_periodic_kdtree.py, benchmark.py and nonperiodic_benchmark.py
(based off of Anne M. Archibald's benchmarks)
Simple queries seem to be substantially slower for now, but ball lookups
aren't that unacceptably slower.
Sample periodic benchmarks (time in seconds)
++++++++++++++++++++++++++++++++++++++++++++
dimension 3, 10000 points
PeriodicKDTree constructed: 0.0793428
PeriodicCKDTree constructed: 0.00343394
PeriodicKDTree 1000 lookups: 14.8779
PeriodicCKDTree 1000 lookups: 1.73712
flat PeriodicCKDTree 1000 lookups: 14.2604
PeriodicKDTree 1000 ball lookups: 39.7997
PeriodicCKDTree 1000 ball lookups: 0.222894
flat PeriodicCKDTree 1000 ball lookups: 1.23763
Ball lookups agree? True
Sample nonperiodic benchmarks
+++++++++++++++++++++++++++++
dimension 3, 10000 points
KDTree constructed: 0.0820239
cKDTree constructed: 0.00158691
KDTree 1000 lookups: 0.561787
cKDTree 1000 lookups: 0.00447702
flat cKDTree 1000 lookups: 0.335597
KDTree 1000 ball lookups: 5.60061
cKDTree 1000 ball lookups: 0.0196991
flat cKDTree 1000 ball lookups: 0.336687
Ball lookups agree? True
Installation in OS X
--------------------
In Mac OS X, the usual automatic downloading of dependencies during a
python setup.py install isn't able to successfully install NumPy and SciPy
(in my machine, it's the lack of a Fortran compiler, but the SciPy docs
point to other potential problems). So you have to download and install
NumPy and SciPy manually.
The good news: binaries are easily available
The bad news: they only work with the version of Python from
http://www.python.org, not the version that ships with OS X!
So you have to download and install three things:
1. Python 2.7.2 from http://www.python.org/download
2. Latest version of NumPy from http://numpy.org
3. Latest version of SciPy from http://scipy.org
This is far less painful than it sounds. In my own case, the disk images
that I ended up downloading were:
1. python-2.7.2-macosx10.6.dmg
2. numpy-1.6.1-py2.7-python.org-macosx10.6.dmg
3. scipy-0.10.0-py2.7-python.org-macosx10.6.dmg
CAREFUL: for some of these packages, the "link to the latest version" that
SourceForge suggests may be incorrect! Do look at the full list of downloads
available and pick the one that is most appropriate to your own setup
Once you've installed python2.7, numpy and scipy, you can run the command
python setup.py install --user