• 今天的目标有两个:一把搜索相关的基础算法,整理白纸编程并完整实现;二切掉DP的三道水题;三恢复下口语和智力测试。
  • 和袁源聊了一下,一是讨论这道题目,二是讨论一些关于工作的事情。题目的讨论让人多有感慨的,袁源的思路还是相当的严谨,这个是要值得自己学习的。工作上的事情,谢谢点虫虫,代毅的关心,兄弟很感激,也会好好规划自己的未来的;袁源说,其实你也可以考虑去一些起步规模不大的公司,但一定要保证自己就是要做核心的事情,有了经验的积累之后很多事情就水到渠成了,先尽全力去能人众多的公司,为自己定的方向找个好老师,好好锻炼吧!涓涓细流,终汇成海,自己虽然起步晚,天资不足,但还可以靠勤奋和踏实找到自己的位置的!加油!
  • 刚刚老谢同学问了一道动规的题目,还是迅速切掉吧,夜长梦多。下面是发给他的分析和代码实现,可以用字典树优化的,不难就是了。
1,动规方程分析:
和刚才的思路一样,最原始的动规方程式d[i,j]=min{d[i, k-1]+d[k,j]},d[i,j]表示从i到j的数字索引位置包含的最少词个数。[忘记加这个了,呵呵!最优子结构嘛,编程的时候先就去想字典的结构了,还是要注意的。其实这里没写,关键在于如何存储转化字典用vector<int>还是其他的,再扫下题目的输入,就有答案了。]
再进一步,由于我们可以从0的位置开始,那么这个方程就可以简化为d[i]=1+min{d[j]},j>i,表示从i到j-1的位置匹配了一个单词。这样动规就变成线型了。
2,关键的问题在于:如何匹配词和将词转化为字典,观察到要输出这些词,换言之,必须要保存原始的词,同时也要计算出转化为数字的词
所以存储上可以用一个vector<int> words来做每一个数字开头的字典,然后vector<string> org_words[MAXN];存储原来对应的词,至于动规取到的词,我们可以
用一个数组来保存决策值。
3,如何实现动规,可以用至底向上,但是,刚才提到了这个状态是稀疏的,也就是每一个数字开头不一定能匹配到值,所以好的办法是记忆搜索。可惜的是,这道题目的运行表现差强人意了,我郁闷!瓜了,运行的结果和CEOI的答案不一样,想了5分钟,结果是special judge,差点一口血吐到屏幕了。

Source Code

Problem: 1732 User: orlando22
Memory: 2040K Time: 157MS
Language: C++ Result: Accepted
  • Source Code
    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    //dictionary check
    const int dicSize=26, MAXNUM=100, MAXN=10;
    char dic[dicSize]={'2', '2', '2', '3', '3', '3', '4', '4', '1', '1', '5', '5', '6', '6', '0',
                '7', '0', '7', '7', '8', '8', '8', '9', '9', '9', '0'};
    vector<string> words[MAXN];
    vector<string> org_words[MAXN];
    string tword;//for target word for string
    int dp[MAXNUM];
    string ins[MAXNUM];
    
    //declaration
    string ToNumStr(string temp);
    int calShort(int index);
    
    //impelemenation
    string ToNumStr(string temp){
        string tw;
        for(int i=0; i<temp.size(); i++) tw.push_back(dic[temp[i]-'a']);
        return tw;
    }
    int calShort(int index){
        if(index==tword.size()) return 0;//upper boundary
        if(dp[index]!=-1) return dp[index];
        //enum for all words of tword[index]
        int ret=INT_MAX, t=tword[index]-'0';
        for(int i=0; i<words[t].size(); i++){
            bool match=true;
            int k=index, tid=0;
            for(;k<tword.size()&&tid<words[t][i].size(); k++, tid++){
                if(tword[k]!=words[t][i][tid]){
                    match=false; break;
                }
            }
            if(match&&k<=tword.size()&&tid==words[t][i].size()){//all length has been used by tid.写些垃圾代码,边界值老子
                int next=calShort(index+words[t][i].size());
                if(next!=INT_MAX&&next+1<ret){
                    ret=next+1, ins[index]=org_words[t][i];
                }
            }
        }
        dp[index]=ret;
        return ret;
    }
    
    int main()
    {
        //implementation
        int diclen, result; string temp, trword;
        cin>>tword>>diclen;
        for(int i=0; i<diclen; i++){
            cin>>temp, trword=ToNumStr(temp);
            words[trword[0]-'0'].push_back(trword),
            org_words[trword[0]-'0'].push_back(temp);//must store the orignal string
        }
        //DP table
        memset((void*)dp, 0xff, sizeof(dp));
        result=calShort(0);
        if(result==INT_MAX) cout<<"No solution."<<endl;
        else{
            int num=0;
            for(int j=0; j<tword.size(); j=j+ins[j].size(), num++){
                if(num==0) cout<<ins[j];
                else cout<<" "<<ins[j];
            }
            cout<<endl;
        }
        return 0;
    }
  • 从基础的排序实现到基础的搜索算法:题目的抽象原型是BOP的K个最大的数,第一次看写程序的时候觉得那些方法完全没有内在联系,什么东西嘛。再回头都实现一遍[搜索部分留到写软件的时候实现,先提代码实现框架吧]大多数东西是BOP上的衍生思考,没有原创性。^_^|||
Q:假如给你一堆数,怎么求出最大的K个?
应该反思的是,数在哪里?有多大[每个数的字节长度,总数组的规模],求的过程需要多长时间,空间。数的输入规模和输出规模多大。一切都不知道,那只有把(N,K)作为参数做一个递增的分析了。
  • 1,假设N<10^9,那么一个程序的bss段里面应该是能放下的,不妨从内部排序开始分析。

    先假设K~N,那么可以用最简单的思路比较排序嘛,下面实现了比较排序里面的快排,归并和堆排。提醒自己还是要小心,基础的咚咚要一点都不能含糊。

    //inneral sorting algorithm
    template<class Type>
    void qsort(int l, int r, Type* arr){
        while(l<r){
            int p=l, q=r+1;
            while(true){
                while(++p<r&&arr[p]<arr[l]);
                while(--q>l&&arr[q]>arr[l]);
                if(p>=q) break;
                swap(arr[p], arr[q]);//previous bug
            }
            if(l!=q) swap(arr[q], arr[l]);
            qsort(l, q-1, arr);
            l=q+1;
        }
    }

    //merge sort algorithm
    int b[9];
    template<class Type>
    void mergesort(int l, int r, Type* arr){
        if(l<r){
            int mid=l+((r-l)>>1), p=l, q=mid+1, k=l;
            mergesort(l, mid, arr), mergesort(q, r, arr);
            while(p<=mid||q<=r){
                if(p<=mid&&(q>r||arr[p]<=arr[q])) b[k++]=arr[p++];
                else b[k++]=arr[q++];
            }
            for(int i=l; i<=r; i++) arr[i]=b[i];//where is it b?
        }
    }

    //heap-sort algorithm : selective algorithm.
    template<class Type>
    void heapadjust(int current, int heapEnd, Type* arr){
        int child=(current<<1)+1;
        Type tmp=arr[current];
        while(child<=heapEnd){
            if(child+1<=heapEnd&&arr[child]<arr[child+1]) child++;
            if(tmp<arr[child]||tmp==arr[child]) break;
            swap(arr[current], arr[child]);
            current=child, child=(child<<1)+1;
        }
    }
    template<class Type>
    void heapsort(int size, Type* arr){
        for(int i=(size>>1); i>=0; i--) heapadjust(i, size-1, arr);
        for(int i=size-1; i>0; i--){
            swap(arr[0], arr[i]);
            heapadjust(0, i-1, arr);
        }
    }

    先全部排序,然后把K个输出即可,时间复杂度为O(NlogN)。由于K~N,所以在比较决策树的模型之下,已经是比较好的一种算法了。

  • [当然,可以来个逆向思维,K~N那么N-K~0,那么这个问题就可以转化为求N-K个最小数的模型,复杂度是可以改进的。但这里是总结思路,主要看算法的实现技巧,不钻牛角尖料。]
    2,对于K<<N的情况下,可以只取前面的最大K个。等下没说过前K个一定排序,所以首先想到的是中位数处理问题的算法。求出K大的即可
    • 对于内排而言,可以直接写出求k大数的快排,实现代码如下,O(N*logK)

    //k’s sorting algorithm
    template<class Type>
    void ksort(int l, int r, const int& k, Type* arr){//min-k
        if(l<r){
            int p=l, q=r+1;
            while(true){
                while(++p>r&&arr[p]<arr[l]);//remember the boundary check.
                while(–q>l&&arr[q]>arr[l]);
                if(p>=q) break;
                swap(arr[p], arr[q]);
            }
            if(l!=q) swap(arr[l], arr[q]);
            if(q-l+1==k) return;
            else if(q-l+1<k) ksort(q+1, r, k-(q-l+1), arr);
            else ksort(l, q-1, k, arr);
        }
    }

    • 下一个方法是开始我没想通的,觉得BOP的神牛们简直太强了,神来之笔呀。仔细分析下,其实是有来源的,这是一种参数搜索的思路,在一些DP和搜索的算法实现中,由于参数范围过大,导致盲目搜索代价太高,所以我们利用其函数单调性[抄书问题是个典型]来在不同的范围求解以求最终逼近真实值。这个问题的真实值是具备单调性的,原始的我们可以猜想k大的数为最小数,然后统计出个数,再一步一步来,进一步二分可解。只是要先求出K大的数,再过一遍N数[是N数么?其实不是只需要[目标区间]的所有值,这样就可能从内排突破到外派,强呀,佩服]。下面是代码实现,复杂度为O(Nlog(|Vmax-Vmin|/delta)).

    //declaration
    void ksearch(int size, const int& k, int* arr);
    void MinMax(int l, int r, int* arr, int& Vmax, int& Vmin);
    int count(int size, int* arr, int Vmid);
    //parameter search
    void ksearch(int size, const int& k, int* arr){
        double delta=.5;
        int Vmax, Vmin, Vmid;
        MinMax(0, size-1, arr, Vmax, Vmin);
        while(Vmax-Vmin>delta){
            Vmid=Vmin+(Vmax-Vmin)/2;
            //here is the bottle neck of algorithm.
            if(count(size, arr, Vmid)>=k) Vmin=Vmid;
            else Vmax=Vmid;
        }
        Vmax=floor(Vmax);
        for(int i=0; i<size; i++){
            if(arr[i]>=Vmax) cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
    void MinMax(int l, int r, int* arr, int& Vmax, int& Vmin){//用了个瓜兮兮的分治
        if(l+1<=r){
            if(arr[l]<=arr[r]) Vmax=arr[r], Vmin=arr[l];
            else Vmax=arr[l], Vmin=arr[r];
            return;
        }
        int mid=l+((r-l)>>1), k1, k2;
        MinMax(l, mid, arr, Vmax, Vmin), MinMax(mid+1, r, arr, k1, k2);
        if(Vmax<k1) Vmax=k1;
        if(Vmin>k2) Vmin=k2;
    }
    int count(int size, int* arr, int Vmid){
        int count=0;
        for(int i=0; i<size; i++) if(arr[i]>=Vmid) count++;
        return count;
    }

    • 大顶堆算法,呵呵,好耍!这个算法就可以彻底将内排在可能情况下(K内存可存)扩展到外排。过一遍数组,一边过一边建堆,大顶堆即为所求。O(NlogK)

    //minheap algorithm.
    template<class Type>
    void filterup(int current, Type* arr){
        int parent=(current-1)/2; Type tmp=arr[current];
        while(parent>=0){
            if(arr[parent]<=arr[current]) break;
            swap(arr[parent], arr[current]);
            current=parent, current=(current-1)/2;
        }
    }
    template<class Type>
    void filterdown(int current, int heapEnd, Type* arr){
        int child=(current<<1)+1; Type tmp=arr[current];
        while(child<=heapEnd){
            if(child+1<=heapEnd&&arr[child+1]<arr[child]) child++;
            if(tmp<arr[child]||tmp==arr[child]) break;
            swap(arr[child], arr[current]);
            current=child, child=(child<<1)+1;
        }
    }

    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("in1.txt");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif

        //implementation, inneral sorting. O(NlogK)
        int u;
        while(!in.eof()&&cin>>u){
            if(lsize<MAXK){
                list[lsize++]=u, filterup(lsize-1, list);//maintain minheap
            }
            else if(u>list[0]){
                list[0]=u, filterdown(0, MAXK-1, list);
            }
        }
        for(int i=0; i<MAXK; i++) cout<<list[i]<<" ";
        cout<<endl;

    #ifdef fbase
        in.close();
    #endif
        return 0;
    }
    #undef fbase

    • 然后就是线形排序的处理了,计数排序的实现如下:注意可以省去Copy数组的。好,看代码

    const int MAXN=20, MAXM=40;
    int t[MAXN], ct[MAXM], b[MAXN];
    //counting sort
    void csort(int size, int* arr){
        for(int i=0; i<size; i++) ct[arr[i]]++;//clr ct in advance.
        for(int i=1; i<MAXM; i++) ct[i]+=ct[i-1];
        //suppose there are tareget array
        //s1 : for(int i=0; i<size; i++) b[ct[arr[i]]-1]=arr[i], ct[arr[i]]–;//can we ignore such b[0…size] array or not?
        //s2 : forward-star
        for(int i=MAXM-1; i>=1; i–){
            for(int j=ct[i]-1; j>=ct[i-1]; j–) arr[j]=i;
        }
        for(int i=0; i<ct[0]; i++) arr[i]=0;
    }

    完了么?但作者在最后莫名其妙的写了一个桶排[分段后面用链表连起来,在链头维护下元素范围和大小],好奇怪,而且似乎欲言又止。

    3,扩展的外沿==在线搜索的基础算法雏形

  • 扩展1,求N个数中不同的k数。
    思路一:在内排许可下,可以先用insertsort去重,然后再套用上面的快排或者参数搜索。[但这个局限性太大,只能内排,设N->无穷,就肯定没戏]
    思路二:外排扫描一次文件,求出其数值区间;然后使用桶排分块,插入数据,维护一个K数的可用区间范围,然后进行插入,这样就可以避免重复。条件:在K内存可放的情况下
    思路三:其实是最先想到的,大顶堆算法,加一个K的比较,假如再加一个挨球的改进进去,不是我想的。Jon有个人为二分的算法,在大顶堆内记录其1/2区间范围,
  • 就可以将判重的查找强行降到O(logK). 想了下,写了个快排的实现,结果发现有点忘记考虑了,除平衡位置外,其他数据的重复不可用。
    思路四:大顶堆算法,做一个try-rollback的操作,这个思路相当妙。值得让人拍案,不敢贪功,袁源的思路,但值得一写。
     
    所以,这条路貌似不行,或许是我有点笨吧。
     
  • 至于k到m的,思路二三都可用。
  • 扩展3的问题:就是一个搜索的基本算法问题了,原始的思路就是思路二,学名叫HYBRID Scheme;再多线程条件的改进算法,叫做Codir。不敢说是自己想的,见参考资料:BalalaBa
  • 扩展4的问题:可以提炼为一个模型,单查询多机存储的调度问题[自己改的名字,瓜求得很]:因为对于一个query的查询结果已经不可能在一台机器下存下了,但用户又需要快速的反应,起码一秒吧,如果是我的话,100MS没反应,我肯定就要锤墙了。那就用多台机器把query的返回结果放入各自的内存系统,然后用调度算法来取出其最大的K个。这里作者是提示不要钻牛角尖吧,将多个机器的K个或者。9K个精确页面进行合并求出其最大的K个,最经典的是多路归并的败者树[达平和老谢的最爱],或者k路归并的经典算法,其实大顶堆也在可取之类。只是如作者所说,应该要多个连续堆来处理吧。
  • 扩展5的问题:我已经无力解答了[确实经验不够],因为关键字的相似度如何推算出文档的相关度,确实不知道,但可以这样看,假设我们能获取到前K个文档,然后呢,下一个查询关键字和当前关键字很接近[相似度公式],我们就可以求出其相似度,进而用相似度求出其文档权重,但这个文档权重是估计值,应该还要加上估计公式,这样大概就能求出其准确程度,我们提供这个K个文档最精确的子集作为下一次查询的备选集。很多地方没想清楚,首先公式不好设计,其次是搜索的模型还和这些东西相关.瞎说的,烧烤而已。
  • 想写个小软件跑下抓取和桶排了!手痒的很。上面的扩展分析自己写的,应该很有多错误,希望假设有的朋友觉得有错,一定要给我指出来哈,最好能分析下!先谢谢了!

    Advertisements