标签: localityofreference

for(int i = 0; i<100; i++)

    for(int j = 0; j<100; j++)

         array[j][i] = 0;
         // array[i][j] = 0;

我的教授说,第一种方式初始化二维数组要比第二种方式要昂贵得多.有人可以解释引擎盖下面发生了什么事情吗？或者,这两种初始化方法是否具有相同的性能？

假设我们有一个未排序的数组和链表.搜索两个数据结构的元素时最糟糕的情况是O(n),但我的问题是:

由于在缓存中使用空间局部性,阵列是否仍然会更快,或者缓存是否会使用分支局部性,从而允许链接列表与任何阵列一样快？

我对数组的理解是,如果访问一个元素,那么该存储器块和许多周围的块将被带入高速缓存,从而允许更快的存储器访问.

我对链表的理解是,由于遍历列表所采用的路径是可预测的,因此缓存将利用它并仍然存储适当的内存块,即使列表中的节点在堆内可能相距很远.

分区功能是否可以快速排序其参考位置？如果有,怎么样？

我的意思是,在快速排序中,与其他算法(如合并排序或堆排序)相比,它的位置是什么？

我也看了

"快速排序中的分区步骤通常具有出色的局部性,因为它可以访问前后靠近的连续数组元素".

我不明白 ？

假设我有一个C++类,其实现看起来像这样:

// ...

MyClass::iterativeFunction() {
     for (int i = 0; i < 1000000; i++) {
          performAction(i);
     }
}

MyClass::performAction(int index) {
     // Block of code (non-inline-able)
}

// ...

在C++级别,我是否可以控制这些方法的空间局部性,或者我是否只是希望编译器会注意到相关方法并相应地优化其程序集？理想情况下,我希望它们彼此相邻,以便将它们一起加载到指令缓存中,但我不知道如何让编译器知道我真的希望这种情况发生.

根据我的理解,空间位置与附近未来使用的附近记忆有关.但是我想知道循环是否多次执行,这是否会导致良好的空间局部性？提前谢谢,对不起,如果我很难理解的话.