0

在我的项目中，我正在使用用户决定长度的对象数组（object []）。在应用程序的过程中，它也至少每秒循环数百次。这个数组还有一个与之关联的类，它确保对它的任何添加都将使用一个为每个占用的元素设置一个位的数组来填充第一个空缺点。一旦分配的数组条目保持在原位，因为它会影响元素的跟踪以移动它们，因此可能存在间隙。可以删除或添加的元素数量是未知的。与循环访问元素相比，添加和删除发生的频率要低得多。

我需要知道的是，当循环通过这个数组时，哪个会提供更好的平均性能......

  1. 检查每个条目是否为空

或者

  1. 调用以下代码以获取循环中的下一个索引，以检查 -1 是否停止。Tracker 包含元素的按位位置。该函数只需要为每个填充元素运行一次。&= 行和下一行的减法产生最低位集的整数值。DeBruijn 序列位执行对数基数 2 以获得位位置。

    private List<Int32> Tracker = new List<Int32>();
private int EnumTemp;
private int EnumTemp2;
private int EnumResult;
private int EnumIndex = -1;
//from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
protected internal static readonly Int32[] MultiplyDeBruijnBitPosition2 =
{
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
public int NextIndex()
        {
            if (EnumIndex == -1)
            {
                EnumTemp = Tracker[0];
                EnumIndex = 0;
            }
            while (EnumTemp == 0)
            {
                if (EnumIndex == Tracker.Count -1)
                {
                    EnumIndex = -1;
                    return -1;
                }
                EnumIndex++;
                EnumTemp = Tracker[EnumIndex];
            }
            EnumTemp2 &= EnumTemp - 1;
            EnumResult = Engine.MultiplyDeBruijnBitPosition2[(UInt32)((EnumTemp-EnumTemp2) * 0x077CB531U) >> 27];
            EnumResult += (EnumIndex * 32);
            EnumTemp = EnumTemp2;
            return EnumResult;
        }
    }

    假设在这两种情况下都将访问数组元素并将其存储在临时变量中。

4

1 回答 1

0

有一点是，检查 x 空行是否为空的速度会比使用跟踪器的快步慢。您需要对差距有多大有所了解。但我的直觉表明，在这会有帮助之前，应该有相当大的间隙（比如空行是填充行的 5 倍）。至于我为什么这么认为；

  • 数组访问是按顺序且完美地预取的。因此，填充后的第一个 y 条目已经在缓存中。跳过它们不会阻止内存访问

  • 空检查非常快。与此相比，跟踪器“复杂”

  • 您的代码变得更加复杂，可能获得的收益很少。

  • 我认为在您的情况下，双向链表可能会更快，因为它根本没有间隙并且可以有效地循环。您不需要数组中的位置，因为您可以使用链接列表引用删除对象。

于 2012-09-13T08:52:03.480 回答