Archive for the ‘My Line’ Category

MySQL Column Types

Sunday, June 21st, 2009

昨天开始有点恢复了,今天正式进入状态,晚上还有有道难题复赛,白天睡了一觉,起来开始看MySQL,这次准备把以前所有的疑问都解决掉。

这一篇是关于MySQL中列(Column)的类型(Type)的叙述。

Text column types

MySQL提供了七种用来存储字符串文本的类型。

CHAR

用法:char(最大长度)。char类型最长可达255个字符,是定长类型。当实际长度小于最大长度时,剩余的部分会以空格填充。从表中取出字段时,多余的空格会自动被去掉。

VARCHAR

用法:varchar(最大长度)。varchar类型最长可达255个字符,是变长类型。MySQL会自动记录字符串的实际长度,并从字符串的末尾去掉空格。如果定义的最大长度小于4,MySQL会自动将列类型转换为char。

TINYTEXT

用法:tinytext。tinytext类型最长可达255个字符,是变长类型;实际上跟varchar(255)是等同的。整个字段都可以作为索引。

TEXT

用法:text。text类型最长可达65535个字符,是变长类型。可以在字段的前255个字符创建索引。

MEDIUMTEXT

用法:mediumtext。mediumtext类型最长可达16777215个字符,是变长类型。可以在字段的前255个字符创建索引。

LONGTEXT

用法:longtext。longtext类型最长可达4294967295个字符,是变长类型。可以在字段的前255个字符创建索引。实际上这个类型并不常用,因为MySQL目前只能支持最长为1600万个字符的字符串。

ENUM

用法:enum (‘value1’, ‘value2’, …) [default ‘value’]。enum类型最多可以允许多达65535个不同的枚举值,但一般实际应用的数目很少。以下是一个建表时的例子:

create table my_table (
    id int auto_increment primary key,
    answer enum (‘yes’, ‘no’) default ‘no’
);

Numeric column types

MySQL提供了七种数字类型;其中有些类型还有别名。所有的数字类型,最大显示长度(Maximum display size)都是255。有些数字类型提供了一个zerofill选项,用来对数字左边补零。比如显示长度为10的int类型的字段,值为25的时候,MySQL会显示为0000000025。数字类型还可以指定是否有符号(signedunsigned);默认是有符号。

INT(或INTEGER)

用法:int(显示长度) [unsigned] [zerofill]。int类型可以表示0~4294967295(无符号)或-2147483648~2147483647(有符号)以内的整数。int类型经常和auto_increment一同使用用来定义一个主键(Primary key)。

TINYINT

用法:tinyint(显示长度) [unsigned] [zerofill]。tinyint类型可以表示0~255(无符号)或-128~127(有符号)以内的整数。

MEDIUMINT

用法:mediumint(显示长度) [unsigned] [zerofill]。mediumint类型可以表示0~16777215(无符号)或-8388608~8388607(有符号)以内的整数。

BIGINT

用法:bigint(显示长度) [unsigned] [zerofill]。bigint类型可以表示0~18446744073709551615(无符号)或-9223372036854775808~9223372036854775807(有符号)以内的整数。

FLOAT

用法一:float(precision) [zerofill]。此用法中float类型为有符号浮点数。precision指定精度;精度不大于24为单精度,25~53为双精度。

用法二:float[(M,D)] [zerofill]。有符号单精度浮点数,有效范围约为-3.402823466E+38~-1.175494351E-38或0或1.175494351E-38~3.402823466E+38。M为显示长度,D为数字位数。参数省略后的float类型为精度不大于24的单精度浮点数。

DOUBLE(或DOUBLE PRECISION,REAL)

用法一:double[(M,D)] [zerofill]。有符号双精度浮点数,有效范围约为-1.7976931348623157E+308~-2.2250738585072014E-308或0或2.2250738585072014E-308~1.7976931348623157E+308。M为显示长度,D为数字位数。

用法二:decimal[(M[,D])] [zerofill]。以字符串形式保存的数字类型。

Date and time types

MySQL提供了五种用来存储日期或时间的类型。MySQL中的日期或时间类型很灵活,可以接受insert语句中用字符串或数字表示的形式。下面是一个例子:

create table date_test (
    id int unsigned auto_increment,
    the_date date
);

insert into date_test (the_date) values (‘09-06-21’);
insert into date_test (the_date) values (‘2009-06-21’);
insert into date_test (the_date) values (‘20090621’);
insert into date_test (the_date) values (090621);

DATE

用法:date。以YYYY-MM-DD格式存储,范围是1000-01-01至9999-12-31。

DATETIME

用法:datetime [null | not null] [default]。以YYYY-MM-DD HH:MM:SS格式存储,范围是1000-01-01 00:00:00至9999-12-31 23:59:59。

TIMESTAMP

用法:timestamp(size)。自动记录最后更新时间(insertupdate)。size的默认值是14;下表列出了详细信息:

Size Format
2 YY
4 YYMM
6 YYMMDD
8 YYYYMMDD
10 YYMMDDHHMM
12 YYMMDDHHMMSS
14 YYYYMMDDHHMMSS
TIME

用法:time。以HH:MM:SS格式存储,范围是-838:59:59至838:59:59。

YEAR

用法:year[(2|4)]。两位数年份的范围是1970年至2069年,四位数年份的范围是1901年至2155年。

1840 — Eqs

Wednesday, May 20th, 2009

初看这道题的时限就很警觉,暴力枚举铁定超时。于是在想如何优化。枚举的五层循环最内层其实是多余的,因为x5可以直接求出来。于是弄出了108的算法,无奈常系数太大,依然超时。其实如果我能放弃掉解方程的思想,转而去重视移项,应该就会很快得到正解。正解是用哈希(Hash),将方程左边的后三项移到右边,然后枚举x1和x2得到此式左边的值,做哈希。预处理过后就枚举右边三个变元求和,如果能与左边出现过的值相等则存在某些数量的相应解。规模是106,系数再大都超不了时了。我实现的时候偷了懒,没有做哈希(O(1)),直接用了STL里的map(O(lg n)),速度也还可以。

转化的思想依然很重要。这让我联想到SRM 440的那道物理题,我推了半天公式没弄出来最后放弃掉。实际上二分枚举就可以了。这就是需要思维的变换,不能直接顺着题意走,有时候需要重新从另一个角度建模,进行转化。二分确实是一个很有用的东西,对于可以构造出单调性的优化问题很有效。当然本题与二分无关……扯远了……

点击这里查看poj_1840.cpp(780K,2766MS)

3734 — Blocks

Monday, May 18th, 2009

PKU Campus 2009结束了,我也很自然而华丽地考挂了。从赛前到赛后状态一直很差(因为她……),今天开始在一片纠结中改题。D题是全场最早出的题,我当时确实把公式推出来了,可惜一个小的细节没有注意到,结果答案有一点点偏差。这直接导致了我出的第一题居然是G而不是D(话说当时出G的时候题目描述还有问题,所以2Y……)。

其实思路很简单,从N个里取出k个,让k是偶数表示红的和绿的之和,其中红的又设出来是r个,剩下的N-k个直接作为2的指数求幂。这样我们得到:S = ∑k( ∑r( C(N,k) × C(k,r) × 2N-k ) ),其中k和r都是满足相应限制条件的偶数。把S整理一下,将求和式中的公共项提出来,得到:S = ∑k( C(N,k) × 2N-k × ∑r( C(k,r) ) ),其中∑r( C(k,r) ) = 2k-1(根据二项式展开系数性质易得)。但到这里需要注意,k可以等于零!我比赛时就是这里忽略了,所以得到了错误的结果。k = 0时,C(k,r)是没有意义的,所以我们需要把k = 0的情况单独弄出来,是2N,然后整理合并其余的式子,得到:S = 2N + 2N-1 × ∑k( C(N,k) );这里的k是从2开始的。于是最终整理一下就得到:S = 2N + 2N-1 × ( 2N-1 – 1 ) = 4N-1 + 2N-1

有了公式,程序就很好写了。为了保证不越界,令T = 2N-1,则S = T2 + T = T × (T + 1),同时对10007取模就可以了。另外,求幂的时候我用了快速幂取模加速,实践结果也很好(16MS)。

点击这里查看poj_3734.cpp(220K,16MS)

Notes of C Programming FAQs (5)

Wednesday, May 13th, 2009

下面是一些通常的检查要点:
² 未初始化的局部变量
² 整数上溢, 特别是在一些16 比特的机器上, 一些中间计算结果可能上溢, 象a * b / c
² 未定义的求值顺序
² 忽略了外部函数的说明, 特别是返回值不是int 的函数, 或是参数“缩小” 或可变的函数
² 复引用空指针
² malloc/free 的不适当使用: 假设malloc 的内存都被清零、已释放的内存还可用、再次释放已释放内存、malloc 的内部被破坏
² 指针类常规问题
² printf() 格式与参数不符, 特别是用%d 输出long int
² 试图分配的内存大小超出一个unsigned int 类型的范围, 特别是在内存有限的机器上
² 数组边界问题, 特别是暂时的小缓冲, 也许用于sprinf() 来构造一个字符串
² 错误的假设了typedef 的映射类型, 特别是size t
² 浮点问题
² 任何你自己认为聪明的在特定机器上的机器代码生成小技巧

“Segmentation violation”, “Bus error” 和“General protectionfault” 意味着什么?
通常, 这意味着你的程序试图访问不该访问的内存地址, 一般是由于堆栈出错或是不正确的使用指针。可能的原因有: 局部数组溢出(用堆栈分配的自动变量);不小心, 用了空指针、未初始化指针、地址未对齐的指针或其它没有适当分配的指针; malloc 内部被破坏; 函数调用参数不匹配, 特别是如果用了指针, 两个可能出错的函数是scanf()和fprintf() (确定他的第一个参数是FILE *)。

“印第安山风格指南” (Indian Hill Style Guide)

用gcc -Wall -pedantic替代lint

怎样显示一个百分比或“转动的短棒” 的进展表示器?
这个简单的事情, 你可以做到相当的可移植。输出字符’\r’ 通常可以得到一个回车而没有换行, 这样你就可以复写当前行。字符’\b’ 代表退格, 通常会使光标左移一格。记住要调用fflush()。

使用数据库来取代平坦文件

怎样抓获或忽略像control-C 这样的键盘中断?
基本步骤是调用signal():
#include <signal.h>
singal(SIGINT, SIG_IGN);
就可以忽略中断信号, 或者:
extern void func(int);
signal(SIGINT, func);
使程序在收到中断信号时, 调用函数func()。

怎样判断机器的字节顺序是高字节在前还是低字节在前?
有个使用指针的方法:


int x = 1;
if(*(char *)&x == 1)
    	printf("little-endian\n");
else
    	printf("big-endian\n");

另外一个可能是用联合。

从其他语言转换到C的工具:p2c, ptoc, f2c

由一个日期, 怎样知道是星期几?
这个由Tomohiko Sakamoto 提供的优雅的代码:


int dayofweek(int y, int m, int d) /* 0 = Sunday */
{
        static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
        y -= m < 3;
        return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}

自打印程序:


char*s="char*s=%c%s%c;main(){printf(s,34,s,34);}";main(){printf(s,34,s,34);}

还有一个有James Hu 发布的改进版:


#define q(k)main(){return!puts(#k"\nq("#k")");}
q(#define q(k)main(){return!puts(#k"\nq("#k")");})

什么是“达夫设备” (Duff’s Device)?
这是个很棒的迂回循环展开法, 由Tom Duff 在Lucasfilm 时所设计。它的“传统” 形态, 是用来复制多个字节:


register n = (count + 7) / 8; /* count > 0 assumed */
switch (count % 8)
{
case 0: do { *to = *from++;
case 7:      *to = *from++;
case 6:      *to = *from++;
case 5:      *to = *from++;
case 4:      *to = *from++;
case 3:      *to = *from++;
case 2:      *to = *from++;
case 1:      *to = *from++;
            	} while (--n > 0);
}

这里count 个字节从from 指向的数组复制到to 指向的内存地址(这是个内存映射的输出寄存器, 这也是为什么它没有被增加)。它把swtich 语句和复制8 个字节的循环交织在一起, 从而解决了剩余字节的处理问题(当count 不是8 的倍数时)。相信不相信, 象这样的把case 标志放在嵌套在swtich 语句内的模块中是合法的。当他公布这个技巧给C 的开发者和世界时, Duff 注意到C 的swtich 语法, 特别是“跌落” 行为, 一直是被争议的, 而“这段代码在争论中形成了某种论据, 但我不清楚是赞成还是反对”。

Notes of C Programming FAQs (4)

Wednesday, May 13th, 2009

\n 在scanf 格式串中不表示等待换行符, 而是读取并放弃所有的空白字符。

在scanf() 转换数字的时候, 它遇到的任何非数字字符都会终止转换并被保留在输入流中。因此, 除非采用了其它的步骤, 那么未预料到的非数字输入会不断“阻塞” scanf(): scanf() 永远都不能越过错误的非数字字符而处理后边的合法数字字符。

通常先用类似fgets() 的函数读入整行, 然后再用sscanf() 或其它技术解释。

要避免溢出问题, 你可以使用限制长度的sprintf() 版本, 即snprintf()。这样使用:snprintf(buf, bufsize, “You typed \”%s\”", answer);
snprintf() 在几个stdio 库中已经提供好几年了, 包括GNU 和4.4bsd。在C99中已经被标准化了。作为一个额外的好处, C99 的snprintf() 提供了预测任意sprintf() 调用所需的缓冲区大小的方法。C99 的snprintf() 返回它可能放到缓冲区的字符数, 而它又可以用0 作为缓冲区大小进行调用。因此nch = snprintf(NULL, 0, fmtstring, /* 其它参数*/ );这样的调用就可以预测出格式串扩展后所需要的字符数。

没有什么标准的办法可以丢弃标准输入流的未读取字符, 即使有, 那也不够,因为未读取字符也可能来自其它的操作系统级的输入缓冲区。

读取二进制数据文件的时候你应该用“rb” 调用fopen(), 确保不会发生文本文件的解释。类似的, 写二进制文件时, 使用“wb”。注意文本/二进制区别只是发生在文件打开时: 一旦文件打开之后, 在其上调用何种I/O 函数无关紧要。

怎样产生标准分布或高斯分布的随机数?
这里有一个由Marsaglia 首创Knuth 推荐的方法:


#include <stdlib.h>
#include <math.h>
double gaussrand()
{
    	static double V1, V2, S;
    	static int phase = 0;
    	double X;
    	if(phase == 0) {
    	    	do {
            	double U1 = (double)rand() / RAND_MAX;
            	double U2 = (double)rand() / RAND_MAX;
            	V1 = 2 * U1 - 1;
            	V2 = 2 * U2 - 1;
            	S = V1 * V1 + V2 * V2;
    	    	} while(S >= 1 || S == 0);
    	    	X = V1 * sqrt(-2 * log(S) / S);
    	} else
        	X = V2 * sqrt(-2 * log(S) / S);
    	phase = 1 - phase;
    	return X;
}

大多数电脑都是用二进制来表示浮点和整数的。在十进制里, 0.1 是个简单、精确的小数, 但是用二进制表示起来却是个循环小数0.0001100110011 . . . 。

“参数默认晋级” 规则适用于在可变参数中的可变动部分: 参数类型为float 的总是晋级(扩展) 到double, char 和short int 晋级到int。所以va arg(arpg, float)是错误的用法。应该总是用va arg(arpg, double)。

程序在执行用之前就崩溃了, 用调试器单步跟进, 在main() 之前就死了。
也许你定义了一个或多个非常大的局部数组(超过上千字节)。许多系统只有固定大小的堆栈, 即使那些自动动态堆栈分配的系统也会因为一次性要分配大段堆栈而失败。
一般对大规模数组, 定义为静态的数组会更好。如果由于递归的原因, 每次都需要一组新的数组, 可以用malloc() 动态申请内存。

Notes of C Programming FAQs (3)

Wednesday, May 13th, 2009

一般地说, 使用指针的时候, 你必须总是考虑内存分配, 除非明确知道编译器替你做了此事。

那么返回字符串或其它集合的争取方法是什么呢?
返回指针必须是静态分配的缓冲区, 或者调用者传入的缓冲区, 或者用malloc() 获得的内存, 但不能是局部(自动) 数组。

sizeof(char) 严格为1。

一个常见的bug 是用malloc(strlen(s)) 而不是strlen(s) + 1。

当你调用free() 的时候, 传入指针指向的内存被释放, 但调用函数的指针值可能保持不变, 因为C 的按值传参语义意味着被调函数永远不会永久改变参数的值。

calloc(m, n) 本质上等价于 p = malloc(m * n); memset(p, 0, m * n); 填充的零是全零, 因此不能确保生成有用的空指针值或浮点零值。free() 可以安全地用来释放calloc() 分配的内存。

C语言中的字符常数是int 型, 因此sizeof(’a’) 是sizeof(int),这是另一个与C++ 不同的地方。

如果你认为“if((a == b) == TRUE)” 比“if(a == b)” 好, 为什么就此打住呢?为什么不使用“if(((a == b) == TRUE) == TRUE)” 呢?

如果宏体内的语句都是简单语句, 没有声明或循环, 那么还有一种技术, 就是写一个单独的, 用一个或多个逗号操作符分隔的表达式。这种技术还可以“返回” 一个值。

作为一般规则, 你应该把这些东西放入头(.h) 文件中:
² 宏定义(预处理#defines)
² 结构、联合和枚举声明
² typedef 声明
² 外部函数声明
² 全局变量声明
当声明或定义需要在多个文件中共享时, 尤其需要把它们放入头文件中。特别是, 永远不要把外部函数原型放到.c 文件中。
另一方面, 如果定义或声明为一个.c 文件私有, 则最好留在.c 文件中。

我在文件的第一个声明就遇到奇怪的语法错误, 但是看上去没什么问题。可能你包含的最后一个头文件的最后一行缺一个分号。

C99 引入了对参数个数可变的函数式宏的正式支持。在宏“原型” 的末尾加上符号… (就像在参数可变的函数定义中), 宏定义中的伪宏__VA_ARGS__ 就会在调用时替换成可变参数。

“const char *p” (也可以写成“char const *p”) 声明了一个指向字符常量的指针, 因此不能改变它所指向的字符; “char * const p” 声明一个指向(可变) 字符的指针常量, 就是说, 你不能修改指针。

在使用符号粘接操作符## 连接两个宏的值(而不是名字) 时也要采用同样的“迂回战术”。

当你希望把宏参数转成字符串时,你可以使用新的预处理操作符# 和字符串常量连接(ANSI 的另一个新功能)

如果源和目的参数有重叠, memmove() 提供有保证的行为。而memcpy()则不能提供这样的保证, 因此可以实现得更加有效率。

保存getchar 的返回值的变量必须是int 型。getchar() 可能返回任何字符值, 包括EOF。如果把getchar 的返回值截为char 型, 则正常的字符可能会被错误的解释为EOF, 或者EOF 可能会被修改(尤其是char 型为无符号的时候), 从而永不出现。

在C 语言中, 只有输入例程试图读并失败以后才能得到文件结束符。换言之,C 的I/O 和Pascal 的不一样。通常你只需要检查输入例程的返回值, 例如, fgets()在遇到文件结束符的时候返回NULL。实际上, 在任何情况下, 都完全没有必要使用feof()。

我如何在printf 的格式串中输出一个’%’?我试过\%, 但是不行。
只需要重复百分号: %%。
\%不行, 因为反斜杠\ 是编译器的转义字符, 而这里我们的问题最终是printf的转义字符。

在printf 中使用%lf 不正确。scanf() 需要%lf,printf 的%f 标识符的确既可以输出浮点数又可以输出双精度数。printf() 的确接受%Lf, 用于输出长双精度数。

对于size t 那样的类型定义, 当我不知道它到底是long 还是其它类型的时候, 我应该使用什么样的printf 格式呢?
把那个值转换为一个已知的长度够大的类型, 然后使用与之对应的printf 格式。例如, 输出某种类型的长度, 你可以使用
printf(“%lu”, (unsigned long)sizeof(thetype));

我如何用printf 实现可变的域宽度?就是说, 我想在运行时确定宽度而不是使用%8d?
printf(“%*d”, width, x) 就能达到你的要求。

Notes of C Programming FAQs (2)

Wednesday, May 13th, 2009

*((condition) ? &a : &b) = complicated_expression;

*p++ 和*(p++) 等价,如果副作用的顺序无关紧要也可以使用++*p。

对函数extern int f(int *);用引用方式传入一个常数。在C99 中, 可以使用“复合常量”:f((int[]){5});

最初, 一个函数指针必须用* 操作符(和一对额外的括弧) “转换为” 一个“真正的” 函数才能调用:
int r, func(), (*fp)() = func;
r = (*fp)();
而函数总是通过指针进行调用的, 所有“真正的” 函数名总是隐式的退化为指针(在表达式中, 正如在初始化时一样。)。这个推论表明无论fp 是函数名和函数的指针
r = fp();
ANSI C 标准实际上接受后边的解释, 这意味着* 操作符不再需要, 尽管依然允许。

execl(“/bin/sh”, “sh”, “-c”, “date”, (char *)0);
如果省略最后一个参数的(char *) 转换, 则编译器无从知道这是一个空指针,从而当作一个0 传入。(注意很多Unix 手册在这个例子上都弄错了。)

有两条简单规则你必须遵循:
1. 当你在源码中需要空指针常数时, 用“0” 或“NULL”。
2. 如果在函数调用中“0” 或“NULL” 用作参数, 把它转换成被调函数需要的指针类型

一个图形胜过千言万语。声明
char a[] = “hello”;
char *p = “world”;
将会初始化下图所示的数据结果:


   +---+---+---+---+---+---+
a: | h | e | l | l | o |\0 |
   +---+---+---+---+---+---+
   +-----+     +---+---+---+---+---+---+
p: |  *======> | w | o | r | l | d |\0 |
   +-----+     +---+---+---+---+---+---+

说数组和指针“等价”不表示它们相同, 甚至也不能互换。它的意思是说数组和指针的算法定义可以用指针方便的访问数组或者模拟数组。

一个T 的数组类型的左值如果出现在表达式中会蜕变为一个指向数组第一个成员的指针(除了三种例外情况); 结果指针的类型是T 的指针。

一旦数组出现在表达式中, 编译器会隐式地生成一个指向数组第一个成员地指针, 就像程序员写出了&a[0] 一样。例外的情况是, 数组为sizeof 或&操作符的操作数, 或者为字符数组的字符串初始值。

C99引入了变长数组(VLA),局部数组的大小可以用变量或其它表达式设置, 可能也包括函数参数。

如果你向函数传递二位数组:
int array[NROWS][NCOLUMNS];
f(array);
那么函数的声明必须匹配:
void f(int a[][NCOLUMNS])
{ … }
或者
void f(int (*ap)[NCOLUMNS]) /* ap 是个数组指针*/
{ … }