问如何对内存中的数据进行重新排序以优化缓存访问？

EN

选项1：

使Record成为struct，这样List<Record>就可以在内存中保存连续的数据。

然后直接对其排序，或者(如果记录很大)不直接对列表排序，而是生成一个索引数组(最初只有{0, 1, ..., n - 1})，然后通过让比较器比较索引所引用的元素来对索引进行排序。最后，如果您需要排序的数组，可以通过查看索引来按随机排列的顺序复制元素。

请注意，这可能比直接对结构排序更不适合缓存，但至少它是一次遍历数据，因此它更有可能更快，这取决于结构的大小。如果结构很大，就无法避免这种情况，所以如果不确定Record是否很大，就必须尝试这两种方法，看看直接对记录进行排序是否更有效。

如果您不能更改类型，那么您唯一的解决方案就是以某种方式使它们在内存中连续。要做到这一点，唯一现实的方法是执行初始垃圾收集，然后按顺序分配它们，并祈祷运行时会连续分配它们。如果你不能让它成为一个struct，我想不出还有什么其他的方法可以工作。

如果您认为在中间运行另一个垃圾收集可能会打乱顺序，您可以尝试创建第二个GCHandle数组，其中包含对这些对象的固定引用。我不推荐这样做，但这可能是您目前唯一的解决方案。

选项2：

你真的使用整个记录进行排序吗？这不太可能。如果不是，那么只需提取每条记录中相关的部分，对它们进行排序，然后重新洗牌原始数据。

对你来说，最好不要接触这个列表。相反，您可以为list创建一个访问器方法。首先，按随机顺序创建n个元素的数组，例如类似于var arr = [2, 5, .., n-1, 0];的数组

然后创建一个访问方法：

Record get(List<Record> list, int i) {
    return list[arr[i]];
}

通过这样做，列表保持不变，但您在每个索引上都会得到一个随机记录。

编辑:创建随机数组：

int[] arr = new int[n];

// Fill the array with values 1 to n;
for (int i = 0; i < arr.Length; i++)
    arr[i] = i + 1;

// Switch pairs of values for unbiased uniform random distribution:
Random rnd = new Random();
for (int i = 0; i < arr.Length - 1; i++) {
    int j = rnd.Next(i, arr.Length);
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}