In perl 5.10, is $needle ~~ @haystack binary search?

thanks,
~greg

Re: In perl 5.10, is $needle ~~ @haystack binary search?

scratch that, it was a dumb question -
@haystack would have to be sorted.
and I don't expect ~~ to be *that* smart to know when it is,
(or else write $needle ~~ sort @haystack ?)

anyway, my real question is,
just how efficient is ~~?

Re: In perl 5.10, is $needle ~~ @haystack binary search?

_
~greg (g_m@remove-comcast.net) wrote on VCCLI September MCMXCIII in
:
?? scratch that, it was a dumb question -
?? @haystack would have to be sorted.
?? and I don't expect ~~ to be *that* smart to know when it is,
?? (or else write $needle ~~ sort @haystack ?)
??
?? anyway, my real question is,
?? just how efficient is ~~?


What do you mean by "how efficient"? Do you want a number?
If I tell you its efficiency is 17, does that tell you
anything?


Abigail
--
echo "==== ======= ==== ======"|perl -pes/=/J/|perl -pes/==/us/|perl -pes/=/t/\
|perl -pes/=/A/|perl -pes/=/n/|perl -pes/=/o/|perl -pes/==/th/|perl -pes/=/e/\
|perl -pes/=/r/|perl -pes/=/P/|perl -pes/=/e/|perl -pes/==/rl/|perl -pes/=/H/\
|perl -pes/=/a/|perl -pes/=/c/|perl -pes/=/k/|perl -pes/==/er/|perl -pes/=/./;

Re: In perl 5.10, is $needle ~~ @haystack binary search?

> What do you mean by "how efficient"? Do you want a number?
> If I tell you its efficiency is 17, does that tell you
> anything?
>
>
> Abigail



big-O will do.

Re: In perl 5.10, is $needle ~~ @haystack binary search?

"~greg" writes:

> thanks,
> ~greg

No. It can't be, since @haystack is not guaranteed to be sorted.

perlop says:

for $a ~~ $b and $b ~~ $a:

$a $b Type of Match Implied Matching Code
====== ===== ===================== =============
Array Num array contains number grep $_ == $b, @$a
Array Any array contains string grep $_ eq $b, @$a

Joost.

Re: In perl 5.10, is $needle ~~ @haystack binary search?

_
~greg (g_m@remove-comcast.net) wrote on VCCLI September MCMXCIII in
:
...
... > What do you mean by "how efficient"? Do you want a number?
... > If I tell you its efficiency is 17, does that tell you
... > anything?
... >
... >
... > Abigail
...
... big-O will do.


O (N) where N is the size of @haystack, with the assumption that
comparing two scalar can be done in constant time.

This is optimal.


But does this help you? $needle ~~ @haystack might first sleep for a
week or so, and you wouldn't notice that in "big-O".


Abigail
--
package Just_another_Perl_Hacker; sub print {($_=$_[0])=~ s/_/ /g;
print } sub __PACKAGE__ { &
print ( __PACKAGE__)} &
__PACKAGE__
( )

Re: In perl 5.10, is $needle ~~ @haystack binary search?

Joost Diepenmaat wrote:
> "~greg" writes:
>
>> thanks,
>> ~greg
>
> No. It can't be, since @haystack is not guaranteed to be sorted.
>
> perlop says:
>
> for $a ~~ $b and $b ~~ $a:
>
> $a $b Type of Match Implied Matching Code
> ====== ===== ===================== =============
> Array Num array contains number grep $_ == $b, @$a
> Array Any array contains string grep $_ eq $b, @$a

Given that the equivalent code looks fine, I fail to see the need
for ~~ at all?

BugBear

Re: In perl 5.10, is $needle ~~ @haystack binary search?

On Wed, 16 Jan 2008 14:26:28 +0000, bugbear
wrote:

>> for $a ~~ $b and $b ~~ $a:
>>
>> $a $b Type of Match Implied Matching Code
>> ====== ===== ===================== =============
>> Array Num array contains number grep $_ == $b, @$a
>> Array Any array contains string grep $_ eq $b, @$a
>
>Given that the equivalent code looks fine, I fail to see the need
>for ~~ at all?

"syntactic sugar"!


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^ ..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER 256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,

Re: In perl 5.10, is $needle ~~ @haystack binary search?

_
bugbear (bugbear@trim_papermule.co.uk_trim) wrote on VCCLI September
MCMXCIII in :
:} Joost Diepenmaat wrote:
:} > "~greg" writes:
:} >
:} >> thanks,
:} >> ~greg
:} >
:} > No. It can't be, since @haystack is not guaranteed to be sorted.
:} >
:} > perlop says:
:} >
:} > for $a ~~ $b and $b ~~ $a:
:} >
:} > $a $b Type of Match Implied Matching Code
:} > ====== ===== ===================== =============
:} > Array Num array contains number grep $_ == $b, @$a
:} > Array Any array contains string grep $_ eq $b, @$a
:}
:} Given that the equivalent code looks fine, I fail to see the need
:} for ~~ at all?


If you prefer to program in a language that doesn't have redundancy,
Perl is about the worst choice you can make. Certainly, ~~ can be
written differently, but if that's a reason to question its need,
would you question the need for 'for', 'while', 'until' and bare
blocks, given that you can do it all with a goto?

Besides, noone forces you to use ~~. Not to mention that ~~ is somewhat
faster in general, and lots faster if there's a match early on in a big
array (~~ will stop on a match, grep will always check the entire array).
And the implied ~~ works quite nice with given/when. But feel free to use
the longhand.



Abigail
--
$_ = "\nrekcaH lreP rehtona tsuJ"; my $chop; $chop = sub {print chop; $chop};
$chop -> () -> () -> () -> () -> () -> () -> () -> () -> () -> () -> () -> ()
-> () -> () -> () -> () -> () -> () -> () -> () -> () -> () -> () -> () -> ()

Re: In perl 5.10, is $needle ~~ @haystack binary search?

Abigail wrote:
>
> If you prefer to program in a language that doesn't have redundancy,
> Perl is about the worst choice you can make. Certainly, ~~ can be
> written differently, but if that's a reason to question its need,
> would you question the need for 'for', 'while', 'until' and bare
> blocks, given that you can do it all with a goto?
>
> Besides, noone forces you to use ~~. Not to mention that ~~ is somewhat
> faster in general, and lots faster if there's a match early on in a big
> array (~~ will stop on a match, grep will always check the entire array).
> And the implied ~~ works quite nice with given/when. But feel free to use
> the longhand.

Early termination is good :-)

BugBear

Re: In perl 5.10, is $needle ~~ @haystack binary search?

On 2008-01-16, Abigail wrote:
> _
> bugbear (bugbear@trim_papermule.co.uk_trim) wrote on VCCLI September
> MCMXCIII in :
>:} Joost Diepenmaat wrote:
>:} > "~greg" writes:
>:} >
>:} >> thanks,
>:} >> ~greg
>:} >
>:} > No. It can't be, since @haystack is not guaranteed to be sorted.
>:} >
>:} > perlop says:
>:} >
>:} > for $a ~~ $b and $b ~~ $a:

Sorry for interrupting and pardon my ignorance, but what is the ~~
operator? I don't see it in 'perldoc perlop' (for perl 5.8.6). And I
cannot figure out how to search for "~~" in google.

Thanks.

>:} >
>:} > $a $b Type of Match Implied Matching Code
>:} > ====== ===== ===================== =============
>:} > Array Num array contains number grep $_ == $b, @$a
>:} > Array Any array contains string grep $_ eq $b, @$a
>:}
>:} Given that the equivalent code looks fine, I fail to see the need
>:} for ~~ at all?
>
>
> If you prefer to program in a language that doesn't have redundancy,
> Perl is about the worst choice you can make. Certainly, ~~ can be
> written differently, but if that's a reason to question its need,
> would you question the need for 'for', 'while', 'until' and bare
> blocks, given that you can do it all with a goto?
>
> Besides, noone forces you to use ~~. Not to mention that ~~ is somewhat
> faster in general, and lots faster if there's a match early on in a big
> array (~~ will stop on a match, grep will always check the entire array).
> And the implied ~~ works quite nice with given/when. But feel free to use
> the longhand.
>

--

Re: In perl 5.10, is $needle ~~ @haystack binary search?

On Wed, 16 Jan 2008 19:19:17 +0100 (CET), Jim Cochrane
wrote:

>>:} > for $a ~~ $b and $b ~~ $a:
>
>Sorry for interrupting and pardon my ignorance, but what is the ~~
>operator? I don't see it in 'perldoc perlop' (for perl 5.8.6). And I

It's something that's been introduced in stable Perl with 5.10.0!


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^ ..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER 256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,

Re: In perl 5.10, is $needle ~~ @haystack binary search?

On Jan 16, 1:19=A0pm, Jim Cochrane allowed.org> wrote:
> On 2008-01-16, Abigail wrote:
>
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0_
> > bugbear (bugbear@trim_papermule.co.uk_trim) wrote on VCCLI September
> > MCMXCIII in :
> >:} =A0Joost Diepenmaat wrote:
> >:} > "~greg" writes:
> >:} >
> >:} >> thanks,
> >:} >> ~greg
> >:} >
> >:} > No. It can't be, since @haystack is not guaranteed to be sorted.
> >:} >
> >:} > perlop says:
> >:} >
> >:} > for $a ~~ $b and $b ~~ $a:
>
> Sorry for interrupting and pardon my ignorance, but what is the ~~
> operator? =A0I don't see it in 'perldoc perlop' (for perl 5.8.6). =A0And I=

> cannot figure out how to search for "~~" in google.

This is for Perl 5.10.

Check out Equality Operators:
"smart match"
http://perldoc.perl.org/perlop.html

HTH

Re: In perl 5.10, is $needle ~~ @haystack binary search?

On 2008-01-16, nolo contendere wrote:
> On Jan 16, 1:19 pm, Jim Cochrane > allowed.org> wrote:
>>
>> Sorry for interrupting and pardon my ignorance, but what is the ~~
>> operator?  I don't see it in 'perldoc perlop' (for perl 5.8.6).  And I
>> cannot figure out how to search for "~~" in google.
>
> This is for Perl 5.10.
>
> Check out Equality Operators:
> "smart match"
> http://perldoc.perl.org/perlop.html

Or try

http://perldoc.perl.org/perlsyn.html#Smart-matching-in-detai l

which has the full chart which Joost referenced.

--keith

--
kkeller-usenet@wombat.san-francisco.ca.us
(try just my userid to email me)
AOLSFAQ=http://www.therockgarden.ca/aolsfaq.txt
see X- headers for PGP signature information

Re: In perl 5.10, is $needle ~~ @haystack binary search?

> O (N) where N is the size of @haystack, with the assumption that
> comparing two scalar can be done in constant time.
>
> This is optimal.
>
>
> But does this help you? $needle ~~ @haystack might first sleep for a
> week or so, and you wouldn't notice that in "big-O".
>
>
> Abigail
> --

right, thanks.

Best case 1, avg case N/2, worst case N.

(I'm mainly interested in how it scales, so the constant factor doesn't matter.)
~~

I think I know now what I was thinking last night!

Everything about perl 5.10 seems faster.
(You don't have to measure it. You feel it.)

So I was thinking - there must be nothing it doesn't do better.

A linear search - in better than linear time?
Sure - why not.
:)


~greg

Re: In perl 5.10, is $needle ~~ @haystack binary search?

In article <13os50l4a053gb9@corp.supernews.com>, bugbear
wrote:

> Joost Diepenmaat wrote:
> > "~greg" writes:
> >
> >> thanks,
> >> ~greg
> >
> > No. It can't be, since @haystack is not guaranteed to be sorted.
> >
> > perlop says:
> >
> > for $a ~~ $b and $b ~~ $a:
> >
> > $a $b Type of Match Implied Matching Code
> > ====== ===== ===================== =============
> > Array Num array contains number grep $_ == $b, @$a
> > Array Any array contains string grep $_ eq $b, @$a
>
> Given that the equivalent code looks fine, I fail to see the need
> for ~~ at all?
>
> BugBear

You're only looking at two of the cases. The smart match handles many
cases, so it handles those as well. The "matching code" isn't
nessicarily the code it actually runs (read the notes after that table
in perlop).

Additionally, smart matching appears to be faster:

http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2007- 12/msg00644.
html

Re: In perl 5.10, is $needle ~~ @haystack binary search?

_
~greg (g_m@remove-comcast.net) wrote on VCCLI September MCMXCIII in
:
!!
!! > O (N) where N is the size of @haystack, with the assumption that
!! > comparing two scalar can be done in constant time.
!! >
!! > This is optimal.
!! >
!! >
!! > But does this help you? $needle ~~ @haystack might first sleep for a
!! > week or so, and you wouldn't notice that in "big-O".
!! >
!! >
!! > Abigail
!! > --
!!
!! right, thanks.
!!
!! Best case 1, avg case N/2, worst case N.

Why do you think the average case in N/2? Sure, if all your matches
actually succeed, and the thing you are looking for occurs only once
in your array, and can appear on any index with equal probability,
the average case is N/2. But then, if all your matches always succeed
there's no point in asking whether there's a match. The less likely
your match succeeds, the more your average will go towards N. The more
the thing you're looking for appears in the array (as duplicates), the
more your average will go towards 1.

!! (I'm mainly interested in how it scales, so the constant factor doesn't matter.)
!! ~~
!!
!! I think I know now what I was thinking last night!
!!
!! Everything about perl 5.10 seems faster.
!! (You don't have to measure it. You feel it.)
!!
!! So I was thinking - there must be nothing it doesn't do better.
!!
!! A linear search - in better than linear time?
!! Sure - why not.


Cannot be done without preprocessing.



Abigail
--
perl -we '$| = 1; $_ = "Just another Perl Hacker\n"; print
substr $_ => 0, 1 => "" while $_ && sleep 1 => 1'

Re: In perl 5.10, is $needle ~~ @haystack binary search?

"Abigail" wrote in message news:slrnfot28d.t74.abigail@alexandra.abigail.be...
> _
> ~greg (g_m@remove-comcast.net) wrote on VCCLI September MCMXCIII in
> :
> !!
> !! > O (N) where N is the size of @haystack, with the assumption that
> !! > comparing two scalar can be done in constant time.
> !! >
> !! > This is optimal.
> !! >
> !! >
> !! > But does this help you? $needle ~~ @haystack might first sleep for a
> !! > week or so, and you wouldn't notice that in "big-O".
> !! >
> !! >
> !! > Abigail
> !! > --
> !!
> !! right, thanks.
> !!
> !! Best case 1, avg case N/2, worst case N.
>
> Why do you think the average case in N/2?
> Sure, if all your matches
> actually succeed, and the thing you are looking for occurs only once
> in your array, and can appear on any index with equal probability,
> the average case is N/2. But then, if all your matches always succeed
> there's no point in asking whether there's a match. The less likely
> your match succeeds, the more your average will go towards N. The more
> the thing you're looking for appears in the array (as duplicates), the
> more your average will go towards 1.
>

~~~~~

Thank you.

Why did I think that the average case was N/2?

I didn't. I wasn't thinking.
I must have mis-read it somewhere.
Possibly here - http://en.wikipedia.org/wiki/Linear_search

Anyway, thank you for forcing me to think about these things again!
I has been awhile.

I remember now that there is no substitue for clarity,
and for trying to be careful.
~~

Given completely random data,
the probability that a $needle will be found in a @haystack,
when it may not be there at all, is essentially zero,
and almost all searches will have to complete
N comparisons.

~~
Now, for the hell of it: ....

Simplifying the problem to invovle only two objects , 0 and 1,

What is the expected number of comparisons that will
have to be made before hitting the first match,
when there may be any number of matches,
or not match at all?

For example, when n=3, the sample space for this is
{000, 001, 010, 011, 100, 101, 110, 111}
and the event sets, and the random variable's values on them,
are

event "match on 1st comparison"
set = {100,101,110,111}
count = 4
prob = 4/8
value = 1
expectation = 1*(4/8)

event "match on 2nd comparison"
set = {010, 011}
count = 2
prob = 2/8
value = 2
expectation = 2 * (2/8)

event = "match on 3rd comparison"
set = {001}
count = 1
prob = 1/8
value = 3
expectation = 3*(1/8)

event = "no match after 3 comparisons"
set = {000}
count = 1
prob = 1/8
value = 3
expectation = 3*(1/8)
---------------------------------------------
Expected value = 1*(4/8) + 2*(2/8) + 3*(1/8) + 3*(1/8) = 1.75

Generally,
event "matches at kth comparison"
set = { k-1 0s, one 1, sequences of N-k 0s and 1s }
count = 2**(N-k)
prob = 2**(N-k) / 2**N = 1/2**k
value = k
expectation = k/2**k

plus

event "doesn't match after N comparions"
set = {0...0}
count = 1
prob = 1/2**N
value = N
expectation = N/2**N

So
sub Expected
{
my $N = shift;
my $e;
for(my $k=1; $k<=$N; $k++)
{
$e += $k * 2**($N-$k) / 2**$N;
}
$e += $N * (1/ (2**$N);
}

Which reduces to (2**$N - 1) / 2**($N-1)
after using a formula for the "Arithmetic power series"
which can be found, eg, here:
http://mathtable.com/errata/smtf30_errata_p2/

Which => 2
as $N => infinity.

which shouldn't come as a surprise!
Because if you toss a coin lots of times,
then you expect it to come up heads,
if not on the first toss,
then very likely on the second, ...
~~~

In any case, it's not 1, or N/2, or N.
~~~

I have been trying to figure it out when there are M objects
instead of just 2. In particular, for very large M.
(eg M=total number of integers representable on the computer).

But I am am not getting consistent results. :)
(--it has been quite awhile, and the algebra
is really hairy. But I'm trying to figure out how to use Maple again.)

The expected value will involve M.
In fact I got (a couple of times anyway)
that it will approache M, as M approaches infinity!

Which doesn't appear to make much sense. But maybe
it might. In any case I am pretty sure that the expected value
of the number of comparisons is not 1, or N/2, or N.

There are of course lots of more intelligent ways to do all this.
I just don't know what they are.

Re: In perl 5.10, is $needle ~~ @haystack binary search?

On 2008-01-16, Keith Keller wrote:
> On 2008-01-16, nolo contendere wrote:
>> On Jan 16, 1:19 pm, Jim Cochrane >> allowed.org> wrote:
>>>
>>> Sorry for interrupting and pardon my ignorance, but what is the ~~
>>> operator?  I don't see it in 'perldoc perlop' (for perl 5.8.6).  And I
>>> cannot figure out how to search for "~~" in google.
>>
>> This is for Perl 5.10.
>>
>> Check out Equality Operators:
>> "smart match"
>> http://perldoc.perl.org/perlop.html
>
> Or try
>
> http://perldoc.perl.org/perlsyn.html#Smart-matching-in-detai l
>
> which has the full chart which Joost referenced.
>
> --keith
>

Thanks, all, for the answers and links.

By the way, does anyone know how to search for something like
perl ~~
on google? I've not been able to figure out a way. (Perhaps it's not
possible.)


--

Re: In perl 5.10, is $needle ~~ @haystack binary search?

"Jim Cochrane" >
>
> By the way, does anyone know how to search for something like
> perl ~~
> on google? I've not been able to figure out a way. (Perhaps it's not
> possible.)
>

Nothing is ever impossible.

It just sometimes takes too long
(eg > expected remaining duration of the universe.)

this
http://www.krugle.org/

may not help very often.
But it's promising, and fun.

~greg