建议使用以下浏览器,以获得最佳体验。 IE 9.0+以上版本 Chrome 31+ 谷歌浏览器 Firefox 30+ 火狐浏览器
温馨提示

抱歉,您需设置社区昵称后才能参与社区互动!

前往修改
我再想想

2020华为软件精英挑战赛

话题 : 430 成员 : 6437

加入HCSD

正式结束了,分享一下经验

ddd2020 2020/5/16 3363

想当然的以为Linux下换行符没有\r,所以没有判,5发 0% INCORRECT,正式退赛了

昨晚熬夜把19630345的数据优化到了6.3s,分享一下我个人的经验。

1. 存图用vector会很慢。考虑把所有边排个序,那么一个点的所有出边就是一段连续的区间,再遍历就会快很多了。

2. 给边排序是很花时间的,但考虑到离散化本身就需要排序(写的不精细的hash其实不会比排序快),所以可以把给边排序和离散化同时完成。可以参考下面的代码:

// 边的定义
struct Edge {
  uint32_t x, y, z;
};
  
void SortEdges() {
  RadixSortY();
  uint32_t last = E[0].y - 1;
  for (int i = 0; i < edge_cnt; ++i) {
    if (E[i].y != last) {
      table[n++] = E[i].y;
      last = E[i].y;
    }
    E[i].y = n - 1;
  }
  RadixSortX();
  memset(st, -1, sizeof(st));
  memset(ed, -2, sizeof(ed));
  int ptr = 0;
  for (int i = 0; i < edge_cnt; ++i) {
    if (E[i].z == 0) break;
    while (ptr < n && table[ptr] < E[i].x) ptr += 1;
    if (ptr < n && table[ptr] == E[i].x) {
      E[i].x = ptr;
      if (st[ptr] == -1) st[ptr] = i;
      ed[ptr] = i;
    } else {
      E[i] = {~0U, ~0U, 0};
    }
  }
}

其中 RadixSortY() 是以 y 为关键字,对所有边进行基数排序,注意基数排序按256分组会快;RadixSortX() 是以 x 为关键字,对所有边进行基数排序。table[] 表示离散化后的值在离散化之前是什么;st[i] 和 ed[i] 表示以 i 为起点的所有出边在边集里所在的位置(一个区间)。

3. 上述过程中边都是 struct {x, y, z}; 这样存的,但后面遍历的时候其实 x 已经没用了,所以排完序之后可以重新定义一个 struct {y, z};,再遍历可以快得多。

4. 计算的时候IO资源没有充分利用,可以考虑把计算中的一部分分离出来。我的做法是(感谢chier提供这个思路):搜索时,答案先存到一个 uint32_t 的数组里,而不是直接存成字符串。等搜完之后再把 uint32_t 的答案转成 char,在这个转换过程中可以同时开一个线程负责输出。这样就可以实现流水线,快很多。

还有很多技巧,但应该都是well-known的,就不多提了。过几天会抽时间把代码整理一下放到GitHub。

感谢这个比赛给我机会可以认识这么多人。祝进决赛的大佬们奖金多多!

回复 (6)

ls
0 0
2020/5/17 10:41

Orz ddd

我是bug
0 0
2020/5/16 18:21

膜拜大佬,同0% INCORRECT,不过还是大佬强,我1963W得10s。本来挺失落的,看了大佬,发现原来我不是最惨的。

凌少
0 0
2020/5/16 18:06

膜拜

难顶啊
0 0
2020/5/16 17:56

膜拜

ryero
0 0
2020/5/16 17:42


Bota5ky
0 0
2020/5/16 17:37

前排膜拜

上划加载中
标签
您还可以添加5个标签
  • 没有搜索到和“关键字”相关的标签
  • 云产品
  • 解决方案
  • 技术领域
  • 通用技术
  • 平台功能
取消

ddd2020

角色:成员

话题:5

发消息
发表于2020年05月16日 17:35:41 33636
直达本楼层的链接
楼主
正序浏览 只看该作者
[复赛问题咨询] 正式结束了,分享一下经验

想当然的以为Linux下换行符没有\r,所以没有判,5发 0% INCORRECT,正式退赛了

昨晚熬夜把19630345的数据优化到了6.3s,分享一下我个人的经验。

1. 存图用vector会很慢。考虑把所有边排个序,那么一个点的所有出边就是一段连续的区间,再遍历就会快很多了。

2. 给边排序是很花时间的,但考虑到离散化本身就需要排序(写的不精细的hash其实不会比排序快),所以可以把给边排序和离散化同时完成。可以参考下面的代码:

// 边的定义
struct Edge {
  uint32_t x, y, z;
};
  
void SortEdges() {
  RadixSortY();
  uint32_t last = E[0].y - 1;
  for (int i = 0; i < edge_cnt; ++i) {
    if (E[i].y != last) {
      table[n++] = E[i].y;
      last = E[i].y;
    }
    E[i].y = n - 1;
  }
  RadixSortX();
  memset(st, -1, sizeof(st));
  memset(ed, -2, sizeof(ed));
  int ptr = 0;
  for (int i = 0; i < edge_cnt; ++i) {
    if (E[i].z == 0) break;
    while (ptr < n && table[ptr] < E[i].x) ptr += 1;
    if (ptr < n && table[ptr] == E[i].x) {
      E[i].x = ptr;
      if (st[ptr] == -1) st[ptr] = i;
      ed[ptr] = i;
    } else {
      E[i] = {~0U, ~0U, 0};
    }
  }
}

其中 RadixSortY() 是以 y 为关键字,对所有边进行基数排序,注意基数排序按256分组会快;RadixSortX() 是以 x 为关键字,对所有边进行基数排序。table[] 表示离散化后的值在离散化之前是什么;st[i] 和 ed[i] 表示以 i 为起点的所有出边在边集里所在的位置(一个区间)。

3. 上述过程中边都是 struct {x, y, z}; 这样存的,但后面遍历的时候其实 x 已经没用了,所以排完序之后可以重新定义一个 struct {y, z};,再遍历可以快得多。

4. 计算的时候IO资源没有充分利用,可以考虑把计算中的一部分分离出来。我的做法是(感谢chier提供这个思路):搜索时,答案先存到一个 uint32_t 的数组里,而不是直接存成字符串。等搜完之后再把 uint32_t 的答案转成 char,在这个转换过程中可以同时开一个线程负责输出。这样就可以实现流水线,快很多。

还有很多技巧,但应该都是well-known的,就不多提了。过几天会抽时间把代码整理一下放到GitHub。

感谢这个比赛给我机会可以认识这么多人。祝进决赛的大佬们奖金多多!

点赞2 举报
分享

分享文章到朋友圈

分享文章到微博

ls

角色:成员

话题:0

发消息
发表于2020年05月17日 10:41:08
直达本楼层的链接
7#
只看该作者

Orz ddd

点赞 评论 引用 举报

我是bug

角色:成员

话题:0

发消息
发表于2020年05月16日 18:21:24
直达本楼层的链接
6#
只看该作者

膜拜大佬,同0% INCORRECT,不过还是大佬强,我1963W得10s。本来挺失落的,看了大佬,发现原来我不是最惨的。

点赞 评论 引用 举报

凌少

角色:成员

话题:0

发消息
发表于2020年05月16日 18:06:00
直达本楼层的链接
5#
只看该作者

膜拜

点赞 评论 引用 举报

难顶啊

角色:成员

话题:0

发消息
发表于2020年05月16日 17:56:20
直达本楼层的链接
地板
只看该作者

膜拜

点赞 评论 引用 举报

ryero

角色:成员

话题:1

发消息
发表于2020年05月16日 17:42:07
直达本楼层的链接
板凳
只看该作者


点赞 评论 引用 举报

Bota5ky

角色:成员

话题:0

发消息
发表于2020年05月16日 17:37:06
直达本楼层的链接
沙发
只看该作者

前排膜拜

点赞 评论 引用 举报

游客

您需要登录后才可以回帖 登录 | 立即注册