如何对运行时指定的数组维度求和?
-
09-06-2019 - |
题
我正在研究一个函数来建立分布的熵。它使用系词(如果有熟悉的话)。我需要根据“关心”的维度来总结数组中的值。
例子:考虑下面的例子......
Dimension 0 (across) _ _ _ _ _ _ _ _ _ _ _ _ _ |_ 0 _|_ 0 _|_ 0 _|_ 2 _| Dimension 1 |_ 1 _|_ 0 _|_ 2 _|_ 0 _| (down) |_ 0 _|_ 3 _|_ 0 _|_ 6 _| |_ 0 _|_ 0 _|_ 0 _|_ 0 _| I "care about" dimension 0 only, and "don't care" about the rest (dim 1). Summing this array with the above specifications will "collapse" the "stacks" of dimension 1 down to a single 4 x 1 array: _ _ _ _ _ _ _ _ _ _ _ _ _ |_ 1 _|_ 3 _|_ 2 _|_ 8 _| This can then be summed, or have any operation performed.
我需要使用一个“n”维数组来完成此操作,该数组可能为 20。另外,我需要能够做到这一点,关心某些维度,并折叠其余维度。我在这方面遇到了特别困难,因为我无法想象 20 个维度:p。如果有人可以帮助我设置一些 c/c++ 代码来折叠/求和,我将非常感激。
更新:
刚到家。以下是一些信息来回答您的问题:
- 抱歉回滚编辑,我希望当我单击回滚时它会向我显示更改,以便我可以看到我搞砸的内容,有点像维基百科。据我发现,情况并非如此。
- @jeff - 什么没有意义?我使用这项出色的服务(我认为是)有正当理由。我想在我的爱好上做得更好,仅此而已,就像我在高中时一样。我的许多帖子都涉及实现遗传算法(这篇文章,稀疏数组,排列数组,指针操作)。
- 我使用稀疏数组表示,因为使用传统(密集)数组可能会超过宇宙中的分子数量。目前,稀疏数组本身的实现并不重要,因为我正在努力使其在使用稀疏表示之前与标准数组一起使用。对于那些没有见过我之前的问题的人,我使用二叉搜索树作为包含稀疏数组点的结构,并使用“驱动程序”函数根据需要遍历树,返回该函数设计的任何功能。这是灵活的,因此我可以适应许多不同的访问数组的方法。
- 该结构是一个超立方体,维数以及每个维度的长度在运行时指定(它们都是相同的,因为它是一个超立方体)。
感谢大家的贡献。
解决方案
这可能有应用。假设您实现了 2D Conway 的生命游戏(定义了 2D 平面,1 表示“活着”,0 表示“死亡”),并且存储了每次迭代的游戏历史记录(然后定义了 3D 立方体)。如果您想知道历史上有多少活细菌,您可以使用上述算法。您可以对生命游戏网格的 3D(以及 4D、5D 等)版本使用相同的算法。
我想说这是一个递归问题,我还不是 C 程序员,但我知道这在 C 中是可能的。在Python中,
def iter_arr(array):
sum = 0
for i in array:
if type(i) == type(list()):
sum = sum + iter_arr(i)
else:
sum = sum + i
return sum
- 迭代数组中的每个元素
- 如果element是另一个数组,则再次调用该函数
- 如果元素不是数组,则将其添加到总和中
- 返回总和
然后,您可以将其应用于“关心”维度中的每个元素。
不过,由于鸭子类型,这在 python 中更容易......
其他提示
@杰夫
我实际上认为这是一个有趣的问题。我不确定它有多大用处,但这是一个有效的问题。
@艾德
您能否就这个问题提供更多信息?你说数组的维度是动态的,那么元素的数量也是动态的吗?
编辑:无论如何,我会尝试回答这个问题。我无法直接给你代码(在这台电脑上没有任何编译器的情况下,需要一段时间才能得到它),但我可以为你指出正确的方向......
我们以索引为 0 到 3 的 8 个维度 (0-7) 为例。你只关心 1,2 和 6。这意味着您有两个数组。第一的, array_care[4][4][4]
对于 1,2 和 6。这 array_care[4][4][4]
将保留最终结果。
接下来,我们想以一种非常具体的方式进行迭代。我们有数组 input[4][4][4][4][4][4][4][4]
进行解析,我们关心维度 1、2 和 6。
我们需要定义一些临时索引:
int dim[8] = {0,0,0,0,0,0,0,0};
我们还需要存储要增加索引的顺序:
int increase_index_order[8] = {7,5,4,3,0,6,2,1};
int i = 0;
此命令对于执行您的请求非常重要。
定义终止标志:
bool terminate=false;
现在我们可以创建循环:
while (terminate)
{
array_care[dim[1]][dim[2]][dim[6]] += input[dim[0]][dim[1]][dim[2]][dim[3]][dim[4]][dim[5]][dim[6]][dim[7]];
while ((dim[increase_index_order[i]] = 3) && (i < 8))
{
dim[increase_index_order[i]]=0;
i++;
}
if (i < 8) {
dim[increase_index_order[i]]++; i=0;
} else {
terminate=true;
}
}
这应该适用于 8 维,关心 3 维。让它变得动态需要更多的时间,而我没有时间。希望这可以帮助。我很抱歉,但我还没有学会代码标记。:(
如果你使用STL容器的话,这种事情会容易得多,或者也许 Boost.MultiArray. 。但如果你必须使用数组:
#include <iostream>
#include <boost/foreach.hpp>
#include <vector>
int sum(int x) {
return x;
}
template <class T, unsigned N>
int sum(const T (&x)[N]) {
int r = 0;
for(int i = 0; i < N; ++i) {
r += sum(x[i]);
}
return r;
}
template <class T, unsigned N>
std::vector<int> reduce(const T (&x)[N]) {
std::vector<int> result;
for(int i = 0; i < N; ++i) {
result.push_back(sum(x[i]));
}
return result;
}
int main() {
int x[][2][2] = {
{ { 1, 2 }, { 3, 4 } },
{ { 5, 6 }, { 7, 8 } }
};
BOOST_FOREACH(int v, reduce(x)) {
std::cout<<v<<"\n";
}
}
实际上,通过折叠列,您已经对它们进行了求和,因此对于您的示例来说,维度根本不重要。我错过了什么还是你错过了什么?
我认为在这里做的最好的事情是两件事之一/两者:
- 重新考虑设计,如果太复杂,找到一种不太复杂的方法。
- 别再试图想象它了..:P 只需存储需要求和的相关维度,然后一次计算一个。一旦有了基本代码,就可以考虑提高算法的效率。
我不敢苟同,总有另一种方法..
如果你真的 不能 重构,那么你需要将问题分解成更小的部分。就像我说的,确定需要求和的维度,然后一次一个地进行计算。
另外,停止更改编辑,他们正在纠正您的拼写错误,他们正在努力帮助您;)
你在 c/c++ 中这样做......所以你有一个数组的数组的数组......您不必可视化 20 个维度,因为对于 2 维来说,这不是数据在内存中的布局方式:
[1] --> [1,2,3,4,5,6,...]
[2] --> [1,2,3,4,5,6,...]
[3] --> [1,2,3,4,5,6,...]
[4] --> [1,2,3,4,5,6,...]
[5] --> [1,2,3,4,5,6,...]
. .
. .
. .
那么,为什么不能迭代第一个总结其内容呢?如果您想找到尺寸,那么 sizeof(array)/sizeof(int)
是一种冒险的做法。您必须知道能够处理此数据的维度,并设置内存,以便您知道求和的递归深度。这是一些你应该做的伪代码,
sum( n_matrix, depth )
running_total = 0
if depth = 0 then
foreach element in the array
running_total += elm
else
foreach element in the array
running_total += sum( elm , depth-1 )
return running_total
x = number_of_dimensions;
while (x > 1)
{
switch (x)
{
case 20:
reduce20DimensionArray();
x--;
break;
case 19:
.....
}
}
(抱歉,没能抗拒。)
如果我理解正确的话,您想要将沿 1 维的每个“bin”定义的横截面中的所有值相加。我建议为您的目的地创建一个一维数组,然后循环遍历数组中的每个元素,将值与感兴趣维度的索引添加到目的地。
如果您使用任意数量的维度,则必须有一种寻址元素的方法(我很好奇您是如何实现这一点的)。您对此的实现将影响您设置目标索引的方式。但一个明显的方法是在迭代循环中检查 if 语句。
当您说您不知道有多少个维度时,您到底是如何定义数据结构的?
在某些时候,有人需要创建这个数组,为此,他们需要知道数组的维度。您可以强制创建者将此数据与数组一起传递。
除非问题是定义这样的数据结构......