www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Opportunistic worst-case complexity upgrade? aka binary search with

reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
We should talk about a design question surrounding binary search 
with `canFind`/`find` and possibly other linear-search functions.

Currently we have binary search in Phobos as part of 
std.range.SortedRange. Its interface is not compatible with 
`canFind` or `find` - you can't simply wrap the haystack in a 
SortedRange and pass it to an algorithm to give you logarithmic 
complexity.

The first question is whether this opportunistic upgrade is 
desirable - binary search has much better worst-case complexity 
than linear search, but it's not necessarily faster in the 
average case, which depends on the specific use pattern. One 
important thing to note is that, assuming the binary-search 
specialization is documented, the user can use 
`SortedRange.release` to explicitly request linear search.

Myself and others have sometimes mistakenly expected `find` and 
friends to be specialized for `SortedRange` inputs, 
opportunistically providing better worst-case complexity, but 
this is not the case. It seems simple at first glance, but the 
problem lies in the predicate - binary search can only be 
leveraged when the specific order is known:

---
auto data = assumeSorted([1, 2, 3]);

// Equality, so bsearch then trot left
auto result = data.find!((x, e) => x == e)(2); // default 
predicate
assert(result.equal([2, 3]));

// Opposite order and exclusive, bsearch then trot right
result = data.find!((x, e) => x > e)(2);
assert(result.equal([3]));

// Same order, bsearch then trot left.
// Compare first element as an optimization?
result = data.find!((x, e) => x < e)(0);
assert(result.empty);

struct S { string name; }
auto data2 = assumeSorted!((a, b) => a.name < b.name)(
     [S("a"), S("b"), S("c")]
);

// Same order and exclusive, but with a transformation, yikes...
auto result2 = data2.find!((x, e) => x.name < e.name)(S("b"));
assert(result2.equal(data2));
---

Identifying the characteristics described in the code comments 
above is the biggest problem: predicate functions don't have any 
notion of equality.

String lambdas can be compared for equality, but they're really 
fragile: "a == b" != "b == a" etc. Besides, string lambdas are 
undesirable for other reasons and should be phased out in the 
long-term[1].

Someone suggested defining a standard set of predicates, making 
it look like this:

---
auto data = assumeSorted!less([1, 2, 3]); // Would be default

// Equality, so bsearch then trot left
auto result = data.find!equality(2); // Would be default
---

Templates can be compared with __traits(isSame, ...), so this 
approach seems feasible. If we want to do this, this seems like 
the most realistic approach. I'm not sure if it can be made to 
work when transformation of arguments is involved, but it might 
still be worth doing.

Another issue is that SortedRange's interface does not actually 
support all the above patterns because it splits the result into 
3 instead of 2; we would need to amend SortedRange to support the 
inverse functions of lowerBound and upperBound.

So, what does the community think? Desirable, or not? Thoughts 
about implementation?

[1] 
http://forum.dlang.org/post/jnlqesrwxfekdsxjerlp forum.dlang.org
Jul 23 2014
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Thursday, 24 July 2014 at 01:21:44 UTC, Jakob Ovrum wrote:

 -snip-


Another point is that the range types of the two currently 
available sorted containers - RedBlackTree and BinaryHeap - are 
*not* instances of SortedRange. If algorithms working on sorted 
ranges become a thing, it seems like they should be.
Jul 23 2014
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, 24 July 2014 at 01:26:48 UTC, Jakob Ovrum wrote:

 On Thursday, 24 July 2014 at 01:21:44 UTC, Jakob Ovrum wrote:

 -snip-


 Another point is that the range types of the two currently 
 available sorted containers - RedBlackTree and BinaryHeap - are 
 *not* instances of SortedRange. If algorithms working on sorted 
 ranges become a thing, it seems like they should be.


Maybe a better approach would be do just have sorted range types 
define find themselves? UFCS would then make it so that the best 
search function for that type would be used (e.g. I don't think 
that binary search is the best method to use a red-black tree).

However, regardless of that, it could be useful to know whether a 
range is sorted or not in general, and we may want to change how 
we do that so that there's an enum which indicates it rather than 
simply wrapping it in SortedRange (e.g. we know that 
RedBlackTree's range type is sorted, but I doubt that we want to 
always be wrapping it in a SortedRange to show that).

- Jonathan M Davis
Jul 24 2014
parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Thursday, 24 July 2014 at 21:08:58 UTC, Jonathan M Davis wrote:

 On Thursday, 24 July 2014 at 01:26:48 UTC, Jakob Ovrum wrote:

 On Thursday, 24 July 2014 at 01:21:44 UTC, Jakob Ovrum wrote:

 -snip-


 Another point is that the range types of the two currently 
 available sorted containers - RedBlackTree and BinaryHeap - 
 are *not* instances of SortedRange. If algorithms working on 
 sorted ranges become a thing, it seems like they should be.


 Maybe a better approach would be do just have sorted range 
 types define find themselves? UFCS would then make it so that 
 the best search function for that type would be used (e.g. I 
 don't think that binary search is the best method to use a 
 red-black tree).


Right, the two tree structures can't be searched properly using a 
generic binary search algorithm.

I don't think having containers define `find` as a member is 
really feasible. `find` is a highly generic function with a 
multitude of forms, and to be interchangeable, every container 
would have to support all these forms. That sounds extremely 
impractical.


 However, regardless of that, it could be useful to know whether 
 a range is sorted or not in general, and we may want to change 
 how we do that so that there's an enum which indicates it 
 rather than simply wrapping it in SortedRange (e.g. we know 
 that RedBlackTree's range type is sorted, but I doubt that we 
 want to always be wrapping it in a SortedRange to show that).

 - Jonathan M Davis


The container could simply make its Range type an alias to 
SortedRange!(RangeImpl, pred). It wouldn't cost anything. But, of 
course, as you pointed out, it's not possible for the tree 
structures, at least not without changing something in 
SortedRange.

Maybe SortedRange's search functions should defer to the 
underlying range if the underlying range supports logarithmic 
search, such as by defining `lowerBound` et al. as members of the 
range type. This would cause some duplication of course, as 
currently, `lowerBound` et al. are container primitives. However, 
wouldn't it be the right place for them?

Currently, using `SortedRange`, we can do binary search on a 
*subset* of the original range, as its search functions in turn 
return sorted ranges:

---
auto data = [1, 2, 3, 4, 5].assumeSorted();

auto lower = data.lowerBound(5);
auto target = lower.upperBound(1); // Narrower search area!

assert(target.equal([2, 3, 4]));
---

In the current container model, where they are primitives of the 
container and not the container's range, this is not possible.
Jul 26 2014
prev sibling parent "Xinok" <xinok live.com> writes:
On Thursday, 24 July 2014 at 01:26:48 UTC, Jakob Ovrum wrote:

 On Thursday, 24 July 2014 at 01:21:44 UTC, Jakob Ovrum wrote:

 -snip-


 Another point is that the range types of the two currently 
 available sorted containers - RedBlackTree and BinaryHeap - are 
 *not* instances of SortedRange. If algorithms working on sorted 
 ranges become a thing, it seems like they should be.


Just to clarify, BinaryHeap is heapified but not sorted, so it 
would be impossible to do a binary search on it. It's only an 
InputRange so, at best, you could do a linear search on it.
Jul 27 2014