Re: binary search
On Monday, 7 December 2020 at 06:24:27 UTC, drug wrote: Phobos provides this by SortedRange: https://dlang.org/phobos/std_range.html#.SortedRange Example of usage: https://run.dlang.io/is/WW2bn0 Thanks! :-)
Re: binary search
Phobos provides this by SortedRange: https://dlang.org/phobos/std_range.html#.SortedRange Example of usage: https://run.dlang.io/is/WW2bn0
binary search
We have: // sorted values size_t lines = [20, 1755, 1756, 1757, 1798, 1824, 1825, 1839, 1840]; size_t search = 21; Goal: // Fast find index of the '21' in ordered array 'lines' auto found = lines.binarySearch( 20 ); // 0 - index auto low = lines.binarySearchLow( 21 ); // 0 - near lowest index Where is the implementation of "binary search", please?
Re: Searching string for character in binary search
On Sunday, 25 February 2018 at 21:18:55 UTC, Joel wrote: The number tests work, but not the string one. Thanks guys. I worked it out, I thought my search code was right, since the first asserts worked.
Re: Searching string for character in binary search
On 2/25/18 4:32 PM, Seb wrote:
Also note that Phobos comes with binary search built-in:
---
assert([1,2,3,4,5,6,7,8,9,10,11].assumeSorted.canFind(6));
---
https://run.dlang.io/is/bfpBpA
canFind (and find) works even on non-sorted ranges, so it's not the
greatest proof. But it's good to know that it does work and uses a
binary search!
You can see that it only does a few comparisons with something like:
https://run.dlang.io/is/lax6YP
Also, strings are not doing what you think:
"abcd".find('c'); // OK, linear search
"abcd".assumeSorted.find('c'); // Error
"abcd".assumeSorted.find("c"); // OK, but does NOT do a binary search!
[1,2,3,4].assumeSorted.find([3]); // OK, but also does not do a binary
search!
My knee-jerk reaction is to blame auto-decoding ;) But maybe it's just a
bug.
If you want to guarantee a binary search (i.e. compiler error when it
cannot do it), you need to use SortedRange.lowerBound.
-Steve
Re: Searching string for character in binary search
On Sunday, 25 February 2018 at 21:18:55 UTC, Joel wrote:
The number tests work, but not the string one.
void main() {
assert([1,2,3,4,5,6,7,8,9,10,11].binarySearch(6));
assert(! [1,2,3,4,5,7,8,9,10,11].binarySearch(6));
assert("abcdefghijklmnopqrstuvwxyz".binarySearch('j')); // not
work
import std.stdio;
writeln("Assert tests passed!");
}
bool binarySearch(T)(T[] arr, T n) {
while(arr.length) {
auto i = arr.length/2;
if (arr[i] == n)
return true;
else
if (arr[i] > n)
arr = arr[i + 1 .. $];
else
arr = arr[0 .. i];
}
return false;
}
Your cases are wrong:
---
if (arr[i] > n) // 'n' > 'j'
// The current element is higher than the needle -> you need to
go to the left, not right
--
-> Swap them.
Also note that Phobos comes with binary search built-in:
---
assert([1,2,3,4,5,6,7,8,9,10,11].assumeSorted.canFind(6));
---
https://run.dlang.io/is/bfpBpA
Re: Searching string for character in binary search
On 02/25/2018 10:18 PM, Joel wrote: if (arr[i] > n) arr = arr[i + 1 .. $]; When `arr[i]` is greater than `n`, then the values in `arr[i + 1 .. $]` will only be even greater. You're picking the wrong half of the array.
Searching string for character in binary search
The number tests work, but not the string one.
void main() {
assert([1,2,3,4,5,6,7,8,9,10,11].binarySearch(6));
assert(! [1,2,3,4,5,7,8,9,10,11].binarySearch(6));
assert("abcdefghijklmnopqrstuvwxyz".binarySearch('j')); // not
work
import std.stdio;
writeln("Assert tests passed!");
}
bool binarySearch(T)(T[] arr, T n) {
while(arr.length) {
auto i = arr.length/2;
if (arr[i] == n)
return true;
else
if (arr[i] > n)
arr = arr[i + 1 .. $];
else
arr = arr[0 .. i];
}
return false;
}
Re: Templated Binary Search Tree treats class as const, compiler complains
On Sunday, 21 January 2018 at 20:46:56 UTC, Timon Gehr wrote: On 21.01.2018 21:20, Mark wrote: Just realized that I commented out the creation of the BST new link: https://dpaste.dzfl.pl/ce620cbee919 'in' means 'const scope', but it seems you need references that are allowed to mutate the incoming items. Remove the 'in' attribute from the parameters and your problem should disappear. Ok, I was looking at the wrong stuff. Looking at varidiac functions in the book, I'm seeing what you're saying. I thought that was used as a keyword for variadic arguments. Thanks, that worked perfectly! Mark.
Re: Templated Binary Search Tree treats class as const, compiler complains
On 21.01.2018 21:20, Mark wrote: Just realized that I commented out the creation of the BST new link: https://dpaste.dzfl.pl/ce620cbee919 'in' means 'const scope', but it seems you need references that are allowed to mutate the incoming items. Remove the 'in' attribute from the parameters and your problem should disappear.
Re: Templated Binary Search Tree treats class as const, compiler complains
Just realized that I commented out the creation of the BST new link: https://dpaste.dzfl.pl/ce620cbee919
Templated Binary Search Tree treats class as const, compiler complains
Hello, I re wrote my old BST. This one is far more complete and clean. However, It fails my final unittest when I try to stick a class in as its type. Link: https://dpaste.dzfl.pl/95e1ae49b25b Ive done this type of thing before, but it is giving me this error: BinarySearchTree.d(30): Error: function BinarySearchTree.BinarySearchTree!(Empty).BinarySearchTree.New (Empty item) is not callable using argument types (const(Empty)) BinarySearchTree.d(40): Error: function BinarySearchTree.BinarySearchTree!(Empty).BinarySearchTree.New (Empty item) is not callable using argument types (const(Empty)) BinarySearchTree.d(574): Error: template instance BinarySearchTree.BinarySearchTree!(Empty) error instantiating the New method is on line 94; I was looking through the Programming in D book, and can't find what this is really telling me. I have templated Stack and queue classes that don't give me these errors?? How do I make the BST accept classes like the one in my test? I don't deal with const stuff, so I'm not too sure what to look for concerning these problems. I'm still looking in the book/site for answers. Thanks!
Binary search
Is there no way to do a simple binary search of a sorted array using Phobos? I found `SortedRange.contains`, but that just returns true/false. I want the index of the element, or the element itself. I also found `SortedRange.equalRange`, but that sounds like it has an unreasonable amount of (admittedly O(1)) overhead for the (extremely common) case in which I am looking for only a single element, not a range.
Re: Binary search
On Tuesday, 15 December 2015 at 00:22:37 UTC, tsbockman wrote: I also found `SortedRange.equalRange`, but that sounds like it has an unreasonable amount of (admittedly O(1)) overhead for the (extremely common) case in which I am looking for only a single element, not a range. If your array doesn't contain duplicates, the overhead is just one extra comparison. For cheap comparisons, this overhead will be completely dwarfed by the actual search (assuming your array is big enough to justify binary search over linear search). If your array contains duplicates but you are only interested in getting any one of them, or your comparison is non-trivial, then I agree this could potentially be a problem. For sorted arrays you won't find any other standard facility for doing binary search, but the containers RedBlackTree and BinaryHeap provide something related.
Re: Binary search
On Tuesday, 15 December 2015 at 00:31:45 UTC, Jakob Ovrum wrote: On Tuesday, 15 December 2015 at 00:22:37 UTC, tsbockman wrote: I also found `SortedRange.equalRange`, but that sounds like it has an unreasonable amount of (admittedly O(1)) overhead for the (extremely common) case in which I am looking for only a single element, not a range. If your array doesn't contain duplicates, the overhead is just one extra comparison. Actually, it's two I think - `equalRange` calls both `upperBound` and `lowerBound` after the main search. For cheap comparisons, this overhead will be completely dwarfed by the actual search (assuming your array is big enough to justify binary search over linear search). If your array contains duplicates but you are only interested in getting any one of them, or your comparison is non-trivial, then I agree this could potentially be a problem. I think there are cases where the difference would be meaningful, although I agree that most of the time it wouldn't be noticeable. For sorted arrays you won't find any other standard facility for doing binary search, but the containers RedBlackTree and BinaryHeap provide something related. You could also get the upper bound (SortedRange.upperBound) and calculate the index from its length. If I'm thinking straight, this might result in fewer comparisons for some patterns. OK. Thanks for the advice.
Re: Binary search
On Tuesday, 15 December 2015 at 00:31:45 UTC, Jakob Ovrum wrote: For sorted arrays you won't find any other standard facility for doing binary search, but the containers RedBlackTree and BinaryHeap provide something related. You could also get the upper bound (SortedRange.upperBound) and calculate the index from its length. If I'm thinking straight, this might result in fewer comparisons for some patterns.
Re: Binary search in structs
I think I found solution using opBinaryRight
import std.range;
struct S
{
int i;
string s;
int opCmp(int i) {
return this.i - i;
}
int opCmp(ref const S s) {
return this.i - s.i;
}
int opBinaryRight(string op)(int i) if (op == ) {
return i - this.i;
}
}
void main(string [] args)
{
S[] structs = [{1,hello}, {2,world}, {3, !}]; //sorted
by i
auto sortedRange = assumeSorted(structs);
auto t = sortedRange.trisect(2);
}
Binary search in structs
I have array of structs sorted by specific field. How can I
perform binary search using this field as a key?
Currently I ended up with this, but it gives error:
struct S
{
int i;
string s;
}
import std.range;
void main(string [] args)
{
S[] structs = [{1,hello}, {2,world}, {3, !}]; //sorted
by i
auto sortedRange = assumeSorted!(function bool(ref const S
item, int needle) {
return item.i needle;
})(structs);
sortedRange.trisect(2); //compilation error
}
Re: Binary search in structs
On Sunday, 5 April 2015 at 23:06:27 UTC, FreeSlave wrote:
I have array of structs sorted by specific field. How can I
perform binary search using this field as a key?
Currently I ended up with this, but it gives error:
struct S
{
int i;
string s;
}
import std.range;
void main(string [] args)
{
S[] structs = [{1,hello}, {2,world}, {3, !}];
//sorted by i
auto sortedRange = assumeSorted!(function bool(ref const S
item, int needle) {
return item.i needle;
})(structs);
sortedRange.trisect(2); //compilation error
}
I believe you have to pass trisect a value of S. So S(2, )
would do here, I suppose.
Re: Binary search in structs
On Sunday, 5 April 2015 at 23:15:04 UTC, w0rp wrote:
On Sunday, 5 April 2015 at 23:06:27 UTC, FreeSlave wrote:
I have array of structs sorted by specific field. How can I
perform binary search using this field as a key?
Currently I ended up with this, but it gives error:
struct S
{
int i;
string s;
}
import std.range;
void main(string [] args)
{
S[] structs = [{1,hello}, {2,world}, {3, !}];
//sorted by i
auto sortedRange = assumeSorted!(function bool(ref const S
item, int needle) {
return item.i needle;
})(structs);
sortedRange.trisect(2); //compilation error
}
I believe you have to pass trisect a value of S. So S(2, )
would do here, I suppose.
Of course I could pass dummy object, but this is ugly solution. I
hoped there's some better one.
