(C++)Leetcode:为什么我的代码比示例顶级解决方案慢得多?(547.省份数量)

Question

https://leetcode.com/problems/number-of-provinces/

当我第一次尝试就解决了这个问题时，我非常兴奋，只花了20/30分钟，尽管当我提交代码时，我的成绩是8.43%。我研究了最快的解决方案是如何解决这个问题的，结果发现，顶部的示例解决方案与我的代码几乎相同，但运行速度快了3倍。我一直在比较代码，但无法真正指出足够大的差异。两者都应该同样快。。。有人能解释一下原因吗？如果我没有记错的话，这两种情况都是O(mn(性能。

以下是我的代码。这是非常不言自明的，所以不确定大量的评论会有什么好处。

class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int components = 0;
vector<bool> visited (isConnected.size(), false);

// go through each row
for (int i = 0; i < isConnected.size(); i++) {
// explore only unvisited items
if (!visited[i]) {
queue<int> q;

q.push(i);
components++;

while (!q.empty()) {
int node = q.front();
q.pop();
visited[node] = true;

// push all direct connections onto the queue so we explore them
for (int j = 0; j < isConnected[0].size(); j++) {
if (isConnected[node][j] == 1 && !visited[j]) {
q.push(j);
}
}
}
}
}

return components;
}
};

下面是一个运行速度比我的代码快3倍的顶级解决方案示例。

class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
if (M.empty()) {
return 0;
}
int count = 0;
vector<bool> visited(M.size());
auto bfs = [&](int student) {
queue<int> q;
q.push(student);
visited[student] = true;

while (!q.empty()) {
auto current = q.front();
cout << "current " << current << endl;
q.pop();

for (int i = 0; i < M.size(); i++) {
if (M[current][i] == 1 and !visited[i]) {
visited[i] = true;
q.push(i);
}
}
}
};
for (int r = 0; r < M.size(); r++) {
if (visited[r] == false) {
count++;
bfs(r);
}
}
return count;
}
};

Answer 1

就我所见，差异在于visited[i] = true;的位置，这会减少每次迭代的内存访问。OP代码需要重新获取布尔的位置。

之间可能存在数据或控制流相关性

visited[node] = true;

和

!visited[j]

这在最佳代码中不存在。

OP码内环

.L118:
mov     rax, QWORD PTR [rsi+rbx]
cmp     DWORD PTR [rax+rcx*4], 1
jne     .L116
mov     rax, rbp
mov     r8, rcx
sal     rax, cl
mov     rcx, QWORD PTR [rsp+80]
shr     r8, 6
and     rax, QWORD PTR [rcx+r8*8]
jne     .L116
mov     rax, QWORD PTR [rsp+192]
sub     rax, 4
cmp     rdi, rax
je      .L117

"最佳"；代码

.L76:
mov     rax, QWORD PTR [rsi+rbx]
cmp     DWORD PTR [rax+rcx*4], 1
jne     .L74
mov     rax, QWORD PTR [r12]
mov     rsi, rcx
shr     rsi, 6
mov     rax, QWORD PTR [rax]
lea     rsi, [rax+rsi*8]
mov     eax, 1
sal     rax, cl
mov     rcx, QWORD PTR [rsi]
test    rcx, rax
jne     .L74
or      rax, rcx <------------ visited[i] = true;
mov     QWORD PTR [rsi], rax
mov     rax, QWORD PTR [rsp+96]
sub     rax, 4
cmp     r8, rax
je      .L75
mov     DWORD PTR [r8], edx
add     r8, 4
mov     QWORD PTR [rsp+80], r8
jmp     .L74

[1]: https://godbolt.org/z/obfqf7