[PerlChina] Re: 在我遇到的这种情况下散列和数组哪个快？

2009/9/21 空格 <ribozyme2004@gmail.com>

有一个长度为4.8G的字符串，其中只有四种字母ATGC。按照排列组合数，这四个字母组成的长度为15字符串总共有1｀073｀741｀824种可能
性。我想统计一下，这个大字符串中是否包含了所有的长度为15的可能的字串。如果没有包含全部，那么有哪些字串的出现次数为零。
为此，我想需要建立一个很大的表，然后从那个超大的字符串中逐个取出长度为15的字串，然后在表中统计其出现次数。这样可以得到结果。
我的问题是，这样大的表格，用散列写好还是用二维数组写比较好？或者有什么别的方式实现更可行一些。

我猜你没有那么大内存的机器吧？呵呵。我们这里的 32 GB RAM 的机器，用 Perl 数据结构的话也可能会溢出，呵呵。

如果一定要用 table 去统计各种 15 字节的字符串个数，可以考虑使用 TokyoCabinet (TC)，并预留大约 10 GB 的磁盘空间，并将 bucket number 置为 15! 的 2 到 3 倍。扫描字符串需要做成流式的，比如几 KB 几 KB 或者几 MB 几 MB 地从文件读取。照你所说，扫描过程中，把 15 字节字符串在 table （即 tokyocabinet）中 set value，最后看 TC 数据库中一共有多少个 key-value 对，如果不足 15!，则回答了你的第一个问题"这个大字符串中是否包含了所有的长度为15的可能的字串"。而至于找出没有出现过的 15 长字串的所有实例，似乎也比较花时间，需要遍历 15! 种 15 长度的串，分别测试它是否已出现在了 TC 数据库里。

TC 占用的空间大约可以估计为 15! * (15 + 4) * 2，大约是 40 GB 吧，需要预留好磁盘空间，这个倒是可以接受的。

但如果假设 TC 平均读写速度为 0.1ms，则遍历一遍 15! 个组合，貌似需要 3404 年！呃。。。好像还没有生物有那么长寿吧？呵呵。当然了，如果找几百台机器实现几千个 TC 操作并行起来，可以缩减到 1 年，还是有些长。。。那再多找些盘吧。。。

上面是蛮力法。更聪明的做法可能需要一些组合数学方面的规律了。。。我数学不太好，还需要多想想。。。

当然了，如果有许多台机器，总　RAM 达到几十 GB 的量级的话，就不必用 TC，也不必走磁盘了。以 RAM 10G/s 的读写速度算，在运算时间上还是可以接受的。。。但最好不要用 Perl 哈，直接上 C/C++ 吧！呵呵！Lua

Cheers,
-agentzh

--~--~---------~--~----~------------~-------~--~----~
您收到此信息是由于您订阅了 Google 论坛"PerlChina Mongers 讨论组"论坛。
 要在此论坛发帖，请发电子邮件到 perlchina@googlegroups.com
 要退订此论坛，请发邮件至 perlchina+unsubscribe@googlegroups.com
 更多选项，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问该论坛

-~----------~----~----~----~------~----~------~--~---