Rob,
Thanks!
My use-case is that I'm rewriting List::BinarySearch in XS via
Inline::C and eventually InlineX::C2XS. I haven't had a chance to put
your clues to the test, but should be able to get to it this
afternoon.
My eventual goal (once I get around to figuring out prototypes via
Inline::C) will be:
my $found_ix = bsearch { $a cmp $b } @haystack;
or
my $found_ix = bsearch { $a <=> $b } @haystack;
or even
my $found_ix = bsearch { $a->{key} cmp $b->{key} } @complex_haystack;
There are several binary search implementations to convert, each with
subtly different result properties, but once I get one done the rest
will be fairly straightforward.
Why?
Because for an already ordered list of items a binary search lookup
will be O(log2 n), where a hash lookup would require converting to a
hash (O(n)), and then searching (O(1)), or just calling grep (O(n)).
With some care, we ought to be able to get that binary search routine
to be efficient enough that if someone already has an ordered list
they will naturally gravitate to the bsearch rather than thinking of
grep, or a hash based approach.
On Wed, Aug 14, 2013 at 3:14 AM, <sisyph...@optusnet.com.au> wrote:
>
>
> -----Original Message----- From: David Oswald
> Sent: Wednesday, August 14, 2013 7:24 AM
> To: inline
> Subject: Implementing a callback with Inline::C
>
> See also http://www.perlmonks.org/index.pl?node_id=976632 for some other
> ideas.
>
> The "perfect" approach still eludes me, however.
>
> Cheers,
> Rob
--
David Oswald
daosw...@gmail.com
