PHPはbitmapビットマップの並べ替えと交差を求める方法を実現する
3626 ワード
本明細書の例では、PHPがbitmapビットマップ並べ替えを実現して交差を求める方法について説明する.皆さんの参考にしてください.具体的には以下の通りです.
すべて0のバイナリの列を初期化します.
無秩序な整数配列が存在する.
整数xがこの整数配列にある場合、バイナリ列のx番目の位置は1となる.
そしてこのバイナリ列を順番に読み、1のビットを整数に変換し、新しい集合に順番に格納すると、順番に並べられます
ソートコード:
ブラウザ出力:
array 0 => int 1 1 => int 3 2 => int 4 3 => int 34 4 => int 50 5 => int 60 6 => int 88 7 => int 100 8 => int 150 9 => int 200 10 => int 300
交差コードを求める:
ブラウザ出力:
array 0 => int 1 1 => int 3 2 => int 34 3 => int 50 4 => int 100 5 => int 150 6 => int 300
PHPに関する内容についてもっと兴味のある読者は、「PHP配列(Array)操作技巧大全」、「phpソートアルゴリズム総括」、「PHP常用遍歴アルゴリズムと技巧総括」、「PHPデータ構造とアルゴリズム教程」、「phpプログラム设计アルゴリズム総括」、「PHP数学演算技巧総括」、「php正則表式用法総括」、「PHP演算と演算子の使い方のまとめ」、「php文字列(string)使い方のまとめ」および「php一般的なデータベース操作テクニックのまとめ」
ここで述べたことが皆さんのPHPプログラム設計に役立つことを願っています.
すべて0のバイナリの列を初期化します.
無秩序な整数配列が存在する.
整数xがこの整数配列にある場合、バイナリ列のx番目の位置は1となる.
そしてこのバイナリ列を順番に読み、1のビットを整数に変換し、新しい集合に順番に格納すると、順番に並べられます
ソートコード:
function sort()
{
// var_dump(PHP_INT_MAX, PHP_INT_SIZE);
// int 9223372036854775807
// int 8
$bitmap = array_fill(0, 50, 0); // , 50 , 0
$int_bit_size = PHP_INT_SIZE * 8; //$bitmap ( int = 8*8 = 64bit; $bitmap 50*64 = 3200 bit ), 3200
$a = array(1,4,3,50,34,60,100,88,200,150,300); //
// $a , x*64 + y
foreach ($a as $k => $v) {
$shang = $v / $int_bit_size;
$yushu = $v % $int_bit_size;
$offset = 1 << $yushu;
$bitmap[$shang] = $bitmap[$shang] | $offset;// bit 1
}
// $bitmap bit ,
$b = array();
foreach ($bitmap as $k => $v) {
for ($i = 0; $i < $int_bit_size; $i++) {
$tmp = 1 << $i;
$flag = $tmp & $bitmap[$k];
// $b[] = $flag ? $k * $int_bit_size + $i : false;
if ($flag) {
$b[] = $k * $int_bit_size + $i;
}
}
}
var_dump($b);exit;
}
ブラウザ出力:
array 0 => int 1 1 => int 3 2 => int 4 3 => int 34 4 => int 50 5 => int 60 6 => int 88 7 => int 100 8 => int 150 9 => int 200 10 => int 300
交差コードを求める:
public function sort($a = array())
{
// var_dump(PHP_INT_MAX, PHP_INT_SIZE);
// int 9223372036854775807
// int 8
$bitmap = array_fill(0, 50, 0); // , 50 , 0
$int_bit_size = PHP_INT_SIZE * 8; //$bitmap ( int = 8*8 = 64bit; $bitmap 50*64 = 3200 bit )
// $a = array(1,4,3,50,34,60,100,88,200,150,300); //
// $a , x*64 + y
foreach ($a as $k => $v) {
$shang = $v / $int_bit_size;
$yushu = $v % $int_bit_size;
$offset = 1 << $yushu;
$bitmap[$shang] = $bitmap[$shang] | $offset;// bit 1
}
return $bitmap;
}
public function intersect()
{
$int_bit_size = PHP_INT_SIZE * 8;
$a = array(1,4,3,50,34,60,100,88,200,150,300);
$b = array(1,5,3,50,34,55,100,87,222,150,300);
$bit_a = $this->sort($a);
$bit_b = $this->sort($b);
$c = array();
foreach ($bit_a as $k => $v) {
$c[$k] = $bit_a[$k] & $bit_b[$k]; // &
}
$d = array();
foreach ($c as $k => $v) {
for ($i = 0; $i < $int_bit_size; $i++) {
$tmp = 1 << $i;
$flag = $tmp & $c[$k];
// $b[] = $flag ? $k * $int_bit_size + $i : false;
if ($flag) {
$d[] = $k * $int_bit_size + $i;
}
}
}
var_dump($d);exit;
}
ブラウザ出力:
array 0 => int 1 1 => int 3 2 => int 34 3 => int 50 4 => int 100 5 => int 150 6 => int 300
PHPに関する内容についてもっと兴味のある読者は、「PHP配列(Array)操作技巧大全」、「phpソートアルゴリズム総括」、「PHP常用遍歴アルゴリズムと技巧総括」、「PHPデータ構造とアルゴリズム教程」、「phpプログラム设计アルゴリズム総括」、「PHP数学演算技巧総括」、「php正則表式用法総括」、「PHP演算と演算子の使い方のまとめ」、「php文字列(string)使い方のまとめ」および「php一般的なデータベース操作テクニックのまとめ」
ここで述べたことが皆さんのPHPプログラム設計に役立つことを願っています.