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

2009/9/22 agentzh <agentzh@gmail.com>

嗯嗯嗯，忘了是有重复元素的列表了。。。哈哈，多谢指正。总排列数确实是 4^15 :) 每一个位子都只有 4 种可能性，便是 4*4*4*...*4 这 15 个 4 相乘。为避免存储各个 key，将 key 作 hash 到一个 int32 整数，便只有 4 个字节。

当然，我在写上一封邮件的时候其实并不知道这样的 hash 函数是否好写。。。呵呵，应该是好写的：

1. 事先约定 A,T,G,C 分别对应 00, 01, 10, 11，即 2 个比特的数值。
2. 然后把当前的15长度的串顺序地两个比特两个比特地编码，最终得到的值便是我们要的 hash 后的数值。
3. 接着用它去下标访问我们的 1G 大小的位数组，这个寻址当是极快的。置比特也当是极快的。
4. 最后，我们遍历这个 1G 位数组，找出比特为 0 的下标，再还原为 ATGC 形式的碱基序列，便是从未出现过的 15 长度的串了，呵呵。
   

这里我们就不关心出现的 15 长度序列的具体次数了。只记录出现过或者未出现过。这样 2 GB RAM 的机器是很够的了 ;)

不知这个是否靠谱？哈哈？

Cheers,
-agentzh

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

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