创新计划

From TCS Wiki
Revision as of 07:12, 9 November 2010 by 172.25.49.151 (talk)
Jump to navigation Jump to search

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

11/9/10

 My progress   by kaiyuan

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

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

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