imported>Y0ukn0w |
imported>Y0ukn0w |
| (16 intermediate revisions by the same user not shown) |
| Line 3: |
Line 3: |
| *'''''Attitude decides everthing''''' | | *'''''Attitude decides everthing''''' |
|
| |
|
| =Document= | | = Progress Log = |
| ===Literature Review===
| |
| [[Literature Review]]
| |
|
| |
|
| =Member=
| | *[[Yonghang]] |
| === ===
| |
| ;Member 1
| |
| :name:徐勇航
| |
| ----
| |
| :E-mail:xuyonghang@gmail.com
| |
|
| |
|
| === ===
| | *[[Kaiyuan]] |
| ;Member 2
| |
| :name:温开源
| |
| ----
| |
| :E-mail:weikaiyuan123@gmail.com
| |
|
| |
|
| =Progress Log=
| | *[[current target]] |
| ===My Progress by yonghang===
| |
| ====11/9/10====
| |
| 今天把ubuntu重新安装了一遍，将分区大小改为了6GB。在重新装的时候遇到了一点问题，可以上网,但update manager无法正常工作，正在国外论坛查找解决方案，不知怎么就突然好了，下次遇到还是没有办法。
| |
| 在windows中的文件和ubuntu中的文件互相移动后（通过将磁盘mount的方式），如果再次访问，经常会出现permission denied的情况，不是太建议这么做。
| |
| 下面介绍gnu库的基本安装方法
| |
| #从gnu的ftp上下载你所需要的库，以gsl为例
| |
| #将压缩包解压至非mount设备的地方，比如home/y0ukn0w/Documents //y0ukn0w is my username
| |
| #cd /home/Documents/gsl-1.14<br /> chmod a+x configure //有时不需要这一句 <br /> ./configure <br /> make <br /> make install
| |
| #ps : 可以打开文件夹，找到对应的INSTALL，里面会有说明
| |
| #在连接的时候可能还是会出错。这时，可以选择输入相应的指令；如果你用的是codeblocks，那么，settings->compilers and debugger settings->linker libraries,在这里加入相应的lib
| |
|
| |
|
| 下面介绍gsl/gsl_rng.h的简单使用方法
| | =Document= |
| 代码如下
| |
| #include <stdio.h>
| |
| #include <gsl/gsl_rng.h>
| |
| #include<time.h>
| |
| int
| |
| main (void)
| |
| {
| |
| const gsl_rng_type * T;
| |
| gsl_rng * r;
| |
| T = [[gsl_rng_rand]]; //可以将其设置为不同的值，以获取不同的随机数,如改为gsl_rng_randu,gsl_rng_knuthran2002,具体参考manul
| |
| r = gsl_rng_alloc (T);
| |
| int i, n = 10;
| |
| [[gsl_rng_set]](r,int(time(NULL))); //设置随机数seed
| |
| gsl_rng_env_setup();
| |
| for (i = 0; i < n; i++)
| |
| {
| |
| double u = gsl_rng_uniform (r);
| |
| printf ("%.5f\n", u);
| |
| }
| |
| double u = gsl_rng_uniform(r);
| |
| printf("%.5f\n",u);
| |
| gsl_rng_free (r);
| |
| return 0;
| |
| }
| |
|
| |
|
| | *[[Literature Review]] |
| | *[[FSK Hashing]] |
| | *[[Dynamic Perfect Hashing]] |
| | *[[Cuckoo Hashing]] |
|
| |
|
| 在写需要template的头文件时，为方便调试，往往通过修改头文件的方式来完成。
| | =Member= |
| 现在想来，是自己的接口设计的还不够好。
| |
| 现在数据的输入输出打算这样完成：
| |
| #一个程序负责生成随机数，将其输入到data.in文件中
| |
| #主程序中有一个函数ReadData，测试程序中打开data.in和data.out，调用ReadData，将数据读入，处理后输出到data.out中。
| |
| --You will when you believe 13:03, 8 November 2010 (UTC)
| |
|
| |
|
| ----
| | *;Member 1 |
| ===My progress by kaiyuan===
| | :true name:徐勇航 |
| 这次进展主要是尝试使用申请空间次数更少的方式尝试编写FSK，主要思想还是没有发生变化，与前面代码的不同在于确定完成每个桶内可能散进的key的个数后，使用一个统一的空间table来存储所有的key。虽然代码的实现可以完成的，但是总结下来，这种方式在编写FSK的时侯与先前的对每个桶申请空间的方式并没有太大效率优势，我总结可能是我的代码实现中存在以下影响效率和影响理解的地方：
| | :nickname:y0ukn0w,xyhchess |
| #对桶内数据的个数的统计和初始化桶内字段时的效率降低：因为我们要在统计完每个桶的可能散进的数时存在以下逻辑，首先我们必须待每个数都确定它的桶号，才能统计处每个桶中可能有多少数，这里显然要用到一个循环；接下来我们要做的是另外的一个循环计算每个桶容量的平方和；确定平方和之后我们才可以确定总的table的大小；确定完每个table的大小后，我们还要使用一个循环来确定每个桶中起始位置在table中的起点。事实上这一步就已经比前面所写的代码多了两重层循环（计算平方和的运算和计算桶地址起点的运算），我们可以这样考虑，每次循环与我们的现有数据量是正比关系，即循环时间开销是O(n),这对于在运算大量数据的情形下来说确实不是一个好消息。
| | :E-mail:xuyonghang@gmail.com |
| #当我们第一次散列不成功是重新散列的代价很大：可以想象如果散列不成功，我们必须重复上述的步骤之后，再进行另一次散列，这里可能就会再次出现上述问题。而在单独申请空间的代码中，我们一旦散列不成功，可以将单个单个的桶进行处理而不必以下全部处理，这也是效率降低的一方面。
| |
| #每个桶的起始地址和table中的地址对应问题：这显然增加程序的复杂性，使得程序理解性和可读性降低。
| |
|
| |
|
| 当然使用这种方法也存在着优点，从总体上来看：总体存储有助于管理，申请释放都比较容易。另外，我们要实现数据接口，即散列的数据支持从外部以多种方式输入，在这种情况下，使用总体的申请空间显然更方便。
| | *;Member 2 |
| 目前代码的效率在实践上还不够高，但我还在不断修改之中，希望可以达到一个优缺点良好的平衡。
| | :name:温开源 |
| | | :nickname:NULL |
| ===11/10/10===
| | :E-mail:weikaiyuan123@gmail.com |
| | |
| ====By kaiyuan====
| |
| 今天的主要进展是对各自代码的修改，我和徐勇航各自采取不同的方式来进行代码编写和测试，最后将会比较各自的效率从而选取最好的程序。
| |
| 我现在面临的主要是效率不够问题和以及随机数取值随机性不够好的问题。
| |
| #针对效率不够好的问题，今天对代码做了以下改正：在初始化table的函数Create里面进行改进，不再使用count数组来计数，而是直接使用每个bucket的size字段进行计数。这样做有好处如下：首先，不使用count方式减少了一次申请数组空间的时间，减少了空间的使用；减少了给每个bucket赋容量的一个O（n）循环时间，减少了给每个count初始化的一个O(n)循环时间时间，这显然会在在效率上有所提升。但同时也 可以看到，这样做也存在不足：首先，不使用count字段的话，每次在使用bucket的size进行计数时，必须保证size的初始值为零，那么这就意味着我们要对其进行初始化（为了保证我们可以不浪费初始化的时间，我决定每次重新散列的时候就删掉原来的bucket，再申请一个bucket，这样可以利用他的初始化构造函数自然地初始化size，而不用显式初始化，我认为这样毕竟比做个循环时间效率高吧）；其次，直接使用size进行计数的话，我们只能使用size记录散在桶中的个数，而不能记录个数的平方，这样，在代码的很多阶段，将会导致复杂性增加（这个不影响多少效率，也不必考虑太多）。
| |
| #针对随机数的问题，明显在代码运行的时候可以看到，随机数的随机性不好，将会导致程序的执行时间大大加长，而今天我的执行并未使用非常良好的随机数，也导致程序效率理想（这点明天就可以改正在ubuntu使用gsl)。此外还必须完成素数的选择，经过试验，我发现使用一个素数在函数内，能很好的提升散列的效果。
| |
| 另外有点疑惑，从理论上来讲，碰撞的概率不是二分之一吗。为什么在程序的运行阶段，碰撞发生的概率会很大了，不明白怎么会多次重新散列都会有碰撞产生了？今天先到此为止吧，这样看来明天要完成两样工作：第一，使用gsl随机数将程序完全调试好；第二，尽量找到合适素数的生成方式，在函数中加入素数，希望可以提高效率。
| |
| | |
| We will complete it soon！^-^
| |
|
| |
|
| =Links= | | =Links= |
| Line 92: |
Line 35: |
| *[http://bbs.nju.edu.cn lilybbs] | | *[http://bbs.nju.edu.cn lilybbs] |
| *[http://songshuhui.net songshuhui:)] | | *[http://songshuhui.net songshuhui:)] |
| | *[http://innov.nju.edu.cn innovation project] |
| | *[http://www.mtime.com mtime] |