65.9K
CodeProject 正在变化。 阅读更多。
Home

SimpleDiff：一个简单的文件比较实用程序

Alain Rist
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.53/5 (6投票s)

2009年8月30日

CPOL

5分钟阅读

viewsIcon

32830

downloadIcon

554

这是提交到 CodeProject “精简高效”挑战项目的一部分。

引言

本文是为“Code Lean and Mean”挑战赛的贡献。比赛的介绍说明：在过去的日子里，能够将一个完整的文件管理器、电子表格应用程序、日程提醒器和俄罗斯方块彩蛋集成到32KB的可执行文件中，是一项荣誉的象征。

这个可执行文件大小高达22.5 KB，并且只计算两个文件之间的最小差异。没有多少空间留给电子表格了。

挑战

创建一个应用程序，以尽可能快的速度和尽可能少的内存来计算和显示两个文本文件之间的更改。提供计时数据和最大内存使用数据。

背景

diff 工具的描述在这里：链接，相关的LCS（最长公共子序列）算法的详细介绍在这里：链接。该算法主要应用于 DNA 研究，我们的序列只由一个字母组成，但文件却有数百万行长。

问题

LCS 算法需要将一个文件中的每一行（用于比较相等性）与另一个文件中的所有行进行比较。唯一的捷径是排除两个文件开头和结尾的匹配行。

该算法是二次方的，需要完全填充一个表，其中一个文件的每一行对应一个行，另一个文件的每一行对应一个列。如果文件大约有一百行，那就是 10000；对于大约 3000 行的文件，那就是 1000 万。不要指望能快速比较两本圣经的翻译本。

处理时间也随着文件大小的平方增长。所以，至少用这个经过验证的算法来说，内存使用和处理速度之间没有全局的设计权衡。寻找被全球数千名研究人员探索过的新方法，除非是那些天才，否则就像在《爱丽丝梦游仙境》中的冒险一样，所以我将坚持使用这个算法。

设计

这个过程是纯粹的顺序执行

  1. 检查文件名并启动计时器。

  2. 打开并访问文件。

  3. 排除开头和结尾的匹配行（如果有）。

  4. 索引剩余的行。

  5. 用行比较的结果填充 LCS 数组。

  6. 从 LCS 数组中提取不匹配的行索引。

  7. 输出结果并停止计时器。

  8. 报告时间和内存消耗。

每个步骤的目标都是在内存使用上节俭，同时在处理上高效快速。

工作代码

数据设计

文件内容通过内存映射访问，节省了部分空间。

内存映射空间中的行地址存储在两个向量中。

CAtlFileMapping<CHAR> FileMaps[2]; // File memory mappings
UINT iFirstWorkLine = 0; // Pos of first processed line
vector<LPCSTR> Lines[2]; // Beginning of processed lines

每对行的 LCS 数据存储为

struct LCSInfo
{
    SHORT size;  // LCS size
    bool bMatch; // lines equality
};

这是一个权衡：记录对的匹配状态可以避免重复读取和比较相同的行，但会增加内存占用。将 `bool` 打包到 `short` 中会将数组占用空间减少一半，但会不成比例地增加记录和比较的处理时间，并很快被文件大小增加 41% 所抵消。

LCSInfo 数据存储在一个具有二维访问的单个向量中

class LCSArray : public vector<LCSInfo>

{
public:
    reference operator()(UINT i, UINT j)
    {
        static const size_t s1 = Lines[1].size();
        ATLASSERT((i < Lines[0].size()) && (j < s1));  
        return operator[](s1 * i + j);    }
} LCS;

LCS 在其固定大小下只分配一次。

流程图

步骤 1 和 2：检查文件名，启动计时器，打开并访问文件。

在步骤 1 结束时，初始化计时器并打开和映射文件。在多处理器机器上，该步骤是并行化的，但这在大多数情况下可能是不必要的。

步骤 3：排除开头和结尾的匹配行（如果有）。

两个并行线程（如果使用多处理器）从文件开头和结尾寻找第一个不匹配的 `char`。

// Find matching lines at begin and end (multithreaded)
size_t 
    iFirstMismatch = 0, 
    iLastMismatch = 0;
#pragma omp parallel sections 
{
    #pragma omp section
    {
        // Find first mismatch
        PCHAR 
            pc0 = FileMaps[0],
            pc0Max = pc0 + FileMaps[0].GetMappingSize(),
            pc1 = FileMaps[1];
        for (; (*pc0 == *pc1) && (pc0 != pc0Max); ++pc0, ++pc1)
            if (*pc0 == '\n')
                ++iFirstWorkLine;
        // Adjust to line begining
        for (; pc <= pcLast ; ++pc)
            if (*pc == '\n')
                Lines[i].push_back(pc + 1);
    }
// ... backwards

如果没有找到不匹配项，则文件相同，程序终止。

步骤 4：索引剩余的行。

在每个文件中，一个线程（如果使用多处理器）在第一个和最后一个不匹配项之间寻找 '\n' 字符，并将地址存储在 `Lines` 向量中。

向量首先根据从开头匹配行计算出的近似行长度进行分配，如果没有匹配行，则默认为 1024 行。

// Build line indexes (multithreaded)

#pragma omp parallel for
for (int i = 0; i < 2; ++i)

{
    PCHAR 
        pc = FileMaps[i] + iFirstMismatch,
        pcMax = FileMaps[i] + FileMaps[i].GetMappingSize(),
        pcLast = pcMax - iLastMismatch ;

    if (iFirstWorkLine)
        Lines[i].reserve(FileMaps[i].GetMappingSize() * iFirstWorkLine / 
            iFirstMismatch);
    else 
        Lines[i].reserve(1024);

    // Never accessed index 0
    Lines[i].push_back(NULL);
    // First mismatching line at index 1
    Lines[i].push_back(pc++);

    // Add line indexes including last mismatching
    for (; pc <= pcLast ; ++pc)
        if (*pc == '\n')
            Lines[i].push_back(pc + 1);
}
步骤 5：用行比较的结果填充 LCS 数组。

LCS 数组按照其已知大小分配，并按顺序处理行对。从现在开始，无法进行并行化，因为每一步都依赖于其前一步。

// Fill up LCS array
// Allocate and set to {0, false}
size_t sizeLCS = (Lines[0].size() + 1) * (Lines[1].size() + 1);
LCS.resize(sizeLCS);
// Start with first mismatching lines
UINT 
    iStart = 1, 
    jStart = 1;
// End before last indexed lines
const UINT 
    iEnd = Lines[0].size() - 2, 
    jEnd = Lines[1].size() - 2;
// http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
for (UINT i = iStart; i <= iEnd; ++i) 
    for (UINT j = jStart; j <= jEnd; ++j)
    {
        if (MatchLines(i, j))
            LCS(i, j).size = LCS(i - 1, j - 1).size + 1, 
            LCS(i, j).bMatch = true;
        else if (LCS(i - 1, j).size > LCS(i, j - 1).size) 
            LCS(i, j).size = LCS(i - 1, j).size;
        else 
            LCS(i, j).size = LCS(i, j - 1).size;
    }

`MatchLines()` 函数在这里对每一对行调用一次，并占用约三分之一的处理时间。

// Lines equality

inline bool MatchLines(UINT i, UINT j) 
{
     static const size_t 
        s0 = Lines[0].size() - 1,
        s1 = Lines[1].size() - 1;

    ATLASSERT((i < s0) && (j < s1));

    if (Lines[0][i+1] - Lines[0][i] != Lines[1][j+1] - Lines[1][j])
        return false;

    PCCH 
        ps0 = Lines[0][i], 
        ps1 = Lines[1][j];

    while (*ps0 == *ps1)
        if (*ps1 == '\n')
            return true;
        else
            ++ps0, ++ps1;

    return false;
}

如果大小相等，则执行字符比较，直到找到 '\n'。

步骤 6：从 LCS 数组中提取不匹配的行索引。

不匹配的行索引和类型按相反顺序从 LCS 数组中提取，并推送到 `Diffs` 堆栈。

// Extract diff lines from LCS array

UINT 
    y = iEnd,
    x = jEnd;

while ((y > 0) || (x > 0))
{
    if (LCS(y, x).bMatch)
       --y, --x;

    else if ((x > 0) && ((y == 0) || (LCS(y, x - 1).size > LCS(y - 1, x).size)))
        AddDiffLine(1, x, DIFF_ADDED), --x;
    
    else if ((y > 0) && ((x == 0) || (LCS(y, x - 1).size <= LCS(y - 1, x).size)))
        AddDiffLine(0, y, DIFF_REMOVED), --y;
 }

// Record number of diffs and output computing time
size_t nDiffLines = Diffs.size();
cout << endl << nDiffLines << " difference(s) found in " 
    << omp_get_wtime() - fstartTime << " second(s)." << endl;

此时，所有计算都已完成，因此输出中间时间。总执行时间不到一半花在了计算上。

步骤 7：输出结果并停止计时器。

结果行索引和类型从 `Diffs` 堆栈中弹出，并通过 `std::cout::operator<<()` 以简单的格式输出到 `stdout`。然后停止计时器。

对于一个包含 21 行的测试，输出时间超过了计算时间。

步骤 8：报告时间和内存消耗。

内存资源占用是合理的，处理时间高度依赖于系统负载，有时在几秒钟内会有两倍的差异。

结论

在如此简单的线性过程中，内存小与高效率之间的权衡很容易被发现。

没有人是完美的，干杯！

历史

  • 2009 年 8 月 30 日：初始发布。

  • 2009 年 9 月 3 日：更新

    • 正确处理首行和末行的不匹配。

    • 正确处理首行前的插入。

    • 各种局部优化。

© . All rights reserved.