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

我做了个实现，计算一个2.4G的基因组里12bp长度的出现次数。先用hash算一遍再用array算一遍。从昨晚到现在近20个小时了，hash的
算了有1.6G的样子。内存消耗维持在60%占用的水平上。我的内存是4G的，估计这个hash大小有2.4G左右的样子吧。12bp字串的种类有
16'777'216种。不过我用的是十位数字的0,1,10,11来表示的ATGC。昨晚犯的错，呵呵。

郝先生的文章我拜读过，其实我的思路也有些是受他的启发。所不同的是，CVTree是做系统发育树的。基本不会用到9bp以上的寡核甘酸，而且目前
CVTree也主要是构建原核生物树，只有到了很少的几种真核生物基因组。

On 9月23日, 上午11时02分, "Jester"<jes...@perlchina.org> wrote:
> 我有个不太成熟的想法，不太知道数组的存储是否会比hash节约？如果是，到底能节约多少？（请高手指教）
> 我的想法是把ATCG用0123代替，然后看作是一个4进制的数，这样可以很容易转换成一个数值，也就是数组的下标，如此对应。
> 当然，如果数组的开销还是很大，就不行了......
>
> 我不知道你在哪个实验室，国内应该有不少做类似分析的人，郝先生今年刚发在NAR webserverissue上的CVTree本质上就是分析这个。
> 说到底用C还是最高效的，不过用perl尝试一下也挺好。我也是丢了C很多年了，执着的perler ^_^
> 请高手再指点吧，我也想提高一下coding技巧。
>
> Jester，jes...@perlchina.org
> 2009-09-23
>
> ----- Original Message -----
> From: 空格
> To: PerlChina Mongers 讨论组
> Sent: 2009-09-22, 23:33:47
> Subject: [PerlChina] Re: 在我遇到的这种情况下散列和数组哪个快？
>
> >原来是这个意思。。。。
> >基因组字串的分布应该还是比较均匀的。因为它很接近随机序列。cache的效果如何很难说。。。
> >我原来想的就是用简单的文本文件处理。
> >因为hash表会按键值排序，所以相似的字串在文本上比较也会比较容易些吧。
>
> >On 9月22日, 下午6时44分, msmouse wrote:
> >> 比如sqlite。。
>
> >> 这个想法就是把这个内存放不下的数组放在硬盘上。由于这1G种不同组合很可能不是均匀分布的，也就是说其中某些更经常出现，那么如果存储引擎有cache的话，-就可以加快访问。但是实际的效果怎么样没有试就不好说，因为在这个问题里数据访问频度虽然很可能不均匀，但是也是没有什么局部性的，如果是按块的cache（比-如OS本身的disk
> >> cache）对这种应用的效果可能就不大理想，因为相邻访问之间涉及的地址不是连续的，cache必须不停换页。
> >> ----------------------------------
> >> msmo...@ir.hit.edu.cn
> >> msmo...@gmail.com
>
> >> 2009/9/22 空格
>
> >> > 抱歉你说的这个"带cache的嵌入式数据库"我不懂。具体是什么，在cpan上有包么？
>
> >> > On 9月22日, 下午1时08分, msmouse wrote:
> >> > > 同意 C++的用一个vector或者bitset就搞定了，不需要自己做位计算，只需要125M内存 哈哈
>
> >> > > 如果要perl并且需要计数的话，考虑用一个带有cache的嵌入式数据库即可。。前面也提到了吧？
>
> >> > > ----------------------------------
> >> > > msmo...@ir.hit.edu.cn
> >> > > msmo...@gmail.com
>
> >> > > 2009/9/22 agentzh
>
> >> > > > 2009/9/22 agentzh
>
> >> > > >> 嗯嗯嗯，忘了是有重复元素的列表了。。。哈哈，多谢指正。总排列数确实是 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 访问该论坛
-~----------~----~----~----~------~----~------~--~---