【CSP】2021-09-3 脉冲神经网络 使用滚动数组代替map优化时间+常数级优化

本文主要是介绍【CSP】2021-09-3 脉冲神经网络 使用滚动数组代替map优化时间+常数级优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2021-09-3 脉冲神经网络 使用滚动数组代替map优化时间+常数级优化

首先说这题非常的恶心，算是一个垃圾题目，竟然卡的不是算法而是一些常数级优化，同样的算法可以拿到66分，而且同样的算法可以在acwing上过，但是csp的官方oj却有时候过有时候不过，很恶心，要是考试遇到了这种题目是不可能拿到100分的。

思路

这题的思路基本上所有人都能想到，和之前的第三题一样要建立索引。

首先我们解决这个题目一定是要遍历每个时刻，然后更新每个脉冲源和神经元的，然后可能会发出脉冲到突触（边）上，但是突触上脉冲的传播有时延，是在D个时间后，接收端才能接收到脉冲，所以这时候我们就要为每个神经元建立一个索引 用时间索引接受到脉冲的和（I[i][j] 表示i号神经元在j时刻接受到脉冲强度的总和），这样我们如果有脉冲到，可以直接加在对应的神经元的时间上，取的时候也可以直接取。

遇到的问题

1. 使用double 做map的索引有问题

一开始没发现，用浮点数做索引会出现精度问题，就是同样是6.2 存储的时候有可能是6.19999999和6.20000001这样的然后判断索引的时候就取不到6.2索引对应的数据。后面改成int就好了

2. 常数级优化

这题如果你是按照上边的思路写的，那么不出意外会只能拿到66分

会超时，因为题目时间限制是1s并且时间复杂度是$10^8$所以我们需要一些常数级的优化（很恶心没见过卡这个的）。

3. 将map换成二维数组

就是

struct neuron
{unordered_map<int, double> I;double v, u, a, b, c, d;int t;           // 表示neuron所处的时间
} nes[2001];         // 神经元

将里面的I提出出来

改成

double I[1005][1005];

这样就好了，并且由于时间是$10^5$而神经元也有$10^3$个这样就会导致超出空间限制

不知道为啥csp的oj报这个错误

然后使用滚动数组就好了

之后多提交几次就可以拿到时而83时而66的分数

3. 其他的常数级优化

不使用万能头

// #include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <vector>

使用 inline优化函数

inline int myrand(void)
{next1 = next1 * 1103515245 + 12345;return ((unsigned)(next1 / 65536) % 32768);
}

使用scanf printf 优化输入输出

    scanf("%d %d %d %d", &N, &S, &P, &T);scanf("%lf", &dt);printf("%.3f %.3f\n", min_v, max_v);printf("%d %d", min_times, max_times);

使用register优化循环

    for (register int i = 0; i < S; i++){struct link temp;int s;// cin >> s >> temp.t >> temp.w >> temp.D;scanf("%d %d %lf %d", &s, &temp.t, &temp.w, &temp.D);m[s].push_back(temp);mod = max(mod, temp.D + 1);// m[s][temp.t] = temp;}

然后就可以时而100分时而83分,但是acwing可以稳定拿到100分

完整代码

// #include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <vector>using namespace std;
static unsigned long next1 = 1;
int N, S, P, T;
double dt;
struct neuron
{// unordered_map<int, double> I;// double I[2010];double v, u, a, b, c, d;int t;           // 表示neuron所处的时间
} nes[2001];         // 神经元
int out_times[2001]; // 发生脉冲的次数
int mod = 0;
double I[1005][1005];
struct link
{double w;int D;int t = -1;
};// 突触 注意第一个索引有可能大于等于N
// 如果大于等于N则为脉冲源
// unordered_map<int, vector<struct link>> m;
vector<struct link> m[2001];double r[2001]; // 脉冲源
/* RAND_MAX assumed to be 32767 */
inline int myrand(void)
{next1 = next1 * 1103515245 + 12345;return ((unsigned)(next1 / 65536) % 32768);
}signed main()
{// ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0);// cin >> N >> S >> P >> T;// cin >> dt;scanf("%d %d %d %d", &N, &S, &P, &T);scanf("%lf", &dt);int sum = 0;while (sum < N){int rn;double v, u, a, b, c, d;// cin >> rn >> v >> u >> a >> b >> c >> d;scanf("%d %lf %lf %lf %lf %lf %lf", &rn, &v, &u, &a, &b, &c, &d);for (register int i = 0; i < rn; i++){nes[sum + i].a = a, nes[sum + i].b = b, nes[sum + i].c = c, nes[sum + i].d = d;nes[sum + i].v = v, nes[sum + i].u = u;}sum += rn;}for (register int i = 0; i < P; i++){// cin >> r[i];scanf("%lf", &r[i]);}for (register int i = 0; i < S; i++){struct link temp;int s;// cin >> s >> temp.t >> temp.w >> temp.D;scanf("%d %d %lf %d", &s, &temp.t, &temp.w, &temp.D);m[s].push_back(temp);mod = max(mod, temp.D + 1);// m[s][temp.t] = temp;}int t = 0;while (t < T){t++;int t_tmp = t % mod;for (register int i = 0; i < P; i++) // 遍历脉冲源{// vector<struct link> temp = m[i + N];int rand = myrand();if (rand < r[i]){// for (int j = 0; j < N; j++)// {//     struct link item = m[i + N][j];//     if (item.t != -1)//         nes[item.t].I[t + item.D] += item.w;// }for (int j = 0; j < m[i + N].size(); j++){struct link item = m[i + N][j];I[(t_tmp + item.D) % mod][item.t] += item.w;// nes[item.t].I[t + item.D] += item.w;}}}for (register int i = 0; i < N; i++) //{nes[i].t = t;double v = nes[i].v, u = nes[i].u;nes[i].v = v + dt * (0.04 * v * v + 5 * v + 140 - u) + I[t_tmp][i];// nes[i].v = v + dt * (0.04 * v * v + 5 * v + 140 - u) + nes[i].I[t];// nes[i].I.erase(t);nes[i].u = u + dt * nes[i].a * (nes[i].b * v - u);if (nes[i].v >= 30){out_times[i]++;nes[i].v = nes[i].c;nes[i].u += nes[i].d;for (int j = 0; j < m[i].size(); j++){struct link item = m[i][j];I[(t_tmp + item.D) % mod][item.t] += item.w;// nes[item.t].I[t + item.D] += item.w;}}}memset(I[t_tmp], 0, sizeof I[t_tmp]);}double max_v = -1 * 1e8, min_v = 1e8;int max_times = -1, min_times = 1e5;for (register int i = 0; i < N; i++){max_v = max(nes[i].v, max_v);min_v = min(nes[i].v, min_v);max_times = max(out_times[i], max_times);min_times = min(out_times[i], min_times);}// cout << fixed << setprecision(3) << min_v << ' ' << max_v << endl;// cout << min_times << ' ' << max_times;printf("%.3f %.3f\n", min_v, max_v);printf("%d %d", min_times, max_times);return 0;
}

这篇关于【CSP】2021-09-3 脉冲神经网络 使用滚动数组代替map优化时间+常数级优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---