怎样处理一个3M多的文本文件?

Question

我有很多3M大的文本文件,现在要把里面的<table> 替换为 <table id='##'>,我用String 来处理,文件小的时候可以,但大文件的时候 CPU的使用100%,机子没反应了,但内存只用10%.. 请问应怎样处理3M多的大文件?

Answer 1

字符串操作应当说应用相当广泛， 如何高效地操作字符串，将极大影响程序的运行效率。 操作字符串无非就是搜索和修改（包括插入/删除）。先说说如何高效地搜索字符串。我们先看一个例子：
要求写一个计算子串出现次数的函数。方法一：
function CountSubStr(SubStr, Source: string): Integer;
begin
  result := 0;
  while pos(SubStr, Source)>0 do
  begin
    inc(result);
    Source := copy(Source, pos(SubStr, Source)+Length(SubStr), $7FFFFFFF);
  end;
end;方法二：
function CountSubStr(const SubStr, Source: string): Integer;
var
  i, len1, len2: Integer;
begin
  result := 0;
  len1 := length(SubStr);
  len2 := length(Source)-len1+1;
  i := 1;
  while i<=len2 do
    if (Source[i]=SubStr[1]) 
       and CompareMem(@(Source[i]), Pointer(SubStr), len1) then
    begin
      inc(result);
      inc(i, len1);
    end 
    else 
      inc(i);
end;方法一代码非常简洁直观, 三句搞定方法二有点晦涩。看上去毫无必要地定义了两个变量(len1和len2), 而且用了一句很奇怪的判断语句(and两边的值肯定是一样的，要么都是true，要么都是false，看起来像一个生手写的)。您会选哪一种方法？答案是：选第二种。为什么？ 这里就牵涉到一个字符串操作效率的问题。
让我慢慢道来：我们先看方法一：>>  while pos(SubStr, Source)>0 do       
查字串位置，如果找不到循环结束>>  begin>>    inc(result);>>    Source := copy(Source, pos(SubStr, Source)+Length(SubStr), $7FFFFFFF);  
找到了则计数加1，并且截去前面已经搜索过的字符串，只留下未搜索过的等待下一次循环。问题就在这句，让我们看看这时到底干了些什么：
  1. 调用pos函数从头重新搜索Source字符串以查找字串SubStr的位置。
  2. 调用Length函数计算SubStr的长度
  3. 重新申请内存并复制Source中剩余的字符串然后每循环一次就重复一次上述步骤直到循环结束。
仔细看看其实上述步骤中没有一步是有用的。
1. 循环开始时已经调用pos取得位置了。 此时又调用一次纯属浪费， 如果子串位于字符串的后面将重新扫描大部分无用的字符串。
2. substr在这个过程中属于一个常量， 不会改变， 其长度完全可以在进入循环前保留下来作为常量使用， 没有必要每次重复调用子过程再去计算一遍（不过由于length函数的实现只有3句汇编指令(call和ret不占cpu时间), 所以这点开销可以忽略）
3. 这是最恐怖的一步， 假设Source有几兆之多， 那么每次复制的数量就非常可观了。造成最后过程运行的大部分时间都在复制字符串了。这步完全是不需要的，只要我们能记录下本次查找到的位置，然后下一次从这个位置继续查找就能达到目的了。 为什么要毫无必要地复制几兆数据呢（而且是循环里每次复制）？
根据这个思路，就有了方法二。方法二：
>>  len1 := length(SubStr);  
将SubStr的长度保留做一个常数，供循环中使用。 不过你也可以不用这个变量而在循环中直接写成函数形式， 因为开销很小。
不过我喜欢这么用。length函数尽管开销小，但也是开销呀。 如果循环几千几万次那每用一个length函数就等于多执行了循环次数*2条无效语句。>>  len2 := length(Source)-len1+1;
控制循环次数。 >>  i := 1;
>>  while i<=len2 do
>>    if (Source[i]=SubStr[1]) and CompareMem(@(Source[i]), Pointer(SubStr), len1) then
为什么要这么写？这是有原因的，如果source[i]不等于substr[1]，那么后面的comparemem就根本不会执行。如果查找的是一个很长的子串的话，那么节约的时间就很可观了。 为什么不用copy(source, i, len1)=substr判断而要用comparemem呢？ 这样做的话是将子串复制到一块临时内存然后和substr逐字节比较，既然这样，为什么不直接逐字节地比较呢？由于每次找到substr第一个字符时就会进行比较，那么copy的浪费就太大了。
    begin
      inc(result);
      inc(i, len1);
    end 
    else 
      inc(i);可以发现，方法二对source串头到底搜索一次就完成任务了。 没有额外的开销， 不运行无效的代码， 因此效率是相当高的。通过例子可以发现， 要想高效地处理字符串，就是尽可能地减少循环次数（字符串操作就是一个循环）与提高循环体的执行效率（一个有效的办法就是尽可能将不改变的部分提到循环体外先执行掉）。 如果能顺序搜索一次便达到目的的就绝不重复操作已经搜索过的字符串（包括复制啦（这是最浪费的，除非你的目的就是复制），从头再搜索字符串啦等等）。 
根据上面的原则， 现在我们可以改造一下方法一，使其也具备高效率。代码如下：function CountSubStr(const SubStr, Source: string): Integer;  // 注意，必须加const或者var关键字
var
  i, n, len1, len2: Integer;
begin
  result := 0;
  i := 1;
  len1 := Length(SubStr);
  len2 := Length(Source)-len1+1;
  while (i <=len2) do
  begin
    n := pos(SubStr, string(@Source[i]));     // 这里的技巧是高效的关键, 直接将上一次找到的位置作为字符串的起始传入pos函数
    if n > 0 then
    begin
      inc(result);
      inc(i, n+len1-1);      
    end
    else break;
  end;
end;现在让您选择呢？两种方式效率几乎一样。选哪种都不错。

Answer 2

下面将要讲讲怎样高效地插入/删除子串开始讨论这个问题前。 让我先重申一下前篇的观点：
要提高字符串操作的效率：
1. 尽可能降低循环的次数。 
2. 尽可能将不改变的部分提到循环体外先算好。对字符串的修改delphi是怎么做的？
主要分两种情况： 
1、结果串长度和源串相同(特定情况下：比如替换子串中被替换的长度和替换内容长度相同，或者插入、添加、删除一个空串时)
 这种情况相当简单， 只要直接将源串中相关子符改掉就达到目的了。2、结果串长度和源串不同(绝大部分修改的情况下)，我们要优化的主要是这种情况。delphi的字符串管理机制将先申请一块新内存，大小等于结果串长度， 然后将源串复制到目的串中：
一般分3步复制：先复制源串中插入/删除/修改位置前的字符到目的内存，然后复制新增的子串(插入，修改时), 最后复制剩下的源串（如果是修改和删除时则跳过被修改和被删除子串的长度）
最后释放掉源串（如果是直接操作在源串上的话）的内存。其实delphi的内存管理就是如此：比如ReAllocMem过程也就是先判断一下目的内存块与原始内存块的大小，如果一样则什么都不做直接返回源内存块地址。如果有变化（变大/变小），则先申请目的大小的内存，然后复制源内存块的内容到目的内存（如果源比目的大则复制目的大小的内存）根据以上限制， 我们做批量替换子串时，要高效的关键一步就是尽可能减少这种重新申请内存并复制的次数。
也就是说，我们不能循环找到一个就先替换一个然后再找下一个。而应该将所有的位置都先确定下来，再一次性申请结果大小的内存然后根据事先确定的位置进行复制源串与替换串的操作。 
也就是说至少两次循环：第一次是搜索， 先确定所有要替换的位置，第二次循环才是真正的替换工作。下面是一个替换所有子串的例子：
替换工作分三种情况：
1. 被替换的子串与替换串长度一样
2. 被替换串比源串长
3. 被替换串比源串短
(2, 3 要分开是因为它们的操作步骤上有细微的区别）由于我们要记录所有要替换的位置， 因此我们需要牺牲一块内存以保存第一次搜索后用来记录所有替换的位置信息。 我这里用的是动态数组。事先申请一个合适数量动态数组就显得很关键了。如果事先申请的太小， 那么在搜索过程中就要不断改变这个数组的大小(也就是不断重新分配内存），这显然是一种浪费。如果申请得太大，那对内存上的浪费就很显眼了。
例子中事先申请了512个整数的大小(1k), 然后每次重新分配都增加32个。 另外一点， 这个动态数组我用的是全局变量而不是局部变量， 这也是出于效率上的考虑， 如果是局部变量的话，每次调用过程都将重新申请然后过程结束时又释放掉它， 显然大多数情况下有些浪费(毕竟大多数调用被替换的字符串都不会很长)， 不过用全局变量就存在一个问题了， 即这个过程不是线程安全的。 
如果您想在线程中使用这个函数， 那么请将数组定义部分放入过程中或者改成
threadvar 
  MatchPoses: array of Integer; 
这样每个线程就都有一个MatchPoses数组了, 线程间不会发生冲突。（这样做是否需要在线程结束时调用SetLength(MatchPoses, 0)呢？我不知道, 想来应该不要吧）先给出与delphi的StringReplace比较测试的结果：（测试了1k, 5k, 10k, 100k, 1M, 5M, 10M不同数据量时程序的运行速度）
测试数据都是随机生成的。其中10M数据量测试了3批，可以从这3批数据中看出MatchPoses的大小对程序的影响(不是很大)