大文件快速分割算法

Question

我正在研究一种通过标题 fafafafa 将大文本文件(实际任务 > 20GB，但你可以假设 1GB)拆分成较小文件的缓慢算法，发现以下算法表示为伪代码

您可以通过以下命令创建二进制测试数据 1GB，已讨论 here

dd if=/dev/urandom of=sample.bin bs=64M count=16

当前

i=1;
matchCount=0;
while not end of file
    read.file
    while matchCount < i 
        match(header "fafafafa", file)
        match(2nd header "fafafafa", file)
        matchCount++; 
    end;
    store everything between two headers into a new file called rd$i.txt
    i++; 
end;

评论

• 每次迭代都从头开始读取文件

还有哪些其他因素使该算法变慢？

我的建议

i=1;
read.file
eventOn = 0; 
while line in linesInFile
    if not match header AND eventOn=0
        stop; # go to next line
    end;
    if match(header "fafafafa" in line)
        negate eventOn; # from 1 to 0; from 0 to 1.
        if newFile is not empty
            store.newFile as rd$i.txt
            newFile = ""; 
            i++;
            stop; # go to next line
        end;
    end; 

    if eventOn=1 
        newFile += line;
    end;
end;

评论

• 这不应该一次又一次地从文件的开头读取
• 我不确定这里的 newFile 的数据结构是否足够用 addition 和 delete；堆栈可能是一个不错的；因为我只需要按标题和快速拆分文件

哪种数据结构适合快速拆分？

您如何考虑快速拆分大文件的算法？

Answer 1

单次扫描，将所有内容保存在缓冲区中，直到找到分隔符，然后写入一个新文件:

f=1temp= empty stringi=0delimiter= "fafafafa"while not eof   b=readbyte   if b == delimiter[i]      if ++i == delimiter length          truncate delimiter from end of temp          write temp to rd$f.txt          f++          i=0          temp = delimiter   else      i=0   temp += bwrite temp to rd$f.txt