19

给定两个排序数组，如下所示：

a = array([1,2,4,5,6,8,9])

b = array([3,4,7,10])

我希望输出为：

c = array([1,2,3,4,5,6,7,8,9,10])

或者：

c = array([1,2,3,4,4,5,6,7,8,9,10])

我知道我可以执行以下操作：

c = unique(concatenate((a,b))

我只是想知道是否有更快的方法来做到这一点，因为我正在处理的数组有数百万个元素。

欢迎任何想法。谢谢

4

8 回答 8

31

由于您使用 numpy，我怀疑 bisec 是否对您有帮助……因此，我建议做两件事：

  1. 不要使用np.sort, 使用方法c.sort()来对数组进行就地排序并避免复制。
  2. np.unique必须使用np.sort哪个不到位。因此，不要使用np.unique手动执行逻辑。IE。首先排序（就地）然后np.unique手动执行该方法（还要检查它的python代码），flag = np.concatenate(([True], ar[1:] != ar[:-1]))使用 which unique = ar[flag]（对 ar 进行排序）。为了更好一点，您可能应该自行进行标志操作，即。flag = np.ones(len(ar), dtype=bool)然后np.not_equal(ar[1:], ar[:-1], out=flag[1:])基本上避免了flag.
  3. 我不确定这一点。但是.sort有 3 种不同的算法，因为您的数组可能几乎已经排序，更改排序方法可能会产生速度差异。

这将使完整的东西接近你所得到的（没有事先做一个独特的）：

def insort(a, b, kind='mergesort'):
    # took mergesort as it seemed a tiny bit faster for my sorted large array try.
    c = np.concatenate((a, b)) # we still need to do this unfortunatly.
    c.sort(kind=kind)
    flag = np.ones(len(c), dtype=bool)
    np.not_equal(c[1:], c[:-1], out=flag[1:])
    return c[flag]
于 2012-09-14T15:30:34.787 回答
12

将元素插入到 an 的中间array是一个非常低效的操作，因为它们在内存中是平坦的，因此每当您插入另一个元素时，您都需要将所有内容都移动。因此，您可能不想使用bisect. 这样做的复杂性大约是 O(N^2).

您当前的方法是O(n*log(n))，因此要好得多，但并不完美。

将所有元素插入哈希表（例如 a set）是一件事情。uniquify需要一些O(N)时间，但是你需要排序哪一个需要O(n*log(n)). 还是不太好。

真正的O(N)解决方案涉及分配一个数组，然后通过获取输入列表的最小头部来一次填充一个元素，即。合并。不幸的是numpy，Python 似乎都没有这样的东西。解决方案可能是在 Cython 中编写一个。

它看起来很模糊，如下所示：

def foo(numpy.ndarray[int, ndim=1] out,
        numpy.ndarray[int, ndim=1] in1, 
        numpy.ndarray[int, ndim=1] in2):

        cdef int i = 0
        cdef int j = 0
        cdef int k = 0
        while (i!=len(in1)) or (j!=len(in2)):
            # set out[k] to smaller of in[i] or in[j]
            # increment k
            # increment one of i or j
于 2012-09-14T15:41:47.800 回答
9

当对时间感到好奇时，最好只是timeit. 下面，我列出了各种方法的一个子集及其时间：

import numpy as np
import timeit
import heapq



def insort(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo, np.insert(a, lo, [x])

size=10000
a = np.array(range(size))
b = np.array(range(size))

def op(a,b):
    return np.unique(np.concatenate((a,b)))

def martijn(a,b):
    c = np.copy(a)
    lo = 0
    for i in b:
        lo, c = insort(c, i, lo)
    return c

def martijn2(a,b):
    c = np.zeros(len(a) + len(b), a.dtype)
    for i, v in enumerate(heapq.merge(a, b)):
        c[i] = v

def larsmans(a,b):
    return np.array(sorted(set(a) | set(b)))

def larsmans_mod(a,b):
    return np.array(set.union(set(a),b))


def sebastian(a, b, kind='mergesort'):
    # took mergesort as it seemed a tiny bit faster for my sorted large array try.
    c = np.concatenate((a, b)) # we still need to do this unfortunatly.
    c.sort(kind=kind)
    flag = np.ones(len(c), dtype=bool)
    np.not_equal(c[1:], c[:-1], out=flag[1:])
    return c[flag]

结果：

martijn2     25.1079499722
OP       1.44831800461
larsmans     9.91507601738
larsmans_mod     5.87612199783
sebastian    3.50475311279e-05

我在这里的具体贡献是larsmans_mod避免创建 2 个集合——它只创建 1 个，这样做可以将执行时间减少近一半。

编辑被删除martijn，因为它太慢而无法竞争。还测试了稍大的数组（排序）输入。我也没有测试输出的正确性......

于 2012-09-14T15:34:28.827 回答
4

除了关于 using 的其他答案bisect.insort，如果您对性能不满意，您可以尝试使用blistmodule with bisect。它应该提高性能。

传统的list 插入复杂度是O(n)，而插入blist的复杂度是O(log(n))。

此外，您的数组似乎已排序。如果是这样，您可以使用mudule 中的merge函数heapq来利用两个数组都已预先排序的事实。由于在内存中创建了一个新数组，因此这种方法会产生开销。这可能是一个考虑的选项，因为这个解决方案的时间复杂度是O(n+m)，而具有 insort 的解决方案是O(n*m)复杂的（n 个元素 * m 个插入）

import heapq

a = [1,2,4,5,6,8,9]
b = [3,4,7,10]


it = heapq.merge(a,b) #iterator consisting of merged elements of a and b
L = list(it) #list made of it
print(L)

输出：

[1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10]

如果要删除重复值，可以使用groupby：

import heapq
import itertools

a = [1,2,4,5,6,8,9]
b = [3,4,7,10]


it = heapq.merge(a,b) #iterator consisting of merged elements of a and b
it = (k for k,v in itertools.groupby(it))
L = list(it) #list made of it
print(L)

输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
于 2012-09-14T15:14:19.133 回答
2

您可以使用该bisect模块进行此类合并，将第二个 python 列表合并到第一个。

这些bisect*函数适用于 numpy 数组，但insort*函数不适用。使用模块源代码来调整算法很容易，它非常基础：

from numpy import array, copy, insert

def insort(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo, insert(a, lo, [x])

a = array([1,2,4,5,6,8,9])
b = array([3,4,7,10])

c = copy(a)
lo = 0
for i in b:
    lo, c = insort(c, i, lo)

并不是说自定义insort真的在这里添加了任何东西，默认bisect.bisect也可以正常工作：

import bisect

c = copy(a)
lo = 0
for i in b:
    lo = bisect.bisect(c, i)
    c = insert(c, i, lo)

使用这种改编insort比组合和排序更有效。因为b也是排序的，所以我们可以跟踪lo插入点并从那里开始搜索下一个点，而不是在每个循环中考虑整个数组。

如果您不需要保存a，只需直接对该数组进行操作并保存副本即可。

更高效：因为两个列表都是排序的，我们可以使用heapq.merge：

from numpy import zeros
import heapq

c = zeros(len(a) + len(b), a.dtype)
for i, v in enumerate(heapq.merge(a, b)):
    c[i] = v
于 2012-09-14T15:06:30.613 回答
1

为此使用该bisect模块：

import bisect

a = array([1,2,4,5,6,8,9])
b = array([3,4,7,10])

for i in b:
    pos = bisect.bisect(a, i)
    insert(a,[pos],i)

我现在无法测试这个，但它应该可以工作

于 2012-09-14T15:10:12.457 回答
1

sortednp包实现了排序后的 numpy数组的有效合并，只是对值进行排序，而不是使它们唯一：

import numpy as np
import sortednp
a = np.array([1,2,4,5,6,8,9])
b = np.array([3,4,7,10])
c = sortednp.merge(a, b)

我测量了时间并将它们在这个答案中与一个类似的帖子进行了比较，其中它优于 numpy 的合并排序（v1.17.4）。

于 2020-05-22T20:29:00.600 回答
0

似乎没有人提到union1d（union1d）。目前，它是 的快捷方式unique(concatenate((ar1, ar2)))，但它是一个要记住的短名称，并且它有可能被 numpy 开发人员优化，因为它是一个库函数。insort它的性能与seberg 接受的大型数组答案非常相似。这是我的基准：

import numpy as np

def insort(a, b, kind='mergesort'):
    # took mergesort as it seemed a tiny bit faster for my sorted large array try.
    c = np.concatenate((a, b))  # we still need to do this unfortunatly.
    c.sort(kind=kind)
    flag = np.ones(len(c), dtype=bool)
    np.not_equal(c[1:], c[:-1], out=flag[1:])
    return c[flag]

size = int(1e7)
a = np.random.randint(np.iinfo(np.int).min, np.iinfo(np.int).max, size)
b = np.random.randint(np.iinfo(np.int).min, np.iinfo(np.int).max, size)

np.testing.assert_array_equal(insort(a, b), np.union1d(a, b))

import timeit
repetitions = 20
print("insort: %.5fs" % (timeit.timeit("insort(a, b)", "from __main__ import a, b, insort", number=repetitions)/repetitions,))
print("union1d: %.5fs" % (timeit.timeit("np.union1d(a, b)", "from __main__ import a, b; import numpy as np", number=repetitions)/repetitions,))

我机器上的输出：

insort: 1.69962s
union1d: 1.66338s
于 2017-08-28T17:44:23.287 回答