python - 将值插入排序数组

Question

将值插入到排序的 numpy 数组中正确位置的最快方法是什么？

例如，我想将每个值插入binto a：

a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70]

b = [5,7,9,45]

我已经尝试循环遍历a每个值b并以这种方式插入它。我也试过这个bisect_left方法：

for i in b:
a.insert(bisect_left(a,i),i)

这两种方法都太慢了，因为我要处理数十万个数据元素。

有任何想法吗？

Answer 1

你可以使用searchsortedand insert：

a = numpy.array([1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70])
b = numpy.array([5,7,9,45])
ii = numpy.searchsorted(a, b)
a = numpy.insert(a, ii, b)

Answer 2

让我们注意n = len(a) and m = len(b)，

1. 您可以使用二进制搜索来查找每个元素的位置并插入它，这将在m*n*log(n)时间内完成
2. 您可以合并两个数组，这将具有 n+m 复杂度
3. 可以使用专门的结构，平衡二叉树，在python中可以找到很多实现，时间复杂度为mlog(n)

现在给定 n 和 m 的可能值，您可以确定哪个解决方案是最好的，但不要期望做得比这更好

Answer 3

只需使用内置sort方法。它实现timsort. 如果列表几乎排序，它会非常快。

a.extend(b)
a.sort()

Answer 4

对于更 Pythonic 的方法，您可以使用bisect.insort(your_list, your_value)将值插入到排序列表的正确位置。像这样：

import bisect

a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70]
b = [5,7,9,45]

for value in b:
    bisect.insort(a, value)

# Now a == [1, 1, 2, 4, 5, 7, 7, 7, 9, 11, 13, 13, 13, 15, 20, 25, 26, 27, 30, 45, 45, 70]

Answer 5

你的解决方案很慢，因为你有很多插入。每个插入都是 O(N) 复杂度。

我的解决方案：a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70] b = [5,7,9 ,45]

将 b.Length 项目插入 a 的末尾。a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70,x,x,x,x] b = [ 5,7,9,45]

拿3个指针：

1. 指向最后一个实际元素的指针（在示例中指向70的指针）
2. 指向b到最后一个元素的指针（在示例中指向45的指针）
3. 指向最后一个的指针a

这是我在 C# 中的解决方案：

    int p1 = a.Length - 1;
    int p2 = b.Length - 1;
    int p3 = a.Length + b.Length - 1;

    //Insert b.Length items to end of a.

    while (p3 >= 0 && p2 >= 0)
    {
        if (p1 < 0 || b[p2] >= a[p1])
        {
            a[p3--] = b[p2--];
        }
        else
        {
            a[p3--] = a[p1--];
        }
    }