Categories
读书有感

抄抄笔记——格雷码

想起来差不多十年前从图书馆里面一本又一本的借出来各种算法和数据结构的书籍,却从来没读完过...

今天看到一个东西,格雷码。看了半天硬是没怎么看懂(除了第一种递归的办法)...一看到二进制我就懵掉了,脑子里面一点线索都没有的悲催感。想想这块儿的知识应该也会挺有意思的吧?什么二叉树啊,红黑树啊,好像我都完全不了解是怎么个玩法。唉。

抄一点百度百科的笔记。争取过段时间再来看,能多看懂一些...现在脑子里面完全没有一点感觉。

递归生成码表

这种方法基于格雷码是反射码的事实,利用递归的如下规则来构造:
  1. 1位格雷码有两个码字
  2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字,按顺序书写,加前缀0
  3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字,按逆序书写,加前缀1[3] 
2位格雷码 3位格雷码 4位格雷码 4位自然二进制码
00
01
11
10
000
001
011
010
110
111
101
100
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

异或转换

二进制码→格雷码(编码)
此方法从对应的n位二进制码字中直接得到n位格雷码码字,步骤如下:
  1. 对n位二进制的码字,从右到左,以0到n-1编号
  2. 如果二进制码字的第i位和i+1位相同,则对应的格雷码的第i位为0,否则为1(当i+1=n时,二进制码字的第n位被认为是0,即第n-1位不变)[3] 
公式表示

(G:格雷码,B:二进制码)

例如:二进制码0101,为4位数,所以其所转为之格雷码也必为4位数,因此可取转成之二进位码第五位为0,即0 b3 b2 b1 b0。
0 xor 0=0,所以g3=0
0 xor 1=1,所以g2=1
1 xor 0=1,所以g1=1
0 xor 1=1,所以g0=1
因此所转换为之格雷码为0111
格雷码二进制码(解码)
从左边第二位起,将每位与左边一位解码后的值异或,作为该位解码后的值(最左边一位依然不变)。依次异或,直到最低位。依次异或转换后的值(二进制数)就是格雷码转换后二进制码的值。
公式表示

(G:格雷码,B:二进制码)

原码:p[n:0];格雷码:c[n:0](n∈N);编码:c=G(p);解码:p=F(c);
书写时按从左向右标号依次减小,即MSB->LSB,编解码也按此顺序进行
举例:
如果采集器器采到了格雷码:1010
就要将它变为自然二进制:
0 与第四位 1 进行异或结果为 1
上面结果1与第三位0异或结果为 1
上面结果1与第二位1异或结果为 0
上面结果0与第一位0异或结果为 0
因此最终结果为:1100 这就是二进制码即十进制 12
当然人看时只需对照表1一下子就知道是12
...................c[n]=p[n],
解码:

利用卡诺图

利用卡诺图相邻两格只有一位变化以及卡诺图的变量取值以低阶格雷码的顺序排布的特征,可以递归得到高阶格雷码。由于此方法相对繁琐,使用较少。生成格雷码的步骤如下:
  1. 将卡诺图变量分为两组,变量数目相近(最好相等)
  2. 以逻辑变量高位在左低位在右建立卡诺图
  3. 从卡诺图的左上角以之字形到右上角最后到左下角遍历卡诺图,依次经过格子的变量取值即为典型格雷码的顺序
三位格雷码(三位格雷码由建立在二位基础上)
AB╲ C
0
1
00
0→
1↓
01
↓2
←3
11
6→
7↓
10
4
←5
格雷码次序:000起点001011010110→111101100终点
四位格雷码
AB╲CD
00
01
11
10
00
0→
1→
3→
2↓
01
↓4
←5
←7
←6
11
12→
13→
15→
14↓
10
8
←9
←11
←10
格雷码次序:0000起点→000100110010011001110101010011001101
111111101010101110011000终点

使用异或乘除

用异或代替加减进行二进制竖式乘除,称为异或乘除,它的特点是无进退位。
如:10101除以11将变成1100余1。
二进制转格雷码
只要异或乘以二分之三,即二进制的1.1,然后忽略小数部分;也可以理解成异或乘以三(即11),再右移一位。
格雷码转二进制
异或除以三分之二,即除以1.1,忽略余数;或者左移一位,再异或除以三,忽略余数。
Categories
日常应用

七天搞定SAS(一):数据的导入、数据结构

标题有些噱头,不过这里的重点是: speak SAS in 7 days。也就是说,知识是现成的,我这里只是要学会如何讲这门语言,而不是如何边学SAS边学模型。顺便发现我最近喜欢写连载了,自从西藏回来后.....

之所以下定决定学SAS,是因为周围的人都在用SAS。为了和同事的沟通更有效率,还是多学一门语言吧。R再灵活,毕竟还是只有少数人能直接读懂。理论上语言是不应该成为障碍的~就像外语一样,多学一点总是好的,至少出门不发怵是不是?

最后一根稻草则是施老师传给我的一个link:http://blog.softwareadvice.com/articles/bi/3-career-secrets-for-data-scientists-1101712/,据说有数据分析师的职业秘笈...我就忍不住去看了看。其中一句话还是蛮有启发的:

如果有人问你要学什么工具,是SAS,R,EXCEL,SQL,SPSS还是?直接回答:所有。

这个答案一方面霸气,一方面也是,何必被工具束缚呢?

这东西宜突击不宜拖延,所以还是集中搞定吧。七天应该是个不错的时间段。

大致分配如下:
1. 熟悉SAS的数据结构,如基本的向量,数据集,数组;熟悉基本的数据类型,如文本,数字。
2. 熟悉基本的数据输入与输出。
3. 熟悉基本的逻辑语句:循环,判断
4. 熟悉基本的数据操作:筛选行列,筛选或计算变量,合并数据集,计算基本统计量,转置
5. 熟悉基本的文本操作函数
6. 熟悉基本的计量模型函数
7. 熟悉基本的macro编写,局部变量与全局变量

其实这大概也是按照我常用的R里面完成的任务来罗列的。基本计划是完成就可以大致了解SAS的语法了,其他的高级功能现用现学吧。

书籍方面,中文的抢了同事的一本《SAS编程与数据挖掘商业案例》,英文的找了一本「Applied Econometrics Using The SAS System」和「The Little SAS Book」,先这么看着吧。

后知后觉的补充:其实这一系列笔记都是先写再发布的,主要是方便我调整顺序什么的。事实证明绝大多数时间我在看(或者更直接的,抄)「The Little SAS Book」这本书,姚老师的《SAS编程与数据挖掘商业案例》简单看了一晚,作为对于SAS语法的预热。最后那本「Applied Econometrics Using The SAS System」更多是看具体模型的用法了,不是熟悉语法的问题了。例子都是第一本little book上的,很好用。

本系列连载文章:

-------笔记开始-------

SAS的数据类型

2013-12-09 16_41_10-The Little SAS Book(Fourth).PDF - Adobe Reader

首先,sas的编程大概就两块:Data和PROC,这个倒是蛮清晰的划分。然后目前关注data部分。

SAS的数据类型还真的只有两种:数字和文本。那么看来日期就要存成文本型了。变量名称后面加$代表文本型。

SAS的数据读入

手动输入这种就不考虑了,先是怎么从本地文件读入。比如我们有文本文件如下:

Lucky 2.3 1.9 . 3.0
Spot 4.6 2.5 3.1 .5
Tubs 7.1 . . 3.8
Hop 4.5 3.2 1.9 2.6
Noisy 3.8 1.3 1.8 1.5
Winner 5.7 . . .

然后SAS里面就可以用

* Create a SAS data set named toads;
* Read the data file ToadJump.dat using list input;
DATA toads;
INFILE ’c:\MyRawData\ToadJump.dat’;
INPUT ToadName $ Weight Jump1 Jump2 Jump3;
RUN;
* Print the data to make sure the file was read correctly;
PROC PRINT DATA = toads;
TITLE ’SAS Data Set Toads’;
RUN;

这样就建立了一个名为toads的临时数据集,然后读入外部文件ToadJump.dat,然后告诉SAS有四个变量,其中第一个是文本型。这样就OK了。缺失值用一个点.标记。

偶尔数据没那么规范,比如长成:

----+----1----+----2----+----3----+----4
Columbia Peaches 35 67 1 10 2 1
Plains Peanuts 210 2 5 0 2
Gilroy Garlics 151035 12 11 7 6
Sacramento Tomatoes 124 85 15 4 9 1

那么就要有点类似正则表达式的感觉,告诉SAS更多的参数:

* Create a SAS data set named sales;
* Read the data file OnionRing.dat using column input;
DATA sales;
INFILE ’c:\MyRawData\OnionRing.dat’;
INPUT VisitingTeam $ 1-20 ConcessionSales 21-24 BleacherSales 25-28
OurHits 29-31 TheirHits 32-34 OurRuns 35-37 TheirRuns 38-40;
RUN;
* Print the data to make sure the file was read correctly;
PROC PRINT DATA = sales;
TITLE ’SAS Data Set Sales’;
RUN;

这样SAS就可以正确的读数据了—类似于excel的导入文本-固定宽度分隔。

再不规则的话,比如有日期型的:

Alicia Grossman 13 c 10-28-2008 7.8 6.5 7.2 8.0 7.9
Matthew Lee 9 D 10-30-2008 6.5 5.9 6.8 6.0 8.1
Elizabeth Garcia 10 C 10-29-2008 8.9 7.9 8.5 9.0 8.8
Lori Newcombe 6 D 10-30-2008 6.7 5.6 4.9 5.2 6.1
Jose Martinez 7 d 10-31-2008 8.9 9.510.0 9.7 9.0
Brian Williams 11 C 10-29-2008 7.8 8.4 8.5 7.9 8.0

那么接下来就是:

* Create a SAS data set named contest;
* Read the file Pumpkin.dat using formatted input;
DATA contest;
INFILE ’c:\MyRawData\Pumpkin.dat’;
INPUT Name $16. Age 3. +1 Type $1. +1 Date MMDDYY10.
(Score1 Score2 Score3 Score4 Score5) (4.1);
RUN;
* Print the data set to make sure the file was read correctly;
PROC PRINT DATA = contest;
TITLE ’Pumpkin Carving Contest’;
RUN;

就是说,name是一个长度为16的字符;age是长度为3、无小数点的数字;+1跳过空列;type是长度为1的文本;date是MMDDYY长度为10的日期;score1-5是长度为4,小数部分为1位的数字。

还有若干更复杂的,可以遇到时侯回来查手册。此外还有@可用来直接指定开始读的列。鉴于我接触的数据一般比较规范,这些就不细看了。

此外SAS可以指定开始读的行数,读取的行数等。

DATA icecream;
INFILE ’c:\MyRawData\IceCreamSales.dat’ FIRSTOBS = 3;
INPUT Flavor $ 1-9 Location BoxesSold;
RUN;

SAS读取CSV数据

以我最关心的CSV文件为例,如下数据:

Lupine Lights,12/3/2007,45,63,70,
Awesome Octaves,12/15/2007,17,28,44,12
"Stop, Drop, and Rock-N-Roll",1/5/2008,34,62,77,91
The Silveyville Jazz Quartet,1/18/2008,38,30,42,43
Catalina Converts,1/31/2008,56,,65,34

只需要:

DATA music;
INFILE ’c:\MyRawData\Bands.csv’ DLM = ’,’ DSD MISSOVER;
INPUT BandName :$30. GigDate :MMDDYY10. EightPM NinePM TenPM ElevenPM;
RUN;
PROC PRINT DATA = music;
TITLE ’Customers at Each Gig’;
RUN;

其实,貌似更简单的办法是:

DATA music;
INFILE ’c:\MyRawData\Bands.csv’ DLM = ’,’ DSD MISSOVER;
INPUT BandName :$30. GigDate :MMDDYY10. EightPM NinePM TenPM ElevenPM;
RUN;
PROC PRINT DATA = music;
TITLE ’Customers at Each Gig’;
RUN;

好吧,import果然更直接一点...excel文件也可以如法炮制。

SAS读取excel数据

* Read an Excel spreadsheet using PROC IMPORT;
PROC IMPORT DATAFILE = 'c:\MyExcelFiles\OnionRing.xls' DBMS=XLS OUT = sales;
RUN;
PROC PRINT DATA = sales;
TITLE 'SAS Data Set Read From Excel File';
RUN;

如果需要SAS永久存着这些数据,则需要先指定libname:

LIBNAME plants ’c:\MySASLib’;
DATA plants.magnolia;
INFILE ’c:\MyRawData\Mag.dat’;
INPUT ScientificName $ 1-14 CommonName $ 16-32 MaximumHeight
AgeBloom Type $ Color $;
RUN;

后期就可以直接调用啦:

LIBNAME example ’c:\MySASLib’;
PROC PRINT DATA = example.magnolia;
TITLE ’Magnolias’;
RUN;

SAS 读取Teradata数据

最后就是从teradata里面读数据,可以利用teradata fastexport特性:

libname tra Teradata user=terauser pw=XXXXXX server=boom;
proc freq data=tra.big(dbsliceparm=all);
table x1-x3;
run;

等价于:

proc sql;
connect to teradata(user=terauser password=XXXXXX server=boom dbsliceparm=all);
select * from connection to teradata
(select * from big);
quit;

暂时没有fastload的需求,就先这样吧。可以参见SAS的TD手册:http://support.sas.com/resources/papers/teradata.pdf

本系列连载文章: