C#中的List<char[]>是否在连续内存中分配？

Question

如果我声明一个字符数组的列表，它们是在连续的内存中分配还是.NET创建了一个链接列表？

如果它不是连续的，那么我能否声明一个连续的字符数组列表？字符数组的大小是预先知道且固定的（它们都是相同的大小）。

- David Mulder

---

我想我可以声明一个List<char>，然后手动跟踪边界。这样会存储在连续的内存中，对吧？ - David Mulder

是的，这就是我建议的。这是唯一的方法。只是好奇：你为什么需要它们连续并像一个大数组一样运行？我的想法是，与在迭代单个数组时发生的元素之间的跳跃相比，数组之间的跳跃不会太重要，因为它们很少发生。 - Ed S.

这是一门人工智能课程。非连续的数据将会影响算法的执行时间，并且会影响我的成绩 :) - David Mulder

我会经常访问char数组，性能损失可能会很明显。 - David Mulder

好的。只是看起来你会偶尔失去缓存一致性（在外部循环中），并且大部分时间保持它（内部循环）。这取决于内部数组的大小，但如果它们很大，我敢打赌不会有什么明显的影响。在使用一个大数组复杂化代码之前，我至少会测试一下。事实上，如果证明这不是问题，我会向你的老师展示性能差异。甚至可能得到额外的学分（我会给你，但我不是你的老师:D） - Ed S.

Answer 1

是的，但不是你想的那样。 List<T> 保证其元素存储在连续的位置。

数组是引用类型，因此作为List<T>保证的一样，这些引用也是相互连续存储的。但是，数组本身是单独分配的，它们存储的位置与列表无关，只涉及到元素，即引用。

如果您需要的话，应该只需使用一个大型数组并维护边界数据。

编辑：根据您的评论：

  

内部数组始终为 9 个字符。

因此，在这种情况下，缓存一致性可能成为问题，因为子数组非常小。您将在内存中来回跳跃地从一个数组到另一个数组，我只会相信您所说的代码性能敏感性。

如果可以，请使用多维数组。当然，这假定您知道大小或者可以对其施加最大大小限制。

是否有可能交换一些内存以减少复杂性/时间，并仅设置N的最大大小？使用多维数组（但不要使用后者）是您唯一能保证连续分配的方法。

第二次编辑：

试图使答案与评论同步。您说第一维的最大大小为 9！ ，并且像以前一样，第二维的大小为 9。

一次性分配所有内容。您正在交换一些内存以获取时间。9！*9*2/1024/1024 == 约 6.22MB。

如您所说，列表可能会增长到该大小，因此最坏情况下会浪费几 MB 的内存。除非您计划在烤箱中运行此代码，否则我认为这不会成为问题。只需一次性将缓冲区分配为一个数组即可。

- Ed S.

---

无论是交错数组还是多维数组更快或更慢可能取决于您的访问模式。多维数组是连续的，因此CPU可以轻松地从中预取数据。如果您的代码通过数组执行线性扫描，则我认为在多维数组上它会比在交错数组上更快（如果数组足够大）。 - user541686

@Mehrdad：是的，实际上我本来想在OP给我更多信息后删除那一部分。谢谢。 - Ed S.

Answer 2

List 函数作为一个动态数组，而不是链表，但这已经无关紧要了。在实例化之前，char[] 不会分配任何内存空间。当第一次创建时，List 仅负责保存对 char[] 的引用，其中不包含任何 char[]。

如果它不是连续的，我是否可以声明一个连续的 char 数组列表？char 数组的大小是提前知道且固定的（它们都是相同的大小）。

不行，但是如果您也知道将有多少个 char 数组，则可以实例化 二维数组：

char[,] array = new char[x, y];

- Paul Bellora

---

如果数据类型是引用，我认为List会创建一个链表？ - David Mulder

@David：不是的。List<T>具有数组的语义，而不是链表。例如，您可以对其进行索引。如果索引的时间复杂度为O(n)（如链表），那将是一个令人讨厌的技巧。 - Ed S.