所以转置矩阵的显而易见的方法是使用:
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ )
destination[j+i*n] = source[i+j*n];
但是我想要一些能利用局部性和缓存阻塞的东西.我正在查找它并且找不到可以执行此操作的代码,但我被告知它应该是对原始的非常简单的修改.有任何想法吗？
编辑:我有一个2000x2000矩阵,我想知道如何使用两个for循环更改代码,基本上将矩阵拆分为我单独转置的块,比如2x2块或40x40块,并查看哪个块大小最有效.
编辑2:矩阵以列主要顺序存储,即对于矩阵
a1 a2
a3 a4
存储为a1 a3 a2 a4.
给定两个排序的数字数组,我们希望找到具有第k个最大可能总和的对.(一对是第一个数组中的一个元素,第二个数组中是一个元素).例如,使用数组
具有最大总和的对是
因此,第四大总和是(13,8).如何找到具有第k个最大可能总和的对？
另外,最快的算法是什么？数组已经排序,大小为M和N.
我已经知道O(Klogk)解决方案,使用此处给出的Max-Heap .
它也是Google最喜欢的采访问题之一,他们需要一个O(k)解决方案.
我还在某处读到存在O(k)解决方案,我无法弄清楚.
有人可以用伪代码解释正确的解决方案.
PS请不要发布此链接作为答案/评论.它不包含答案.