sortednp 0.2.1

numpy和numpy数组是一个非常好的工具。但是，相交和 合并多个排序的numpy数组的性能要差得多。当前的数字 实现将两个数组连接起来并对组合进行排序。如果你 想要合并或交叉多个numpy数组，有一种更快的方法， 通过使用属性，对结果数组进行排序。

sortednp（sorted numpy）对已排序的numpy数组进行操作，以计算 两个numpy数组的交集或并集。这个 结果数组还是一个已排序的numpy数组，可以合并或 与下一个数组相交。预期的用例是已排序的numpy 数组按基本数据结构排序，并合并或相交于 请求。典型的应用包括信息检索和搜索引擎 尤其是。

也可以实现K向合并或相交算法， 它同时操作任意数量的数组。这个包裹 用于处理具有$10^6$或$10^{10}$项的数组。通常，这些 数组太大，无法将其中两个以上的数组同时保存在内存中 时间。这个包实现了合并和交叉多个数组的方法， 可按需加载。

安装

有两种不同的安装方法sortednp

使用pip（推荐）

您可以使用pip（这里是pip3）直接从pypi安装包。有 预编译的控制盘用于Linux32位和64位。

$ pip3 install sortednp

使用设置工具

或者，您可以克隆git存储库并运行 设置脚本。

$ git clone https://gitlab.sauerburger.com/frank/sortednp.git
$ cd sortednp
$ python3 setup.py install

numpy依赖性

安装在某些情况下会失败，因为构建时依赖于 麻木的通常，可以通过手动安装最近的numpy来解决这个问题。 版本通过pip3 install-u numpy

用法

这个包提供了两种不同的方法。头等舱 在两个阵列上操作。第二类操作两个或多个数组，并且 在内部调用第一类方法。

双向方法

两个numpy排序的数组可以用merge方法合并，该方法需要两个 numpy数组并返回两个数组的排序并集。

# merge.pyimportnumpyasnpimportsortednpassnpa=np.array([0,3,4,6,7])b=np.array([1,2,3,5,7,9])m=snp.merge(a,b)print(m)

如果运行此命令，则应将两个数组的并集看作一个排序的numpy 数组，

$python3merge.py[01233456779]

两个已排序的numpy数组可以与intersect方法相交，该方法需要两个 numpy数组并返回两个数组的排序交集。

# intersect.pyimportnumpyasnpimportsortednpassnpa=np.array([0,3,4,6,7])b=np.array([1,2,3,5,7,9])i=snp.intersect(a,b)print(i)

如果运行此命令，则应将两个数组的交集视为已排序的numpy 数组，

$python3intersect.py[37]

返回数组索引

intersect方法接受一个可选参数索引它是false 默认情况下。如果设置为true，则返回值由 交叉数组和一个二者都有公共值索引的元组 数组，

# intersect_indices.pyimportnumpyasnpimportsortednpassnpa=np.array([2,4,6,8,10])b=np.array([1,2,3,4])intersection,indices=snp.intersect(a,b,indices=True)print(intersection)print(indices)

以上示例给出：

$python3intersect_indices.py[24](array([0,1]),array([1,3]))

第一行显示两个数组的交集。第二行 打印包含索引的元组，其中公共值出现在输入中 数组。例如，值4位于数组a中的位置1和位置 3在数组中b

K-路方法

类似地，k-way intersect和merge方法采用两个或多个数组 对其参数执行合并或相交操作。

# kway_intersect.pyimportnumpyasnpimportsortednpassnpa=np.array([0,3,4,6,7])b=np.array([0,3,5,7,9])c=np.array([1,2,3,5,7,9])d=np.array([2,3,6,7,8])i=snp.kway_intersect(a,b,c,d)print(i)

如果运行此命令，则应将所有四个数组的交集视为已排序的numpy 数组，

$ pip3 install sortednp

0

k-way合并sortednp.kway_merge的工作原理类似。然而，本地人 numpy实现比这个包提供的合并更快。 为了完整起见，增加了k-way合并。Ppackageheapq提供 同时合并多个数组的有效方法。

方法kway_merge和kway_intersect接受可选关键字 参数假定已排序。默认情况下，它设置为true。如果设置为false， 在执行操作之前，该方法对输入数组调用sort（）。 如果数组已经排序以节省时间，则应保留默认值 对数组进行排序。

因为数组可能太大，无法将它们全部保存在内存中 时间，可以将可调用的而不是数组传递给方法。 可调用的应该返回实际数组。它被立即调用 在需要数组之前。这样可以减少内存消耗。

算法

通过迭代两个数组来计算交点。对于中的给定元素 一个数组，方法需要搜索另一个数组并检查元素是否 包含的。为了提高效率，我们可以使用 数组被排序。有三种搜索方法，可以通过 可选关键字参数算法

• sortednp.simple_search：通过在 按元素排列元素。 更多信息
• sortednp.binary_search：将数组的其余部分切成两半，然后 在包含搜索元素的切片上重复该过程。 更多信息
• sortednp.gallowing_search：首先，线性搜索元素，加倍 每一步后的步长。如果步骤超出了搜索元素， 在最后两个位置之间执行二进制搜索。 更多信息

默认为sortednp.galloping_search。三个人的表现 算法将在下一节中进行比较。

性能

包的性能可以与默认实现进行比较 numpy的intersect1d方法。sortednp和numpy之间的执行时间比率是 用于各种不同的基准测试。

在两种不同的假设下，可以估计合并或相交时间。如果 合并或相交的数组已经排序，不应该 考虑一下对基准中的随机数组进行排序所需的时间。上 另一方面，如果考虑数组未排序的情况，则 应考虑到分拣时间。

相交

交叉口操作的性能取决于 两个数组。例如，如果其中一个数组的第一个元素较大 与其他数组中的所有元素相比，只需搜索另一个数组 （线性、二元或指数）。同样，如果公共元素是 在数组中相隔甚远（稀疏性），可以跳过数组的大块。 基准中的数组包含随机（唯一）整数。稀疏是 定义为一个数组中两个连续元素之间的平均差。

第一组测试研究性能对 数组。第二组测试研究了对 数组，

假设已排序数组

下表总结了忽略时与numpy相比的性能 对初始数组排序所需的时间。

<表>测试 简单搜索 二进制搜索 快速搜索 相交 交集稀疏性 <表>

包括排序时间

下表总结了与numpy相比的性能 对初始数组进行排序所需的时间。

<表>测试 简单搜索 二进制搜索 快速搜索 相交 交集稀疏性 <表>

合并

<表>假定已排序 包括排序时间

标签：

方法

numpy

元素

排序

np

数组

array

交叉

intersect

欢迎加入QQ群-->： 979659372

推荐PyPI第三方库

• jonDevMeDisx

  非常基本的计算器

• apachebookkeeperclient

  防止漏洞攻击的软件包

• calendarweek

  在Python和Django中使用日历周的实用工具

• units-converter

  波单元转换器

• stoicheia

  未提供项目说明

• vupload

  用于VMware InitiateFileTransferToGuest的CLI工具

• Maxis_EA_Messenger_Client

  Messenger_客户端

• python-pype-lang-3

  pype的版本3是一种python集成函数式编程语言，它为常见的函数式编程任务（如映射、reduce、过滤器、条件语句、字典操作和列表操作）提供了易于使用的伪宏。。

• BayesianOptimization

  贝叶斯优化

• ImageNetwork

  创建用于分析的N维二进制图像网络。

• vvm-distributions

  高斯分布

• image-filter-tjr

  图像的简单自动阈值化

• site-auditor

  现场审核员

• TOPSIS-NAMAN-BANSAL-101803202

  TOPSIS的Python包。

• aiotcloud

  Ver1.2.1 修复repl导入了socket超时