Printable View
Hello,
I have a table like:
index value
-------------
64 and more x1
32 to 63 x2
16 to 31 x3
8 to 15 x4
1 to 7 x5
Now we store , the index, values, 1, 8, 16, 32, 64 in a vector A.
and x1, to x5 in another vector B.
I need to write a function (efficint, may be use cache)
to get value, for the particular index.
thankyou very much for the inputs
pdk
Sorry, but I'm not understanding. Perhaps you could provide an example of A and B and what is expected from the function.
Thankyou very much kaud.
Sorry for delay
vector A = {1,8,16,32,64}
vector B={ x5, x4, x3,x2,x1}
The function needs to check,
- if the passed index , falls to 64 and above , Return value "x1"
- if the passed index is from 32 to 63 , Return " x2"
Is something like this what you are after? I'm not sure what type x1 - x5 are so I've just made them literals.
Code:#include <iostream>
#include <vector>
#include <iterator>
int main() {
const std::vector A { 1, 8, 16, 32, 64 };
const std::vector B { "x5", "x4", "x3", "x2", "x1" };
for (int i {1}; i > 0; ) {
std::cin >> i;
for (auto it { A.rbegin() }; it != A.rend(); ++it)
if (i - *it >= 0) {
std::cout << B[std::distance(A.begin(), it.base()) - 1] << '\n';
break;
}
}
}
Code:66
x1
32
x2
63
x2
1
x5
7
x5
8
x4
17
x3
16
x3
100
x1
Thankyou very much kaud.
Yes, I needed exactly same logic.
x1, x2, etc are "double" type.
if we put them in a function to pass the index and the double type as output
double GetValue(int index)
{
}
If we keep calling the same function, several times (with consecutive calls having same index).. is there anyway to cache the old value, so to avoid the search again ?
I never written cache, but there is suggestion that cache is helpful...
This does not use cache, but one way is to use local static variables
in the function. They are initialized once and remembered between
function calls.
Code:double GetValue(int index)
{
static int index_last = -1; // must be an index that is not possible
static double value = 0.0f;
if (index == index_last)
{
//cout << "using last call\n";
return value;
}
//cout << "calculating\n";
static const std::vector<int> A{ 1, 8, 16, 32, 64 };
static const std::vector<double> B{ 5.0, 15.0, 6.0, 19.0, 33.0 };
// code to find the value in "B" based on "index"
// this does not verify if "index" is in the A array
for (int i = 0; i < (int)A.size(); ++i)
{
if (index == A[i])
{
index_last = index;
value = B[i];
break;
}
}
return value;
}
Thankyou very much for the idea Philip.
@kaud : thankyou very much. Is there any other ways to do this, using predicate may be. Also was wondering, if binary search can be used ?
What are the sizes of A and B?
If they are just values from 1 to 64 even in production, then a simple table lookup using an array of size 64 with each element the required x value. If the given value is > 64 then return the last value.
Thankyou very much kaud.
As of now, the A and B, contain just 1 to 64. It may change in future, so its ok as of now.
Then just do it as a simple lookup-table. You don't need A - just B with 64 elements.
x5, x5, x5, x5, x5, x5, x5, x4, x4, x4, x4, x4, x4, x4 ,x4.....
etc. Then just check that index is within range and if is use an index into B. If out of range then return x1.
PS make B std::array as static constexpr within GetValue() (you can't have a constexpr std::vector):
Code:double GetValue(unsigned i) {
static constexpr double x1 { 1 }, x2 { 2 }, x3 { 3 }, x4 { 4 }, x5 { 5 };
static constexpr std::array B { x5, x5, x5, x5, x5, x5, x5, x4, x4, x4, x4, x4, x4, x4, x3/* .....*/}; // required 64 elements
if (i > B.size())
return x1;
// what if i == 0 ??
return B[i - 1];
}
It is possible to use 2kaud's approach (in #8) but in a way that reduces the size of B. That can be useful if A grows in the future but still holds numbers that are all powers of 2. The idea is to use the new (C++ 20) bit-manipulation function std::bit_width to turn the members of A into index positions in B. Your example would look something like thisQuote:
Originally Posted by pdk5
The std::bit_width function should be pretty cheap. It is based on the lzcnt (leading zero count) instruction which is supported by many processors.Code:const std::vector<int> A { 1, 2, 4, 8, 16, 32, 64 }; // 2 and 4 added
const std::vector<double> B { x5, x5, x5, x4, x3, x2, x1 }; // two x5 added
double GetValue(int index) {
// First sanity check all ranges, then
return B[std::bit_width(A[index])];
}
std::bit_width() requires an unsigned type for argument.
"This overload participates in overload resolution only if T is an unsigned integer type (that is, unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long, or an extended unsigned integer type). "
https://en.cppreference.com/w/cpp/numeric/bit_width
Use std::array rather than std::vector so that constexpr can be used for compile-time initialisation.
There's no need for A. B can be accessed direct using index. Consider:
Code:include <iostream>
#include <array>
#include <bit>
#include <algorithm>
auto GetValue(unsigned index) {
static constexpr double x1 { 1 }, x2 { 2 }, x3 { 3 }, x4 { 4 }, x5 { 5 };
static constexpr std::array B { x5, x5, x5, x4, x3, x2, x1 }; // two x5 added
// index == 0 ???
return B[std::min<unsigned>(B.size(), std::bit_width(index)) - 1];
}
int main() {
for (unsigned i {}; (std::cin >> i) && i > 0;)
std::cout << GetValue(i) << '\n';
}
Well, I should have tested my code but it was intended more as an illustration for a suggestion. Anyway, the GetValue function can be declared constexpr and noexcept to make it even better.Quote:
Originally Posted by 2kaud