- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我想(高效地)找到比某个距离 max_d
更近的所有点对。我当前使用 cdist
的方法是:
import numpy as np
from scipy.spatial.distance import cdist
def close_pairs(X,max_d):
d = cdist(X,X)
I,J = (d<max_d).nonzero()
IJ = np.sort(np.vstack((I,J)), axis=0)
# remove diagonal element
IJ = IJ[:,np.diff(IJ,axis=0).ravel()<>0]
# remove duplicate
dt = np.dtype([('i',int),('j',int)])
pairs = np.unique(IJ.T.view(dtype=dt)).view(int).reshape(-1,2)
return pairs
def test():
X = np.random.rand(100,2)*20
p = close_pairs(X,2)
from matplotlib import pyplot as plt
plt.clf()
plt.plot(X[:,0],X[:,1],'.r')
plt.plot(X[p,0].T,X[p,1].T,'-b')
但我认为这是矫枉过正(而且可读性不强),因为大部分工作只是为了消除 self 距离和重复项。
我的主要问题是:有更好的方法吗?
(注意:此时输出的类型(array
, set
, ...)并不重要)
我目前的想法是使用 pdist
,它返回一个仅包含正确对的压缩距离数组。但是,一旦我从压缩距离数组中找到合适的坐标 k
,我该如何计算它等效于哪些 i,j
对?
所以另一个问题是:是否有一种简单的方法来获取相对于 pdist
输出条目的坐标对列表:
f(k)->i,j
cdist(X,X)[i,j] = pdist(X)[k]
最佳答案
根据我的经验,有两种最快的方法可以在 3D 中查找邻居列表。一种是使用用 C++ 或 Cython(在我的例子中,两者)编写的最简单的双循环代码。它以 N^2 的速度运行,但对于小型系统来说速度非常快。另一种方法是使用线性时间算法。 Scipy ckdtree 是一个不错的选择,但有局限性。来自分子动力学软件的邻居列表查找器功能最强大,但很难包装,而且初始化时间可能很慢。
下面我比较四种方法:
Scipy.spatial.ckdtree
scipy.spatial.distance.pdist
测试设置:n
点散布在体积密度为 0.2 的矩形框中。系统大小从 10 到 1000000(一百万)个粒子不等。接触半径取自 0.5, 1, 2, 4, 7, 10
。请注意,因为密度为 0.2,所以在接触半径为 0.5 时,我们平均每个粒子有大约 0.1 个接触,在 1 = 0.8、2 = 6.4 和 10 - 大约 800!对于小型系统重复多次接触查找,对于大于 30k 粒子的系统重复一次。如果每次调用的时间超过 5 秒,则运行中止。
设置:双至强 2687Wv3、128GB RAM、Ubuntu 14.04、python 2.7.11、scipy 0.16.0、numpy 1.10.1。所有代码都没有使用并行优化(OpenMM 除外,尽管并行部分执行得如此之快以至于在 CPU 图形上什至不明显,但大部分时间都花在了管道数据与 OpenMM 之间)。
结果:请注意,下面的图是对数尺度的,分布在 6 个数量级上。即使很小的视觉差异实际上也可能是 10 倍。对于少于 1000 个粒子的系统,Cython
代码总是更快。但是,1000 个粒子后的结果取决于接触半径。 pdist
的实现总是比 cython 慢,并且占用更多的内存,因为它显式地创建了一个距离矩阵,由于 sqrt 的存在,它很慢。
ckdtree
是所有系统大小的不错选择。 ckdtree
表现仅差 3-10 倍安装 OpenMM 非常棘手;您可以在 http://bitbucket.org/mirnylab/openmm-polymer 中阅读更多内容文件“contactmaps.py”或在自述文件中。然而,下面的结果表明,对于 N>100k 的粒子,每个粒子只有 5-50 个接触是有利的。
下面的 Cython 代码:
import numpy as np
cimport numpy as np
cimport cython
cdef extern from "<vector>" namespace "std":
cdef cppclass vector[T]:
cppclass iterator:
T operator*()
iterator operator++()
bint operator==(iterator)
bint operator!=(iterator)
vector()
void push_back(T&)
T& operator[](int)
T& at(int)
iterator begin()
iterator end()
np.import_array() # initialize C API to call PyArray_SimpleNewFromData
cdef public api tonumpyarray(int* data, long long size) with gil:
if not (data and size >= 0): raise ValueError
cdef np.npy_intp dims = size
#NOTE: it doesn't take ownership of `data`. You must free `data` yourself
return np.PyArray_SimpleNewFromData(1, &dims, np.NPY_INT, <void*>data)
@cython.boundscheck(False)
@cython.wraparound(False)
def contactsCython(inArray, cutoff):
inArray = np.asarray(inArray, dtype = np.float64, order = "C")
cdef int N = len(inArray)
cdef np.ndarray[np.double_t, ndim = 2] data = inArray
cdef int j,i
cdef double curdist
cdef double cutoff2 = cutoff * cutoff # IMPORTANT to avoid slow sqrt calculation
cdef vector[int] contacts1
cdef vector[int] contacts2
for i in range(N):
for j in range(i+1, N):
curdist = (data[i,0] - data[j,0]) **2 +(data[i,1] - data[j,1]) **2 + (data[i,2] - data[j,2]) **2
if curdist < cutoff2:
contacts1.push_back(i)
contacts2.push_back(j)
cdef int M = len(contacts1)
cdef np.ndarray[np.int32_t, ndim = 2] contacts = np.zeros((M,2), dtype = np.int32)
for i in range(M):
contacts[i,0] = contacts1[i]
contacts[i,1] = contacts2[i]
return contacts
Cython 代码的编译(或生成文件):
cython --cplus fastContacts.pyx
g++ -g -march=native -Ofast -fpic -c fastContacts.cpp -o fastContacts.o `python-config --includes`
g++ -g -march=native -Ofast -shared -o fastContacts.so fastContacts.o `python-config --libs`
测试代码:
from __future__ import print_function, division
import signal
import time
from contextlib import contextmanager
import matplotlib
import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial import ckdtree
from scipy.spatial.distance import pdist
from contactmaps import giveContactsOpenMM # remove this unless you have OpenMM and openmm-polymer libraries installed
from fastContacts import contactsCython
class TimeoutException(Exception): pass
@contextmanager
def time_limit(seconds):
def signal_handler(signum, frame):
raise TimeoutException("Timed out!")
signal.signal(signal.SIGALRM, signal_handler)
signal.alarm(seconds)
try:
yield
finally:
signal.alarm(0)
matplotlib.rcParams.update({'font.size': 8})
def close_pairs_ckdtree(X, max_d):
tree = ckdtree.cKDTree(X)
pairs = tree.query_pairs(max_d)
return np.array(list(pairs))
def condensed_to_pair_indices(n, k):
x = n - (4. * n ** 2 - 4 * n - 8 * k + 1) ** .5 / 2 - .5
i = x.astype(int)
j = k + i * (i + 3 - 2 * n) / 2 + 1
return np.array([i, j]).T
def close_pairs_pdist(X, max_d):
d = pdist(X)
k = (d < max_d).nonzero()[0]
return condensed_to_pair_indices(X.shape[0], k)
a = np.random.random((100, 3)) * 3 # test set
methods = {"cython": contactsCython, "ckdtree": close_pairs_ckdtree, "OpenMM": giveContactsOpenMM,
"pdist": close_pairs_pdist}
# checking that each method gives the same value
allUniqueInds = []
for ind, method in methods.items():
contacts = method(a, 1)
uniqueInds = contacts[:, 0] + 100 * contacts[:, 1] # unique index of each contacts
allUniqueInds.append(np.sort(uniqueInds)) # adding sorted unique conatcts
for j in allUniqueInds:
assert np.allclose(j, allUniqueInds[0])
# now actually doing testing
repeats = [30,30,30, 30, 30, 20, 20, 10, 5, 3, 2 , 1, 1, 1]
sizes = [10,30,100, 200, 300, 500, 1000, 2000, 3000, 10000, 30000, 100000, 300000, 1000000]
systems = [[np.random.random((n, 3)) * ((n / 0.2) ** 0.333333) for k in range(repeat)] for n, repeat in
zip(sizes, repeats)]
for j, radius in enumerate([0.5, 1, 2, 4, 7, 10]):
plt.subplot(2, 3, j + 1)
plt.title("Radius = {0}; {1:.2f} cont per particle".format(radius, 0.2 * (4 / 3 * np.pi * radius ** 3)))
times = {i: [] for i in methods}
for name, method in methods.items():
for n, system, repeat in zip(sizes, systems, repeats):
if name == "pdist" and n > 30000:
break # memory issues
st = time.time()
try:
with time_limit(5 * repeat):
for ind in range(repeat):
k = len(method(system[ind], radius))
except:
print("Run aborted")
break
end = time.time()
mytime = (end - st) / repeat
times[name].append((n, mytime))
print("{0} radius={1} n={2} time={3} repeat={4} contPerParticle={5}".format(name, radius, n, mytime,repeat, 2 * k / n))
for name in sorted(times.keys()):
plt.plot(*zip(*times[name]), label=name)
plt.xscale("log")
plt.yscale("log")
plt.xlabel("System size")
plt.ylabel("Time (seconds)")
plt.legend(loc=0)
plt.show()
关于python - 找到比给定的最大距离更近的所有点对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21285058/
我有一个功能是转换 ADO Recordset 进入html: class function RecordsetToHtml(const rs: _Recordset): WideString; 该函
经过几天的研究和讨论,我想出了这种方法来收集访客的熵(你可以看到我的研究历史here) 当用户访问时,我运行此代码: $entropy=sha1(microtime().$pepper.$_SERVE
给定一个无序列表 List ,我需要查找是否存在 String与提供的字符串匹配。 所以,我循环 for (String k : keys) { if (Utils.keysM
我已经搜索过这个问题,但没有找到我正在寻找的答案。 基本上,我想将类构造函数包装在 try/except 子句中,以便它忽略构造函数内特定类型的错误(但无论如何都会记录并打印它们)。我发现做到这一点的
我有一组三个数字,我想将一组数字与另一组数字进行比较。即,第一组中的每个数字小于另一组中的至少一个数字。需要注意的是,第一组中的下一个数字必须小于第二组中的不同数字(即,{6,1,6} 对 {8,8,
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题吗? Update the question所以它是on-topic用于堆栈溢出。 关闭 9 年前。 Improve this
首先介绍一下背景: 我正在开发一个带有 EJB 模块和应用程序客户端模块的企业应用程序 (ear)。我还使用 hibernate JPA 来实现持久性,并使用 swingx 来实现 GUI。这些是唯一
我正在尝试在我的上网本上运行 Eclipse 以便能够为 Android 进行开发。 您可能已经猜到了,Eclipse 非常慢,并且不容易有效地开发。 我正在使用 Linux Ubuntu 并且我还有
for row, instrument in enumerate(instruments): for col, value in enumerate(instrument):
return not a and not b ^ 我如何以更好的格式表达它 最佳答案 DeMorgan's Law , 也许? return not (a or b) 我认为在这一点上已经足够简单了
我正在尝试让 Font Awesome 图标看起来更 slim https://jsfiddle.net/cliffeee/7L6ehw9r/1/ . 我尝试使用“-webkit-text-strok
假设我有一个名为 vals 的数据框,如下所示: id…………日期…………min_date…… .........最大日期 1…………2016/01/01…………2017/01/01…………2018/
是否有更 Pythonic 的方式来做到这一点?: if self.name2info[name]['prereqs'] is None: se
我有一个函数可以将一些文本打印到它接收到的 ostream&。如果 ostream 以终端为目标,我想让它适应终端宽度,否则默认为某个值。 我现在做的是: 从 ostream 中获取一个 ofstre
这个问题在这里已经有了答案: Should a retrieval method return 'null' or throw an exception when it can't produce
我有这个 bc = 'off' if c.page == 'blog': bc = 'on' print(bc) 有没有更 Pythonic(和/或更短)的方式在 Python 中编写? 最佳
输入:一个包含 50,000 行的 CSV;每行包含 910 列值 0/1。 输出:运行我的 CNN 的数据框。 我编写了一个逐行读取 CSV 的代码。对于每一行,我将数据分成两部分,称为神经元(90
据我所知,with block 会在您退出 block 后自动调用 close(),并且它通常用于确保不会忘记关闭一个文件。 好像没有技术上的区别 with open(file, 'r+') as f
我有一个使用 Entity Framework V6.1.1 的 MVC 5 网站。 Entity Framework DbContext 类和模型最初都在网站项目中。这个项目有 3 个 DbCont
我是编程新手,在尝试通过将 tableView 和关联 View 的创建移动到单独的类并将委托(delegate)和数据源从 VC 移动到单独的类来精简我的 ViewController 时遇到了一些
我是一名优秀的程序员,十分优秀!