thoughtworks作业

thoughtworks作业

待完善的内容

数据结构中没有存储日期，仅存储了所有日期中最新的日期。如果要求输出日期，就需要设计数据结构存储它。
输入的内容仅当自身抛出异常时才会返回"Invalid format."，

运行环境

java version "1.8.0_91"
Java(TM) SE Runtime Environment (build 1.8.0_91-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)

第三方包(已加入工程)

common-io-2.5
hamcrest-core-1.3
junit-4.1.1

本markdown文件的在线版本

https://www.zybuluo.com/xialu/note/506915

测试方法

导入thoughtworks java project。在类UnitTest内运行单元测试。
该类内有5个预置的测试方法：

testValidData1：观测内容正常，测试查询第一条观测。
testValidData2：观测内容正常，测试查询第七条观测。
testValidData3：观测内容正常，测试查询最后一条观测。
testConflictData：数据有冲突，查看返回值是否符合此时的要求。
testInvalidFormat：格式无效，查看是否返回“Invalid format.”

自定义测试

最后，我还在UnitTest类内准备了一个方法用于自定义测试。

@Ignore
@Test
public void selfDefinedTest() throws IOException{
        //需要自定义测试内容时，文件的地址
        String filePath = "";
        //预计输出结果
        String expectedResult = "";
        //待查询的记录id
        String qSSId = "";
        ...
}

使用步骤：

1. 删除@Ignore注解。
2. 按照注释提示填写变量值。
3. 运行单元测试。

数据结构的讨论：

背景/变量 假设：

设所有动物集合为$animals\in \{a_1,a_2...a_m\}$
监控过程中动物数量：m个。
设监控记录的集合为$IDs\in \{ID_1,ID_2...ID_n\}$
监控记录数量：n个。
对于某个动物$a_i$与任意$ID_j$，假设$ID_{a_i,j}$为该动物在$ID_j$时最后一次移动的监控ID
设查询ID为$ID_q$
假设$m\ll n$。

存储移动信息：

如果我们按照类似输入的格式进行存储，即对于某个动物$a_i$：
1. 存储$a_i$起始时刻的坐标。$L(a_i,ID_1)$
2. 当$a_i$移动时，存储其移动的坐标。$Move(a_i,ID_j)$
进行查询时，需要依次查询动物$a_i$的监控信息，并更新动物位置，$ID_1,ID_2...,ID_{a_i,j}$直到$ID_{a_i,j}\le ID_q$

数据结构：链表
查询形式：顺序访问，时间复杂度 $T(m,n)=O(n)$。
空间复杂度：$O(n)<S(m,n)<O(mn)$，当$m\ll n$，时，$S(m,n)\approx O(n)$

存储位置信息：

1. 存储$ID_j$与$ID_{a_i,j}$的对应关系，即：MAP($ID_j,ID_{a_i,j}$)。
2. 存储$ID_{a_i,j}$时动物$a_i$的位置。MAP$(ID_{a_i,j},L(a_i,ID_{a_i,j}))$
   查询时依次访问两个MAP可以得到结果。

数据结构：MAP
查询形式：随机访问，时间复杂度 $O(1)$
空间复杂度：$O(n)$

由上讨论可知，存储位置信息消耗的空间复杂度没有明显的增高，同时可以获得更好的时间复杂度。

不规范输入的类型：

当以下错误被考虑为数据错误：
1. 后输入的时间早于先输入的时间。
2. 动物移动时给出的旧坐标位置信息有误。
3. 输入的单次观察中出现的动物名发生了重复。
4. 对于刚进入区域的动物，给出了移动信息。

其他情况输出：Invalid forma。