Programming 版 (精华区)

发信人: SwordLea (飞刀李), 信区: Programming
标  题: [程序大战]20040720之守擂程序
发信站: 哈工大紫丁香 (Tue Aug  3 08:59:53 2004), 转信

8:51 2004-8-3
    考虑过对小于最小长度的串采用二分查找以减少比较次数，
但实际应用发现算法复杂度开销将使算法用时更多（可能最小
长度增加到一定程度情况会有好转），故现将第3小板凳作为守
擂程序。
    攻擂方法，攻擂者可在VC中新建DIALOG工程，将下面代码
加入工程（可能需要加入“说明”中的计时器类），运行后得
出本地运行所需时间作为参照（建议连续运行三次取平均值）。
任何符合本次比赛规则的VC程序，如果所需时间少于本守擂程
序200ms 以上，可以作为攻擂程序帖出来，由擂主编译后在其
  ~~~~~~ 这里改了一下，大概10%的效率提升。
本地机器运行检测。当然其它感兴趣的同学也可以编译运行，
作为评判。
    Ok, are you ready ?

本次测试结果：21441ms  
              ~~~~~~~声明：一直以来这里有个错误，
                     后面的%ul应为%u，其实是2144ms
#include <vector>

typedef struct _Filter
{
    DWORD dwID;     // 该字符串出现序号(由0开始)
    DWORD dwOffset; // 在文件中偏移
    short nLength;  // 该字符串长度
    char* lpString; // 该字符串内容
}Filter,*PFilter;

void StrFilter(LPBYTE pBuffer, DWORD dwFileSize, int nLen, CString &sResult)
{
    std::vector<Filter> vFilter;
    DWORD dwID = 0;
    int len = 0;
    for (DWORD i = 0; i < dwFileSize; i ++)
    {

        // 2004-7-23 9:57 最短长度处字符判断
        BYTE ch = *(pBuffer + i + nLen - 1);
        if (!(ch >= 32 && ch <= 126)) 
        {
            i += nLen - 1; // -1为了抵消 i ++
            continue;
        }

        ch = *(pBuffer + i );
        for(int len = 0; ch >= 32 && ch <= 126; len ++)
            ch = *(pBuffer + i + len);

        if (len > nLen)
        {
            // 长度合格
            Filter f;
            f.dwID = dwID ++;
            f.dwOffset = i ;
            f.lpString = new char[len];
            if (!f.lpString ) return ;
            strncpy(f.lpString , (LPCTSTR)pBuffer + i, --len);
            f.lpString[len] = 0;
            f.nLength = len;
            vFilter.push_back(f);
            i += len;
        }
    }
    std::vector<char> vBuffer;
    for (PFilter p = vFilter.begin(); p != vFilter.end(); p ++)
    {
        CString sBuf;
        sBuf.Format("%u: Offset:%u   Length:%d\t%s\r\n", 
            p->dwID, p->dwOffset, p->nLength,p->lpString);
        
        for ( int j = 0; j < sBuf.GetLength(); j ++) 
            vBuffer.push_back(sBuf.GetAt(j));

        delete(p->lpString);
    }
    vBuffer.push_back(0);
    sResult = &vBuffer[0]; 
}
void CTest1Dlg::OnOK()
{
    CRichEditCtrl *pRiched = &m_ctrlRichEd;
    CLocalCalculagraph cc;
    CFile f;
    if (!f.Open("d:\\tmp\\MinGWStudioFullSetupPlus-2.02.exe",CFile::modeRead))
        return;

    DWORD dwSize = f.GetLength();

    LPBYTE pBuffer = new BYTE[dwSize + 1];
    f.Read(pBuffer ,dwSize );
    f.Close();

    cc.Start();
    CString sResult;
    StrFilter(pBuffer , dwSize, 5, sResult);
    cc.Stop();

    pRiched->SetWindowText(sResult);
    delete pBuffer ;

    // 以下是用于评测的结果
    CString sMsg;
    sMsg.Format("Used time:%ulms", cc.GetElapsedTime() );
                            ~~~~~ 注意，应该是%u
    AfxMessageBox(sMsg);
}
--
    I came, I saw, I conquered ! — Caesar


※ 修改:·SwordLea 于 Aug  3 17:00:12 修改本文·[FROM: 202.118.246.*]
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.246.*]