创新计划

What We'd Like to Say

• Theory is modern art
• Attitude decides everthing

Document

Literature Review

Literature Review

Member

Member 1

name:徐勇航

---

E-mail:xuyonghang@gmail.com

Member 2

name:温开源

---

E-mail:weikaiyuan123@gmail.com

Progress Log

11/9/10

author：yonghang

今天把ubuntu重新安装了一遍，将分区大小改为了6GB。在重新装的时候遇到了一点问题，可以上网,但update manager无法正常工作，正在国外论坛查找解决方案，不知怎么就突然好了，下次遇到还是没有办法。 在windows中的文件和ubuntu中的文件互相移动后（通过将磁盘mount的方式），如果再次访问，经常会出现permission denied的情况，不是太建议这么做。 下面介绍gnu库的基本安装方法

1. 从gnu的ftp上下载你所需要的库，以gsl为例
2. 将压缩包解压至非mount设备的地方，比如home/y0ukn0w/Documents //y0ukn0w is my username
3. cd /home/Documents/gsl-1.14
   chmod a+x configure //有时不需要这一句
   ./configure
   make
   make install
4. ps : 可以打开文件夹，找到对应的INSTALL，里面会有说明
5. 在连接的时候可能还是会出错。这时，可以选择输入相应的指令；如果你用的是codeblocks，那么，settings->compilers and debugger settings->linker libraries,在这里加入相应的lib

下面介绍gsl/gsl_rng.h的简单使用方法 代码如下

#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;
}

在写需要template的头文件时，为方便调试，往往通过修改头文件的方式来完成。 现在想来，是自己的接口设计的还不够好。 现在数据的输入输出打算这样完成：

1. 一个程序负责生成随机数，将其输入到data.in文件中
2. 主程序中有一个函数ReadData，测试程序中打开data.in和data.out，调用ReadData，将数据读入，处理后输出到data.out中。

--You will when you believe 13:03, 8 November 2010 (UTC)

---

Links

• wikipedia
• google
• lilybbs
• songshuhui:)

11/9/10

 My progress   by kaiyuan

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

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

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