dwavesystems / dwavesystems/dwave-optimization

Make `MeanNode` a variety of `ReduceNode`

Open
#579 2 comments 0 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.