Zade's Weblog
程序人生
小妞妞的牙牙学语
我记得好像是在小妞妞很小的时候，大约1,2个月的时候，她就能发出比较模糊的声音，非常类似于“不”。对此我很欣慰，我的性格比较软弱，不善于拒绝别人。小妞妞的第一个声音竟然是表示拒绝，相当于克服了我的这个最大的缺点。遗传变异，优胜劣汰，进化的趋势让我高兴。
“哦”，是她最早学会的声音之一。无论她想表达什么意思，这几乎是她唯一的声音。指着电灯，指着空调，指着电视机，她都用这个声音表达她的思想。为人父母者向理解婴儿的意思，不能光凭声音，还要看表情和动作。
在她10个月的时候，有一次她在镜子前面饶有兴趣的看自己的样子，她姥姥不经意的问道，“美不美？”，“美！”，小妞妞非常清晰的发出了这个声音。这是她发音最清楚的一个字；而且，貌似她还理解了这个字的意思。这对于她而言真是一个重大的突破。
“妈妈”这两个字也是在她大约10个月的时候，就能比较清楚的发出这个声音了。“爸爸”要稍后一些，我虽然更希望她能够更早的学会叫爸爸，但是老婆在她身上付出的心血确实比我多。小妞妞很好的体现了“多劳多得”的良好精神。
大约在她1岁的时候，“哦”这个简单的发音有了变化，她用拖长或者变音的方式表达自己的惊讶或者惊喜的心情。看到一个新的玩具，看到图书上小鸭子倒背翅膀走路的姿态，她都会发出这个声音。她已经学会简单的使用感叹词表达自己的感情了。
在给小妞妞的众多的育儿书中，其中的一本上有一个蓝色的大象，上面写着“blue”的英文单词，她妈妈就对着她说“blue”，小妞妞也跟着学。这个发音她学的不是而别像，只是有些样子，但是这却是她的第一个英文单词发音。
小妞妞现在14个月了，以后她当然还会更多的发音，让我拭目以待吧！
小妞妞终于会走了
早在小早在小妞妞11个月的时候，她就有会走的摸样了。但是期间她病了一场，有些耽搁，所以我们一直也没有继续着方面的锻炼。
过了一岁生日的时候，可以确定的是小妞妞会走了。但是好像她的胆子太小，还必须我们牵着她的手。其实与其说我们牵着她的手，还不如说她牵着我们的手。在温泉宾馆前面的草坪上，我故意不牵她的手，而是抓着她的衣领。她虽然开始的时候反抗，但是后来也不得不同意了。她到处跑着玩，我偷偷的放手了，她不知道，照样是导出跑着玩。不过一旦她发现我的阴谋，立刻停下，等我去牵她的手。所以说她已经会走了，只是胆小而已。
前几天元旦放假，老婆到成都去玩，小妞妞中午的时候跟我一起玩。我躺在床上，她沿着床边玩，很长的一段时候她是双手离开床边的。我一旦站起来，她又找我的手牵。
大前天我下班回家，看到小妞妞再到处的跑，已经完全不需要手牵了。
这真是一个值得纪念的时刻！
signal和多线程
今天在linux下面使用signal，用在多线程的环境下，环境是red hat.
signal函数可以使得程序接管OS的一些特殊的信号。我在主线程下面执行了这个函数，但是所有的子线程也受到了这个信号的影响。我的本意是是只是主线程拦截这些信号，而子线程使用默认的处理方式。看来是不行了。
signal本来就是单线程模式下的函数，signal的标准对于多线程没有任何的评说，只能是各个实现着自己定义了，red hat是这样的定义，可能其他的OS会有其他的行为。
找到最小的元素
int findFirst(const vector<int>& A)
{
int size = static_cast<int>(A.size());
if (size == 0){
return -1;
}else if (size == 1){
return 0;
}
int firstMin = A.front();
int secondMax = A.back();
if (firstMin <= secondMax){
return 0;
}
int start = 0;
int end = size – 1;
while(start <= end){
int mid = (start + end) / 2;
if (A[mid] > firstMin){
start = mid + 1;
}else if (A[mid] < firstMin){
end = mid – 1;
}else{
if (A[mid] > secondMax){
start = mid + 1;
}else if (A[mid] < secondMax){
end = mid – 1;
}else{
return mid;
}
}
}
return start;
}
算法小结
这几天因为参加了一些公司的面试和笔试,总的感觉是包括微软,google和IBM都是比较重视算法的.当我们遇到一个具体的算法问题的时候,我们该如何的考虑呢?
我总结了几点经验:
1.
变无序为有序,减少时间开销
一般程序给出的都是无序的序列,我们转换为有序之后,就可以减少时间的开销.
例如google的一道笔试题,求得字符串中第一个只是出现一次的字符,例如abaccd,那和输出是b.
使用最简单的算法,如下:
int firstChar(const string& str)
{
if(str.empty())
return -1;
for(string::const_iterator itr= str.begin();itr != str.end(); ++ itr){
if(count(str.begin(),str.end(),*itr) == 1){
return *str;
}
}
return -1;
}
非常简洁的一段代码,但是时间复杂度是N^2。把str排序以后就可以减少这个复杂度了:
int firstChar(const string& str)
{
if(str.empty())
return -1;
string sorted(str);
sort(sorted.begin(),sorted.end());
typedef string::const_iterator
itr_t;
for(itr_t itr = str.begin(); itr !=str.end();++ itr) {
itr_t pos = lower_bound(sorted.begin(),sorted.end(),*itr);
assert(pos != sorted.end());
itr_t next = pos + 1;
if(next == sorted.end() || *itr != *next){
return *itr;
}
}
return -1;
}
这段代码的复杂度就是N*logN.
2.
模型转换
一个问题初始看起来很复杂,但是经过模型转换以后就会很简单.
上面无序变有序的例子也是一个模型转换的例子,我们看一个更加直观的例子,求得两个字符串的最大公共子串,例如abcdefg abdefg的最大子串是defg.
最简单的想法是求得所有的子串,然后求得长度最大的一个,时间复杂度是N*M+K,K是所有子串的长度之和.这不仅似的算法实现比较复杂,时间复杂度也很大.
我见到了一个把这个问题转换的很好的例子,通过矩阵求解.
首先构造一个N*M的矩阵,初始化全部为0，如果A的第i个字符和B的第j个字符相等,则置1，否则保持不变.这样的一个矩阵,所谓的最长的子串,就是这个矩阵中左对角为1的最长的一个序列.
再进一步,除了边缘的元素,如果A的第i个字符和B的第j个字符相等,则使得矩阵V的 v[i][j] =
v[i-1][j-1]+1,这样最大的子串,就是这个矩阵中数值最大的那个所在的左对角.
程序如下:
string LCS(const string& first,const string& second)
{
int row_count = static_cast<int>(first.length());
int col_count = static_cast<int>(second.length());
if (row_count == 0 || col_count == 0){
return string();
}
vector<int> arr(row_count * col_count);
int max = 0;
int row = 0;
int index = 0;
for (int i= 0 ; i < row_count;++ i)
for (int j = 0 ; j < col_count; ++ j)
{
if (second[j] == first[i]){
if (i > 0 && j > 0){
int idx = index – col_count – 1;
arr[index] = arr[idx] + 1;
}else{
arr[index] = 1;
}
if (arr[index] > max){
max = arr[index];
row = i;
}
}
++
index;
}
if (max != 0){
return first.substr(row – max + 1,max);
}
return string();
}
C++指针类型
看到一类面试题,如下:
Write in words the data type identifier involved in the following definations:
1) float (**def)[10]
2) double* (*gh)[10]
3)double (*f[10])()
4) int* ((*b)[10])
5) int (* (*F(int,int))(int)
我们先看答案:1)二级指针,指向一个10个元素的数组,数组的类型是float
2) 指针,指向一个数组,数组有10个元素,类型是double*
3)函数指针数组,10个元素,函数的类型是返回值是double,没有参数
4)指针,指向一个数组,数组的个数是10，类型是int*
5)函数指针,函数参数是两个int,返回值是一个函数指针,这个函数的返回值是int,一个参数,类型是int
在上面的定义中,除了函数指针让人繁琐以外,还有数组指针和指针数组的相互混淆.
那么,判断的依据是什么呢?
- 首先,如果表达式的最后是(),里面有若干个参数类型,那么这个肯定是和函数指针相关,要么本身是一个函数指针,要么返回值实施一个函数指针
- 变量前面是*,那么首先表示这是一个指针;如果是**,二级指针
- T* var[X],这是数组指针,即指向指针的数组,T (*var)[X],这是指针数组,指向数组的指针,和T var2[10]不同的是,var是可变的,var2不可变
对于函数指针,在实际的工程应用中,我们一般使用typedef,例如:
int Func(int){}
与其:int (*f)(int) = &Func
不如: typedef int (*Func_Type)(int); Func_Type f = &Func;更加的清晰.
还有,int (* (*F(int,int))(int),我们可以:
typedef int (*Func_Type)(int);
typedef Func_Type (*Func_Type2)(int,int);
Func_Type2 F = NULL;
这样会更加的清晰.
Qt的界面模式-Model/View
MVC是界面设计的经典范例.虽然这个理念已经深入人心,但是在各个具体的实现里面是有差别的.最近我使用了Qt的界面开发,开始的时候使用了Item Based的界面类,例如QTreeWidget,但是后来我很快意识到这个方法的问题,从而转向了Model/View的模式.在这里把经验总结一下.
所谓的Item Based的界面控件,具体到Qt而言,就是QTreeWidget QListWidget等,这类控件的特点是,都是通过Item的方式向这些要素添加界面元素,例如QTreeWidgetItem, QListWidgetItem等.这样设计的好处是使用简单,界面元素和底层的数据方式隔离.但是问题是数据冗余,存储代价增大,并且进而带来了数据的一致性问题.
我们使用一个实例说明这类模式的主要问题,例如我们要删除QTreeWidget的一个条目,我们该如何做呢?一般的做法是删除底层的数据,然后删除相应的界面元素QTreeWidgetItem,二者的次序一般没有关系,特殊的情况需要特殊的处理.这样做是否比较麻烦呢?或者说,我们认为更好的方式是这样的: 删除底层的数据结构,界面刷新,以反映数据结构的变化.更直接的说,更好的模式是把数据结构存储在唯一的一个地方,界面显示只是一个获得这个数据并且显示的过程.
这个原理似乎很明显,但是Item Based的控件类明显不是这种做法,界面元素和底层的数据方式是隔离的,并不是一致的存储在某个地方.
原理虽然简单,但是具体并不如此简单,我们以QTreeView和QAbstractItemModel为例,简单的说明一下:
- QAbstractItemModel有几个函数必须重载,例如
- data() 返回特定行的数据,其中值得注意的是参数role,一般的DisplayRole返回的是显示的文本,DecorationRole返回的是显示的图片,CheckStateRole返回的是显示选中状态的数值,所有这些数据通过QVariant的包装转发给系统,系统通过这些来显示当前的元素
- index()返回指定行列的索引,函数原型是QModelIndex index(int row, int col,const QModelIndex &parent) const,刚开始的时候我有些疑惑,提供一个默认的实现,parent.child(row,col)不就可以了,为什么还让上层的用户提供一个不同的实现呢?后来逐渐的明白,这是给你一个构造更加复杂的QModelIndex 的机会,因为你可以在QModelIndex 上附加一个指针数据.
- rowCount和columnCount提供行数和列数,一般我们是根据附加的指针数据获得的
- parent返回指定元素的父亲,这个一般也是根据附加的指针数据获得的
- QModelIndex 是在View和Model之间传递数据的一个媒介,但是QModelIndex 是一个瞬时变量,在数据结构调整以后,会导致其无效.这告诉我们不能长期的保留一个QModelIndex 数值,在这种情况下应该使用QPersistentModelIndex.
- 在QModelIndex 附加指针,一旦更改这个指针,我们如何通知view使用新的指针而不是旧的指针呢(旧指针可能已经无效)?我在这个问题上费了好长的时间.最早的时候我没有做任何特定的实现,因为通过model的parent或者index函数得到的指针就是我修改以后的指针.但是实际上view会崩溃,原始就是view使用了被废弃的指针.这说明系统内部做了一定的缓存,我需要更新这个缓存.根据QModelIndex 和QPersistentModelIndex的关系,如果系统做了缓存,那么肯定是基于QPersistentModelIndex的缓存,QAbstractItemModel提供了changePersistentIndex函数,从字面的意思来看,应该是通知系统内部修改缓存的数据,调用了这个函数以后,程序不在崩溃,但是界面的对应的行数据不在显示,如图所示:
这个诡异的结果应该是界面对应的元素没有找到,但是如何更新相应的解密那元素,我没有找到合适的函数,我的最终实现如下:
void LayerItemModel::updateData(const QModelIndex& child,const QModelIndex& parent)
{
int row = child.row();
this->beginRemoveRows(parent,row,row);
this->endRemoveRows();
this->beginInsertRows(parent,row,row);
this->endInsertRows();
this->changePersistentIndex(child,parent.child(row,0));
}
我知道这应该不是最好的方案,但是目前只能这样.
GIS影像数据的显示
GIS的数据分成两大类:矢量数据,以.shp数据和oracle spatial geometry为代表;还有就是栅格数据,以geotiff和oracle spatial georaster为代表.
矢量数据的显示比较直观,矢量符号配上显示符号即可.我用了不少的时间实现矢量数据的显示,最近一段时间以GDAL为底层的数据引擎,实现了栅格数据的显示,现在把我实现栅格数据显示的思路整理一下.
在实现思路上,我参考了开源的SharpMap软件.
栅格数据显示需要考虑的因素:
- 波段和颜色通道的映射.一个波段可以映射为不同的颜色通道,不同的颜色通道可以显示,也可以不显示.有些数据存储这些映射信息,有些数据不存储这些映射信息
- 波段数据和颜色通道数据的映射.颜色通道数据一般是8bit的,但是GIS的影像数据有很多的格式,这意味着我们必须通过某种手段进行映射.GeoAPI给出了3中方法:None,Normalize,Histogram.我们在这里并不解释这些具体的映射方式,具体的可以参考GEOAPI.
一旦完成了这两个工作,栅格数据就可以显示了.
波段和颜色通道的映射
颜色通道有多种模型,RGB,CMYK,HLS,YUV等.虽然并不精确,但是不同的模型之间存在一定的转换关系.因为现在的很多显示引擎直接支持的是RGB的模型,所以从实现的角度来看,我们按照给定的模型获得不同的颜色模型,然后转化为RGB的模型即可.当然,RGB模型本身不需要转化.以CMYK为例
byte* c_data = read_channel_data(C_CHANNEL);//这里具体的读取过程涉及波段数据和颜色通道数据的映射,参见下一个议题
byte* m_data = read_channel_data(M_CHANNEL);//同上
byte* y_data = read_channel_data(Y_CHANNEL);//
byte* k_data = read_channel_data(K_CHANNEL);//
byte* a_data = read_channel_data(ALPHA_CHANNEL);//
ARGB* data = get_img_data(ImageFormat::ARGB_FORMAT);
for (ARGB* end = data + bytes; data!= end;++ cdata,++ c_buf,++ m_buf,++ y_buf,++ k_buf,++ a_buf){
*data = Color::fromCmyk(*c_buf,*m_buf,*y_buf,*k_buf,*a_buf).rgba();
}
其他颜色模型的转换是类似的.
颜色的像素格式我们使用ARGB的格式,虽然有些空间占用,但是对于屏显数据而言,并不是很多.这样做的好处是不管使用什么颜色模型,到最后都要转换为ARGB的模型,在算法实现上是非常的便利的.
有的数据格式存储这样的映射关系,有的数据不存储这样的数据关系.为了解决和这个问题,我们使用栅格符号RasterSymbolizer来定义这个映射关系.如果数据本身存储这样的映射关系,那么我们直接的使用这个映射关系;如果数据本身不存储这样的映射关系,我们的做法是:如果波段的个数>=3，选取前三个波段映射为RGB模型,否则,选取第一个作为灰度波段显示
波段数据和颜色通道数据的映射
栅格数据的格式很多,不仅包含我们常见的图像数据,例如GIF/PNG等数据,也包括DEM等数据.从GDAL的类型我们可以知道,存储的格网数据类型包括整型,从8bit到32bit,包括无符号有符号的整型.浮点型,从32bit到64bit.实数型,16bit到32bit的整数型实数,32bit到64bit的实数.具体参见GDAL文档.
从ARGB的格式上说,每个颜色通道的数据类型就是8bit的byte,这个映射很显然的要损失一些精度.我们把这个转换定义为一个函数:
byteValueOfColorComponent = Function(channelValue)
这个映射从GeoAPI的角度kan,有三种:
None:从实现的角度看,none意味着截取和转换,比如16bit截取为8bit,float转换为byte等.很显然,这里面有数据丢失的情况,严重的时候是不可接受的.但是这个方法的好处:一旦原始数据类型是byte,那么不存在截取和转换的情况.另外这种方法是最快的,最为初始的显示方式是可以接受的.
Normalize:归一化.从实现的角度上说,就是在最大值和最小值之间做一个线性映射,最大值显示为某种颜色(一般是最亮的值),最小值显示为某种颜色(一般是最暗色).
Histogram:柱状图.Normalize是一个波段数据值和颜色值之间的一个线性映射,Histogram是波段数据出现的频率值和颜色值之间的映射,同样的是:最大平率值显示为某种颜色(一般是最亮的值),最小频率值显示为某种颜色(一般是最暗色).
在映射的过程中,单值映射比较容易,实数值映射的是实数实部和虚部的平方根(也就是轴长).
灰度值和颜色表
灰度值映射为颜色值的公式是:color = makeARGB(gray,gray,gray,Alpha),gray来自于单一的一个波段数值.
颜色表是直接把波段数值作为颜色索引,在这里我们假设所有的索引值都小于256。
C++的前置声明
我们定义一个完整的接口,并且以插件的方式实现之,这是非常灵活的体系方案.当然对于这个方案,我们的问题也很多,例如我们是否使用智能指针,需要注意哪些问题;我们如何使用前置声明,要注意哪些问题,等等.
我们现在讨论一下C++的前置声明.
std里面关于iosfwd是关于前置声明使用的一个经典的例子.
前置声明有很多的作用,例如解决重复包含问题,智能指针问题等;当然,节省编译时间也是一个很重要的原因.
以我们GIS为例,我们定义了GIS的标准接口GeoAPI,并且定义了geoapifwd.hpp文件.根据前置声明的原理,只要是需要指针的接口定义,并不需要看到类的完整的声明,我们就没有必要包含类的定义文件.
简单的这样说是没有错的,但是实际上着还行不通,有时候我们还必须看到类的定义,这样的情况包括:
1)基类定义,例如class Parent:public Child{};那么Parent必须见到Child的完整定义
2)协变返回值.例如
class Child2{
virtual Child1 *get() const;
};
class Parent2: public Child2{
virtual Parent1* get() const;
};
这里Parent1和Child1是父子关系,在这种情况下,Parent2必须见到Parent1的定义(当然也就见到了Child1的定义),以保证C++编译器确认二者的继承关系.
从这个意义上,我们看到协变返回值是一种和继承关系类似的很强的耦合关系.
Zade's Weblog 