BUAA2020软工个人项目小结
零、小结说明
作业链接: 个人项目作业
本次小结四-六部分由子渊学长编写!
一、评分规则
总体分数构成
本次个人项目分数由三部分组成,分别是:
- 博客 — 15 分;
- 程序 — 35 分;
- 附加题 — 2 分。附加题不参与总分映射,直接进入期末成绩。
博客评分规则
发表在你的个人博客上,也可以同时转发到你的团队博客上来增加你们团队博客的人气。博客共 15 分,具体要求如下:
-
在文章开头给出教学班级和
可克隆
的 Github 项目地址(例子如下)。(1')
- 教学班级:005
- 项目地址:https://github.com/github/platform-samples.git
-
在开始实现程序之前,在下述 PSP 表格记录下你估计将在程序的各个模块的开发上耗费的时间。(0.5')
-
解题思路描述。即刚开始拿到题目后,如何思考,如何找资料的过程。(3')
-
设计实现过程。设计包括代码如何组织,比如会有几个类,几个函数,他们之间关系如何,关键函数是否需要画出流程图?单元测试是怎么设计的?(4')
-
记录在改进程序性能上所花费的时间,描述你改进的思路,并展示一张性能分析图(由 VS 2019 的性能分析工具自动生成),并展示你程序中消耗最大的函数。(3')
-
代码说明。展示出项目关键代码,并解释思路与注释说明。(3')
-
在你实现完程序之后,在 PSP 表格(详见作业要求)记录下你在程序的各个模块上实际花费的时间。(0.5')
程序评分规则
- 源代码管理 — 5 分。具体关注点为:
- 源代码目录管理。源代码目录管理是否清晰。注:测试须知中给出的目录结构除了
/bin/
为强制要求外,其余仅为示例。同学可以自行选择合适的目录的结构进行源代码管理。 - Git 工具使用情况。Commit 信息是否区分标题和详细描述,是否清晰易懂,增量修改是否合适等。
- 运行说明。是否有运行说明,运行说明的质量等。
- 是否消除 Code Quality Analysis 中的所有警告。请在博客中给出相应截图。
- 单元测试。单元测试的数目,测试粒度等。
- 源代码目录管理。源代码目录管理是否清晰。注:测试须知中给出的目录结构除了
- 正确性评分 — 20 分。正确性测试中输入的几何对象个数满足 1 <= N <= 1000,要求程序在 60 秒内给出结果,超时则认定运行结果无效。
- 性能评分 — 10 分。性能测试中输入的几何对象个数满足 1000 <= N <= 500000,交点个数 h 满足 0 <= h <= 5000000,要求程序在 60 秒内给出结果。性能评分将采取档级评分制度,助教将根据同学们的程序跑同一数据耗费的时间长度将程序分为若干档,第 n 档的同学得到的分数为 10 / n。注:当程序的正确性评分等于 20 分时才可以参与性能评分环节,所以请各位同学务必保证自己程序的正确性。
附加题评分规则
- 正确性评分 — 1 分。正确性测试中输入的几何对象个数满足 1 <= N <= 1000,要求程序在 60 秒内给出结果,超时则认定运行结果无效。
- 性能评分 — 1 分。性能测试中输入的几何对象个数满足 1000 <= N <= 500000,交点个数 h 满足 0 <= h <= 5000000,要求程序在 60 秒内给出结果。性能评分将采取档级评分制度,助教将根据同学们的程序跑同一数据耗费的时间长度将程序分为 3 档,第 n 档的同学得到的分数为 0.5 * (3 - n)。注:当程序的附加题正确性评分等于 1 分时才可以参与性能评分环节。
注:只有当程序在基础需求的正确性评分达到 20 分时才参与附加题评分环节,所以请各位同学务必保证自己程序在基础需求的正确性。
二、得分情况
本次评分点比较多,故评分表格较宽。部分浏览器需调整比例才可完整查看
学号后四位 | 作业链接 | 提交时间 | 博客印象 | 1.文章开头 | 2.PSP-估计 | 3.解题思路描述 | 4.设计实现过程 | 5.改进与性能 | 6.代码说明 | 7.PSP-实际 | 源代码管理 | 评论的回复 | 博客分数 | 正确性通过测试点数目 | 性能得分 | 正确性得分 | 总分 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1025 | 软工个人项目作业 | 2020-03-09 16:42 | 中上 | 0.5 | 0.5 | 1 | 3 | 3 | 2 | 0.5 | 4 | 1 | 11.5 | 39 | 0 | 16.25 | 31.75 |
5001 | BUAA软件工程个人项目作业 | 2020-03-09 22:55 | 中上 | 0.5 | 0.5 | 3 | 3.5 | 2.5 | 3 | 0.5 | 3 | 1 | 14.5 | 48 | 3.333333333 | 20 | 40.83333333 |
5016 | 软工个人项目作业 | 2020-03-10 13:00 | 中 | 0.5 | 0 | 2 | 2.5 | 2.5 | 3 | 0.5 | 3 | -1 | 10 | 0 | 0 | 0 | 13 |
5044 | 个人项目作业 | 2020-03-09 21:37 | 中上 | 0.5 | 0.5 | 3 | 2.5 | 2.5 | 3 | 0.5 | 3 | 1 | 13.5 | 39 | 0 | 16.25 | 32.75 |
5046 | BUAA SE 个人项目作业 | 2020-03-10 18:24 | 中上 | 0.5 | 0.5 | 3 | 2 | 2.5 | 3 | 0.5 | 2 | 1 | 13 | 0 | 0 | 0 | 15 |
1088 | 个人项目作业 求交点个数 | 2020-03-10 14:55 | 中上 | 1 | 0.5 | 3 | 3 | 2.5 | 3 | 0.5 | 5 | 1 | 14.5 | 48 | 10 | 20 | 49.5 |
1142 | 2019软件工程-个人项目作业 | 2020-03-10 07:26 | 中 | 0.5 | 0.5 | 2 | 3 | 2 | 1.5 | 0.5 | 5 | 1 | 11 | 37 | 0 | 15.41666667 | 31.41666667 |
1169 | 软工个人项目:平面直线交点 | 2020-03-10 15:44 | 中 | 0.5 | 0.5 | 3 | 3 | 0.5 | 0 | 0.5 | 3 | -1 | 7 | 44 | 0 | 18.33333333 | 28.33333333 |
1051 | 软件工程个人项目作业 | 2020-03-10 15:58 | 好 | 0.5 | 0.5 | 3 | 3.5 | 2.5 | 3 | 0.5 | 5 | 1 | 14.5 | 48 | 10 | 20 | 49.5 |
1263 | NULL | NULL | 0 | 0 | 0 | 0 | 0 | ||||||||||
1122 | 软工个人项目作业 | 2020-03-09 19:01 | 中上 | 1 | 0.5 | 2 | 2.5 | 2.5 | 3 | 0.5 | 5 | 1 | 13 | 37 | 0 | 15.41666667 | 33.41666667 |
1145 | 【软工】个人项目作业——个人软件流程(PSP) | 2020-03-10 18:49 | 好 | 1 | 0.5 | 3 | 3.5 | 2.5 | 3 | 0.5 | 5 | 1 | 15 | 48 | 2 | 20 | 42 |
1151 | 个人项目作用 | 2020-03-10 18:59 | 中 | 0.5 | 0.5 | 1 | 2 | 2 | 2 | 0.5 | 5 | 1 | 9.5 | 48 | 5 | 20 | 39.5 |
1162 | 【BUAA 软工个人项目作业】玩转平面几何 | 2020-03-10 18:44 | 中上 | 0.5 | 0.5 | 3 | 3.5 | 0.5 | 1 | 0.5 | 5 | 1 | 10.5 | 48 | 2 | 20 | 37.5 |
3010 | 2020BUAA软工个人项目作业 | 2020-03-10 18:15 | 中上 | 0.5 | 0.5 | 2 | 2.5 | 2 | 1 | 0.5 | 5 | 1 | 10 | 48 | 10 | 20 | 45 |
3015 | BUAA 软件工程个人作业 | 2020-03-10 17:07 | 中上 | 0.5 | 0.5 | 2 | 3 | 1.5 | 1.5 | 0.5 | 3 | 1 | 10.5 | 48 | 5 | 20 | 38.5 |
3051 | BUAA 2020 软件工程 个人项目作业 | 2020-03-10 13:29 | 中上 | 0.5 | 0.5 | 3 | 3 | 2 | 1.5 | 0.5 | 5 | 1 | 12 | 39 | 16.25 | 33.25 | |
3052 | 软工-第一次个人项目作业 | 2020-03-09 20:04 | 好 | 0.5 | 0.5 | 3 | 4 | 3 | 1.5 | 0.5 | 5 | 1 | 14 | 39 | 16.25 | 35.25 | |
3053 | 个人项目作业(1) | 2020-03-10 14:34 | 中上 | 0.5 | 0.5 | 2 | 2.5 | 2 | 3 | 0.5 | 5 | -1 | 10 | 48 | 5 | 20 | 40 |
3059 | [敏捷软工个人项目博客]几何对象公共点 | 2020-03-10 18:43 | 中上 | 1 | 0.5 | 3 | 3 | 1.5 | 2 | 0.5 | 5 | 1 | 12.5 | 39 | 16.25 | 33.75 | |
3061 | 个人项目作业 | 2020-03-10 12:37 | 中下 | 0.5 | 0.5 | 1 | 2 | 1.5 | 1.5 | 0.5 | 4 | 1 | 8.5 | 48 | 2.5 | 20 | 35 |
3067 | 【软件工程】个人项目作业 | 2020-03-10 18:29 | 中 | 0.5 | 0.5 | 3 | 2 | 1.5 | 1.5 | 0.5 | 5 | 1 | 10.5 | 48 | 2 | 20 | 37.5 |
3071 | 【BUAA_2020_软工】个人作业 | 2020-03-10 15:25 | 好 | 0.5 | 0.5 | 3 | 3.5 | 3 | 3 | 0.5 | 5 | 1 | 15 | 48 | 10 | 20 | 50 |
3072 | BUAA软工__个人项目作业 | 2020-03-08 14:40 | 中 | 0.5 | 0.5 | 2 | 2.5 | 2 | 2 | 0.5 | 5 | 1 | 11 | 48 | 10 | 20 | 46 |
3078 | 个人项目作业-求交点个数 | 2020-03-10 13:29 | 中上 | 1 | 0.5 | 2 | 2.5 | 2.5 | 3 | 0.5 | 5 | 1 | 13 | 48 | 10 | 20 | 48 |
3086 | 个人项目作业 | 2020-03-10 18:45 | 中下 | 0.5 | 0.5 | 3 | 2.5 | 0 | 1.5 | 0.5 | 5 | -1 | 7.5 | 0 | 0 | 12.5 | |
3100 | 个人项目作业 | 2020-03-10 18:49 | 中 | 0.5 | 0.5 | 2 | 3 | 1.5 | 2 | 0.5 | 5 | 1 | 11 | 48 | 10 | 20 | 46 |
3106 | 个人项目博客 | 2020-03-10 08:06 | 中 | 0.5 | 0.5 | 2 | 2.5 | 2 | 2 | 0.5 | 5 | 1 | 11 | 48 | 3.333333333 | 20 | 39.33333333 |
3111 | 交点问题 | 2020-03-09 22:21 | 中下 | 0.5 | 0.5 | 2 | 1 | 2 | 1.5 | 0.5 | 3 | 1 | 9 | 37 | 15.41666667 | 27.41666667 | |
3118 | 软工个人项目作业 | 2020-03-10 17:32 | 中下 | 0.5 | 0.5 | 2 | 2.5 | 0 | 1.5 | 0.5 | 4 | 1 | 8.5 | 0 | 0 | 12.5 | |
3124 | 软件工程个人项目作业——平面交点个数 | 2020-03-10 18:53 | 中上 | 0.5 | 0.5 | 2 | 3.5 | 2.5 | 2.5 | 0.5 | 4 | 1 | 13 | 44 | 18.33333333 | 35.33333333 | |
3146 | 个人项目 | 2020-03-10 18:31 | 中 | 1 | 0.5 | 2 | 3 | 0 | 3 | 0.5 | 4 | 1 | 11 | 0 | 0 | 15 | |
3165 | 2020软工个人项目作业 | 2020-03-10 17:50 | 中上 | 1 | 0.5 | 2.5 | 3.5 | 2.5 | 2.5 | 0.5 | 4 | 1 | 14 | 48 | 2.5 | 20 | 40.5 |
3167 | 软工个人项目(图形交点) | 2020-03-10 17:36 | 中上 | 0.5 | 0.5 | 2.5 | 3.5 | 2 | 3 | 0.5 | 5 | 1 | 13.5 | 48 | 3.333333333 | 20 | 41.83333333 |
3170 | 个人项目作业 | 2020-03-10 18:32 | 中 | 0.5 | 0.5 | 2.5 | 1.5 | 1 | 2 | 0.5 | 2 | -1 | 7.5 | 3 | 1.25 | 10.75 | |
3172 | 个人项目作业 | 2020-03-10 18:31 | 中 | 0.5 | 0.5 | 1.5 | 2.5 | 2.5 | 1.5 | 0.5 | 2 | 1 | 10.5 | 0 | 0 | 12.5 | |
3174 | 软工作业——求交点 | 2020-03-10 16:22 | 中下 | 0.5 | 0.5 | 1.5 | 1.5 | 0.5 | 1.5 | 0.5 | 2 | -1 | 5.5 | 48 | 2.5 | 20 | 30 |
3178 | BUAA_2020_软件工程_个人项目作业 | 2020-03-10 16:50 | 中上 | 1 | 0.5 | 2 | 3.5 | 2.5 | 3 | 0.5 | 5 | 1 | 14 | 48 | 10 | 20 | 49 |
3182 | 个人项目作业 | 2020-03-10 18:05 | 中下 | 0.5 | 0.5 | 2.5 | 1.5 | 0 | 2 | 0.5 | 4 | -1 | 6.5 | 48 | 5 | 20 | 35.5 |
3187 | 【软工】个人项目作业 | 2020-03-09 21:04 | 好 | 1 | 0.5 | 3 | 3.5 | 3 | 2.5 | 0.5 | 5 | 1 | 15 | 48 | 3.333333333 | 20 | 43.33333333 |
3190 | 个人项目作业——交点检测 | 2020-03-10 18:47 | 中下 | 0.5 | 0.5 | 2 | 2 | 0 | 1.5 | 0.5 | 4 | -1 | 6 | 0 | 0 | 10 | |
3192 | 17373192 段正旭 | 2020-03-09 19:37 | 中上 | 1 | 0.5 | 3 | 3 | 2 | 2.5 | 0.5 | 4 | 1 | 13.5 | 37 | 15.41666667 | 32.91666667 | |
3194 | 17373194陈丛文第一次项目作业 | 2020-03-10 11:05 | 中上 | 0.5 | 0.5 | 2 | 3 | 2.5 | 2 | 0.5 | 4 | 1 | 12 | 39 | 16.25 | 32.25 | |
3224 | 北航软工项目作业(一) | 2020-03-10 16:44 | 中 | 0.5 | 0.5 | 2 | 2.5 | 1 | 1.5 | 0.5 | 2 | 1 | 9.5 | 0 | 0 | 11.5 | |
3239 | 软件工程--个人项目作业 | 2020-03-10 17:18 | 好 | 0.5 | 0.5 | 3 | 4 | 1 | 2 | 0.5 | 3 | 1 | 12.5 | 48 | 2.5 | 20 | 38 |
3250 | 软工个人项目 | 2020-03-09 08:20 | 中 | 0 | 0.5 | 1.5 | 2 | 2 | 2 | 0.5 | 3 | -1 | 7.5 | 48 | 10 | 20 | 40.5 |
3253 | 软工第一次个人作业 | 2020-03-10 15:54 | 中上 | 0.5 | 0.5 | 3 | 2 | 0 | 2 | 0.5 | 4 | 1 | 9.5 | 0 | 0 | 13.5 | |
3259 | SE_Work2_交点个数 | 2020-03-07 11:26 | 中上 | 0.5 | 0.5 | 3 | 3 | 2 | 2 | 0.5 | 3 | 1 | 12.5 | 44 | 18.33333333 | 33.83333333 | |
3260 | 第一次软件工程个人项目作业——algo for intersection | 2020-03-10 17:45 | 中上 | 0.5 | 0.5 | 2 | 4 | 3 | 1.5 | 0.5 | 2 | -1 | 11 | 48 | 10 | 20 | 43 |
3262 | 软件工程个人项目作业 | 2020-03-10 18:09 | 中 | 0.5 | 0.5 | 2.5 | 2.5 | 2 | 1.5 | 0.5 | 2 | -1 | 9 | 48 | 2.5 | 20 | 33.5 |
3263 | 个人项目作业 | 2020-03-10 10:02 | 中 | 0.5 | 0.5 | 2 | 2 | 0 | 1 | 0.5 | 5 | 1 | 7.5 | 48 | 5 | 20 | 37.5 |
3266 | 个人项目 | 2020-03-10 18:09 | 中 | 0.5 | 0.5 | 2.5 | 2.5 | 1.5 | 1 | 0.5 | 5 | 1 | 10 | 48 | 5 | 20 | 40 |
3267 | 软工个人项目博客 | 2020-03-10 17:06 | 中 | 0.5 | 0.5 | 2 | 2 | 2.5 | 2 | 0.5 | 2 | -1 | 9 | 48 | 3.333333333 | 20 | 34.33333333 |
3275 | 个人项目博客 | 2020-03-10 02:10 | 中上 | 0.5 | 0.5 | 3 | 3 | 2 | 2 | 0.5 | 4 | 1 | 12.5 | 39 | 16.25 | 32.75 | |
3282 | 个人项目 | 2020-03-10 01:17 | 中上 | 0.5 | 0.5 | 2.5 | 3 | 3 | 2 | 0.5 | 4 | 1 | 13 | 48 | 2.5 | 20 | 39.5 |
3287 | 软工个人项目作业 | 2020-03-10 01:44 | 中上 | 0.5 | 0.5 | 2.5 | 3 | 2 | 2 | 0.5 | 4 | 1 | 12 | 48 | 10 | 20 | 46 |
3292 | 软工个人项目作业 | 2020-03-10 11:08 | 中上 | 0.5 | 0.5 | 3 | 3 | 2 | 2 | 0.5 | 5 | 1 | 12.5 | 48 | 3.333333333 | 20 | 40.83333333 |
3299 | 软工个人项目 | 2020-03-10 17:07 | 好 | 0.5 | 0.5 | 3 | 3.5 | 2.5 | 2 | 0.5 | 5 | 1 | 13.5 | 48 | 3.333333333 | 20 | 41.83333333 |
3308 | 个人项目作业 | 2020-03-17 08:05 | 中下 | 0.5 | 0.5 | 2 | 1 | 1 | 2 | 0.5 | 2 | -1 | 3.25 | 0 | 0 | 0 | 5.25 |
3312 | 个人项目博客作业 | 2020-03-10 16:41 | 中上 | 0.5 | 0.5 | 2.5 | 2.5 | 2.5 | 2 | 0.5 | 5 | 1 | 12 | 48 | 3.333333333 | 20 | 40.33333333 |
3318 | PSP初体验:求交点 | 2020-03-09 14:41 | 中上 | 0.5 | 0.5 | 3 | 3 | 2.5 | 2 | 0.5 | 5 | 1 | 13 | 0 | 0 | 18 | |
3321 | 软件工程 - 个人项目(平面交点个数) | 2020-03-10 18:56 | 中上 | 0.5 | 0.5 | 3 | 3.5 | 2 | 1 | 0.5 | 5 | 1 | 12 | 48 | 5 | 20 | 42 |
3323 | 交点计数 -- 软工个人项目作业 | 2020-03-10 18:22 | 中上 | 0.5 | 0.5 | 2.5 | 2.5 | 1 | 2 | 0.5 | 5 | 1 | 10.5 | 48 | 10 | 20 | 45.5 |
3325 | [2020 BUAA 软件工程]个人项目作业 | 2020-03-09 21:52 | 中上 | 0.5 | 0.5 | 3 | 3.5 | 1 | 2.5 | 0.5 | 5 | 1 | 12.5 | 48 | 2 | 20 | 39.5 |
3331 | 软工个人项目-求交点数目 | 2020-03-10 18:58 | 中 | 0.5 | 0.5 | 2.5 | 3.5 | 0 | 2.5 | 0.5 | 5 | -1 | 9 | 17 | 7.083333333 | 21.08333333 | |
3349 | 软工个人项目 | 2020-03-10 00:56 | 中上 | 0.5 | 0.5 | 3 | 3 | 2 | 2 | 0.5 | 5 | 1 | 12.5 | 48 | 10 | 20 | 47.5 |
3362 | 交点——软工第一次个人项目作业 | 2020-03-10 12:07 | 中上 | 0.5 | 0.5 | 3 | 3 | 2 | 2 | 0.5 | 4 | 1 | 12.5 | 48 | 10 | 20 | 46.5 |
3373 | 第一次个人项目 | 2020-03-10 14:02 | 中上 | 0.5 | 0.5 | 2.5 | 3 | 1.5 | 2 | 0.5 | 4 | 1 | 11.5 | 37 | 15.41666667 | 30.91666667 | |
3375 | 个人项目作业 | 2020-03-10 11:54 | 中 | 0.5 | 0.5 | 2 | 3 | 1 | 1.5 | 0.5 | 3 | -1 | 8 | 0 | 0 | 11 | |
3380 | 软工个人作业 | 2020-03-10 11:30 | 中上 | 0.5 | 0.5 | 2 | 3 | 1.5 | 2 | 0.5 | 4 | -1 | 9 | 0 | 0 | 13 | |
3407 | 个人项目作业 | 2020-03-10 17:30 | 中上 | 0.5 | 0.5 | 2 | 3 | 2 | 2 | 0.5 | 5 | 1 | 11.5 | 48 | 2.5 | 20 | 39 |
3417 | 软件工程个人项目 | 2020-03-10 18:45 | 中上 | 0.5 | 0.5 | 3 | 2.5 | 3 | 2 | 0 | 5 | 1 | 12.5 | 42 | 17.5 | 35 | |
3432 | 个人项目作业 | 2020-03-10 16:50 | 中上 | 0.5 | 0.5 | 3 | 3 | 3 | 2 | 0.5 | 5 | 1 | 13.5 | 48 | 10 | 20 | 48.5 |
3434 | 北航软工个人项目作业 | 2020-03-10 10:28 | 中 | 0.5 | 0.5 | 3 | 2 | 2 | 1.5 | 0.5 | 5 | -1 | 9 | 42 | 17.5 | 31.5 | |
3439 | 2020软工个人项目作业-平面几何图形交点统计 | 2020-03-10 01:32 | 好 | 0.5 | 0.5 | 3 | 3.5 | 3 | 2 | 0.5 | 5 | 1 | 14 | 48 | 5 | 20 | 44 |
3448 | 软工个人项目作业 | 2020-03-09 21:21 | 中上 | 0.5 | 0.5 | 3 | 2 | 2 | 2 | 0.5 | 4 | 1 | 11.5 | 48 | 5 | 20 | 40.5 |
3452 | BUAA2020软工作业(三)——个人项目 | 2020-03-10 18:46 | 中上 | 0.5 | 0.5 | 2 | 2 | 1.5 | 2 | 0.5 | 5 | 1 | 10 | 0 | 0 | 15 | |
3456 | 2020软工个人项目作业 | 2020-03-10 09:15 | 中上 | 0.5 | 0.5 | 3 | 2.5 | 1 | 2 | 0.5 | 5 | 1 | 11 | 48 | 5 | 20 | 41 |
3459 | 软件工程基础 第3次个人作业 | 2020-03-10 18:24 | 好 | 0.5 | 0.5 | 3 | 3.5 | 2 | 2 | 0.5 | 5 | 1 | 13 | 48 | 3.333333333 | 20 | 41.33333333 |
3461 | 软工个人项目作业 | 2020-03-10 18:29 | 中上 | 0.5 | 0.5 | 2.5 | 2 | 1 | 2 | 0.5 | 3 | 1 | 10 | 37 | 15.41666667 | 28.41666667 | |
3492 | 上手软件工程,PSP初体验!——记2020BUAA软工个人项目作业 | 2020-03-10 18:59 | 中上 | 0.5 | 0.5 | 3 | 3 | 2.5 | 2 | 0.5 | 4 | 1 | 13 | 48 | 3.333333333 | 20 | 40.33333333 |
3493 | 软工第三次作业——个人项目作业 | 2020-03-10 17:29 | 中上 | 0.5 | 0.5 | 2 | 3 | 2 | 2 | 0.5 | 5 | 1 | 11.5 | 39 | 16.25 | 32.75 | |
3524 | 2020软工个人项目作业 | 2020-03-09 19:05 | 中上 | 0.5 | 0.5 | 2.5 | 2.5 | 3 | 2 | 0.5 | 5 | 1 | 12.5 | 48 | 5 | 20 | 42.5 |
3532 | 2020软工-个人项目作业 | 2020-03-10 17:26 | 中上 | 0.5 | 0.5 | 2.5 | 2 | 2 | 2 | 0.5 | 5 | 1 | 11 | 48 | 3.333333333 | 20 | 39.33333333 |
1102 | 软件工程个人项目作业 | 2020-03-10 18:26 | 中上 | 0.5 | 0.5 | 2 | 2.5 | 1 | 1.5 | 0.5 | 4 | -1 | 7.5 | 0 | 0 | 11.5 |
三、累计得分图
四、小黄衫
在本次作业中,课程组决定给总分数最高的三位同学颁发领跑小黄衫,以资鼓励:
- 17373071 刘阳(https://github.com/xiaomaoaichiyu/BUAA_SE_work1_person 、 https://www.cnblogs.com/xiaomaoaichiyu/p/12455852.html)
- 16021088 张文煊(https://github.com/zwx980624/IntersectProject 、 https://www.cnblogs.com/old-jipa-deng/p/12453287.html)
- 16191051 朱雨聪(https://github.com/Eadral/SE_Individual_Project 、 https://www.cnblogs.com/wheremeow/p/12456178.html)
五、算法
朴素算法
对于所有几何对象两两配对求出交点后排序去重。时间复杂度 $O(n^2 + n^2 \log n^2)$。
扫描线算法
扫描线算法的关键思想为假设有一条被称为扫描线的竖直线从 x 轴负无穷远处向正无穷远处移动,同时用数据结构维护几何对象在竖直线上交点的位置相对关系。
关于交点的探测,由于扫描线会从左到右扫描过所有状态,因此只需要关注“局部”的未来是否有交点即可(这些交点也是会改变扫描线上交点相对位置的关键点),即只需要探测相邻对象是否有交点即可。
由于只有在事件点上(几何对象同扫描线从有交点状态到无交点状态,几何对象之间的相交等等)几何对象在竖直线上交点的相对顺序才会发生变化,因此扫描线的状态改变量级为 $O(n + m)$,其中 $n$ 为几何对象个数,$m$ 为交点数目。如果采用单次操作 $O(\log)$ 级别的数据结构维护竖直线上的交点位置,则总复杂度为 $O((n + m) \log n)$。
一些实现上的注意事项:
- 对于 $x$ 相同的事件点,假设扫描线有一个无限小的倾角考虑这些事件点造成的影响;
- 对于 $x$ 坐标相同的关键点需要一同处理,否则复杂度不对。考虑所有直线相交于一点,如果每次只调整两条线在扫描线上的位置,则复杂度退化为 $O(n^2 \log n)$;
- 将圆切割成两个半圆。
这里给出算法层面上的一些参考资料:
- https://en.wikipedia.org/wiki/Bentley-Ottmann_algorithm
- http://www.cs.cmu.edu/afs/cs/academic/class/15750-s18/ScribeNotes/lecture14.pdf
精度
浮点数精度
首先可以运用语言提供的 double
类型替换默认的 float
提高精度。
其次由于浮点数的计算是有误差的,因此即使答案是同一个数,根据计算途径的不同,其最终结果的机器表示也有可能不同,导致在用语言的比较操作符对比结果时产生不一致的结果。
为了容忍这部分误差,需要设定一个可允许的误差量 $\epsilon$,在该误差的基础上重写浮点数的比较操作。
关于浮点数如何进行比较也需要格外注意,因为浮点数的表示方式,因此在计算时只能保持相对精度。对于绝对精度,除非问题本身有相应的数值界,否则很难保证。因为前述的原因,所以在比较大数之间的误差和小数之间的误差的时候,所能容忍的范围是不同的,此处给出相关资料供同学们参考:https://stackoverflow.com/questions/4915462/how-should-i-do-floating-point-comparison/32334103#32334103。
算法所需精度
十分出人意料的是,扫描线算法需要的数值精度十分高。一个朴素的扫描线算法实现需要的精度为输入坐标表示的 5 倍(https://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm#Numerical_precision_issues)。
考虑到本次项目在实现扫描线算法时已达到了所需要的区分度,没有必要在精度的问题上为难大家,因此除了一些验证相交正确性的类似单元测试的小数据为手工构造外,其余所有数据均以随机的方式生成。然而即使如此,各位同学在实现的同时也需要尽力去提升精度,尤其是关于圆的附加题。
六、源代码管理
README
一个项目的 README 是使人了解项目的第一步,也是整个项目资料的一个索引。通常一个好的 README 会描述以下事项:
- 项目名称,
- 项目动机,
- 项目特点,
- 如何安装,
- 如何从源代码构建,
- 如何使用,
- ...
一些项目可能会适当增减上述所列的条目,不过核心是让人对项目有一个全局的大致了解,同时可以很快作为用户/开发者上手。
在本次项目中,有一些同学的 README 写的相对较好,这里给出对应的项目链接供同学们参考:
- 16191051 朱雨聪:https://github.com/Eadral/SE_Individual_Project
- 17373432 陈弛:https://github.com/17373432/Project1
- 17373349 胡彬彬(给出了编译说明):https://github.com/mushangui/IntersectProject
除此以外,这里有一些很好的阅读材料供同学们参考:
- Make a README: https://www.makeareadme.com/
- A Beginners Guide to writing a Kickass README: https://medium.com/@meakaakka/a-beginners-guide-to-writing-a-kickass-readme-7ac01da88ab3
- A template to make good README.md: https://gist.github.com/PurpleBooth/109311bb0361f32d87a2
项目结构
项目结构(即何种代码置于哪个文件夹下)具体如何组织在实践中通常是一个观点导向的问题,主要的影响因素包括语言、行业习惯和个人观点等。然而拥有一个清晰的项目则无一是一个共识。这里给出一些 C/C++ 的项目结构阅读材料,仅供参考:
- https://github.com/TheLartians/ModernCppStarter
- https://api.csswg.org/bikeshed/?force=1&url=https://raw.githubusercontent.com/vector-of-bool/pitchfork/develop/data/spec.bs
- https://medium.com/heuristics/c-application-development-part-1-project-structure-454b00f9eddc
commit 信息
commit 信息是对改动的一个总结,拥有结构良好的 commit 信息对于开发者熟悉项目历史以及提供改动的上下文信息非常有帮助。
git commit
的 manpage
中推荐将 commit 信息分为两部分:标题行和内容。其中标题行简述本次 commit 的作用,内容则对本次 commit 进行较为详细的描述。由于标题行通常用作一些 git GUI 的显示,因此在长度上有推荐的上限。
这里给出一些有关 commit 信息的阅读材料:
-
How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
-
Conventional Commits: https://www.conventionalcommits.org/en/v1.0.0-beta.4/
在本次项目中,有一些同学的 commit 信息写的相对较好,这里给出对应的项目链接供同学们参考:
- 16191051 朱雨聪:https://github.com/Eadral/SE_Individual_Project
- 17373078 吴昭邦:https://github.com/yanhuaqaq/BUAASE-HW1-IntersectProject
- 17373072 苏海翔:https://github.com/LastWhisper1/IntersectionCounter
Git 仓库应维护的内容与 .gitignore
Git 仓库应该维护的内容
通常来说,一个代码的 Git 仓库应该维护所有和项目相关的“源”文件,其中包括:
- README,
- 源代码,
- 测试源代码,
- 第三方依赖的源代码/二进制(比如特定版本的 DLL 库),
- 编译链相关配置文件(比如
CMakeLists.txt
), .gitignore
文件,- Linter 相关配置文件,
- ...
而不应该维护所有中间生成文件以及一些和开发环境强相关的内容,包括:
- 一些只对本机起作用的绝对路径,
- 编辑器维护的备份文件(比如 Vim 的以
~
结尾的文件), - 中间的编译结果,
- ...
.gitignore
.gitignore
文件是一个纯文本文件,其作用是指定 Git 忽略其内描述的特定文件。
通过适当的维护 .gitignore
文件,可以避免将上节中提到的不应维护的内容以外添加进 Git 仓库,同时也可以是使 git status
的信息更加精简。
通常,对于项目相关的一些可能产生但不需要维护的文件,比如中间的编译结果,需要添加至 .gitignore
。同时,.gitignore
也应该成为 Git 仓库维护的部分。
对于另外一些和项目不直接相关,同时不应该被仓库维护的文件,是否需要添加至 .gitignore
中视开发所在环境存在商榷的余地。https://stackoverflow.com/a/5765663/710050 分享了一些这方面的看法。
以下是关于 .gitignore
的相关一些阅读资料:
- gitignore 官方文档:https://git-scm.com/docs/gitignore
- gitignore 的一些模板:https://github.com/github/gitignore
作者: braveTester(作业总结部分)、馥世吾爱(得分部分)