Kaiyuan

My progress by kaiyuan

这次进展主要是尝试使用申请空间次数更少的方式尝试编写FSK，主要思想还是没有发生变化，与前面代码的不同在于确定完成每个桶内可能散进的key的个数后，使用一个统一的空间table来存储所有的key。虽然代码的实现可以完成的，但是总结下来，这种方式在编写FSK的时侯与先前的对每个桶申请空间的方式并没有太大效率优势，我总结可能是我的代码实现中存在以下影响效率和影响理解的地方：

1. 对桶内数据的个数的统计和初始化桶内字段时的效率降低：因为我们要在统计完每个桶的可能散进的数时存在以下逻辑，首先我们必须待每个数都确定它的桶号，才能统计处每个桶中可能有多少数，这里显然要用到一个循环；接下来我们要做的是另外的一个循环计算每个桶容量的平方和；确定平方和之后我们才可以确定总的table的大小；确定完每个table的大小后，我们还要使用一个循环来确定每个桶中起始位置在table中的起点。事实上这一步就已经比前面所写的代码多了两重层循环（计算平方和的运算和计算桶地址起点的运算），我们可以这样考虑，每次循环与我们的现有数据量是正比关系，即循环时间开销是O(n),这对于在运算大量数据的情形下来说确实不是一个好消息。
2. 当我们第一次散列不成功是重新散列的代价很大：可以想象如果散列不成功，我们必须重复上述的步骤之后，再进行另一次散列，这里可能就会再次出现上述问题。而在单独申请空间的代码中，我们一旦散列不成功，可以将单个单个的桶进行处理而不必以下全部处理，这也是效率降低的一方面。
3. 每个桶的起始地址和table中的地址对应问题：这显然增加程序的复杂性，使得程序理解性和可读性降低。

当然使用这种方法也存在着优点，从总体上来看：总体存储有助于管理，申请释放都比较容易。另外，我们要实现数据接口，即散列的数据支持从外部以多种方式输入，在这种情况下，使用总体的申请空间显然更方便。 目前代码的效率在实践上还不够高，但我还在不断修改之中，希望可以达到一个优缺点良好的平衡。

11/10/10

今天的主要进展是对各自代码的修改，我和徐勇航各自采取不同的方式来进行代码编写和测试，最后将会比较各自的效率从而选取最好的程序。 我现在面临的主要是效率不够问题和以及随机数取值随机性不够好的问题。

1. 针对效率不够好的问题，今天对代码做了以下改正：在初始化table的函数Create里面进行改进，不再使用count数组来计数，而是直接使用每个bucket的size字段进行计数。这样做有好处如下：首先，不使用count方式减少了一次申请数组空间的时间，减少了空间的使用；减少了给每个bucket赋容量的一个O（n）循环时间，减少了给每个count初始化的一个O(n)循环时间时间，这显然会在在效率上有所提升。但同时也 可以看到，这样做也存在不足：首先，不使用count字段的话，每次在使用bucket的size进行计数时，必须保证size的初始值为零，那么这就意味着我们要对其进行初始化（为了保证我们可以不浪费初始化的时间，我决定每次重新散列的时候就删掉原来的bucket，再申请一个bucket，这样可以利用他的初始化构造函数自然地初始化size，而不用显式初始化，我认为这样毕竟比做个循环时间效率高吧）；其次，直接使用size进行计数的话，我们只能使用size记录散在桶中的个数，而不能记录个数的平方，这样，在代码的很多阶段，将会导致复杂性增加（这个不影响多少效率，也不必考虑太多）。
2. 针对随机数的问题，明显在代码运行的时候可以看到，随机数的随机性不好，将会导致程序的执行时间大大加长，而今天我的执行并未使用非常良好的随机数，也导致程序效率理想（这点明天就可以改正在ubuntu使用gsl)。此外还必须完成素数的选择，经过试验，我发现使用一个素数在函数内，能很好的提升散列的效果。

另外有点疑惑，从理论上来讲，碰撞的概率不是二分之一吗。为什么在程序的运行阶段，碰撞发生的概率会很大了，不明白怎么会多次重新散列都会有碰撞产生了？今天先到此为止吧，这样看来明天要完成两样工作：第一，使用gsl随机数将程序完全调试好；第二，尽量找到合适素数的生成方式，在函数中加入素数，希望可以提高效率。

We will complete it soon！^-^