题
问题:我有一个庞大的原始文本文件(假设3gig),我需要浏览文件中的每个单词,并发现一个单词在文件中出现了多少次。
我建议的解决方案:将大文件拆分为多个文件,每个拆分文件都会按排序方式包含单词。例如,所有以“开头的单词”A“将被存储在”_a.dic“ 文件。因此,任何时候我们都不会执行超过 26 个文件。
这种方法的问题是,
我可以使用流来读取文件,但想使用线程来读取文件的某些部分。例如,用单独的线程读取0-1024字节(根据编号至少有4-8个线程)。盒子里有处理器)。这是可能的还是我在做梦?
还有更好的方法吗?
笔记:它应该是纯 C++ 或基于 C 的解决方案。不允许使用数据库等。
其他提示
我不认为使用多个并行读取文件部分的线程会有很大帮助。我希望这个应用程序绑定到硬盘的带宽和延迟,而不是实际的字数。这样的多线程版本可能实际上表现更差,因为<!>“准随机<!>”;文件访问通常比<!>“线性文件<!>”慢;访问。
如果CPU在单线程版本中真的很忙,可能会加速。一个线程可以读取大块数据并将它们放入容量有限的队列中。一堆其他工作线程可以在自己的块上运行并计算单词。计数工作线程完成后,您必须合并单词计数器。
首先 - 决定保存单词的数据结构。
显而易见的选择是地图。但也许 Trie 会更好地为您服务。在每个节点中,您可以保存单词的计数。 0表示,它只是一个单词的一部分。 您可以使用流插入到trie中并读取基于字符的文件。
第二 - 多线程是或否? 这个不容易回答。根据数据结构的大小增长以及如何并行化答案可能会有所不同。
- 单线程 - 前沿且易于实施。
- 具有多个读取器线程和一个数据结构的多线程。然后,您必须同步对数据结构的访问。在Trie中,您只需要锁定您实际所在的节点,因此多个读取器可以访问数据结构而不会受到太多干扰。自平衡树可能不同,尤其是在重新平衡时。
- 多线程,具有多个读取器线程,每个线程都有自己的数据结构。每个线程在读取文件的一部分时构建自己的数据结构。每一个完成后,必须结合(这应该很容易)。 醇>
你必须要考虑的一件事 - 你必须为每个线程找到一个单词边界,但这不应该构成一个很大的问题(例如,每个线程都会开始它直到第一个单词边界并从那里开始,在结束每个线程完成它正在处理的单词。)
虽然您可以在阅读后使用第二个线程来分析数据,但这样做可能不会获得大量收益。尝试使用多个线程来读取数据几乎肯定会损害速度而不是改进速度。使用多个线程来处理数据是没有意义的 - 处理速度比读取速度快很多倍,所以即使只有一个额外的线程,限制也就是磁盘速度。
获得显着速度的一种(可能的)方法是绕过通常的iostream - 虽然有些速度几乎与使用C FILE *一样快,我不知道任何事情真的更快,有些速度要慢得多。如果您在具有明显不同于C的I / O模型的系统(例如Windows)上运行此功能,则可以稍微小心地获得更多。
问题很简单:你正在阅读的文件(可能)大于你可用的缓存空间 - 但是你不会从缓存中获得任何东西,因为你不会重读那些缓存再次归档(至少如果你明智地做事)。因此,您希望告诉系统绕过任何缓存,并且只是将数据尽可能直接从磁盘驱动器传输到您可以处理它的内存。在类Unix系统中,这可能是open()
和read()
(并且不会让你获得很多)。在Windows上,那是CreateFile
和ReadFile
,将FILE_FLAG_NO_BUFFERING
标志传递给<=> - 如果你做的话,它可能会大致加倍你的速度。
你也得到了一些主张使用各种并行结构进行处理的答案。我认为这些从根本上是错误的。除非你做了一些非常愚蠢的事情,否则计算文件中单词的时间只比简单读取文件的时间长几毫秒。
我使用的结构将是两个缓冲区,例如每个兆字节。将数据读入一个缓冲区。将缓冲区转到计数线程以计算该缓冲区中的单词。当发生这种情况时,将数据读入第二个缓冲区。完成后,基本上交换缓冲区并继续。在交换缓冲区时需要做一些额外的处理,以处理可能从一个缓冲区到下一个缓冲区的跨越边界的字,但它非常简单(基本上,如果缓冲区不以白色结束)空间,当你开始操作下一个数据缓冲区时,你仍然会说一句。)
只要你确定它只会在多处理器(多核)机器上使用,使用真正的线程就可以了。如果有可能在单核机器上完成,那么使用具有重叠I / O的单个线程会更好。
正如其他人所指出的,瓶颈将是磁盘I / O.因此,我建议您使用重叠I / O.这基本上颠倒了程序逻辑。您只需告诉操作系统在完成一些I / O操作后调用您的代码,而不是使用代码来确定何时执行I / O.如果您使用 I / O完成端口,您甚至可以告诉操作系统使用多个线程来处理文件块。
我认为perl是为了这个目的而诞生的。
流只有一个游标。如果您一次使用多个线程访问流,您将无法确定读取到您想要的位置。读取是从光标位置开始的。
我要做的就是只有一个线程(可能是主线程)读取流并将读取字节分派给其他线程。
举例来说:
- 线程 #i 已准备好并要求主线程提供下一部分,
- 主线程读取下一个 1Mb 并将它们提供给线程 1,
- 线程 #i 读取 1Mb 并根据需要计算单词数,
- 线程 #i 完成其工作并再次请求下一个 1Mb。
通过这种方式,您可以将流读取与流分析分开。
您正在寻找的是RegEx。 c ++正则表达式引擎上的这个Stackoverflow线程应该有所帮助:
首先,我很确定C / C ++不是处理此问题的最佳方法。理想情况下,您也可以使用一些map / reduce来实现并行性。
但是,假设你的约束,这就是我要做的事情。
1)将文本文件拆分为更小的块。您不必通过单词的第一个字母来完成此操作。把它们分解成5000字的块。在伪代码中,你会做这样的事情:
index = 0
numwords = 0
mysplitfile = openfile(index-split.txt)
while(bigfile <!> gt; <!> gt; word)
mysplitfile << word
numwords ++
if (numwords > 5000)
mysplitfile.close()
index++
mysplitfile = openfile(index-split.txt)
2)使用共享的地图数据结构和pthreads来生成新的线程来读取每个子文件。再次,伪代码:
maplock = create_pthread_lock()
sharedmap = std :: map()
对于每个index-split.txt文件:
spawn-new-thread(myfunction, filename, sharedmap, lock)
dump_map(sharedmap)
void myfunction(filename,sharedmap){
localmap = std::map<string, size_t>();
file = openfile(filename)
while (file >> word)
if !localmap.contains(word)
localmap[word] = 0
localmap[word]++
acquire(lock)
for key,value in localmap
if !sharedmap.contains(key)
sharedmap[key] = 0
sharedmap[key] += value
release(lock)
}
对不起语法。我最近一直在写很多蟒蛇。
不是C,有点UGLY,但只花了2分钟才敲出来:
perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a} || $a cmp $b} keys %h) {print "$h{$w}\t$w"}}' file > freq
使用-n
循环遍历每一行
使用@F
将每一行拆分为-a
单词
每个$_
字增量哈希%h
到达END
file
之后,
sort
哈希频率$h{$b}<=>$h{$a}
如果两个频率相同,则按字母顺序排序$a cmp $b
打印频率$h{$w}
和单词$w
将结果重定向到文件'freq'
我在3.3GB文本文件上运行此代码,文本为580,000,000个。
Perl 5.22在173秒内完成。
我的输入文件已经删除了标点符号,并使用这段代码将大写转换为小写:
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
结果
(运行时间为144秒)
字数统计脚本也可以用awk编写:
awk '{for (i=1; i<=NF; i++){h[$i]++}} END{for (w in h){printf("%s\t%s\n", h[w], w)}}' file | sort -rn > freq