cache friendly

(Updated: )
(3 mins to read)

尽量减少cache miss保证时空局部性，尽量连续地访存，使用局部变量使用指针访问可以加快速度（仅限于卡常）

1
2
int *st = a + 1, *ed = a + n + 1;
while(st!=ed) work(*(st++));
  • 对树进行树链剖分后，子树是一个连续的区间，树上的路径也可以被划分成log段连续区间。然后利用数据结构对这些连续区间进行操作即可。但是有些时候数据结构这块不好写，或者常数很大，比如说需要$O(n\sqrt n \logn)$来维护$10^5$个节点的操作，这时候我们可以直接对所有连续段for循环暴力$O(n^2)$维护，然后注意访问的连续性，这样cache的miss率是log级别的，通过pragma等预编译命令加速会有不错的效果
1
2
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

该方法可以用于树上dp，如果是子树dp的话直接利用dfs序即可如果是到根的树链上dp，那就先树剖，然后对每个点把到根的路径化成log个连续段，然后暴力我们用一个局部变量存储需要更新的dp[u]，然后用来更新的dp[v]就是连续访存的，可以达到一定的加速效果，用指针可以略微加速

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void updt(int u, int x, int y)
{
  ll cur = LLONG_MAX, a = dep[u], b = p[u];
  while(top[x]!=top[y])
  {
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    ll *p=tmpdep+dfn[top[x]]-1, *q = dp+dfn[top[x]]-1, *ped = tmpdep + dfn[x];
    while(p!=ped) chk(cur, *(++q)+(a-*(++p)*b));
    x = fa[0][top[x]];
  }
  if(dep[x]>dep[y]) swap(x,y);
  ll *p=tmpdep+dfn[x]-1, *ped = tmpdep+dfn[y], *q = dp+dfn[x] - 1;
  while(p!=ped) chk(cur, *(++q)+(a-*(++p)*b));
  dp[dfn[u]] = cur + q[u];
}

经过测试$10^5$次的数据级别2.5s能出结果，这在一些时限比较宽松，正解复杂度要多个log或者根号的情况下可能可以骗过去，而$2\times 10^5$就是10s左右才能出结果了。

  • 点分治的时候我们要处理跨越重心的各部分的贡献，这需要双指针或者一些数据结构来维护，同样的我们把它们映射到连续的数组段上，在进行暴力也会有一定加速