pykdtree 1.3.5

客观的

pykdtree 是 Python 中用于快速最近邻搜索的 kd-tree 实现。目标是为树构造和查询的常见用例（低维度和低数量的邻居）提供最快的实现。

该实现基于 scipy.spatial.cKDTree 和 libANN，结合了两者的最佳特性并专注于实现效率。

该接口类似于 scipy.spatial.cKDTree 的接口，但仅支持欧几里德距离测量。

查询可选地使用 OpenMP 进行多线程处理。

安装

默认情况下，pykdtree 是使用 libgomp 使用启用了 OpenMP 的查询构建的，除了在 OSX 系统上使用 clang 编译器（conda 环境使用单独的编译器）。

$ cd <pykdtree_dir>
$ python setup.py install

如果它因未定义的编译器标志而失败，或者您想使用另一个 OpenMP 实现，请在指示点修改 setup.py 以匹配您的系统。

不支持 OpenMP 的构建由 USE_OMP 环境变量控制

$ cd <pykdtree_dir>
$ export USE_OMP=0
$ python setup.py install

注意使用 sudo 时默认情况下不会导出环境变量，因此在这种情况下，请执行

$ USE_OMP=0 sudo -E python setup.py install

Pykdtree 也可以通过 conda-forge 通道与 conda 一起安装：

$ conda install -c conda-forge pykdtree

用法

pykdtree 的用法类似于 scipy.spatial.cKDTree 所以现在参考它的文档

>>> from pykdtree.kdtree import KDTree
>>> kd_tree = KDTree(data_pts)
>>> dist, idx = kd_tree.query(query_pts, k=8)

可以使用标准 OpenMP 环境变量 OMP_NUM_THREADS 控制启用 OpenMP 的查询中使用的线程数。

用于树创建的leafsize参数（每片叶子的数据点数）可用于控制 kd-tree 的内存开销。pykdtree 使用默认的leafsize=16。增加叶子大小会减少内存开销和构建时间，但会增加查询时间。

pykdtree 接受双精度（numpy.float64）或单精度（numpy.float32）浮点数据。如果使用另一种类型的数据，则会进行双精度内部副本，从而导致内存开销。如果 kd 树是在单精度数据上构建的，则查询点也必须是单精度的。

基准

与 scipy.spatial.cKDTree 和 libANN 的比较。该基准针对具有 10053632 个数据点和 4276224 个查询点的地理空间 3D 数据。结果相对于 scipy.spatial.cKDTree 的构建时间进行索引。使用 10 的叶子大小（scipy.spatial.cKDTree 默认）。

注意：libANN不是线程安全的。在这个基准测试中，libANN 使用“-O3 -funroll-loops -ffast-math -fprefetch-loop-arrays”编译以达到最佳性能。

查看组合的构造和查询，这相对于 scipy.spatial.cKDTree 提供了以下性能改进

注意：里程会因手头的数据集和计算机架构而异。

测试

使用 pytest 运行单元测试

$ cd <pykdtree_dir>
$ pytest

在 AppVeyor 上安装

Pykdtree 需要“stdint.h”头文件，该头文件在某些​​版本的 Windows 或某些 Windows 编译器（包括持续集成平台 AppVeyor 上的编译器）上不可用。为了解决这个问题，可以下载头文件并将其放置在正确的“包含”目录中。这可以通过将anaconda/missing-headers.ps1脚本添加到您的存储库并在appveyor.yml的安装步骤中运行它来完成：

# 安装 MSVC 2008 中未包含的缺失标头 # https://github.com/omnia-md/conda-recipes/pull/524 - “powershell ./appveyor/missing-headers.ps1”

除此之外，AppVeyor 不支持 OpenMP，因此必须通过在 环境部分的appveyor.yml中添加以下内容来关闭此功能：

环境：

全球的：

# 不要使用 openmp 构建，因为它在 appveyor 的编译器中不受支持 USE_OMP: “0”

变更日志

v1.3.5：构建 Python 3.10 轮子和其他 CI 更新

v1.3.4：修复 Python 3.9 轮子不是为 linux 构建的

v1.3.3 : 添加对 python 3.9 的兼容性

v1.3.2 : 将 OSX 安装更改为不使用没有 conda 解释器的 OpenMP

v1.3.1 : 修复 1.3.0 中引入的“查询”方法中的屏蔽

v1.3.0：关键字参数“掩码”添加到“查询”方法。OpenMP 编译现在适用于 MS Visual Studio 编译器

v1.2.2：构建过程修复

v1.2.1：修复了 v1.2.0 中引入的 OpenMP 线程安全问题

v1.2.0：添加了 64 位和 32 位 MSVC Windows 支持

v1.1.1：由于 pypi 版本不正确，与 v1.1 版本相同

v1.1：构建过程改进。为 kdtree 类添加数据属性以实现 scipy 接口兼容性

v1.0：将许可证从 GPLv3 切换到 LGPLv3

v0.3 : 避免安装 egg 的压缩

v0.2：减少内存占用。现在可以在内部处理单精度数据，避免复制转换为双精度。默认叶子大小从 10 更改为 16，因为这减少了内存占用并使其成为高速缓存行倍数（如果在基准测试中观察到任何查询性能，则可以忽略不计）。减少叶节点的内存分配。在 OS X 上构建的应用补丁。

v0.1：初始版本。