导言
ASCYLIB (with OPTIK) is a concurrent data-structure library. It contains over 40 implementations of linked lists, hash tables, skip lists, binary search trees (BSTs), queues, priority queues, and stacks. ASCYLIB contains sequential, lock-based, and lock-free implementations for each data structure.
侧重于测量方法的研究， 给出了并发存储的测量方法和尺度。
在 APC 中， 周期是存储活动周期 (memory active cycle)， 不是通用的 CPU 周期，所以 APC 也叫 APMAC（ 存储活动周期平均访问数， access per memory active cycle）。
同时 APC 采用重叠 (overlapping) 的访存时间统计方法 ： 在有两个或多个存储访 问同时进行时， 周期只增加一次。
HPLinpack benchmark input file
Innovative Computing Laboratory, University of Tennessee
HPL.out output file name (if any) 输出文件名
6 device out (6=stdout,7=stderr,file)
1 # of problems sizes (N) = sqrt((Memory Size in Gbytes * 1024 * 1024 * 1024) /8) * ratio
11136 Ns 矩阵规模
1 # of NBs block sizes (64~512)In the [96,104,112,120,128, …, 256] range; the multiple of 64
96 NBs 矩阵分块方法
0 PMAP process mapping (0=Row-,1=Column-major) 选择处理器阵列是按列的排列方式还是按行的排列方式。
1 # of process grids (P x Q)
2 Ps # two-dimensional block-cyclic data distribution = amount of processes; P≤Q
2 Qs 二维处理器网格（P×Q）
16.0 threshold 阈值
1 # of panel fact # 后面是L分解的方式
2 PFACTs (0=left, 1=Crout, 2=Right)
1 # of recursive stopping criterium
4 NBMINs (>= 1)
1 # of panels in recursion
2 NDIVs
1 # of recursive panel fact.
1 RFACTs (0=left, 1=Crout, 2=Right)
1 # of broadcast
1 BCASTs (0=1rg,1=1rM,2=2rg,3=2rM,4=Lng,5=LnM)
1 # of lookahead depth
1 DEPTHs (>=0)
2 SWAP (0=bin-exch,1=long,2=mix)
64 swapping threshold
0 L1 in (0=transposed,1=no-transposed) form
0 U in (0=transposed,1=no-transposed) form
1 Equilibration (0=no,1=yes)
8 memory alignment in double (> 0)
#include <iostream>
using namespace std;
int main(void)
{
int a, b;
while (cin >> a >> b) { }// 读到EOF结束
while (cin) { // 读到EOF结束
char ch = cin.get() //读取一个字符
}
return 0;
}
其余处理
//接受一个/多个字符
char ch;
ch=cin.get(); //或者cin.get(ch);
char a[20];
cin.get(a,20); //可以接收空格
//getline() // 接受一行字符串，可以接收空格并输出
string str;
getline(cin,str); // #include<string>
````
### cout输出处理
```c++
#include <iomanip>
// 也可以使用 #include <bits/stdc++.h>
int main(void){
int a = 255;
cout << hex << a << endl;//以十六进制的形式输出
cout << dec << a << endl;//以十进制的形式输出
cout << oct << a << endl;//以八进制的形式输出
//结果分别是ff 255 377
return 0;
}
int main(void){
double x = 3.141592658;
//控制输出的宽度，就是printf("%10d");
cout << setw(10) << x << endl;
//限制输出有效数字的个数是5
cout << setprecision(5) << x << endl;
//fixed表示控制小数点后面的数字，两个连用就是小数点后面保留三位小数
cout << fixed << setprecision(3) << x << endl;
//输出结果分别是 3.14159 3.1416 3.142
return 0;
}
sum[0]=0,设置sum[i]=A[0]+...A[i-1])O(nlogn) 快排 10^5元素AddressSanitizer: stack-overflow on address 0x7ffe1ea87fc8 (pc 0x00000034e77b bp 0x7ffe1ea88060 sp 0x7ffe1ea87fc0 T0)min与max的两行都写成min了*(1/2)不是*0.5是*0int direction[8][2] = {{2,1}, {2,-1}, {-2,1}, {-2,-1}, {1,2}, {1,-2}, {-1,2}, {-1,-2}};个人最爱写法
int maxR = *max_element(inputList.begin(), inputList.end());
int left = 0, right = maxR;
// 该方法的问题：默认right是不满足的，需要提前额外判断
if(available(right)) return right;
while(left + 1 < right) {
//由于无论是从left，right相差1、2、3、……开始
//最终都会经过 left+1=right的阶段
int mid = left + ((right-left)>>1); // 注意括号 >> 优先级最低
long long tmpCntSum = 0;
for(auto &x: inputList){
tmpCntSum += (x>mid)? mid : x;
}
if(tmpCntSum <= cnt){
left = mid; // while结束时 left 满足 其tmpCntSum <= cnt
}else{
right = mid; // while结束时 right 满足 其tmpCntSum > cnt
}
}
//求 满足求和不大于cnt 的最大值：left
return left;
其他写法
int dirs[4][2] = {1,0,-1,0,0,1,0,-1};
auto check = [&](int x, int y){
return x >= 0 && y >= 0 && x < n && y < m;
};
for(auto &[addx, addy]: dirs){
int nextx = x + addx;
int nexty = y + addy;
if(!check(nextx, nexty)) continue;
……
}
stack<int> stk;
while (head) {
while (!stk.empty() && stk.top() <= head->val)
stk.pop(); // 保持从底到top单减
stk.push(head->val); // 每个元素要加入
head = head->next;
}
//vector 也行
vector<pair<int, int>> st; // 当前行的单调栈
for (int j = n - 1; j >= 0; --j) {
while (!st.empty() && mn <= st.back().first)
st.pop_back();
st.emplace_back(mn, j);
}
iota构建用于排序的索引数组[aɪ’otə]这个名称是从APL编程语言借鉴过来的。iota(id, id + n, 0); sort(id, id + n, [&heights](const auto &i, const auto &j) {return heights[i] > heights[j];}); 注意[&heights]的lambda表达式引用。1 <= forceField.length <= 100 , 暴力所有矩形四角是错误的，反例两矩阵组成十字架形状++map_cnt[x]pair<int,int>str[i] = tolower(str[i]);//把大写全部转为小写c++
string str="how are you";
transform(str.begin(),str.end(),str.begin(),::toupper);O(n^2)，官方对字符串进行滚动哈希预处理变成O(n)j++, 不一定是j+k+1。s[i+k]<s[j+k]时，s[j+1~j+k]内可能有更大子字符串，如cacacb字符串，比较caca与cacb时，后者有更大字串cb。s[i+k]<s[j+k]时，跳过了以 s[i,..,i+k] 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 s[j,..,j+k] 为起始位置的后缀子串（由于s[i+k]<s[j+k]）。s[i,..,i+k] < s[j,..,j+k]，这时j = max(j + 1, i + k + 1);s[i+k]>s[j+k]时, 以s[i] > s[i+1,..,i+k] > s[j,..,j+k], 这时j=j+k+1vector<vector<int>> g;g = vector<vector<int>>(n, vector<int>(n, INT_MAX / 2));g[e[0]][e[1]] = e[2]; // e[2]权重vector<vector<pair<int, int>>> m_adj;m_adj[edge[0]].emplace_back(edge[1], edge[2]); // edge[2]权重,unordered_set<int> nes[n];g[edge[0]].insert(edge[1]); g[edge[1]].insert(edge[0]);vector<vector<int>> g(n);g[edge[0]].push_back(edge[1]); g[edge[1]].push_back(edge[0]);vector<vector<int>> g(n);queue<pair<int,int>>x如果有邻居y已经被遍历到，环大小为该层最小dist[x]+dist[y]+1find x for min(dis[x]) in V(N)或者int x = min_element(dis, dis + N) - dis;for (int y = 0; y < n; ++y) dis[y] = min(dis[y], dis[x] + g[x][y]); // g为邻接矩阵O(nm)（Bellman-Ford 算法，适用于有负权图）或 O(m * log m)（Dijkstra 算法，适用于无负权图）。O(n+m)。S 装着所有入度为 0 的点（一般是队列，如果题目要求字典序之类，可以换成最大堆/最小堆实现的优先队列），拓扑排序结果L 是一个空列表。(u, v)，若将该边删除后点 v 的入度变为 0，则将 v 放入 S 中。S 为空。检查图中是否存在任何边，如果有，那么这个图一定有环路，否则返回 L，L 中顶点的顺序就是拓扑排序的结果。unordered_set<int> nes[n];nes[i].size() == 1， 删除叶子节点可能会导致新的叶子产生需要queue保存循环处理dig[i],只有节点满足依赖才能入队继续BFS)k^1000。动态规划大约1000*kswap(tmp,cur_queue)耗时。O(logn)，次数k，每节点时间复杂度O(klongn)O(k/2 *long(n/2))uf[x] = y;记录每个起始地址x，已经处理到地址y，也就是跳过了x~y的区域。O(1)f[0]=1nums[j]<nums[i]的最大的已有序列，通过维护辅助数据M[n]存储长度为i的末尾元素的最小值。return *max_element(dp.begin(), dp.end());O(n^3)：\(\(f(i,j) = max[\max_{k\in [0,i-1]}f(k,j),0]+1, \textbf{if}\ a[i]-a[k]=j\)\)a[i]-j对应的最后一个indexd=a[i]-a[k], 更新没处理的f(i,d)j。f(-1,x)=0return [max(dfs(n,j) for j in range(J))dfs(i,j) 表示从前 i 个集合中选择一些集合，并集包含 j（题目限制需要），至少需要选择的集合个数。dfs(i,j)=dfs(i−1,j delete set[i])+1j==0，限制已经满足了，dfs==0f[i][j] 表示用前 i 种字符构造长为 j 的序列的方案数。选k个字符进行放置。k &= k - 1 {x}，即 1 << x。((A >> x) & 1) == 1。A | B。110 | 11 = 111。A & ~B。110 & ~11 = 100。U={0,1,⋯ ,n−1}，即 (1 << n) - 1。k &= k - 1 dp[j][1]=max[max(dp[j-1][0]+x,x),max(dp[j-1][1]+nums[j],nums[j])]10^5, 当时就完全不打算排序s[0]=0c++
int s[n + 1];
s[0] = 0;
partial_sum(nums.begin(), nums.end(), s + 1); // 计算 nums 的前缀和max（∣a−x∣+∣b−y∣−∣a−b∣−∣x−y∣)2×(c−b)
left和right最大的最小值转换成不超过mid的限制(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。a[p]如果和a[q]一组，q = p + nx - ky ,要满足(p + nx) mod k = q。a[q]=a[p+nx+ky]=a[p+gcd(n,k)],q与p的值差gcd(n,k)就在一组gcd(n,k)的结果分组-x时，其结果为modx的相反数i * i <= nbool is_prime(int n) {
for (int i = 2; i * i <= n; ++i)
if (n % i == 0)
return false;
return n >= 2; // 1 不是质数
}
存储质数和非质数的版本：
const int MX = 1e5;
bool np[MX + 1]; // 质数=false 非质数=true
int init = []() {
np[1] = true; // 1 不是质数
for (int i = 2; i * i <= MX; i++) {
if (!np[i]) {
for (int j = i * i; j <= MX; j += i) {
np[j] = true;
}
}
}
return 0;
}();
质数push2vector：
const int MX = 1e6;
vector<int> primes; // 建议一个vector，一个数组
bool np[MX + 1]; // 默认是0
int init = []() {
for (int i = 2; i <= MX; i++) { // 不能是 i*i
if (!np[i]) {
primes.push_back(i); // 预处理质数列表, 写在里面，不能是 i*i
// for (int j = i; j <= MX / i; j++) // 避免int溢出的写法
// np[i * j] = true; //deny后续元素, i*i 开始
// or
for(int j = i*i; j <= MX; j+=i){
np[j] = true;
}
}
}
return 0;
}();
vector<int> generatePrimes(int n) {
vector<bool> isPrime(n + 1, true);
vector<int> primes;
for (int p = 2; p * p <= n; ++p) { // 使用了 i*i，素数要额外push
if (isPrime[p]) {
// primes.push_back(p);
for (int i = p * p; i <= n; i += p) { // 新排除的是新质数的倍数
isPrime[i] = false;
}
}
}
for (int p = 2; p <= n; ++p) {
if (isPrime[p]) {
primes.push_back(p);
}
}
return primes;
}
基于费马小定理的O(log n)的伪素数判断方法。但是机试一般不会考。
gcd(a,b)=gcd(b,a mod b), 大数除以小数得到余数，对三个数中的两小数重复，直到出现整除，较小数为最大公约数。gcd(a,b)=gcd(b,a - b), 大数减小数得到C，对三个数中的两小数重复，直到出现相等，即为最大公约数。ans = lcm(a, b, c) = lcm(lcm(a, b), c),或者ans = tmp/gcd(tmp,c)*c先除后乘防止溢出。其中tmp=lcm(a,b)或者递归。
a[i] * n^iT=(-n)*p+kT=(-n)*(p+1)+(k+n)。余数+n变正数，商++vector<int> int2array(long long num){
const int k = -2;
vector<int> result;
while(num){
if(num > 0 || num%k==0){
// num%k 余数 大于等于0
result.push_back(num%k);
num /= k;
}else{
result.push_back(num%k-k);
num = num/k + 1;
}
}
reverse(result.begin(), result.end());
if(result.size()==0){return {0};}
return result;
}
(-a)/b==-(a/b)a%b=c中c的符号与a相同C++ 除法推导7%(-4) (-7)%4 (-7)%(-4) 三种情况可知暂无
做了30天的leetcode，发现不会的还是不会。我就知道我
学而不思则罔
脑中一团浆糊，虽然学习了一些常见题型的框架、解法以及例题。
但是遇到新题目，是否能使用这些方法，以及如何转换使用还是没考虑清楚。
许多思路来自：灵茶山艾府
how to design a graph when pr executing memory access jump data-array very random?
暂无
暂无
上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。
https://zhuanlan.zhihu.com/p/137561088
GUPS (Giga十亿 UPdates per Second) is a measurement that profiles the memory architecture of a system and is a measure of performance similar to MFLOPS.
The HPCS HPCchallenge RandomAccess benchmark is intended to exercise the GUPS capability of a system, much like the LINPACK benchmark is intended to exercise the MFLOPS capability of a computer. In each case, we would expect these benchmarks to achieve close to the "peak" capability of the memory system. The extent of the similarities between RandomAccess and LINPACK are limited to both benchmarks attempting to calculate a peak system capability.
GUPS is calculated by identifying the number of memory locations that can be randomly updated in one second, divided by 1 billion (1e9).
Select the memory size to be the power of two such that 2^n <= 1/2 of the total memory. Each CPU operates on its own address stream, and the single table may be distributed among nodes. The distribution of memory to nodes is left to the implementer. A uniform data distribution may help balance the workload, while non-uniform data distributions may simplify the calculations that identify processor location by eliminating the requirement for integer divides. A small (less than 1%) percentage of missed updates are permitted.
official web or from GitHub
暂无
暂无
上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。
无
将一件事情分成若干阶段，然后通过阶段之间的转移达到目标。由于转移的方向通常是多个，因此这个时候就需要决策选择具体哪一个转移方向。
动态规划所要解决的事情通常是完成一个具体的目标，而这个目标往往是最优解。并且：
每个阶段抽象为状态（用圆圈来表示），状态之间可能会发生转化（用箭头表示）。可以画出类似如下的图：
性质：
对于一个能用动态规划解决的问题，一般采用如下思路解决：
如何找到转移关系：
f[i,0]=1f[i,0]=1多重背包: 每个物体可以选择\( k_i \)次
n[i] 为 13，就将这种物品分成系数分别为 1, 2, 4, 6 的 4 件物品。int num[maxn][2], dp[maxn];
int N, V, c, w, n, tot;
memset(dp, 0, sizeof dp);
cin >> V >> N; tot = 1;
for(int i = 1; i <= N; ++i)
{
cin >> c >> w >> n; // 第 i 物品的费用、价值和数量
for(int k = 1; k < n; k<<=1)//左移求下一个所需二进制数
{
num[tot][0] = k*c; // 添加 子物品
num[tot++][1] = k*w;
n -= k;
}
num[tot][0] = n*c; // 添加n[i]-2^k+1的 子物品
num[tot++][1] = n*w;
}
for(int i = 1; i < tot; ++i)
{
for(int j = V; j >= num[i][0]; --j) // 0-1 背包 滚动数组实现
dp[j] = max(dp[j], dp[j-num[i][0]]+num[i][1]);
}
区间DP
爬楼梯问题的暴力普通递归DFS代码
function climbStairs(n) {
if (n === 1) return 1;
if (n === 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
memo = {}
def climbStairs(n):
if n == 1:return 1
if n == 2: return 2
if n in memo: return memo[n]
ans = func(n - 1) + func(n-2)
memo[n] = ans
return ans
climbStairs(10)
状压+动态规划(DP, Dynamic Programming)
使用的数有限（共 10 个），并且使用到的数最多出现一次，容易想到使用「状压 DP」来求解：我们使用一个二进制数来表示具体的子集具体方案。
定义 f[state] 为当前子集选择数的状态为 state 时的方案数，state 为一个长度 10 的二进制数，若 state 中的第 k 位二进制表示为 1，代表数值 p[k] 在好子集中出现过；若第 k 位二进制表示为 0 代表 p[k] 在好子集中没出现过。
状态压缩有关，比如用 4 个字节存储状态
动态规划 与 np完全的关系
暂无
视频： https://www.bilibili.com/video/BV1Xj411K7oF/?vd_source=5bbdecb1838c6f684e0b823d0d4f6db3
https://oi-wiki.org/dp/basic/
https://www.zhihu.com/question/316416327/answer/626807333
* 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
* 计数排序 中 k是数据出现的范围
* 基数排序时间复杂度为O(N*M)，其中N为数据个数，M为数据位数。
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 快速排序：在数组中随机选一个数（默认数组首个/末尾元素），数组中小于等于此数的放在左边部分(交换到前面的排列)，大于此数的放在右边部分，这个操作确保了这个数是处于正确位置的，再对左边部分数组和右边部分数组递归调用快速排序，重复这个过程。
分治合并
归并排序： 首先让数组中的每一个数单独成为长度为1的区间，然后两两一组有序合并，得到长度为2的有序区间，依次合并进行得到长度为4、8、16的区间，直到合成整个区间。
计数排序：数据出现的范围k << O(n)时，或者k=O(n)都可以采用该方法。
void heapSort(int array[], int n)
{
int i;
//先建立堆
for (i=n/2;i>0;i--)
{
HeapAdjust(array,i,n);//从下向上，从右向左调整
}
//交换最大堆顶，重复n次
for( i=n;i>1;i--)
{
swap(array, 1, i);
HeapAdjust(array, 1, i-1);//从上到下，从左向右调整
}
}
void HeapAdjust(int array[], int s, int n )
{
int i,temp;
temp = array[s];
for(i=2*s;i<=n;i*=2)
{
if(i<n&&array[i]<array[i+1])
{
//交换左右子树最大的那个
i++;
}
if(temp>=array[i])
{
//找到了插入的合适的位置，子节点更小，父节点更大
break;
}
// 将节点向上移动
array[s]=array[i];
s=i;
}
//将最顶部插入到合适的位置
array[s]=temp;
}
void swap(int array[], int i, int j)
{
int temp;
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
拓扑排序常用来确定一个依赖关系集(图关系)中，事物发生的顺序。
带信号量判断的无依赖队列来实现，入队无依赖集合，出队的无依赖元素(add to result)去除后续元素的依赖信号量，信号量为0代表无依赖，可以入队。
找到图中距离最远的两个节点与它们之间的路径：
以任意节点 pp 出现，利用广度优先搜索或者深度优先搜索找到以 pp 为起点的最长路径的终点 xx；
以节点 xx 出发，找到以 xx 为起点的最长路径的终点 yy；
xx 到 yy 之间的路径即为图中的最长路径，找到路径的中间节点即为根节点。
https://leetcode-cn.com/circle/article/9ixykn/
https://leetcode-cn.com/problems/range-sum-query-mutable/
//input [[0,1],[1,2]]
//维护
vector<vector<int>> adj(n); //先找出每个点的有关边
vector<bool> visit(n, false); //维护已访问元素
queue<int> qu;
qu.emplace(0);
visit[0] = true;
int dist = 1;
while (!qu.empty()) {
int sz = qu.size();
for (int i = 0; i < sz; ++i) {
int curr = qu.front();
qu.pop();
for (auto & v : adj[curr]) {
if (visit[v]) {
continue;
}
qu.emplace(v);
//对应处理
visit[v] = true;
}
}
dist++;
}
对集合大小为n，可以用大于等于0小于1<<n的2^n-1个数字来表示子集。
但是对每个子集都会单独计算，有重复。 不如用按每位是否存在回溯
#2044
class Solution {
public:
int ans = 0;
int countMaxOrSubsets(vector<int>& nums) {
int maxOr = 0;
for (auto n: nums){
maxOr = n | maxOr;
}
dfs(nums, maxOr, 0 , 0);
return ans;
}
void dfs(vector<int>& nums, int maxOr, int idx, int cur){
if (cur == maxOr){
ans += 1 << (nums.size()-idx);
return;
}
if (idx == nums.size()){
return;
}
dfs(nums, maxOr, idx+1, cur | nums[idx]);
dfs(nums, maxOr, idx+1, cur);
}
};
int 可以表示32个元素的使用情况
https://leetcode.cn/problems/can-i-win/
前缀和
和差分
是一组互逆的方法；他们的关系和积分
与求导
实质是一样的。前缀和可以帮我们通过预处理快速的求出区间的和；差分则可以快速帮助我们记录区间的修改。
将区间前一个加一，最后一个减一实现。
leetcode 798
通过预处理记录信息来减少查询的时间
leetcode 2055
二分寻找满足条件的最小整数, 注意left + 1 < right和s >= cars
while (left + 1 < right) { // 开区间
long long mid = (left + right) / 2, s = 0;
for (int r : ranks)
s += sqrt(mid / r);
(s >= cars ? right : left) = mid;
}
// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/minimum-time-to-repair-cars/solutions/2177199/er-fen-da-an-pythonjavacgo-by-endlessche-keqf/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
最常用的方法
根据设定的哈希函数H（key）和处理冲突方法将一组关键字映象到一个有限的地址区间上的算法。也称为散列算法、杂凑算法。
一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区
std::ios::sync_with_stdio(); 是一个“是否兼容stdio”的开关，C++为了兼容C，保证程序在使用了std::printf和std::cout的时候不发生混乱，将输出流绑到了一起。也就是 C++标准streams(cin,cout,cerr…) 与相应的C标准程序库文件(stdin,stdout,stderr)同步，使用相同的 stream 缓冲区。 默认是同步的，但由于同步会带来某些不必要的负担，因此该函数作用是使得用户可以自行取消同步。
cin.tie(NULL) 取消 cin 和 cout 的绑定。
这对于输入数据个数在10^5以上的程序十分有效。
static int x = []() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}();
// or
static const auto io_sync_off = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
or
不如从底层动态规划合并，不要嵌套函数调用，还可以用二维数据，数据局部性较好。
https://leetcode-cn.com/problems/optimal-division/submissions/
可以将复杂的一次遍历，拆开成两次遍历，一次处理数据并存储，一次遍历统计。速度反而会快
用while代替函数递归调用，eg二分法
可以保存分支的值来实现(1748)
//0ms
int sumOfUnique(vector<int>& nums) {
int state[101]{}, ans = 0, d[101]{1,-1};
for(int x: nums) ans += d[state[x]++] * x;
return ans;
}
//4ms
int sumOfUnique(vector<int>& nums) {
array<char,101> isshowed {};
int sum=0;
for(auto& num:nums){
if(isshowed[num]==0){
isshowed[num]=1;
sum+=num;
}else if(isshowed[num]==1){
isshowed[num]=2;
sum-=num;
}
}
return sum;
}
无用的遍历计算(1219)
循环展开，只有一两种情况就不要写for循环了
暂无
暂无
https://oi-wiki.org/dp/basic/
https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md
作者：AC_OIer 链接：https://leetcode-cn.com/problems/the-number-of-good-subsets/solution/gong-shui-san-xie-zhuang-ya-dp-yun-yong-gz4w5/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
https://www.cnblogs.com/guoben/p/13339280.html
散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
在插入元素时,根据待插入元素的关键码,以hashfunc计算出该元素的存储位置,在结构中按此位置进行存放
在搜索元素时,对关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置去元素比较,若关键码相等,则搜索成功
C++11 定义了std::hash
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;
http://c.biancheng.net/view/7231.html
哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许m个地址时,其值域必须在0-(m-1)之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单
https://blog.csdn.net/HappyKocola/article/details/74188452
如果想让自定义的class作为key（unordered_map
std::hash<Key>()(k1) == std::hash<Key>()(k2).std::hash<Key>()(k1) == std::hash<Key>()(k2) should be very small, approaching 1.0/std::numeric_limits<std::size_t>::max(). template <>
struct hash<Myclass>
{
size_t operator()(const Myclass &k) const
{
int h = k.first;
for (auto x : k.second)
{
h ^= x;
}
return h;
}
};
struct MyHash
{
size_t operator() (const pair<int,int>& p) const
{
return hash<long long>()( (static_cast<long long>(x.first) )
^ ( (static_cast<long long>(x.first))<<32) );
}
};
防止黑客攻击
https://blog.csdn.net/qq_21433411/article/details/88365164
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename T>
inline void hash_combine(size_t& seed, const T& val)
{
seed ^= std::hash<T>()(val) + 0X9E3779B9 + (seed << 6) + (seed >> 2);
}
template <typename T>
inline void hash_val(size_t& seed, const T& val)
{
hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Types&... args)
{
hash_combine(seed, val);
hash_val(seed, args...);
}
template <typename... Types>
inline size_t hash_val(const Types&... args)
{
size_t seed = 0;
hash_val(seed, args...);
return seed;
}
class MyObject{
public:
string a;
char b;
unsigned c;
bool operator==(const MyObject& rhs) const
{
return a == rhs.a && b == rhs.b && c == rhs.c;
}
bool operator!=(const MyObject& rhs) const
{
return !operator==(rhs);
}
friend ostream& operator<<(ostream& os, const MyObject& ptr)
{
return os << ptr.a << " " << ptr.b << " " << ptr.c << endl;
}
};
class MyHashFunction{
public:
std::size_t operator()(const MyObject& obj) const {
return hash_val(obj.a, obj.b, obj.c);
}
};
为了避免动态改变哈希表的大小，可以预估容器中带插入元素的数量，并且预先申请好内存空间，避免动态分配过程中造成的 rehash 现象。当容器中的总元素超出了填充因子时，容器会重新申请更大的内存扩充桶的数量，然后重新哈希。
例如，我会预先调用 reverse 成员函数预先分配内存空间，以及设置好最大填充因子。
但是没什么用？
Google 则采用了开放寻址法中最简单的线性探测方法来解决哈希碰撞，取得了更快的速度。
开放定址法,当哈希表未满,在插入同义字时,可以把key值存放在下一个空位置(线性探测) 线性探测: 从发生冲突的位置开始,依次向后探测,直到寻找下一个空位置为止.
https://github.com/greg7mdp/parallel-hashmap
https://github.com/greg7mdp/sparsepp
暂无
IPCC比赛的时候，发现用hash map会比红黑树的map慢。感觉不对劲，我hash空间声明大，冲突不就低了吗？
无
简单bfs是每次从队列中取出当前的访问节点后，之后就将它的邻接节点加入到队列中，这样明显不利于并行化。
使用了两个队列，第一个队列存当前同一层的节点，第二个队列用来存储当前层节点的所有邻接节点(下一层节点)，等到当前层的节点全部访问完毕后，再将第一个队列与第二个队列进行交换，即可。
这样做的优势在于便于以后的并行化。同一层的节点可以一起运行，不会受到下一层节点的干扰。
但是写有问题，并行计算要储存下一层节点时，push操作不是原子的，需要加锁。
q1.push(1);
distance[1]=0;
while(!q1.empty()){
clear(q2);
for(int i=0;i<q1.size();i++){
int node=q1.front();
q1.pop();
cout<<node<<"->";
int start_edge=g.outgoing_starts[node];
int end_edge=(node==g.num_nodes-1)?g.num_edges:g.outgoing_starts[node+1];
for(int j=start_edge;j<end_edge;j++){
int outgoing=g.outgoing_edges[j];
if(distance[outgoing]==-1){
distance[outgoing]=1;
q2.push(outgoing);
}
}
}
swap(q1, q2);
}
思想和实现一一样，但是对并行时竞争情况有处理。
思想：都是将并行处理的一层节点bag的相邻节点存到下一次处理的bag中。
竞争：
最后还是要加锁，屮。
辅助数据结构，称为 "pennant"， 是一个\(2^k\)个节点的特殊树。根只有个left子节点，该子节点有个完整是二叉树。
通过这个辅助数据结构，可以实现动态无序集的 bag 数据结构
注意，普通的k层完全二叉树，有\(\(1+2+4+2^{k-1}=2^k-1\)\)个节点。
bag是pennant的集合，其中没有相同大小的pennant。PBFS采用固定大小的数组S[0...r]称作 backbone 骨干。
数组中的第k元素S[k]为空或者保存着指向大小为\(2k\)的pennant。可知，整个数组S[0...r]最多保存\(2\)元素。
所以BAG-CREATE分配了保存空指针固定大小的数组backbone,会花费Θ(r)时间。
This bound can be improved to O(1) by keeping track of the largest nonempty index in the backbone.
BAG-Insert类似二进制计数器递增的过程
BAG-INSERT(S,x)
1 k = 0
2 while S[k] != NULL
3 x = PENNANT-UNION(S[k],x)
4 S[k++] = NULL
5 S[k] = x #不执行循环 S[0] = x,不是在图7这种插入。
其中FA(x,y,z)相当于三个数的加法，c是进位，s是余位。
BAG-CREATE O(1) BAG-INSERT(n) O(1)-O(lgn) BAG-UNION(n) ~O(lgn)
暂无
PBFS: 1. 11行为什么是lg呢，全部遍历不好吗？ 1. 因为存的是\(2^r\)的元素
This bound can be improved to O(1) by keeping track of the largest nonempty index in the backbone.
flood fill的需要
https://www.cnblogs.com/JsonZhangAA/p/9016896.html
https://zhuanlan.zhihu.com/p/134637247
A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) from ACM SPAA 2010