百度之星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;
}
}