增大和缩小列表<int>与大尺寸布尔值 使用索引作为值的数组

Question

我无法确定使用大量bool数组的增长和缩小列表是否对我的应用程序更有效。

为了扩展这种比较和实际情况，以下是我相信我有的每个选项的示例：

选项1（列表）：

public List<int> list = new List<int>();
while (true) { // game loop
    list.Add(Random.Range(0-300));
    list.Add(Random.Range(0-300));
    ...  // maximum of 10 of these can happen
    if (list.Contains(42)) { // roughly 10 - 50 of these checks can be true
        list.Remove(42);
    }
}

选项2（数组）：

bool[] arr = new bool[300];
while (true) { // game loop
    arr[Random.Range(0-300)] = true;
    arr[Random.Range(0-300)] = true;
    ... // maximum of 10 of these can happen
    for (int i = 0; i < 300; i++) {
        if (arr[i]) { // roughly 10 - 50 of these checks can be true
            arr[i] = false;
        }
    }
}

从本质上讲，我的问题是：

在什么时候.Contains检查变得比每个可能的元素上的for循环更昂贵（基于我的范围）？

？

重要

这不是列表与数组问题。由于条件检查，数据类型很重要。因此，这是一个特定的整数列表，而不是布尔数组比较，因为这两个选项可以给我相同的结果。

Answer 1

我会说数组实现将更快。除了调用List.Add(T)或List.Remove(T)时内部调整数组的成本外，如果您检查列表实现代码。您会注意到List.Contains(T)和List.Remove(T)都使用IndexOf(T)，我相信在内部通过列表进行循环/迭代。在您的示例中，您想在10-50次大约10-50次调用List.Contains(T)和List.Remove(T)。这最多意味着您将花费您20（包含 删除），但是在最坏的情况下，您将花费您 (N * 50) + N，其中n是列表中的项目数。

有了这些信息，我可以得出结论，如果您的列表增长，则性能会更糟。

如果您要更多地研究性能，也许值得一看HashSet数据结构。在look up和remove操作中，它的性能要比List。

Answer 2

这是在数组vs列表上的有趣文章，

https://codeblog.jonskeet.uk/2009/01/29/for-vs-foreach-on-arays-arays-and-list/

根据文章，性能是这样的：

============ int[] ============
For                 1.00
ForHoistLength      2.03
ForEach             1.36
IEnumerableForEach 15.22
Enumerable.Sum     15.73
============ List<int> ============
For                 2.82
ForHoistLength      3.49
ForEach             4.78
IEnumerableForEach 25.71
Enumerable.Sum     26.03

可以像int阵列一样量化结果，以使循环的速度快2.8倍。如果您知道数组的大小及其固定的大小，请使用数组，else列表。

这是另一个链接：数组的性能与列表

，此外，请远离LINQ以获取大数据，并使用/for/foreach循环。