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

还是perl 社区的牛人多，那个C++实现太赞了。
我前两周的时候，也是正好遇到一个做生物的朋友提这个问题，所以写了一个基于Postgres的数据库bimap映射实现，还很简陋，正在整理资料。

数据结构很简单：

create table bitmap(bigint idx, segment bit(32));

其它计算方面的东西相信就都很好写了，这里我献丑放一个记录覆盖的：

create or replace function segment_true(s bigint, e bigint) returns void as $$
declare
    sidx bigint;
    eidx bigint;
    d_data bit(32) := 4294967295::bit(32); -- pow(2, 32) -1
begin
    if currval('bitmap_idx_seq') < (e/32)+1 then
        for i in currval('bitmap_idx_seq')..e/32+1 loop
            insert into bitmap(segment) select 0::bit(32);
        end loop;
    end if;
    sidx := s/32;
    eidx := e/32;
    if sidx = eidx then
        update bitmap set segment = (d_data << cast((32-e%32) as int))&(d_data >> cast((s%32) as int)) where idx = sidx;
    else
        update bitmap set segment = segment | (d_data >> cast((s%32) as int)) where idx = sidx;
        update bitmap set segment = d_data where sidx < idx and idx < eidx;
        update bitmap set segment = segment | (d_data << cast((e%32) AS INT)) where idx = eidx;
    end if;
end;
$$ language plpgsql;

说明一下，PG的整数没有无符号类型，所以操作起来比较讨厌，我干脆直接用它的bit类型，这个类型最多可以支持2^31位，所有基础的位运算它都支持。通过idx可以将分片的bit记录连成一个大的bitmap。具体bit应该多少位，idx应该用int还是bigint，我想应该视数据量和业务来调整，不必太死板，能达到好用，快速就好。

数据库实现的好处是可以在数据量和性能以及并发性上有个比较折中的实现，而且因为都是现成的功能，组合起来比较快，质量也可靠。

空格兄的问题很有意思，我想写写试试。

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

劉鑫
March.Liu

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

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