Yonghang: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Y0ukn0w
No edit summary
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
= 2010 =  
= 2010 =  
== 12/15 ==
[[vim常用命令]]
== 12/13 ==
看了桶排序和基数排序,突然更深地明白了bucket的思想
== 12/1 ==
到目前为止的工作中,获得一个指定范围的素数是我们目前碰到的最大的问题,至今也没有真正解决,miller-rabin的成功率只有3/4,而且数很大后,素数的密度变低,效率是否好也是个问题。
代码的实现事实上只是很低级的事,素数的问题严重影响了我们的进度,所以我们最近在看dynamic perfect hashing的论文。


== 11/25 ==
== 11/25 ==
Line 5: Line 15:
#关于创新项目,应该是由我和温主导的一件事,老师的作用应该是在我们困惑的时候指一下路。要做的事不能当做homework,等着老师来布置,这是非常幼稚的一种心态。
#关于创新项目,应该是由我和温主导的一件事,老师的作用应该是在我们困惑的时候指一下路。要做的事不能当做homework,等着老师来布置,这是非常幼稚的一种心态。
#关于考试的复习,赵建华老师说过,“过度的复习是一种作弊”,如果真正掌握的好,考前是应该不用花这么大力气的,平时应该更用心才是。
#关于考试的复习,赵建华老师说过,“过度的复习是一种作弊”,如果真正掌握的好,考前是应该不用花这么大力气的,平时应该更用心才是。
今天看了别人的bloom filter实现。bloom filter的原理上周六用30分钟看了一下。
这份代码是用C写的,我从中学到了不少东西,其中包括:
#[[在C中如何写参数不确定的函数]],类似于printf之类
#有效地利用typedef和define可以使你的代码看起来更优美
#一份好的代码需要具有很好的健壮性
#size_t的使用(经搜索发现能更好地为跨平台服务),在32位机上往往是typedef unsigned int size_t,4个byte,64位机上就是8个byte
#好的测试文件大致应该怎么写(读file,充分的数据量)
#得到了两个简便的hash函数


== 11/22-11/24 ==
== 11/22-11/24 ==

Latest revision as of 02:10, 15 December 2010

2010

12/15

vim常用命令

12/13

看了桶排序和基数排序,突然更深地明白了bucket的思想

12/1

到目前为止的工作中,获得一个指定范围的素数是我们目前碰到的最大的问题,至今也没有真正解决,miller-rabin的成功率只有3/4,而且数很大后,素数的密度变低,效率是否好也是个问题。 代码的实现事实上只是很低级的事,素数的问题严重影响了我们的进度,所以我们最近在看dynamic perfect hashing的论文。

11/25

上次至今天由于期中考试的复习,拖延了不少时间,11/24刚刚考完最后一门概率论,有一些随想,写在下面

  1. 关于创新项目,应该是由我和温主导的一件事,老师的作用应该是在我们困惑的时候指一下路。要做的事不能当做homework,等着老师来布置,这是非常幼稚的一种心态。
  2. 关于考试的复习,赵建华老师说过,“过度的复习是一种作弊”,如果真正掌握的好,考前是应该不用花这么大力气的,平时应该更用心才是。

今天看了别人的bloom filter实现。bloom filter的原理上周六用30分钟看了一下。 这份代码是用C写的,我从中学到了不少东西,其中包括:

  1. 在C中如何写参数不确定的函数,类似于printf之类
  2. 有效地利用typedef和define可以使你的代码看起来更优美
  3. 一份好的代码需要具有很好的健壮性
  4. size_t的使用(经搜索发现能更好地为跨平台服务),在32位机上往往是typedef unsigned int size_t,4个byte,64位机上就是8个byte
  5. 好的测试文件大致应该怎么写(读file,充分的数据量)
  6. 得到了两个简便的hash函数

11/22-11/24

只剩最后一门概率论,时间较为充裕。FSK的原理已经很清楚了,但我们在做这件事的过程中其实相当不productive,可能有这么几个原因

  1. 对于C++语言本身,认识的还不够深刻,特别是真正用面向对象思想做一件有用的事时(而不是只是完成homework)
  2. 对于FSK的原理,没有仔细地去看。a,b,p的取值范围在老师的wiki上写的非常清楚,但就是去认真看

这三天在复习《thinking in C++》一书,有了一些与第一次看时不同的体会。

11/17

insterested in bloom flitters :)

11/13

经过与老师讨论,发现有p和没p的区别是巨大的,有p之后可以认为理想的状态下perfect hash的概率是二分之一,无p则可能很小,所以才会一直卡在一个bucket内。

重新确认了a,b,p的值域:a [1,p-1],b [0,p-1],p bigger than universe.

现在的程序效率较好,但还有待于进一步检验

11/12

把重写的FSK调试了一下,总是觉得不该时间这么长

11/11

读数据的接口打算使用fstream,这需要重复读取数据,在写一个简单的测试程序时遇到了不少问题

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int main()
{
   ifstream in("data.in");
   ofstream out("data.out");
   string s;
   while(in>>s)
   {
       out<<s<<' ';
   }
   in.seekg(0,ios::beg);
   out.seekp(0,ios::end);
   while(in>>s)
   {
       out<<s;
   }
   in.close();
   out.close();
   return 0;
}

原本应该在data.out中输出两遍data.in的数据,但是实际上只输出了一遍。 也就是说, in.seekg(0,ios::beg);这行没能把读指针指向开头,经过单步调试也未能解决 和大三的学长讨论了很久没有结果

后来在网上搜索,看到一个网页

fstream存在状态:
当被打开第一次以后,状态处于错误状态。
fstream错误状态
fail() , eof() , bad();
failbit , eofbit ,badbit 。
正确状态
good(),
good = not(fail or eof or bad)

实际上文件读完的时候fail会自动置为true,所以可以使用clear函数,将fail设置为false.测试代码如下,只取部分

   ifstream in("data.in",ios::binary);
   cout << "isfail   " << in.fail() << endl;
   cout << "isbad   " << in.bad() << endl;
   cout << "iseof   " << in.eof() <<endl;
   cout << "isgood   "<< in.good() << endl;
   in.clear();
   cout << "isfail   " << in.fail() << endl;
   cout << "isbad   " << in.bad() << endl;
   cout << "iseof   " << in.eof() <<endl;
   cout << "isgood   "<< in.good() << endl; 

输出结果为

isfail   1
isbad   0
iseof   1
isgood   0
isfail   0
isbad   0
iseof   0
isgood   1


写了一个rabin-miller的测试程序,并安装了gmp库,代码就不附在这里了

11/10

11/11 补:昨天把kaiyuan写的代码看了一遍,修改了一下,把gsl_rng.h的东西用了进去,转为ubuntu下可以运行的版本 同样的,关于程序运行的次数,我也有疑问,为什么每次的次数感觉远大于两次

11/9

今天把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;
}

gsl_rng.h的部分可选用参数如下

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

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

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