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

2009/9/23 Jester <jester@perlchina.org>

"基因组字串的分布应该还是比较均匀的。因为它很接近随机序列"----这样的说法很不严谨！我相信这不是你真实的想法，但是这样的表述会误导很多人。任何一个物种的基因组序列都不会是ATCG的随机排布！

我感觉前面有人讨论的建议的使用位运算应该是会比较节约的做法，但具体的实现我也不会。
我有个不太成熟的想法，不太知道数组的存储是否会比hash节约？如果是，到底能节约多少？（请高手指教）
我的想法是把ATCG用0123代替，然后看作是一个4进制的数，这样可以很容易转换成一个数值，也就是数组的下标，如此对应。
当然，如果数组的开销还是很大，就不行了......

我不知道你在哪个实验室，国内应该有不少做类似分析的人，郝先生今年刚发在NAR webserverissue上的CVTree本质上就是分析这个。
说到底用C还是最高效的，不过用perl尝试一下也挺好。我也是丢了C很多年了，执着的perler ^_^
请高手再指点吧，我也想提高一下coding技巧。

位运算我刚基于Postgres做了一个数据库实现，基本上放几个亿还是没有问题的：）

Jester，jester@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- 隐藏被引用文字 -
>>
>> - 显示引用的文字 -
>>

--
光见贼吃肉，没见贼挨打。
……

劉鑫
March.Liu

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

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