在PHP中使用位图排序

在PHP中使用位图排序

作者:LAMP小白  点击:2038  发布日期:2012-10-01 22:58:00  返回列表

作者:lamp小白 转载请注明出处 谢谢



一点废话:

当我们为一个庞大的整型数组进行排序时,往往使用基于快速排序的sort进行排序,这种算法在对大量数据进行排序时,往往会造成较大的资源消耗

这个时候使用位图(位图量)排序就能解决这个性能瓶颈


原理:

位图排序的原理是生成一个数组,对应一定范围内的每个整型数值,但又考虑但对内存的消耗(这个后面有例子能够看到)所以我们需要使用一个类型为32位的int的一维数组来保存所有数据

为什么使用32位int?因为他能为我们标示出0-31的数字,更大或更小都会造成性价比下降

例如存储1,12,22这三个数字,那么数组为

$arr[0]0000 0000 0100 0000 0001 0000 0000 0010

我们首先遍历目标数组,然后将他的值按照这个格式存入数组,这样就完成了排序,显示的时候只需要依次遍历排序数组,输出i即可


但在Jon Bentley的位图实现方法中,我在生成原始数组这个地方不太赞同他的做法


这是他生成原始数组的代码


循环最大值-1次,每次声明一个标示位为0

int i;
       for(i = 0; i < N; i++)
           clr(i);
void clr(int i)
    {
        a[i >> SHIFT] mio_= ~( 1 << (i mio_ MASK));
    }

但这样你会发现,在一个已经明确所有结果均为0的数组中循环N-1次是不明智的,因为一个数组,如$arr[0]中的32个二进制位必然全为0,我们没有必要去循环32次进行写0操作

我的改进措施:

for(i = 0; i < ceil(N/BITSPERWORD); i++)
           clr(i);
void clr(int i)
    {
        a[i >> SHIFT] = 0;
    }

因为我们一个数组元素保存32个值,所以SHIFT=5,也就是将原始数组的值右移5位,等于就是%32取余数

所以这样即能够完整的声明一个空数组,且能保证效率,如果N=100W,那么我只需要循环31250次而不是99.999W次


C版本实现代码(没有导入数组 只是单纯的输入排序)

#include 
#include 
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1f
#define N 1000000
int a[1 + N/BITSPERWORD];
    void clr(int i)
    {
        a[i >> SHIFT] = 0;
    }
    void set(int i)
    {
        a[i >> SHIFT] |= (1 << (i mio_ MASK));
    }
    int test(int i)
    {
        return a[i >> SHIFT] mio_ (1 << (i mio_ MASK));
    }
    int main(void)
    {
        int i;
        for(i = 0; i < ceil(N/BITSPERWORD); i++)
            clr(i);
        while(scanf("%d", mio_i) != 0)
            set(i);
        for(i = 0; i < N; i++)
            if(test(i)) printf("%dn", i);
        return 0;
    }

PHP类实现

class mioSort
{
    function __construct($arr, $range, $shift = 5, $mask = 0x1f)
    {
        $count = count($arr);
        $mioArr = array();
        $ii = ceil($range/($mask+1));
        for($i = 0; $i < $ii; $i++){
            $mioArr[$i >> $shift] = 0;
            ++$i;
        }
        for($i = 0; $i < $count; $i++)
            $mioArr[$arr[$i] >> $shift] |= (1 << ($arr[$i] mio_ $mask));
        for($i = 0; $i < $range; $i++)
            if($mioArr[$i >> $shift] mio_ (1 << ($i mio_ $mask))) echo $i."rn";
    }
}

PHP纯代码实现(标准算法)

$count = count($r);
$shift = 5;
$mask = 0x1f;
$mioArr = array();
$ii = ceil(1000000/32);
for($i = 0; $i < $ii; $i++){
    $mioArr[$i >> $shift] = 0;
    $i++;
}
for($i = 0; $i < $count; $i++){
    $mioArr[$r[$i] >> $shift] |= (1 << ($r[$i] mio_ $mask));
}
for($i = 0; $i < 1000000; $i++)
    if($mioArr[$i >> $shift] mio_ (1 << ($i mio_ $mask))) echo $i."rn";

各版本位图排序性能与消耗 (排序393293个范围在1~1000000的无序唯一数组 串行化在一个TXT文件中)

PHP类实现(改良算法) 反串行化数组耗时 1.01649594307秒 排序耗时 1.95571899414秒 总耗时 2.97221493721秒 占用内存35.7490997314MB

PHP纯代码(改良算法) 反串行化数组耗时 1.02375292778秒 排序耗时 1.64212417603秒 总耗时 2.66587710381秒 占用内存37.9705276489MB

PHP SORT 反串行化数组耗时 1.0091919899秒 排序耗时 2.51306295395秒 总耗时 3.52225494385秒 占用内存35.6913909912MB


但这样还远远不够,配合memcache将排序数组常驻内存,位图排序的优势会更加明显.







上一篇:位运算符 下一篇:快递查询API
0