How to avoid in_array() function.

[Berimor]

Hi,
i've been always used the in_array() function to check availabylity of a
value in array. Until today. Simple code: (do not run it tho :) )

<?
function getmicrotime(){
list($usec, $sec) = explode(" ",microtime ());
return ((float)$usec + (float)$sec);
}

$time_start = getmicrotime();

$first=range("a ","z");
$second=range(" a","z");
$third=range("a ","z");
$all_arr=array( );

foreach ($first as $f){
foreach ($second as $s){
foreach ($third as $t){

$ind=$f.$s.$t;
if (!in_array($ind ,$all_arr)) $all_arr[]=$ind;


}
}
}


$time_end = getmicrotime();
$time = $time_end - $time_start;
echo $time;
?>

It prints the time script worked. Guess the number?
250(!!!!) seconds!!!
Is there any alternative in PHP to check array?




--
Exact Meta Search | Major Search Engine http://exactsearcher.com
Web Design Essex | Multimedia | Printing http://nextwave.co.uk

[Peter van Schie]

Re: How to avoid in_array() function.

Berimor wrote:
[color=blue]
> It prints the time script worked. Guess the number?
> 250(!!!!) seconds!!!
> Is there any alternative in PHP to check array?[/color]

There is array_search, but I didn't benchmark it.

HTH.
Peter.

--

http://www.phpforums.nl

[Berimor]

Re: How to avoid in_array() function.

On Sun, 04 Dec 2005 16:36:43 +0100, Peter van Schie
<vanschie.peter @gmail.com> wrote:
[color=blue]
> Berimor wrote:
>[color=green]
>> It prints the time script worked. Guess the number?
>> 250(!!!!) seconds!!!
>> Is there any alternative in PHP to check array?[/color]
>
> There is array_search, but I didn't benchmark it.
>[/color]

i did - the same.
[color=blue]
> HTH.
> Peter.
>[/color]



--
Exact Meta Search | Major Search Engine http://exactsearcher.com
Web Design Essex | Multimedia | Printing http://nextwave.co.uk

[Chung Leong]

Re: How to avoid in_array() function.

The hash table was invented precisely to solve this sort of problem.

Example:

$first=range("a ","z");
$second=range(" a","z");
$third=range("a ","z");
$all_hash=array ();

foreach ($first as $f){
foreach ($second as $s){
foreach ($third as $t){
$all_hash[$f.$s.$t] = true;
}
}
}
$all_arr = array_keys($all _hash);

[Michael Winter]

Re: How to avoid in_array() function.

On 04/12/2005 15:34, Berimor wrote:

[snip]
[color=blue]
> $first=range("a ","z");
> $second=range(" a","z");
> $third=range("a ","z");
> $all_arr=array( );
>
> foreach ($first as $f){
> foreach ($second as $s){
> foreach ($third as $t){
> $ind=$f.$s.$t;
> if (!in_array($ind ,$all_arr)) $all_arr[]=$ind;
> }
> }
> }[/color]

[snip]
[color=blue]
> It prints the time script worked. Guess the number?
> 250(!!!!) seconds!!![/color]

I'm not that surprised, though it took just less than a minute here. Do
you understand how much work you're expecting PHP to do?

In each iteration of the innermost loop, 'ind' will be assigned a unique
value. The in_array function must then search 'all_arr' and attempt to
find it. As it will never exist, the function will perform an exhaustive
search, eventually returning false.

In the first iteration, 'all_arr' will be empty. In the second, it will
have one element. By the final iteration, 'all_arr' will contain 17,575
elements (the final one yet to be added). To reach, and finally execute,
the final assignment, the in_array function will have performed
154,449,100 string comparisons (the sum of the number of elements on
each iteration) without a single match. The rest of the code will have
its own overheads, too.
[color=blue]
> Is there any alternative in PHP to check array?[/color]

It would seem that a better algorithm is what you really need. On this
machine, removing the if statement reduced the execution time to about
60ms: approximately 93 times faster.

Why do you think you need to keep checking the values in the array? If
you explain what you're doing, someone may be able to show you an
alternative approach.

Mike

--
Michael Winter
Prefix subject with [News] before replying by e-mail.

[Janwillem Borleffs]

Re: How to avoid in_array() function.

Berimor wrote:[color=blue]
> Is there any alternative in PHP to check array?
>[/color]

foreach ($first as $f){
foreach ($second as $s){
foreach ($third as $t){
$all_arr[] = $f.$s.$t;
}
}
}
$all_arr = array_unique($a ll_arr);


JW

[R. Rajesh Jeba Anbiah]

Re: How to avoid in_array() function.

Berimor wrote:[color=blue]
> Hi,
> i've been always used the in_array() function to check availabylity of a
> value in array. Until today. Simple code: (do not run it tho :) )[/color]
<snip>[color=blue]
> It prints the time script worked. Guess the number?
> 250(!!!!) seconds!!!
> Is there any alternative in PHP to check array?[/color]

IIRC, Ilia Alshanetsky, one of the PHP core developer and maintainer
blogged on this some time ago. According to him, isset() will be the
fastest; but for isset(), you need key.

FWIW, it's nice to see many people have now become optimization
advocates recently in c.l.php--a very rarest gesture some years ago:)

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com/