numpy：如何将两个已排序的数组合并成一个更大的已排序数组？

Question

我有两个已排序的np.arrays，比如说：

1, 2, 3, 5

并且

2, 4, 6, 7

I want

1 2 2 3 4 5 6 7

不想使用Python的循环。

是否有一些NumPy函数可以实现此功能？

---

奖励：通过某个轴对矩阵执行此操作（其他轴具有相同的形状）。

- Gulzar

---

这能帮到您吗？https://dev59.com/IF4c5IYBdhLWcg3wc6Dr - adamkgray

这似乎是最快的解决方案：https://dev59.com/lWct5IYBdhLWcg3wAYzq#12427633 - adamkgray

输入数组中的数字是唯一的吗？ - Divakar

@Divakar 不是，但我愿意听取建议。 - Gulzar

Answer 1

导入sortednp，然后就可以开始了：

import numpy as np
import sortednp as s

a = np.array([1,2,3,5])
b = np.array([2,4,6,7])

m = s.merge(a, b)
print(m)

- user11422223

---

可以接受，但我更喜欢使用原生的numpy解决方案。谢谢！ - Gulzar

Answer 2

利用输入数组的排序特性，我们可以使用np.searchsorted来实现如下功能 -

def merge_sorted_arrays(a, b):
    m,n = len(a), len(b)
    # Get searchsorted indices
    idx = np.searchsorted(a,b)

    # Offset each searchsorted indices with ranged array to get new positions
    # of b in output array
    b_pos = np.arange(n) + idx

    l = m+n
    mask = np.ones(l,dtype=bool)
    out = np.empty(l,dtype=np.result_type(a,b))
    mask[b_pos] = False
    out[b_pos] = b
    out[mask] = a
    return out

示例运行（使用重复项的通用案例）-

In [52]: a
Out[52]: array([1, 2, 3, 3, 5, 9, 9, 9])

In [53]: b
Out[53]: array([ 2,  4,  6,  6,  6,  7, 10])

In [54]: merge_sorted_arrays(a, b)
Out[54]: array([ 1,  2,  2,  3,  3,  4,  5,  6,  6,  6,  7,  9,  9,  9, 10])

随机排序的1000000大小数组上的时间 -

与流行的拼接+排序方法进行基准测试。

# Setup
In [141]: np.random.seed(0)
     ...: a = np.sort(np.random.randint(0,1000000,(1000000)))
     ...: b = np.sort(np.random.randint(0,1000000,(1000000)))

# @chmod777's soln
In [142]: %%timeit
     ...: c = np.concatenate((a,b), axis=0)
     ...: c.sort()
141 ms ± 2.13 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [143]: %timeit merge_sorted_arrays(a, b)
55.1 ms ± 5.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

- Divakar

---

请问您能解释一下 ((a[idx]==b) | v) 这部分吗？我猜想它与重复有关，但无法确切地理解其逻辑。 - Gulzar

@Gulzar 简化了那部分代码并添加了注释和一些时间记录。 - Divakar

看起来你删除了那部分... 我有漏掉什么吗？ - Gulzar

@Gulzar 那部分不需要，因此已删除。 - Divakar

明确地使用归并排序，如此答案所示，大大提高了连接-排序方法的性能。我的基准测试数字：连接-排序，默认类型：137毫秒；连接-排序，归并排序类型：14.8毫秒；此答案：57.6毫秒；sortednp合并：9.65毫秒。 - Koen G.

值得注意的是，这种加速需要最近版本的numpy，并且有点依赖于数据类型，因为kind="mergesort"尽管它的名字是mergesort，但实际上并不使用mergesort，而是映射到radix sort或tim sort。 - Paul Panzer

Answer 3

numpy开发者最近实现了tim sort。由于tim sort检查预排序的子序列，因此它将以O(n)的时间复杂度对两个排序数组的串联进行排序。

目前出于某种原因不能直接选择tim sort算法，但是在某些情况下，使用参数kind="stable"会使用tim sort算法。整数类型使用基数排序，其时间复杂度也为O(n)。

在大小为10^6时，与默认的排序方法（我相信是qsort）相比，这将导致速度提高10倍。

tim sort / radix sort的性能也仅比sortednp.merge略慢。

详见官方文档https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html。

# default sort
def so():
    c = np.concatenate((a,b))
    c.sort()
    return c

# tim sort / radix sort
def ts():
    c = np.concatenate((a,b))
    c.sort(kind="stable")
    return c

from sortednp import merge

# extra library
def mg():
    return merge(a,b)

# @Divakar's example (range enlarged)
a = np.sort(np.random.randint(0,100000000,(1000000)))
b = np.sort(np.random.randint(0,100000000,(1000000)))

timeit(so,number=10)
# 1.5669178580283187
timeit(ts,number=10)
# 0.12706473504658788
timeit(mg,number=10)
# 0.12382328097010031

# for comparison @Divakar's solution
timeit(lambda:merge_sorted_arrays(a,b),number=10)
# 0.5367169310338795

# non integer example
a = np.sort(np.random.random(1000000))
b = np.sort(np.random.random(1000000))

timeit(so,number=10)
# 1.7868053679703735
timeit(ts,number=10)
# 0.17676723399199545
timeit(mg,number=10)
# 0.1376464170170948

# and @Divakar
timeit(lambda:merge_sorted_arrays(a,b),number=10)
# 0.5656043770140968

- Paul Panzer