在输入向量的笛卡尔积中创建第 n 个元素的元组
create tuple of nth element in the cartesian product of input vectors
我有一个 python 函数,它 returns 多个输入数组的笛卡尔积中的第 n 个元素
def prod(n, arrs):
out = []
for i,arr in enumerate(arrs):
denom = numpy.prod([ len(p) for p in arrs[i+1:] ], dtype=int)
idx = n // denom % len(arr)
out.append( arr[idx] )
return out
效果很好:
a = [ 1000, 1100, 1200, 1300, 1400 ]
b = [ 1.0, 1.5, 2.0, 2.5, 3.0, 3.5 ]
c = [ -2, -1, 0, 1, 2 ]
for n in range(20, 30):
i = prod(n, [a, b, c])
print(n, i)
[1000, 3.0, -2]
[1000, 3.0, -1]
[1000, 3.0, 0]
[1000, 3.0, 1]
[1000, 3.0, 2]
[1000, 3.5, -2]
[1000, 3.5, -1]
[1000, 3.5, 0]
[1000, 3.5, 1]
[1000, 3.5, 2]
现在我想将其翻译成 C++(最大标准 C++-17)
template<typename... Ts>
auto prod(std::size_t n, const std::vector<Ts>&... vs)
-> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
// template magic here
}
有人可以帮助我使用上述公式构造元组所需的模板魔法吗?
首先,为了简单起见,让我们自动推断函数的 return 类型。
接下来,索引序列是整齐的。有了他们,就可以做到。
使用 C++20,我们可以从 lambda 中的序列中获取索引。在此之前,我们需要一个额外的功能。
最后,我们必须从头开始创建索引,要么存储索引然后以相反的顺序使用它们,要么反转生成的元组。
template <class T, std::size_t... Ns>
static auto prod_impl(std::size_t n, T tuple, std::index_sequence<Ns...>) {
auto f = [&](auto N){ auto r = n % N; n /= N; return r; };
auto x = std::forward_as_tuple(std::get<(sizeof...(Ns)) - Ns - 1>(tuple)[f(std::get<(sizeof...(Ns)) - Ns - 1>(tuple).size())]...);
return std::forward_as_tuple(std::get<(sizeof...(Ns)) - Ns - 1>(x)...);
}
template<class... Ts>
auto prod(std::size_t n, const std::vector<Ts>&... vs) {
return prod_impl(n, std::forward_as_tuple(vs...), std::make_index_sequence<sizeof...(vs)>());
}
使用索引数组的内部函数的更简单替代方法:
template <class T, std::size_t... Ns>
static auto prod_impl(std::size_t n, T tuple, std::index_sequence<Ns...>) {
auto f = [&](auto N){ auto r = n % N; n /= N; return r; };
std::size_t Is[] = { f(std::get<sizeof...(Ns) - Ns - 1>(tuple).size())... , 0};
return std::forward_as_tuple(std::get<Ns>(tuple)[sizeof...(Ns) - Ns - 1]...);
}
我们可以使用 来获取与不同向量关联的索引。
这为我们提供了以下 C++14 解决方案:
#include <tuple>
#include <vector>
#include <cstdlib>
using std::array;
using std::size_t;
template <size_t NDim>
constexpr array<size_t, NDim> delinearize_coordinates(
size_t n, array<size_t, NDim> dimensions)
{
// This might be optimizable into something nicer, maybe even a one-liner
array<size_t, NDim> result{};
for(size_t i = 0; i < NDim; i++) {
result[NDim-1-i] = n % dimensions[NDim-1-i];
n = n / dimensions[NDim-1-i];
};
return result;
}
template<size_t... Is, typename... Ts>
auto prod_inner(
std::index_sequence<Is...>,
size_t n,
const std::vector<Ts>&... vs)
-> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
auto vs_as_tuple = std::make_tuple( vs ... );
auto coordinates = delinearize_coordinates<sizeof...(Ts)>(n, { vs.size()... });
return { std::get<Is>(vs_as_tuple)[coordinates[Is]] ... };
}
template<typename... Ts>
auto prod(size_t n, const std::vector<Ts>&... vs)
-> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
return prod_inner(std::make_index_sequence<sizeof...(Ts)>{}, n,
std::forward<const std::vector<Ts>&>(vs)...);
}
备注:
- 与您的代码不同,我分解了将单个数字转换为坐标序列的函数。
- 如果您提供自己的
make_index_sequence
,我认为您可以将其简化为 C++11。
其他答案已经提到了索引技巧。这是我的尝试,尽可能直接从您的 python 代码转换而来:
template <typename T, std::size_t... I>
auto prod_impl(std::size_t n, T tuple, std::index_sequence<I...>) {
std::array sizes{ std::size(std::get<I>(tuple))... };
auto enumerator = [&sizes,n](std::size_t i, auto&& arr) -> decltype(auto) {
auto denom = std::accumulate(std::begin(sizes) + i + 1, std::end(sizes), 1, std::multiplies<>{});
auto idx = (n / denom) % std::size(arr);
return arr[idx];
};
return std::forward_as_tuple(enumerator(I, std::get<I>(tuple))...);
}
template<typename... Ts, typename Is = std::index_sequence_for<Ts...>>
auto prod(std::size_t n, const std::vector<Ts>&... vs) {
return prod_impl(n, std::forward_as_tuple(vs...), Is{});
}
我有一个 python 函数,它 returns 多个输入数组的笛卡尔积中的第 n 个元素
def prod(n, arrs):
out = []
for i,arr in enumerate(arrs):
denom = numpy.prod([ len(p) for p in arrs[i+1:] ], dtype=int)
idx = n // denom % len(arr)
out.append( arr[idx] )
return out
效果很好:
a = [ 1000, 1100, 1200, 1300, 1400 ]
b = [ 1.0, 1.5, 2.0, 2.5, 3.0, 3.5 ]
c = [ -2, -1, 0, 1, 2 ]
for n in range(20, 30):
i = prod(n, [a, b, c])
print(n, i)
[1000, 3.0, -2] [1000, 3.0, -1] [1000, 3.0, 0] [1000, 3.0, 1] [1000, 3.0, 2] [1000, 3.5, -2] [1000, 3.5, -1] [1000, 3.5, 0] [1000, 3.5, 1] [1000, 3.5, 2]
现在我想将其翻译成 C++(最大标准 C++-17)
template<typename... Ts>
auto prod(std::size_t n, const std::vector<Ts>&... vs)
-> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
// template magic here
}
有人可以帮助我使用上述公式构造元组所需的模板魔法吗?
首先,为了简单起见,让我们自动推断函数的 return 类型。
接下来,索引序列是整齐的。有了他们,就可以做到。
使用 C++20,我们可以从 lambda 中的序列中获取索引。在此之前,我们需要一个额外的功能。
最后,我们必须从头开始创建索引,要么存储索引然后以相反的顺序使用它们,要么反转生成的元组。
template <class T, std::size_t... Ns>
static auto prod_impl(std::size_t n, T tuple, std::index_sequence<Ns...>) {
auto f = [&](auto N){ auto r = n % N; n /= N; return r; };
auto x = std::forward_as_tuple(std::get<(sizeof...(Ns)) - Ns - 1>(tuple)[f(std::get<(sizeof...(Ns)) - Ns - 1>(tuple).size())]...);
return std::forward_as_tuple(std::get<(sizeof...(Ns)) - Ns - 1>(x)...);
}
template<class... Ts>
auto prod(std::size_t n, const std::vector<Ts>&... vs) {
return prod_impl(n, std::forward_as_tuple(vs...), std::make_index_sequence<sizeof...(vs)>());
}
使用索引数组的内部函数的更简单替代方法:
template <class T, std::size_t... Ns>
static auto prod_impl(std::size_t n, T tuple, std::index_sequence<Ns...>) {
auto f = [&](auto N){ auto r = n % N; n /= N; return r; };
std::size_t Is[] = { f(std::get<sizeof...(Ns) - Ns - 1>(tuple).size())... , 0};
return std::forward_as_tuple(std::get<Ns>(tuple)[sizeof...(Ns) - Ns - 1]...);
}
我们可以使用
这为我们提供了以下 C++14 解决方案:
#include <tuple>
#include <vector>
#include <cstdlib>
using std::array;
using std::size_t;
template <size_t NDim>
constexpr array<size_t, NDim> delinearize_coordinates(
size_t n, array<size_t, NDim> dimensions)
{
// This might be optimizable into something nicer, maybe even a one-liner
array<size_t, NDim> result{};
for(size_t i = 0; i < NDim; i++) {
result[NDim-1-i] = n % dimensions[NDim-1-i];
n = n / dimensions[NDim-1-i];
};
return result;
}
template<size_t... Is, typename... Ts>
auto prod_inner(
std::index_sequence<Is...>,
size_t n,
const std::vector<Ts>&... vs)
-> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
auto vs_as_tuple = std::make_tuple( vs ... );
auto coordinates = delinearize_coordinates<sizeof...(Ts)>(n, { vs.size()... });
return { std::get<Is>(vs_as_tuple)[coordinates[Is]] ... };
}
template<typename... Ts>
auto prod(size_t n, const std::vector<Ts>&... vs)
-> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
return prod_inner(std::make_index_sequence<sizeof...(Ts)>{}, n,
std::forward<const std::vector<Ts>&>(vs)...);
}
备注:
- 与您的代码不同,我分解了将单个数字转换为坐标序列的函数。
- 如果您提供自己的
make_index_sequence
,我认为您可以将其简化为 C++11。
其他答案已经提到了索引技巧。这是我的尝试,尽可能直接从您的 python 代码转换而来:
template <typename T, std::size_t... I>
auto prod_impl(std::size_t n, T tuple, std::index_sequence<I...>) {
std::array sizes{ std::size(std::get<I>(tuple))... };
auto enumerator = [&sizes,n](std::size_t i, auto&& arr) -> decltype(auto) {
auto denom = std::accumulate(std::begin(sizes) + i + 1, std::end(sizes), 1, std::multiplies<>{});
auto idx = (n / denom) % std::size(arr);
return arr[idx];
};
return std::forward_as_tuple(enumerator(I, std::get<I>(tuple))...);
}
template<typename... Ts, typename Is = std::index_sequence_for<Ts...>>
auto prod(std::size_t n, const std::vector<Ts>&... vs) {
return prod_impl(n, std::forward_as_tuple(vs...), Is{});
}