如何在内存中重新排序数据以优化缓存访问

本文关键字：数据 排序 优化 访问 缓存 内存 新排序 | 更新日期: 2023-09-27 18:16:07

我想对一个大数据集(类型为List<Record>)进行洗牌，然后对它进行多次迭代。通常，打乱列表只打乱引用，而不是打乱数据。由于频繁的缓存丢失，我的算法的性能受到极大的影响(3倍)。我可以对洗牌后的数据进行深度拷贝，使其适合缓存。但是，这会使内存使用量增加一倍。

是否有一种更节省内存的方法来洗牌或重新排序数据，以便洗牌后的数据是缓存友好的?

如何在内存中重新排序数据以优化缓存访问

选项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;
}
相关文章：