Sliding Window Aggregation

data_structure/sliding_window_aggregation.hpp · GitHub で見る

共通ページ

末尾への追加・先頭の削除ができるキューです。キュー全体を順番どおりに集約した値を取得できます。非可換な演算にも対応します。

#include "lib/data_structure/sliding_window_aggregation.hpp"
#include <string>

std::string op(std::string a, std::string b) { return a + b; }
std::string e() { return ""; }

SlidingWindowAggregation<std::string, op, e> queue;
queue.push_back("ab");
queue.push_back("cd");
auto a = queue.prod(); // "abcd"
queue.pop_front();
auto b = queue.front(); // "cd"

操作	内容・返り値	計算量
SlidingWindowAggregation<S,op,e>()	空のキューを作成	\(O(1)\)
SlidingWindowAggregation(values)	vector<S> から順番に追加	\(O(n)\)
push_back(value)	末尾に追加	償却 \(O(1)\)
pop_front()	先頭を削除	償却 \(O(1)\)、最悪 \(O(n)\)
front() / back()	先頭／末尾の値の const S&	\(O(1)\)
prod()	先頭から末尾まで集約。空なら e()	\(O(1)\)
apply(value, mapping)	mapping(S,T) を使い、集約を値 value に作用させた T を返す	\(O(1)\)
apply(value)	S が関数として呼べるとき、集約を value に作用させた T を返す	\(O(1)\)
size() / empty()	要素数／空判定	\(O(1)\)
reserve(n)	領域を確保	\(O(n)\)
clear()	全要素を削除	\(O(n)\)
swap(other)	内容を交換	\(O(1)\)

op(S,S) は結合的な演算、e() はその単位元です。S はコピー・移動できる型を使います。演算の引数は変更しないでください。front・back・pop_front はキューが空でないときに使います。取得操作は const オブジェクトから呼べます。

apply(value, mapping) は mapping(op(f, g), x) == mapping(g, mapping(f, x)) と mapping(e(), x) == x を満たす作用に使います。引数 value の型を T とし、mapping は S と T を受け取って T に代入できる値を返します。空のキューでは value をそのまま返します。apply(value) は mapping(f, x) = f(x) とした呼び出しで、同じ順序の条件を満たす関数合成に使えます。どちらも const オブジェクトから呼べます。

#include "lib/data_structure/sliding_window_aggregation.hpp"
#include <utility>

using Function = std::pair<long long, long long>;
Function compose(Function f, Function g) {
	return {g.first * f.first, g.first * f.second + g.second};
}
Function identity() { return {1, 0}; }

SlidingWindowAggregation<Function, compose, identity> functions;
functions.push_back({2, 1});
functions.push_back({3, 4});
auto value = functions.apply(5LL, [](Function f, long long x) {
	return f.first * x + f.second;
}); // 37

作用にかかる時間を定数とすると、apply は \(O(1)\) 時間です。整数型の演算結果はその型の範囲に収まるようにしてください。

コピーは独立したキューを作り、移動元は再利用できる空のキューになります。参照は更新後に取得し直してください。size_type は std::size_t です。

要素のコピーと演算を定数時間としたとき、追加・削除は償却 \(O(1)\)、集約は \(O(1)\) 時間です。確保した領域を \(C\) として使用空間は \(O(C)\)、コピーは \(O(n)\) 時間です。文字列結合のように演算自体に時間がかかる場合は、その費用が加わります。

検証コード

• test/sliding_window_aggregation.test.cpp

コード

#ifndef SLIDING_WINDOW_AGGREGATION_HPP
#define SLIDING_WINDOW_AGGREGATION_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <utility>
#include <vector>

template<class S, auto op, auto e>
class SlidingWindowAggregation {
	struct Entry {
		S value, product;
		Entry(S value, S product) : value(std::move(value)), product(std::move(product)) {}
	};
	static constexpr bool inplace = std::is_trivially_destructible_v<S> && std::is_nothrow_move_constructible_v<S> && std::is_nothrow_copy_assignable_v<S> && std::is_nothrow_move_assignable_v<S>;
	std::vector<Entry> left, right;
	std::size_t first = 0, middle = 0;
	[[gnu::noinline]] void transfer_inplace() {
		S saved = right.back().product;
		try {
			if (right.size() - first > 1) {
				right.back().product = right.back().value;
				for (std::size_t i = right.size() - 1; i > first + 1;) {
					--i;
					right[i].product = op(right[i].value, right[i + 1].product);
				}
			}
		} catch (...) {
			right.back().product = std::move(saved);
			throw;
		}
		middle = right.size();
	}
	void transfer() {
		left.reserve(right.size());
		try {
			for (auto it = right.rbegin(); it != right.rend(); ++it) {
				S product = left.empty() ? it->value : op(it->value, left.back().product);
				left.emplace_back(it->value, std::move(product));
			}
		} catch (...) {
			left.clear();
			throw;
		}
		right.clear();
	}
public:
	using value_type = S;
	using size_type = std::size_t;
	SlidingWindowAggregation() = default;
	explicit SlidingWindowAggregation(const std::vector<S> &values) { reserve(values.size()); for (const auto &x : values) push_back(x); }
	SlidingWindowAggregation(const SlidingWindowAggregation &other) {
		if constexpr (inplace) {
			right.reserve(other.size());
			for (std::size_t i = other.first; i < other.right.size(); ++i) right.push_back(other.right[i]);
			middle = other.middle - other.first;
		} else left = other.left, right = other.right;
	}
	SlidingWindowAggregation(SlidingWindowAggregation &&other) noexcept { swap(other); }
	SlidingWindowAggregation &operator=(SlidingWindowAggregation other) noexcept { swap(other); return *this; }
	bool empty() const {
		if constexpr (inplace) return first == right.size();
		else return left.empty() && right.empty();
	}
	size_type size() const {
		if constexpr (inplace) return right.size() - first;
		else return left.size() + right.size();
	}
	void push_back(S value) {
		bool fresh;
		if constexpr (inplace) fresh = middle == right.size();
		else fresh = right.empty();
		S product = fresh ? value : op(right.back().product, value);
		if constexpr (inplace) {
			if (first && right.size() == right.capacity() && first >= right.size() / 2) {
				std::move(right.begin() + first, right.end(), right.begin());
				const auto length = right.size() - first;
				while (right.size() > length) right.pop_back();
				middle -= first;
				first = 0;
			}
		}
		right.emplace_back(std::move(value), std::move(product));
	}
	void pop_front() {
		assert(!empty());
		if constexpr (inplace) {
			if (first == middle) transfer_inplace();
			if (++first == right.size()) clear();
		} else {
			if (left.empty()) transfer();
			left.pop_back();
		}
	}
	const S &front() const {
		assert(!empty());
		if constexpr (inplace) return right[first].value;
		else return left.empty() ? right.front().value : left.back().value;
	}
	const S &back() const {
		assert(!empty());
		if constexpr (inplace) return right.back().value;
		else return right.empty() ? left.front().value : right.back().value;
	}
	S prod() const {
		if constexpr (inplace) {
			if (first == middle) return empty() ? e() : right.back().product;
			return middle == right.size() ? right[first].product : op(right[first].product, right.back().product);
		} else {
			if (left.empty()) return right.empty() ? e() : right.back().product;
			return right.empty() ? left.back().product : op(left.back().product, right.back().product);
		}
	}
	template<class T, class Mapping>
	T apply(T value, Mapping mapping) const {
		if constexpr (inplace) {
			if (first < middle) value = mapping(right[first].product, std::move(value));
			if (middle < right.size()) value = mapping(right.back().product, std::move(value));
		} else {
			if (!left.empty()) value = mapping(left.back().product, std::move(value));
			if (!right.empty()) value = mapping(right.back().product, std::move(value));
		}
		return value;
	}
	template<class T>
	T apply(T value) const {
		return apply(std::move(value), [](const S &f, T x) { return f(std::move(x)); });
	}
	void reserve(size_type n) { if constexpr (!inplace) left.reserve(n); right.reserve(n); }
	void clear() { left.clear(); right.clear(); first = middle = 0; }
	void swap(SlidingWindowAggregation &other) noexcept { left.swap(other.left); right.swap(other.right); std::swap(first, other.first); std::swap(middle, other.middle); }
	friend void swap(SlidingWindowAggregation &a, SlidingWindowAggregation &b) noexcept { a.swap(b); }
};

#endif

Back to top page