Looking for something similar to Python's bisect_right
Zeke
lcarsos at lcarsos.com
Tue Oct 29 23:04:25 PDT 2013
Hello, I'm on day 2 of learning D. I've learned C, C++, Java,
Python, Ruby in University, but I wanted to broaden my palette by
picking up D.
This project is a basic implementation of Project Euler problem
10. I build an array of primes, and for each new test number I
check if the test is divisible by any prime from 2 to sqrt(test)
(which cuts down on number of iterations). Trouble is, I can't
find a method that's in the libraries to calculate the index of
where sqrt(test) would exist or would be inserted into a sorted
array.
I tried casting the primes array to a SortedRange using
assumeSorted() but it didn't work for me. countUntil() returns -1
if the value doesn't exist. and I didn't find anything in the
std.algorithm, std.array, or std.container.
Here's my current working implementation of is_prime and the
functions it uses:
pure nothrow @safe bool is_prime(in ulong[] primes, ulong num) {
// Need to find a more elegant way to find the index of where
a number's
// square root would be in a sorted array.
auto upper = insind(primes, cast(ulong)sqrt(cast(double)num))
+ 1;
// Check each prime in the array up to the square root of our
current test
// number to see if it is prime.
foreach(ulong prime; primes[0..upper]) {
if (num % prime == 0) {
return false;
}
}
return true;
}
/**
* Friendly overload so I don't have to give the bounds of the
array for the
* recursive step.
*/
pure nothrow @safe ulong
insind(in ulong[] arr, ulong key)
{
return insind(arr, key, 0, arr.length);
}
/**
* Using tail-recursion (so we don't build up a huge call stack),
binary search
* the array for the index where the key would be found if it
existed or were
* to be inserted into the array.
*/
pure nothrow @safe ulong
insind(in ulong[] arr, ulong key, ulong lower, ulong upper)
{
if (lower >= upper) {
return lower;
} else {
ulong mid = (lower + upper) / 2;
if (arr[mid] > key) {
return insind(arr, key, lower, mid - 1);
} else if (arr[mid] < key) {
return insind(arr, key, mid + 1, upper);
} else {
return mid;
}
}
}
I would also appreciate tips to help my "D-ness" coding style
develop.
More information about the Digitalmars-d-learn
mailing list