PHP function to extract numbers from the list whose squares are exceed some threshold

Question

This is my naive approach:

$sample1 = [3, -20, 1, -19, -4, 6, 77, -1, 0, 6];
$sample3 = [4, 5, -7, 0, 2, 44, -3, -5, 66, -7];
$sample4 = [4, 25, 1, 6, 9, 5, 999, 4, 43, 2];
$sample2 = [];
for ($i = 0; $i < mt_rand(10, 30); $i++) {
 $sample2[] = mt_rand(-1000, 1000);
}
extractNumbersThatSquaresAreGreaterThan($sample1);
extractNumbersThatSquaresAreGreaterThan($sample2);
extractNumbersThatSquaresAreGreaterThan($sample3);
extractNumbersThatSquaresAreGreaterThan($sample4);
var_dump($sample1);
//var_dump($sample2);
var_dump($sample3);
var_dump($sample4);
function extractNumbersThatSquaresAreGreaterThan(&$list, $boundary = 26) {
 foreach ($list as $key => $value) {
 if (pow($value, 2) <= $boundary) {
 unset($list[$key]);
 }
 }
}

Any hints for optimization? Is it possible, I've tried few, but in the end it was more complicated (and slower) solution

• Your Common Sense: Please fix the code
• DevMed: @YourCommonSense please provide me more test data, than I'll fix

Answer 1

Hints? Ok.

1. Don’t square the values, O(n), instead square-root the boundary. You’ll need an or in your test, though.

2. Don’t unset values in the list. That requires shifting values in memory. Make a new list of same size, fill in values, without gaps, and then resize result.

Answer 2

I don't know about how fast this solution will be, but anyway I suggest to use functional approach to solve your problem. At least you will have concise code:

$sample4 = [4, 25, 1, 6, 9, 5, 999, 4, 43, 2];
var_dump(extractNumbers($sample4, 26));
function extractNumbers($list, $boundary) {
 return array_filter($list, function($x) use ($boundary) {
 return ($x * $x) > $boundary;
 });
}

Answer 3

Instead of remove items with unset, I would use array_filter. And in fact, you could factor out the pow function, if you use basic maths.

$$ num^2 \leq boundary\\ \implies |num| \leq \sqrt{boundary} $$

combining this would result in

function extractNumbersThatSquaresAreGreaterThan(&$list, $boundary = 26) {
 $sqrt_boundary = sqrt($boundary);
 $list = array_filter($list, function ($item) use ($sqrt_boundary) {
 return abs($item) > $sqrt_boundary;
 });
}

In addition, I would avoid the use of referenes for this task and just return your value.

function extractNumbersThatSquaresAreGreaterThan($list, $boundary = 26) {
 $sqrt_boundary = sqrt($boundary);
 return array_filter($list, function ($item) use ($sqrt_boundary) {
 return abs($item) > $sqrt_boundary;
 });
}

• DevMed: Thanks a lot for this. Especially reminding me, that something like ABS exists ;)