|
|
| (21 intermediate revisions by 3 users 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]] |
| ===11/9/10===
| |
| author：yonghang
| |
| 今天把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 |
| | :true name:徐勇航 |
| | :nickname:y0ukn0w,xyhchess |
| | :E-mail:xuyonghang@gmail.com |
|
| |
|
| | *;Member 2 |
| | :name:温开源 |
| | :nickname:NULL |
| | :E-mail:weikaiyuan123@gmail.com |
|
| |
|
| =Links= | | =Links= |
| Line 74: |
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] |
| ===11/9/10===
| | *[http://www.mtime.com mtime] |
| My progress by kaiyuan
| |
| 这次进展主要是尝试使用申请空间次数更少的方式尝试编写FSK，主要思想还是没有发生变化，与前面代码的不同在于确定完成每个桶内可能散进的key的个数后，使用一个统一的空间table来存储所有的key。虽然代码的实现是成功的，但是总结下来，这种方式在编写FSK的时侯与先前的对每个桶申请空间的方式并没有太大效率优势，我总结可能是我的代码实现中存在以下影响效率和影响理解的地方：
| |
| #对桶内数据的个数的统计和初始化桶内字段时的效率降低：因为我们要在统计完每个桶的可能散进的数时存在以下逻辑，首先我们必须待每个数都确定它的桶号，才能统计处每个桶中可能有多少数，这里显然要用到一个循环；接下来我们要做的是另外的一个循环计算每个桶容量的平方和；确定平方和之后我们才可以确定总的table的大小；确定完每个table的大小后，我们还要使用一个循环来确定每个桶中起始位置在table中的起点。事实上这一步就已经比前面所写的代码多了两重层循环（计算平方和的运算和计算桶地址起点的运算），我们可以这样考虑，每次循环与我们的现有数据量是正比关系，即循环时间开销是O(n),这对于在运算大量数据的情形下来说确实不是一个好消息。
| |
| #当我们第一次散列不成功是重新散列的代价很大：可以想象如果散列不成功，我们必须重复上述的步骤之后，再进行另一次散列，这里可能就会再次出现上述问题。而在单独申请空间的代码中，我们一旦散列不成功，可以将单个单个的桶进行处理而不必以下全部处理，这也是效率降低的一方面。
| |
| #每个桶的起始地址和table中的地址对应问题：这显然增加程序的
| |
| | |
| 当然使用这种方法也存在着优点，从总体上来看：总体存储有助于管理，申请释放都比较容易。另外，我们要实现数据接口，即散列的数据支持从外部以多种方式输入，在这种情况下，使用总体的申请空间显然更方便。
| |
| 目前代码的效率在实践上还不够高，但在不断修改之中，希望可以达到一个优缺点良好的平衡。
| |