|
|
Posted by Bob Stearns on 12/15/06 06:53
That is a shorter code, but we don't know what search logic is used. It
may devolve to the O(m*n) case, especially since it accommodates more
than one compare list.
Michael Cooney wrote:
> Or you could use array_diff:
>
> <?php
>
> $list1 = "2,26,345";
> $list2 = "3,4,26,35,525";
>
> $alist1 = split(',', $list1);
> $alist2 = split(',', $list2);
>
> if(count(array_diff($alist1, $alist2)) == 0) {
>
> echo "Yep. They're all in there.\n";
>
> } else {
>
> echo "Nope. Yer missing some.\n";
> }
>
> ?>
>
> Bob Stearns wrote:
>
>>laredotornado@zipmail.com wrote:
>>
>>>Hi,
>>>
>>>I'm using PHP 4.4.4. Let's say I have two scalars, $list1 and $list2.
>>>Both are comma separated lists of ordered, unsigned, unique integers.
>>>An example would be
>>>
>>>$list1 = "2,26,345";
>>>$list2 = "3,4,26,35,525";
>>>
>>>I am wondering if there is a short way of determining if all the
>>>numbers in $list1 occur in $list2.
>>>
>>>Grateful for any advice. Thanks, - Dave
>>>
>>
>>If, as in your example, the two lists are sorted, it can be done in
>>O(n+m) time by doing stepped compare. If they are unsorted, it can also
>>be done in O(n+m) time (with a much bigger constant factor) by making
>>the second list into the subscripts of an array, then checking for the
>>existence of the first list's elements in the new array.
>>
>>Sample code (untested):
>>
>>$i1 = 0;
>>$i2 = 0;
>>while($i1<count($list1) && $i2<count($list2)) {
>> if($list2[$i2]==$list1[$i1]) {
>> $i1++;
>> $i2++;
>> }
>> elseif($list2[$i2]<$list1[$i1]) {
>> $i2++;
>> }
>> else { /* this the failure case */ }
>> $fail = TRUE;
>> break;
>> }
>>}
>>
>>for($i2==0; $i2<count($list2); $i2++) {
>> $test[$list2[$i2]] = TRUE;
>>}
>>for($i1==0; $i1<count($list1); $i1++) {
>> if(!array_key_exists($list1[$i1],$test) {
>> $fail = TRUE;
>> break;
>> }
>>}
>>
>>We use these techniques rather than the much easier to code in_array()
>>because the time for this technique in O(m*n) since $list2 must be
>>searched completely for each element of $list1.
>
>
Navigation:
[Reply to this message]
|