从阵列中删除，镜像(奇怪)行为

本文关键字：奇怪 行为 镜像 阵列 删除 | 更新日期: 2023-09-27 18:20:40

标题可能看起来有点奇怪，因为我不知道如何用一句话来描述它。

对于"算法"课程，我们必须对一些东西进行微观优化，其中之一是找出从数组中删除的工作原理。赋值是从数组中删除一些东西，并重新对齐内容，这样就没有间隙了，我认为这与std:：vector:：erase在c++中的工作方式非常相似。

因为我喜欢理解所有低级事物的想法，所以我走得更远，尝试用我的解决方案。这带来了一些奇怪的结果。

首先，这里有一个我使用的小代码：

class Test {
    Stopwatch sw;
    Obj[] objs;
    public Test() {
        this.sw = new Stopwatch();
        this.objs = new Obj[1000000];
        // Fill objs
        for (int i = 0; i < objs.Length; i++) {
            objs[i] = new Obj(i);
        }
    }
    public void test() {
        // Time deletion
        sw.Restart();
        deleteValue(400000, objs);
        sw.Stop();
        // Show timings
        Console.WriteLine(sw.Elapsed);
    }
    // Delete function
    // value is the to-search-for item in the list of objects
    private static void deleteValue(int value, Obj[] list) {
        for (int i = 0; i < list.Length; i++) {
            if (list[i].Value == value) {
                for (int j = i; j < list.Length - 1; j++) {
                    list[j] = list[j + 1];
                    //if (list[j + 1] == null) {
                    //    break;
                    //}
                }
                list[list.Length - 1] = null;
                break;
            }
        }
    }
}

我只需要创建这个类并调用test（）方法。我做了25次循环。

我的发现：

  • 第一轮比其他24轮要长得多，我认为这是因为缓存，但我不确定
  • 当我使用列表开头的值时，它必须在内存中移动比我使用末尾的值更多的项目，尽管它似乎仍然需要更少的时间
  • 工作时间差别很大
  • 当我启用注释的if时，即使我搜索的值几乎在列表的末尾，性能也会提高（10-20%）（这意味着if会关闭很多次，但实际上并没有用处）

我不知道为什么会发生这些事情，有人能解释（其中的一些）吗？也许如果有人看到这个专业人士，我在哪里可以找到更多信息来以最有效的方式做到这一点？

测试后编辑：

我做了一些测试，发现了一些有趣的结果。我在一个大小为一百万个项目的数组上运行测试，其中填充了一百万个对象。我运行了25次，并以毫秒为单位报告累积时间。我这样做了10次，并将其平均值作为最终值。

当我用上面描述的函数运行测试时，我得到的分数为：362,1

当我用dbc的答案运行它时，我得到的分数是：846,4

所以我的速度更快，但后来我开始用半空的空数组进行实验，事情开始变得奇怪。为了消除不可避免的nullPointerExceptions，我对if添加了一个额外的检查（认为这会破坏更多的性能），如下所示：

if (fromItem != null && fromItem.Value != value)
    list[to++] = fromItem;

这似乎不仅有效，而且大大提高了性能！现在我得到的分数是：247,9

奇怪的是，分数似乎很低，但有时会飙升，这是我从中获得的平均值：94、26、966、36、632、95、47、35、109、439

因此，尽管做了额外的检查，但额外的评估似乎提高了我的表现。这怎么可能？

从阵列中删除，镜像(奇怪)行为

您正在使用Stopwatch为方法计时。这将计算方法调用期间所用的时钟总时间，其中可能包括.Net初始JIT方法所需的时间、垃圾收集的中断或其他进程的系统负载导致的速度减慢。由于缓存未命中，来自这些源的噪声可能会主导噪声。

这个答案给出了一些建议，说明如何最大限度地减少垃圾收集或其他过程中的一些噪音。为了消除JIT干扰，您应该在不计时的情况下调用一次方法，或者在结果表的单独列中显示第一次调用所花费的时间，因为它会非常不同。您还可以考虑使用适当的探查器，该探查器将准确报告您的代码使用了多少时间，不包括来自其他线程或进程的"噪声"。

最后，我要注意的是，从数组中删除匹配项并向下移动其他项的算法使用了嵌套循环，这是不必要的，并且将在匹配索引之后访问数组中的项两次。标准算法如下：

    public static void RemoveFromArray(this Obj[] array, int value)
    {
        int to = 0;
        for (int from = 0; from < array.Length; from++)
        {
            var fromItem = array[from];
            if (fromItem.Value != value)
                array[to++] = fromItem;
        }
        for (; to < array.Length; to++)
        {
            array[to] = default(Obj);
        }
    }

然而，您可以在您的版本中使用Array.RemoveAt()，而不是使用标准算法，因为（我相信）它在内部执行非托管代码中的删除操作。

相关文章：