将值插入已排序数组

Question

什么是向已排序的numpy数组中快速插入值的最快方式？

例如，我想将b的每个值插入到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]

我尝试了通过对每个b的值循环遍历a来插入数据，还尝试使用bisect_left方法：

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

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

有什么好的想法吗？

- user2957178

---

使用更高效的数据结构，如二叉搜索树，肯定会使事情变得更快。插入操作的时间复杂度为O(log n)，而不是O(n)。 - Hunter McMillen

如果 b 已经排序，则可以使用归并排序的 合并 部分：合并已排序数组的算法。 - Ashwini Chaudhary

Answer 1

你可以使用 searchsorted 和 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)

- Ill-Conditioned Matrix

Answer 2

只需使用内置的 sort 方法。它实现了timsort 。如果列表已经接近排序，那么它会非常快。

a.extend(b)
a.sort()

- thefourtheye

---

你的解决方案是O(NlogN)，但可能可以做到O(N)。 - Толя

Answer 3

让我们看一下 n = len(a) and m = len(b)

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

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

- Samy Arous

---

我同意使用二叉搜索树，这里使用结构体将简化并加快插入操作。 - physincubus

Answer 4

如果您想更多地使用Python的方式，您可以使用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]

- farzin vatani

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]

使用三个指针：

1. 指向 a 中最后一个实际元素的指针（在本例中指向 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--];
        }
    }

- Толя

---

如果每个插入操作的时间复杂度为O(N)，那么总的时间复杂度就是O(N^2)。 - thefourtheye

我的解决方案没有插入，只有一个批量插入到开头来预留数组的位置。 - Толя

这是一个关于Python的问题。 - rerx