Skip Menu |
 

This queue is for tickets about the List-MoreUtils CPAN distribution.

Report information
The Basics
Id: 63470
Status: resolved
Priority: 0/
Queue: List-MoreUtils

People
Owner: Nobody in particular
Requestors: EDAVIS [...] cpan.org
Cc:
AdminCc:

Bug Information
Severity: Wishlist
Broken in: 0.26
Fixed in: 0.407



Subject: Feature request: firstidx_monotone
Download (untitled) / with headers
text/plain 896b
Sometimes you use firstidx when you know that the result is 'monotone', that is, the condition is false for the first N elements (N >= 0) and then true for any remaining elements in the list. For example my @sorted = sort @strings; my $pos = firstidx { $_ lt 'xyz' } @sorted; In such situations you could expect a speedup from doing a binary search rather than a linear scan. How about a drop-in replacement: my $pos = firstidx_monotone { $_ lt 'xyz' } @sorted; This could use a binary search internally and so be a lot faster than plain firstidx, and also much faster than implementing a binary search in pure Perl. It is also a lot simpler than the very general interface provided by Search::Binary. I would document it formally as 'does the same thing as firstidx, but has the precondition that for any list index i, 0 <= i < length, if condition(i) then condition(i + 1).'
Download (untitled) / with headers
text/plain 139b
Duuh... in the example I meant to say $pos = firstidx { $_ ge 'xyz' } @sorted; $pos = firstidx_monotone { $_ ge 'xyz' } @sorted;
Download (untitled) / with headers
text/plain 128b
Pushed 8b921d96 which contains a bsearchidx in addition to bsearch (which was introduced in 2009). This should satisfy the wish.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.