没有15！那么大的量级吧 应该是4的15次幂，也就是2的30次幂，大约1G种组合 ，用一个int32数组计数即可，散列的话考虑到很多种组合是不存在的 有2G内存也是可能一次跑成的
不知道我的分析对不对 ---------------------------------- [email protected] [email protected] 2009/9/22 agentzh <[email protected]> > 2009/9/21 空格 <[email protected]> > >> 有一个长度为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 讨论组”论坛。 要在此论坛发帖，请发电子邮件到 [email protected] 要退订此论坛，请发邮件至 [email protected] 更多选项，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问该论坛 -~----------~----~----~----~------~----~------~--~---
