pykdtree 1.3.13

目标

pykdtree是Python中用于快速最近邻搜索的kd-tree实现。目标是成为在常见用例（低维数和低邻居数）中围绕树构建和查询最快实现的之一。

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

接口类似于scipy.spatial.cKDTree，除了只支持欧几里得距离度量。

查询可选项使用OpenMP多线程。

安装

Pykdtree可以通过pip安装

pip install pykdtree

或者，如果在一个基于conda的环境中，可以使用conda从conda-forge频道安装

conda install -c conda-forge pykdtree

注意，默认情况下，这些软件包（PyPI上的二进制车轮和conda-forge上的二进制软件包）仅针对Linux平台构建了OpenMP。要尝试带有OpenMP支持的源代码构建，请

export USE_OMP="probe"
pip install --no-binary pykdtree pykdtree

在某些没有安装OpenMP的系统上可能无法正常工作。请参阅以下开发说明以获取更多指导。通过在上面的命令中将USE_OMP设置为"0"可以禁用OpenMP。

开发安装

如果您想为pykdtree做出贡献，那么从源代码安装是一个好主意，这样您可以快速看到您的更改效果。默认情况下，pykdtree在类Unix系统上使用OpenMP启用的查询进行构建。在Linux上，这通过libgomp实现。在OSX系统上，OpenMP通过clang编译器提供（conda环境使用单独的编译器）。

$ cd <pykdtree_dir>
$ pip install -e .

这会将pykdtree安装在“可编辑”模式下，当运行新的Python解释器实例时，Python文件的变化将自动反映出来（例如，运行使用pykdtree的Python脚本）。它不会自动重新构建或重新编译pykdtree中的.mako模板和.pyx Cython代码。编辑这些文件需要运行pykdtree/render_template.py脚本，然后重新运行上面的pip命令来重新编译Cython文件。

如果安装失败，出现未定义的编译器标志或您想使用其他OpenMP实现，您可能需要修改setup.py或指定额外的pip命令行标志以匹配系统上的库位置。

不使用OpenMP支持的控制由USE_OMP环境变量控制

$ cd <pykdtree_dir>
$ export USE_OMP=0
$ pip install -e .

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

$ USE_OMP=0 sudo -E pip install -e .

用法

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树的内存开销。pykdtree使用默认的leafsize=16。增加leafsize将减少内存开销和构建时间，但会增加查询时间。

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上的编译器）中不可用。为了解决这个问题，可以将头文件下载并放置在正确的“include”目录中。这可以通过将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的environment部分添加以下内容来关闭此功能

环境

全局

# 因为AppVeyor的编译器不支持OpenMP，所以不要使用OpenMP构建 USE_OMP: “0”