在排序数组中查找插入点比 O(n) 更快？

Question

这是为了游戏编程。假设我有一个单位可以在其范围内跟踪 10 个敌人。每个敌人的优先级在 0-100 之间。所以数组目前看起来像这样（数字代表优先级）：

Enemy - 96
Enemy - 78
Enemy - 77
Enemy - 73
Enemy - 61
Enemy - 49
Enemy - 42
Enemy - 36
Enemy - 22
Enemy - 17

假设一个新的敌人在范围内徘徊并且优先级为 69，这将被插入 73 和 61 之间，并且 17 将被移除数组（好吧，我相信 17 会在插入之前被删除）。

有什么方法可以在不进行 O(n) 操作的情况下将其插入 73 和 61 之间？

Answer 1

由于您一直在维护一个排序的搜索池，因此您可以使用二进制搜索。首先检查中间元素，然后检查中间元素和数组中较近的一端之间的元素，依此类推，直到找到位置。这会给你 O(log₂n) 时间。

Answer 2

我觉得你问错了问题。您必须先找到要插入的位置，然后再插入元素。这是两个捆绑在一起的操作，我觉得你不应该问如何在没有另一个的情况下找到更快地完成一个的位置。为什么在问题的最后是有道理的。但我正在解决实际插入速度更快的问题。

简答：否

你会从一个对自己来说太聪明的人那里得到答案：

实现此目的的唯一方法是不使用数组。在数组中，除非您插入第一个或最后一个权限，否则插入将是 O(n)。这是因为数组由在内存中占据连续 space 的元素组成。这就是您能够在 O(1) 时间内引用特定元素的方式，您确切地知道该元素在哪里。代价是在中间插入你需要移动数组中一半的元素。因此，虽然您可以在 log(n) 时间内使用二进制搜索进行查找，但您无法在该时间内插入。

因此，如果您要做任何事情，您将需要不同的数据结构。一个简单的二叉树可能是它将在 log(n) 时间内完成插入的解决方案。另一方面，如果你给它提供一个排序数组，你必须担心树的平衡，所以你可能不需要红黑树。或者，如果您总是弹出最近或最远的元素，那么您可以使用堆排序。堆排序是优先级队列的最佳算法。它还有一个额外的优势，即在数组中拟合树结构，因此它具有更好的空间局部性（稍后会详细介绍）。

真相：

你很可能在附近最多有十几个或几十个敌人。在那个级别，渐近性能并不重要，因为它是专门为 'n' 的大值设计的。您看到的是对您的 CS 201 教授关于 Big Oh 的呼吁的虔诚遵守。线性搜索和插入将是最快的方法，而它能否扩展的答案是，谁在乎呢。如果你试图实现一个复杂的算法来扩展它，你几乎总是会变慢，因为决定你速度的不是软件，而是硬件，你最好坚持做硬件知道如何做的事情处理得好："linearly going down memory"。事实上，在预取器完成它们的工作之后，即使有几千个元素，线性遍历每个元素也会比实现红黑树更快。因为像树这样的数据结构会在整个地方分配内存，而不考虑空间局部性。为节点分配更多内存的调用本身比读取一千个元素所花费的时间更昂贵。这就是显卡到处使用插入排序的原因。

堆排序

堆排序实际上可能更快，具体取决于输入数据，因为它使用的是线性数组，尽管它可能会混淆预取器，因此很难说。唯一的限制是您只能弹出最高优先级的元素。显然，您可以将最高优先级定义为最低或最大的元素。堆排序太花哨了，我无法在这里尝试描述它，只是 Google 它。它确实将插入和删除分为两个 O(log(n)) 操作。堆排序最大的缺点是会严重降低代码的可调试性。堆不是排序的数组，它有一个顺序，但除了堆排序是一个复杂的非直观算法之外，如果堆设置正确，它对人类来说显然是不可见的。因此，在最好的情况下，您会引入更多错误，但收效甚微。该死，上次我不得不进行堆排序时，我复制了它的代码，但其中有错误。

二分查找插入排序

这就是您想要做的事情。事实上，这是一个非常糟糕的主意。平均而言，插入排序需要 O(n)。我们知道这是将随机元素插入排序数组的硬性限制。是的，我们可以通过使用二分查找更快地找到我们想要插入的元素。但是平均插入仍然需要 O(n)。或者，在最好的情况下，如果您正在插入并且元素进入最后一个位置，则插入排序需要 O(1) 时间，因为当您插入时，它已经在正确的位置。但是，如果您进行二进制搜索来查找插入位置，那么找出您应该插入到最后一个位置需要 O(log(n)) 时间。插入本身需要 O(1) 时间。因此，在尝试对其进行优化时，您已经严重降低了最佳情况下的性能。查看您的用例，此队列包含敌人的优先级。敌人的优先级可能取决于他们的力量和距离。这意味着当敌人进入优先级队列时，它的优先级很可能很低。这非常适合插入 O(1) 性能的最佳情况。如果降低最佳案例性能，弊大于利，因为它也是最一般的案例。

Preoptimization is the root of all evil -- Donald Knuth

Answer 3

当然，假设您使用数组类型来存放列表，这真的很容易。

我假设 Enemy 是您的 class 名称，并且有一个名为 Priority 的属性来执行排序。我们需要一个如下所示的 IComparer<Enemy>：

public class EnemyComparer : IComparer<Enemy>
{
    int IComparer<Enemy>.Compare(Enemy x, Enemy y)
    {
        return y.Priority.CompareTo(x.Priority); // reverse operand to invert ordering
    }
}

那么我们可以写一个简单的InsertEnemy例程如下：

public static bool InsertEnemy(Enemy[] enemies, Enemy newEnemy)
{
    // binary search in O(logN)
    var ix = Array.BinarySearch(enemies, newEnemy, new EnemyComparer());
    // If not found, the bit-wise compliment is the insertion index
    if (ix < 0)
        ix = ~ix;
    // If the insertion index is after the list we bail out...
    if (ix >= enemies.Length)
        return false;// Insert is after last item...
    //Move enemies down the list to make room for the insertion...
    if (ix + 1 < enemies.Length)
        Array.ConstrainedCopy(enemies, ix, enemies, ix + 1, enemies.Length - (ix + 1));
    //Now insert the newEnemy into the position
    enemies[ix] = newEnemy;
    return true;
}

还有其他数据结构可以使它更快一些，但事实证明这应该足够有效。如果列表变大，B 树或二叉树就可以了，但是对于 10 个项目，它会更快是值得怀疑的。

通过添加以下内容对上述方法进行了测试：

public class Enemy
{
    public int Priority;
}

public static void Main()
{
    var rand = new Random();
    // Start with a sorted list of 10
    var enemies = Enumerable.Range(0, 10).Select(i => new Enemy() {Priority = rand.Next(0, 100)}).OrderBy(e => e.Priority).ToArray();
    // Insert random entries
    for (int i = 0; i < 100; i++)
        InsertEnemy(enemies, new Enemy() {Priority = rand.Next(100)});
}

在排序数组中查找插入点比 O(n) 更快？

Finding insertion points in a sorted array faster than O(n)?

c#

arrays

performance

insert