【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时刻接受到脉冲强度的总和），这样我们如果有脉冲到，可以直接加在对应的神经元的时间上，取的时候也可以直接取。

遇到的问题

使用double 做map的索引有问题

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

常数级优化

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

在这里插入图片描述

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

将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的分数

其他的常数级优化

不使用万能头

// #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优化时间+常数级优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！