Do you have a question? Post it now! No Registration Necessary. Now with pictures!
- Subject
- Posted on
Re: In perl 5.10, is $needle ~~ @haystack binary search?
~~~~~
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 =
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 =
count = 1
prob = 1/8
value = 3
expectation = 3*(1/8)
event = "no match after 3 comparisons"
set =
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 =
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.
Site Timeline
- » FAQ 1.3 Which version of Perl should I use?
- — Next thread in » PERL Discussions
- » FAQ 8.33 Is there a way to hide perl's command line from programs such as "ps"?
- — Previous thread in » PERL Discussions
- » s suffix question
- — Newest thread in » PERL Discussions
- » SSD partition alignment revisited
- — The site's Newest Thread. Posted in » Computer Hardware