zhjxaoini's Blog

发表于 分类于

此数据结构的正确名字为前向星，为了与链式前向星区别，本文中将其称为数组前向星。

数组前向星是一个特殊的边集数组。将边按照起点排序，那么每个点的所有出边都存储在一个区间中，记下区间的范围即可。排序方式使用计数排序，时间复杂度为线性。

其同时具备 vector 和链式前向星的优点，既能保证遍历时内存访问连续，又不需要动态分配内存。

阅读全文 »

发表于 分类于

以下代码中，mul1 是行向量乘矩阵，mul2 是矩阵乘列向量。

可以看出，两段代码的内存访问都是连续的，那为什么 mul2 会比 mul1 慢 3 倍？

1
2
3
4
5
6
7
8
9
10
11
12
using Vector = int[MAXN];
using Matrix = int[MAXN][MAXN];
void mul1(int n, const Vector& a, const Matrix& b, Vector& ans) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans[j] = (ans[j] + (long long)a[i] * b[i][j]) % MOD;
}
void mul2(int n, const Matrix& a, const Vector& b, Vector& ans) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans[i] = (ans[i] + (long long)a[i][j] * b[j]) % MOD;
}
阅读全文 »