<?php
/* PHP is pass by value semantics.
To pass by reference one uses the $& symbol for the
parameters.
Sorting numbers in a defined range 0 ... N-1 with no repeats
Inspired from Programming Pearls : Jon Bentley
O(n) linear cost.
PHP does not support long bit arrays out of the box.
Code assumption: 32-bits integer
*/
$N = 1000000;
$SHIFT = 5;
$MASK = 0x1f;
$BITS = 32;
$TOPVAL = (1+$N/$BITS);
function set (&$a, $i)
{
global $SHIFT;
global $MASK;
$shift = $i >> $SHIFT; /* Which byte to set */
$mask = $i & $MASK; /* Which bit to set */
$a[$shift] = $a[$shift] | (1 << $mask);
return;
}
function get ($a, $i)
{
global $SHIFT, $MASK;
return ( $a[$i >>$SHIFT] & (1 << ($i & $MASK)) );
}
function linearsort (array & $a)
{
global $TOPVAL;
$bitvec = [];
$maxval = 0;
$i = 0;
for ($indx = 0; $indx < $TOPVAL ; $indx++)
{
$bitvec[$indx] = 0;
}
for ($indx = 0; $indx < count($a) ; $indx++)
{
if ($a[$indx] > $maxval) $maxval = $a[$indx];
set($bitvec, $a[$indx]);
}
for ($indx = 0; $indx <= $maxval ; $indx++)
{
if (get($bitvec, $indx))
$a[$i++] = $indx;
}
}
$a = array(205, 10, 7, 5, 9, 8, 1, 2, 100);
linearsort ($a);
print_r ($a);
?>
/* PHP is pass by value semantics.
To pass by reference one uses the $& symbol for the
parameters.
Sorting numbers in a defined range 0 ... N-1 with no repeats
Inspired from Programming Pearls : Jon Bentley
O(n) linear cost.
PHP does not support long bit arrays out of the box.
Code assumption: 32-bits integer
*/
$N = 1000000;
$SHIFT = 5;
$MASK = 0x1f;
$BITS = 32;
$TOPVAL = (1+$N/$BITS);
function set (&$a, $i)
{
global $SHIFT;
global $MASK;
$shift = $i >> $SHIFT; /* Which byte to set */
$mask = $i & $MASK; /* Which bit to set */
$a[$shift] = $a[$shift] | (1 << $mask);
return;
}
function get ($a, $i)
{
global $SHIFT, $MASK;
return ( $a[$i >>$SHIFT] & (1 << ($i & $MASK)) );
}
function linearsort (array & $a)
{
global $TOPVAL;
$bitvec = [];
$maxval = 0;
$i = 0;
for ($indx = 0; $indx < $TOPVAL ; $indx++)
{
$bitvec[$indx] = 0;
}
for ($indx = 0; $indx < count($a) ; $indx++)
{
if ($a[$indx] > $maxval) $maxval = $a[$indx];
set($bitvec, $a[$indx]);
}
for ($indx = 0; $indx <= $maxval ; $indx++)
{
if (get($bitvec, $indx))
$a[$i++] = $indx;
}
}
$a = array(205, 10, 7, 5, 9, 8, 1, 2, 100);
linearsort ($a);
print_r ($a);
?>
No comments:
Post a Comment