高效扫描一个大文件内字节出现的频率?

2015-04-03 22:07:15 +08:00
 zungmou

比如一个5G的文件,统计每个字节出现的频率,如果是读取一部分到缓存,逐个字节从缓存中扫描的话速度非常慢,伪代码:

内存1 = 读取10MB数据;
扫描 内存1 的每个字节,然后统计;

还有没有更高效的方法?WinHex 就有这样的功能,几乎在瞬间就完成了扫描,它是如何做到的?

1725 次点击
所在节点    C
32 条回复
yangff
2015-04-04 09:22:18 +08:00
@zungmou 直觉告诉我memorymappedfile的那个stream.read可能有一次内存的复制。。
c#的话你统计一下各个调用各花了多少时间吧。。?
还有你的硬盘是机械还是固态?我觉得这时间好像也差不多了。。
zungmou
2015-04-04 09:33:34 +08:00
@Andiry mmap 虽然映射过去了,可IO时间真的能缩减吗?
Andiry
2015-04-04 09:44:30 +08:00
@zungmou 不能,只要你的文件放在普通硬盘上,mmap还是要先读到内存里
只不过一次性读取可以快一些
frankzeng
2015-04-04 10:28:59 +08:00
找台内存大点的机器,全部load到内存里,扫一遍就结了,真正耗时的是文件的IO,简单又暴力,还不费脑子。
ncisoft
2015-04-04 12:35:09 +08:00
@zungmou 既然硬盘IO才是瓶颈,那是无法绕过去的,这是物理限制,没法通过代码实质优化。上SSD加持IO速度吧,有了SSD,随机读取也不是问题了,可以开多线程读取统计。在我的老笔记本做了测试,和atom比差距很大,机械硬盘 vs eMMC。不知windows上有没有类似 flashcache 这样逆天的玩意?

mgwin32不支持mmap函数,就只好屏蔽不测了

D.2 w/count(laptop)
real 3m7.672s
user 0m0.031s
sys 0m0.046s

A.2 w/count(atom)

real 1m18.648s
user 0m45.452s
sys 0m4.648s
billlee
2015-04-04 15:18:53 +08:00
@zungmou mmap 主要是可以避免数据从内核空间拷贝到用户空间的开销
zungmou
2015-04-04 21:02:23 +08:00
@wuxqing
@billlee
@ncisoft
@batman2010
@Andiry
@yangff

首先感谢各位的回复。

我的操作系统是 Win7 x64,CPU I5-4430主频3G,内存16GB,普通机械硬盘,开发环境是VS2013+C#;
经过一夜优化调试,现总结给大家,一个5G 文件,扫描统计后的结果如下:

x64编译:
每200MB扫描耗时0.85秒(不包括IO时间)
总耗时23.37秒(包括IO时间)

x86编译:
每200MB扫描耗时0.58秒(不包括IO时间)
总耗时16.66秒(包括IO时间)

优化主要将C#的数组改为指针去统计,绕过托管内存的消耗。
当中试过并行计算,使用的是.NET的并行类,但扫描时间比 for 循环稍长。

备注:每次缓存的数据大小和扫描时间成正比增长,所以不考虑是否全部载入内存。

源代码如下:

unsafe static class Analyzing
{
public static int[] Count(Stream stream)
{
byte[] buffer = new byte[204800000];
int read = 1;

// 用于保存统计数据的内存。
int* count = (int*)Marshal.AllocHGlobal(sizeof(int) * 256);

// 用0填充内存;
for (int i = 0; i < 256; i++)
{
count[i] = 0;
}

// 记录工作开始的时间。
DateTime begin = DateTime.Now;

// 循环读取数据到内存;
while (read > 0)
{
read = stream.Read(buffer, 0, buffer.Length);
if (read == 0) break;
// 记录扫描开始的时间。
DateTime start = DateTime.Now;
// 扫描内存的数据,并进行统计;
// count为int类型,256大小的内存区域;
// count的索引位置(0-255),代表字节0-255;
// count的索引内容,代表字节出现的频率。
for (int i = 0; i < read; i++)
{
count[buffer[i]]++;
}
// 输出扫描耗费的时间。
Console.WriteLine((DateTime.Now - start).TotalSeconds);
}

Marshal.FreeHGlobal((IntPtr)count);

// 输出工作耗费的时间。
Console.WriteLine((DateTime.Now - begin).TotalSeconds);
Console.ReadKey();

// 将非托管内存转换为托管数组,并返回该结果。
int[] result = new int[256];
Marshal.Copy((IntPtr)count, result, 0, result.Length);

return result;
}
}
zungmou
2015-04-04 21:03:30 +08:00
@wuxqing
@billlee
@ncisoft
@batman2010
@Andiry
@yangff

最后一个问题,为什么 x64 比 x86 进行 for 循环所需的时间更长?
ncisoft
2015-04-04 21:32:15 +08:00
@zungmou 这一般要看汇编码才能知道,尤其是c#这种高阶语言,里面隐藏了了太多的实现细节

一般来说,x64指针长度是一个需要考虑的方向
ncisoft
2015-04-04 21:38:20 +08:00
@zungmou 给你找了个小bug,统计用int类型是否不妥?刚查了c#的int是32位的,5G全零必然溢出
zungmou
2015-04-04 21:53:02 +08:00
@ncisoft 您很细心~ 改成long类型,200MB平均耗时0.76秒,总耗时21秒。
xlrtx
2015-04-05 15:05:42 +08:00
载入内存后吧内存分块多线程会不会有提高?

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/181441

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX