Programming 版 (精华区)

发信人: SwordLea (飞刀李), 信区: Programming
标  题: [程序大战]20040720之守擂程序(修改版)
发信站: 哈工大紫丁香 (Thu Aug  5 09:07:24 2004), 转信

8:37 2004-8-5
    为更好地突出是算法效率的比赛，现将评比方法稍加修改，
结果保存时间不参与计时。
    攻擂方法，攻擂者可在VC中新建DIALOG工程，将下面代码
加入工程（可能需要加入“说明”中的计时器类），运行后得
出本地运行所需时间作为参照（建议连续运行三次取平均值）。
任何符合本次比赛规则的VC程序，如果所需时间少于本守擂程
序  8%  以上，可以作为攻擂程序帖出来，由擂主编译后在其
本地机器运行检测。当然其它感兴趣的同学也可以编译运行，
作为评判。
本次测试结果：632ms  
    测试结果：307457 项

// 使用FileMapping 读文件
// FileMap.h
#ifndef _MY_FILEMAP_H
#define _MY_FILEMAP_H
class CFileMap  
{
public:
        BOOL GetData(LPBYTE * ppBuffer)
        {
                if (m_pBase)
                {
                        *ppBuffer = m_pBase;
                        return true;
                }
                return false;
        }
public:
        DWORD GetSize()
        {
                return m_dwSize;
        }
public:
        CFileMap(LPCTSTR lpFileName)
        {
                m_hMapping = m_hFile = INVALID_HANDLE_VALUE;
                m_pBase = NULL;

                m_hFile = CreateFile(lpFileName , GENERIC_READ , 0, NULL , 
                        OPEN_EXISTING , 0 , NULL);

                if (m_hFile != INVALID_HANDLE_VALUE)
                {
                        // 取数据长度
                        m_dwSize = GetFileSize(m_hFile , NULL);
                
                        m_hMapping = CreateFileMapping(m_hFile ,  NULL , PAGE_READONLY , 0 , 0 , NULL);
                        if (m_hMapping )
                        {
                                m_pBase = (LPBYTE)MapViewOfFile(m_hMapping , FILE_MAP_READ , 0 , 0 , 0);
                        }
                }
        }
        virtual ~CFileMap()
        {
                if (m_pBase) 
                {
                        UnmapViewOfFile(m_pBase);
                        m_pBase = NULL;
                }
                if (m_hMapping != INVALID_HANDLE_VALUE) 
                {
                        CloseHandle(m_hMapping);
                        m_hMapping = INVALID_HANDLE_VALUE;
                }
                if (m_hFile != INVALID_HANDLE_VALUE) 
                {
                        CloseHandle(m_hFile);
                        m_hFile = INVALID_HANDLE_VALUE;
                }
        }
private:
        HANDLE  m_hMapping, m_hFile;
        LPBYTE  m_pBase;
        DWORD   m_dwSize;
};
#endif//_MY_FILEMAP_H

// 使用vector 实现的字符串类
// String.h
#ifndef _MY_STRING_H
#define _MY_STRING_H

#include <vector>

class CVectorString: public std::vector<char>
{
public:
        CVectorString(){}
        CVectorString(LPCTSTR lpString) 
        {
                *this += lpString;
        }
        CVectorString(char ch) 
        {
                *this += ch;
        }
        void operator += (LPCTSTR lpString)
        {
                for (;*lpString;lpString++)
                        push_back(*lpString);
        }
        void operator += (char ch)
        {
                push_back(ch);
        }
public:
        void Trim(char ch)
        {
                while (back() == ch) pop_back();
        }
};
#endif//_MY_STRING_H

// 2004-8-5
#include "String.h"     // CVectorString 支持
#include "FileMap.h"    // CFileMap      支持


// 进程计时器
class CLocalCalculagraph
{
public:
        void Start()
        {
                start = clock();
        }
        void Stop()
        {
                end = clock();
        }
        DWORD GetElapsedTime()
        {
                return end - start + 1; // 防止结果为零
        }
private:
        clock_t start, end;
};     

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


void StrFilter(LPBYTE pBuffer, DWORD dwFileSize, int nLen, CString &sResult, DWORD *pdwElapsedTime)
{
        // 2004-8-5 计时开始
        CLocalCalculagraph cc;
        cc.Start();
        
        std::vector<Filter> vFilter;
        DWORD dwID = 0;
        for (DWORD i = 0; i < dwFileSize; i ++)
        {
                BYTE ch = *(pBuffer + i + nLen - 1);
                if (!(ch >= 32 && ch <= 126)) 
                {
                        i += nLen - 1;
                        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 ) break ;
                        strncpy(f.lpString , (LPCTSTR)pBuffer + i, --len);
                        f.lpString[len] = 0;
                        f.nLength = len;
                        vFilter.push_back(f);
                        i += len;
                }
        }
        
        // 2004-8-5 计时停止
        cc.Stop();
        *pdwElapsedTime = cc.GetElapsedTime() ;
        
        CVectorString vStr;
        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);
                
                // 2004-7-26
                vStr += sBuf;
                
                delete(p->lpString);
        }
        
        // 2004-7-26
        vStr += '\0';
        
        sResult = &vStr[0]; 
}

void CTest1Dlg::OnOK()
{
        CRichEditCtrl *pRiched = &m_ctrlRichEd;
        LPCTSTR lpFn = "d:\\tmp\\MinGWStudioFullSetupPlus-2.02.exe";

        // 2004-8-5        
        DWORD dwElapsedTime = 0;
        CFileMap fm(lpFn);
        LPBYTE pBuffer = NULL;
        if (fm.GetData(&pBuffer ))
        {
                CString sResult;
                StrFilter(pBuffer , fm.GetSize(), 5, sResult, &dwElapsedTime);
                pRiched->SetWindowText(sResult);
        }       
        
        // 以下是用于评测的结果
        CString sMsg;
        sMsg.Format("Used time:%ums", dwElapsedTime);
        AfxMessageBox(sMsg);
}
--
    I came, I saw, I conquered ! — Caesar


※ 修改:·SwordLea 于 Aug  5 09:16:46 修改本文·[FROM: 202.118.246.*]
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.246.*]