Saturday, June 23, 2007

Ubuntu 7.04

“Ubuntu" is an ancient African word that means "humanity to others".

继firefox热潮之后,ubuntu今年开始热起来,可以说这款打着“为人民服务”旗号的操作系统,已经愈来愈受“人民”的欢迎了。现在已经出现了不少get Ubuntu的连接,而且 ubuntu的传播方式比firefox更疯狂(下载/邮寄+免费+鼓励传播的标语)。

头条是Dell表示将在几款机型上预装linux操作系统,而且选择的就是ubuntu这么一个非企业级别(至少和redhat/suse相比)的个人系统。可以参考该网站 http://www.dellideastorm.com/

Dell的问卷调查表示,有70%的人要求能在机器上预装l inux。在Dell确定了预装的计划后,ubuntu及一些linux的粉丝们便开始组织要求各大公司发布linux版本软件的需求,其中包括要求暴雪发布基于linux的星际2,要求google移植主要软件到linux平台等等。(网站我都没记,不好意思)

除了ubuntu本身的四套发行版,Ubuntu/Kubuntu/Xubuntu/Edubuntu以外,不少网友都在为ubuntu扩大阵容:
  • Wubuntu - ubuntu狂热fans写的基于web的模拟ubuntu环境的网站,用的都是js写的。
  • Hiweed & Dubuntu — 在ubuntu中文站看到的,不知道其目的是什么,可能就是一个发行包吧。
  • Medibuntu - 提供关于media的ubuntu包。
当然,ubuntu本身在7.04 里作了不少工作。ubuntu本身bug改了不少,感觉更加舒适稳定了。如果是邮寄ubuntu光盘的话,可以用win来运行光盘,可以看到ubuntu为win用户同样提供了一些win下的软件。果然是for human beings,即使是对头的用户也要服务,这种精神太伟大了(当然不排除抢客户的嫌疑-_-b),如果仔细观察的话,就可以发现,目前大量的开源软件都是同时支持win和linux的,而且有许多人是同时在使用win和linux的,我想这和linux包容的心态是分不开的,毕竟人不应该在一棵树上吊死,不然就死得太冤了(我也支持win的哦),多样化的世界才是多彩的世界嘛。

最后不得不谈的是ubuntu疯狂的传播策略,真的是钱多得用来砸人了。要获得ubuntu或其他发行版,可以通过免费下载,这是大部分linux采用的。而ubuntu还提供了免费邮寄的服务,可以在ubuntu的网站上直接申请少量的光盘,或者申请大量光盘(需要确定)。在上大,机器人协会就申请了500张光盘,Canonical尽还都是免费地寄过来了(-_-b, so cool)。同时,ubuntu每张光盘上会写到,请与你的朋友分享该光盘的字样。我就要求了10张光盘(送贴纸),其中有一些是重复的,也就是~你可以拿出去送人,汗,要ubuntu找我。

Thursday, June 14, 2007

Netbeans的UML工具

今天差点被Netbeans的UML工具感动得哭了出来。从Netbeans4.0开始知道除了Eclipse还有一个这么好的IDE。虽然当时Netbeans离JBuilder和Eclipse还有很大的距离,但我一直十分坚持使用Netbeans,因为我从Netbeans身上学到的不光是使用一个IDE,更多的是做程序开发的思想。

记得那次我是写一个八数码的搜索算法分析的程序,用到了GUI,那时我发现在Label修改文本的时候可以有一个叫Resource Bundle的东西,于是我知道了Java的国际化,当时感叹啊。。。 于是呼,以后写程序坚决不在程序内直接放字符串常量,要么在头上声明个final引用,要么就Resource Bundle一下。

Netbeans的GUI编辑器是让我感动最多的地方,它的易用性给我减轻了很多的负担,使编程变得愉快而轻松。除了GUI编辑器以外,当时他的Web开发包也是让我感动死掉~,整合的Tomcat使得调式如此简便,就在当时我一再向周围的人推荐Netbeans,希望大家能把目光从Eclipse身上转移一点给Netbeans,但最后都是以失败告终。

后来Netbeans的合作开发包,虽然当时一直是对Eclipse的ECF感兴趣,但Netbeans的合作开发实在太先进了。还有JavaHelp等等,从Netbeans身上学了好多好多东西。

今天,为了在毕业设计里加几个UML图,尝试性地下载了Netbeans的UML工具包。哇!哭了,一上来就有三个选项:平台无关模型、Java模型、对Java项目做逆向工程。思路非常清晰,Java模型是主打,其他的仍然可以用平台无关模型。而我选择的是Java逆向工程,完美!把我那个项目所有引用到的类都解析出来了。然后使用使用看看,哦~~~太感动了,功能so强大。前一阵子在唠叨Poseidon For UML又慢又龊,于是乎去网上找了N个UML 开发工具,要么是付费的,要么就是太龊,而Eclipse的UML工具,建模没问题,只是图形开发环境得用最新的Eclipse,更新最新的满麻烦的。

以下这张UML,是我通过选中几个模型之后,自动创建的类图,然后稍加修饰的结果:


总之,Netbeans的UML工具智能化程度已经很高了,可能还不如一些收费工具来的厉害。但作为一款免费的IDE,免费的UML工具,已经是相当相当专业的。Sun不愧是开源的老大啊。

Friday, June 08, 2007

X over SSH

今天又学到一招,用ssh来图形远程登录。原本linux的图形远程登录比较熟悉的是vnc,但这次用ssh登录,比vnc快,而且犹如在本地运行一般。

可以用windows或linux登录有ssh server和x server的linux服务器。理论上,本地需要的是能运行x,及ssh客户端。

详细文档见此:X over SSH - A Tutorial

Wednesday, June 06, 2007

《为什么时光不能倒流》推荐

终于看完了。我一共参加过三次ACM/ICPC的比赛,另外有一次是在本校组织的地区赛。很幸运,四次都见到了CJ教授,而第五次则是CJ教授到学校里来宣传书的那一次。感觉教授有点嬉皮,很能调节气氛,就这一点算是个满讨人喜欢的教授。

昨天晚上睡不着,有点头疼(疼了有一段日子了),再加上蚊子嗡嗡的折磨,更加令我难以入睡。于是,捧起CJ教授的书,本打算是用作催眠的,却没有想到直到凌晨3点才有意识到太晚了。

《为什么时光不能倒流》宛如一碗鸡汤,滋补着我的心灵。拿到书的第一反应是惊讶CJ教授传奇的人生经历,而后从感动到感悟,每个故事都给了我一个人生的哲学。




今早起床,只睡了6个小时,但却额外精神,头不疼了,咦?真是有点奇怪哈,难道是心灵治愈了,身体就可以自然地治愈么。乘着头还没开始疼,赶快读完了书的剩余部分,确实是被感动了。这是一本适合年轻人,特别是那些儿时还是充满了憧憬和幻想,而现在却是忙忙碌碌,只是忙碌地不再是为了儿时所有的美好愿景的人,停下片刻,细细品味的美味鸡汤。

Tuesday, June 05, 2007

Stoer-Wagner算法

Stoer-Wagner算法是用来计算无向图的全局最小割的,理论上复杂度可以为O(|E|+|V|log|V|)。我的实现不是最好的,但觉得还行吧。

网友的好文章:最小割Stoer-Wagner算法

题目是百度06年的复赛题,星球大战。可以在POJ上练习,POJ2914。

相关论文和偶的代码,可点此下载

Stoer-Wagner算法的实现:


#include <iostream>
#include <algorithm>
using namespace std;

#define initSet(n,Arr) for(int i=0;i<n;++i)Arr[i]=i;
#define MAX 1<<30;
int graph[600][600];

// Stoer-Wagner Algorithm
int globalMinCut(int n){
// A is A set for Stoer-Wagner Algorithm
bool* A=new bool[n];
// V is vertex index
int* V=new int[n];
int* W=new int[n];

initSet(n,V);

int best=MAX;
while(n>1){

//the most tightly connected vertex.
int maxj=1;

// initialize set A and other vertex's weight
A[V[0]] = true;
for(int i=1; i<n; ++i){
A[V[i]]=false;
W[i]=graph[V[0]][V[i]];

if(W[i]>W[maxj])
maxj=i;
}

// find a min-cut
int prev=0,buf=n;
while(--buf){
// add it to A
A[V[maxj]]=true;

if(buf==1){
// update min cut
best=min(best,W[maxj]);

// merge prev and last vertex
for(int k=0; k<n; ++k)
graph[V[k]][V[prev]]=(graph[V[prev]][V[k]]
+=graph[V[maxj]][V[k]]);
V[maxj]=V[--n];
}
prev=maxj;
maxj=-1;

// update the weights
for(int j=1; j<n; ++j)
if(!A[V[j]]){
W[j]+=graph[V[prev]][V[j]];

if(maxj<0 || W[j]>W[maxj])
maxj=j;
}
}
}

delete[] A;
delete[] V;
delete[] W;
return best;
}


int main(){
// n - vertex number
// m - edge number
int n,m;

while(scanf("%d %d",&n,&m)==2){
memset(graph,0,sizeof(graph)/sizeof(bool));

// v-w is an edge with c weight
int v,w,c;

while(m--){
scanf("%d %d %d",&v,&w,&c);
graph[v][w]+=c;
graph[w][v]+=c;
}

// output min cut
printf("%d\n",globalMinCut(n));
}
}


Saturday, June 02, 2007

百度之星2007初赛

HOHO,恭喜恭喜,上大的四人都过初赛啦! 我,梁老大,沈还有Jackie Yu。我和Jackie两天都做了,沈做了第一天,梁做了第二天。最后沈和梁晋级,我靠第一天晋级,Jackie靠第二天晋级。我第一天拿了30分(题1全过,题2过一半),比期望的低哦,最后的那道SQL本来希望能过两个CASE的,结果全挂了,555,沈也是用暴力解的,但他过了两个CASE,估计是我哪里细节出了问题,导致全错。第二天很郁闷,中午做题果然没晚上精神爽,直打瞌睡。第二天只做了两道(1,4),最后的结果是第1题只对了一个case, -_-b,超级郁闷,后来发现程序里少了两句判断,555,不然第二天也能晋级啦,现在只有9分,不过还好有第一天保底(只是对不住陈胖子了呀)。

题目可以见某网友的帖子,感谢他保留了百度试题:
http://www.ninstein.com/blog/article.asp?id=199
http://www.ninstein.com/blog/article.asp?id=202

其他的题目就不说了,百度有点评(第二天要准备trie的模板呀),我个人对第一天的第四题SQL的SELECT语句比较感兴趣,所以重新做了一遍:

基本上是做了两点的优化(较暴力法),一个是结构上加了索引,二是计算满足条件的几个集合的交集(在结构的基础上优化的求交算法)。

为了说明结构我画了图,还不错吧 ^_^


简单说明一下,该结构完全是为了针对题目而做的,我考虑下,为了实现Delete, Update还需要修正一下结构,而且结构改动后后面的Select算法也要调整。另外,Select是单向的,即只能由条件找出记录号,不能由记录号找出记录的所有信息,要实现的话应该在Record上再加一些变量。不管了,只是针对AND逻辑的嘛。

Table[i][j]的位置不是存放第 i 记录的第 j 字段值,而是存放一个指针,指向下一个与Table[i][j]值相同的记录号,也就是链表结构。索引表存放的才是字段值,对应一个startId是在Table中的第一个拥有该字段值的记录号,即链表的head。

假设,按图中sample有5条记录,0 1 3的c3字段值为a,2 4的c3为b。那么Select c3为a的所有记录,就是在IndexTable中找c3的字段索引,然后找对应的a的startid,得0。然后回表中开始找出所有记录,Table[0][c3]=1, Table[1][c3]=3, Table[3][c3]=-1。-1为终止,于是有 0 1 3 三条记录。

由上可以求出,满足某字段值的一个集合。第二步是求满足多个字段值的一个交集。由于结构本身提供了一个很有利的条件,即若Table[i][j]的字段值等于Table[i][k]且两者均不为-1,则Table[i][j]<table[i][k]当且仅当 j<k,算法描述如下:

(假设满足求n个condition的记录数count=0)
if condition is empty
count=recordNum, exit

准备一个索引数组tb,tb[i]代表 i 条件下的当前记录号。tb初始全-2。
foreach condition as ci
int tmp= IndexTable中ci条件的startid值,无法满足ci,则tmp=-1
if tb[ci] 已存在,即 !=-2
if tb[ci]!= tmp
count=0, exit
else
next condition
else
tb[ci]=tmp

依某算法(算法很多,自定吧)取字段c为主键,可以理解为取某个condition为主条件

while tb[c]!=-1
foreach condition as ci
if ci==c
continue
else
while tb[ci]<tb[c] && tb[ci]>=0
tb[ci] = Table[tb[ci]][ci] // next record
if tb[ci]>tb[c] || tb[ci]==-1
break;
if all condition matched
count++
else
tb[c]=Table[tb[c]][c]

count is result

复杂度分析: 空间复杂度上是不会亏的啦,字段值没有重复保存过,索引用的都是数字。设记录数n,字段数c,构造DB时的复杂度O(nc)。设某个查询的条件是q条,查询的复杂度min(q,c)+sum(count(qi)) min(q,c)是条件数和字段数取小者,qi表示第i个条件,count是满足i条件的记录数(可以缓存一下的),sum()为求和函数。

其他建议:取主键的算法很多(甚至可以不取,直接假设第一个条件对应的键为主键),可以单纯地用缓存过的满足条件的记录数来决定记录数最少的那个为主键。但对于复杂度不会有提高,因为如果按我上述的算法,复杂度是固定的,主键不影响复杂度。

存在不同主键的情况下会影响复杂度的算法,假设已经求到Table[i]是满足所有条件的记录,那么求下max(Table[i][cj]) cj为每个条件对应的字段,只有最大值对应的记录才有可能为下一条满足所有条件的记录,即使他不是满足所需要的记录,那么只要循着该字段一定能找到真正的下一条满足所有条件的记录。这种跳跃式的算法,可以有效减小复杂度。

缺点:结构只是针对select and做了优化,并没考虑太多,可能会不方便其他操作。优化中将记录标号了,虽然现在大部分表都喜欢加个id,但数据库本意是记录无序的。如我图中所画,DB有许多Table,而只有一个IndexTable,我的想法是一个IndexTable可以管理所有有关联的Table的所有字段,以优化做select and操作。但还没设计完,现在的IndexTable显然是不行的,以后有机会再说吧。

偶的代码(C++),大致实现了上面的结构和算法,测试数据使用MySQL 的sakila sample 的payment表,修正后的数据以及代码点此下载 (放在上大ACM论坛,-_-b荒废好久的论坛啊,只能用来摆摆文件了):



#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <utility>
#include <sstream>
#include <algorithm>
using namespace std;

// DB structs
// first is startId, second is len(len may be tempory used for other target)
typedef pair<int,int> Index;
typedef map<string,Index> FieldIndex;
typedef vector<FieldIndex> IndexTable;
typedef map<string,int> ColumnName;
typedef vector<int> Record;

struct DB{

// a table (since only one table provided)
string name;
vector<Record> records;
int recordNum,columnNum;
ColumnName nameMap;

IndexTable it;

DB(int n,int c):recordNum(n),columnNum(c){
records.resize(n);
it.resize(c);
for(int i=0;i<n;++i){
records[i].resize(c);
}
}
};

// Query structs
typedef pair<string,string> Expression;
typedef vector<Expression> Query;

// called while constructing the DB and IndexTable
int addValue(FieldIndex& index, string& value,int curIndex){
map<string,Index>::iterator iter=index.find(value);
int lastIndex=-1;

if(iter==index.end()){
index[value]=Index(curIndex,curIndex);
}else{
lastIndex=index[value].second;
index[value].second=curIndex;
}

return lastIndex;
}

void initDB(DB& db){
string buf;
// parse db name
cin>>db.name;
getline(cin,buf);

// parse column name
getline(cin,buf);
stringstream ss(buf);
string name;
for(int i=0;i<db.columnNum;++i){
ss>>name;
db.nameMap[name]=i;
}

// parse db records
for(int i=0;i<db.recordNum;++i){
getline(cin,buf);
stringstream ss(buf);

for(int j=0;j<db.columnNum;++j){
string value;
ss>>value;
db.records[i][j]=-1;
int lastId=addValue(db.it[j],value,i);
if(lastId>=0){
db.records[lastId][j]=i;
}
}
}
}

bool isExpression(string& str){
int len=str.length();
for(int i=0;i<len;++i){
if(str[i]=='=')return true;
}
return false;
}

bool validChar(char c){
return (c>='0' && c<='9') || (c>='a' && c<='z') || (c>='A' && c<='Z');
}

void parseExpression(string& str, Expression& exp){
int i=0,st=0,len=0;

while(!validChar(str[i]))++i;
st=i;
while(validChar(str[i]))++i;
len=i-st;

exp.first=str.substr(st,len);

while(!validChar(str[i]))++i;
st=i;
while(validChar(str[i]))++i;
len=i-st;

exp.second=str.substr(st,len);
}

int doQuery(DB& db,string& q){
int cnt=0;
stringstream ss(q);
string buf;
Query query;

while(ss>>buf){
if(isExpression(buf)){
Expression exp;
parseExpression(buf,exp);
query.push_back(exp);
}
}

if(query.empty())return db.recordNum;

int* tb=new int[db.columnNum];
fill(tb,tb+db.columnNum,-2);

for(Query::iterator iter=query.begin(); iter!=query.end(); ++iter){
int col=db.nameMap[iter->first];
map<string,Index>::iterator mapIter=db.it[col].find(iter->second);
if(mapIter!=db.it[col].end()){
int st=(mapIter->second).first;
if(tb[col]>=0 && st!=tb[col]){
return 0;
}else if(tb[col]<0){
tb[col]=st;
}
}else tb[col]=-1;
}

int lastValue=-1;
while(true){
int i=0,curValue=-1;
for(;i<db.columnNum;++i){
if(tb[i]==-2)continue;
if(lastValue>=0 && tb[i]==lastValue){
tb[i]=db.records[tb[i]][i];
}
if(tb[i]==-1)break;

if(curValue==-1){
curValue=tb[i];
}else{
while(tb[i]<curValue && tb[i]>=0){
tb[i]=db.records[tb[i]][i];
}

if(tb[i]>curValue || tb[i]<0){
break;
}
}
}
lastValue=curValue;
if(tb[i]==-1 || curValue==-1)break;
if(i==db.columnNum){
++cnt;
}
}

delete[] tb;
return cnt;
}

// main entry
int main(){
int c,n,q;
cin>>c>>n>>q;
DB db(n,c);
initDB(db);

string line;
while(q--){
getline(cin,line);
cout<<doQuery(db,line)<<endl;
}
}