dwavesystems / dwavesystems/dwave-optimization
Make `MeanNode` a variety of `ReduceNode`
- Dominant language
- C++
- Stars
- 31
- Forks
- 36
- Avg merge
- 16h 55m
- Merged PRs (30d)
- 8
Description
We're pretty close to being able to make `MeanNode` a special case of `ReduceNode`. You can define a ufunc like
```c++
template< DType T>
struct Mean : BinaryFunctionMixin> {
/// @copydoc Add::result_type
using result_type = std::conditional, double, T>::type;
// we use the same convention as NumPy
/// @copydoc Add::reduction_type
class reduction_type {
public:
reduction_type() = delete;
reduction_type(T value) noexcept : sum_(value), count_(1) {}
bool operator==(const result_type& rhs) const {
return static_cast(*this) == rhs;
}
bool operator==(const reduction_type& rhs) const {
return sum_ == rhs.sum_ and count_ == rhs.count_;
}
explicit operator result_type() const noexcept { return sum_ / count_; }
private:
friend Mean;
result_type sum_; // could use Kahan summation here if we wanted
ssize_t count_;
};
/// @brief Return the average of `lhs` and `rhs`.
/// @copydetails Add::operator()
result_type operator()(const DType auto& lhs, const DType auto& rhs) const noexcept {
return (lhs + rhs) / 2;
}
reduction_type operator()(reduction_type lhs, const DType auto& rhs) const noexcept {
lhs.sum_ += rhs;
lhs.count_ += 1;
return lhs;
}
/// @brief Revert an average.
/// @copydetails Add::inverse()
static std::optional inverse(const DType auto& lhs, const DType auto& rhs) noexcept {
return 2 * lhs - rhs;
}
static std::optional inverse(reduction_type lhs, const DType auto& rhs) noexcept {
lhs.sum_ -= rhs;
lhs.count_ -= 1;
return lhs;
}
static ValuesInfo result_bounds(ValuesInfo lhs, ValuesInfo rhs) {
return ValuesInfo((lhs.max + rhs.max) / 2, (lhs.min + rhs.min) / 2, false);
}
static ValuesInfo result_bounds(ValuesInfo bounds, ssize_t) { return bounds; }
static ValuesInfo result_bounds(ValuesInfo bounds, limit_type) { return bounds; }
static constexpr bool associative = false;
static constexpr bool commutative = true;
static constexpr bool invertible = true;
};
```
the hitch is around the definition of `associative`. It works in the reduction case, but not for the bounds calculation. Needs more thought.
Contributor guide
Research direction
Start by tracing the MeanNode and ReduceNode definitions and how their reduction and bounds calculations use the associative property. Determine a consistent treatment of associativity for both paths; done means MeanNode can be represented as a ReduceNode without incorrect bounds behavior, with the relevant tests passing.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100