结合两个数组和排序

Question

给出两个排序的数组,如下所示:

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))

我只是想知道是否有更快的方法来做,因为我正在处理的数组有数百万个元素.

欢迎任何想法.谢谢

Answer 1

既然你使用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]))使用哪个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]

Answer 2

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

你目前的做法是O(n*log(n)),这样做要好得多,但并不完美.

将所有元素插入哈希表(例如a set)就是一种方法.这需要花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

Answer 3

当对时间感到好奇时,总是最好的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并且这样做会将执行时间减少近一半.

EDIT已删除,martijn因为它太慢而无法参与竞争.还测试了稍微更大的数组(已排序)输入.我还没有测试输出的正确性......