Programming 版 (精华区)

发信人: SwordLea (飞刀李), 信区: Programming
标  题: [程序大战]20040720 第3小板凳
发信站: 哈工大紫丁香 (Fri Jul 23 09:50:45 2004), 站内

9:51 2004-7-23
    第2小板凳以失败告终，其hash匹配方式被编译器无情地宣判了死刑。
    考虑到二进制文件中不可显示字符较多，决定采用快速跳跃预判断方法，
原理如下图所示：
              |
              V -> 若最短长度处字符不匹配，快速跳到下一个最短长度
|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|~~|
|* |* |  |* |X |  |  |  |  |* |  |  |  |  |  |  |  |  |  |  |  |  |
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|
                ^
                | 若本次下跳不满足，由下一字符开始

本次测试结果：21441ms  


各次测试结果比较                                
--------------------------------------------------------------------- 
|板凳\耗时|          |                备       注                   |
----------|----------|-----------------------------------------------
|   1     | 27851 ms |   用vector优化了CString 的 += 操作           |
----------|----------|-----------------------------------------------
|   2     | 35361 ms |   用hash表减少了比较次数                     |
----------|----------|-----------------------------------------------
|   3     | 21441 ms |   预判断最短长度处字符，快速下跳             |
--------------------------------------------------------------------- 

  
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]; 
}
    
--
    I came, I saw, I conquered ! — Caesar


※ 修改:·SwordLea 于 Jul 23 10:07:59 修改本文·[FROM: 202.118.246.241]
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.246.241]