Como uma soma das dimensões de um array é especificada em tempo de execução?

Question

Estou trabalhando em uma função para estabelecer a entropia de uma distribuição.Ele usa uma cópula, se alguém estiver familiarizado com isso.Preciso resumir os valores na matriz com base em quais dimensões são "preocupadas".

Exemplo:Considere o seguinte exemplo...

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.

Preciso fazer isso com uma matriz de 'n' dimensões, que poderia ser 20.Além disso, preciso ser capaz de fazer isso, me preocupando com certas dimensões e desmontando o resto.Estou tendo dificuldades especialmente com isso porque não consigo visualizar 20 dimensões :p.Se alguém pudesse me ajudar a configurar algum código c/c++ para recolher/soma, eu ficaria muito grato.

Atualizar:

Acabei de chegar em casa.Aqui estão algumas informações para responder às suas perguntas:

1. Desculpe por reverter as edições, eu esperava que quando clicasse em reverter ele me mostrasse as alterações para que eu pudesse ver o que errei, um pouco como a Wikipedia.Não foi esse o caso, como descobri.
2. @jeff - O que não faz sentido?Estou usando este excelente serviço por (o que considero) um motivo legítimo.Quero melhorar no meu hobby, que é tudo, já que estou no ensino médio.Muitas das minhas postagens tratam da implementação de um algoritmo genético (esta postagem, sparsearray, classificação de um array, manipulação de ponteiro).
3. Estou usando uma representação de array esparso, pois é possível exceder o número de moléculas no universo usando um array tradicional (denso).Por enquanto, a implementação do sparsearray em si não importa muito, pois estou trabalhando para fazê-lo funcionar com um array padrão antes de passar para uma representação esparsa.Para aqueles que não viram minhas perguntas anteriores, estou usando uma árvore de pesquisa binária como estrutura para conter os pontos esparsos da matriz e uma função "driver" para percorrer a árvore conforme necessário, retornando tudo o que a função foi projetada para fazer.Isso é flexível, então posso acomodar vários métodos diferentes de acesso ao array.
4. A estrutura é um hipercubo, e o número de dimensões é especificado em tempo de execução, bem como o comprimento de cada dimensão (que são todas iguais, pois se trata de um hipercubo).

Obrigado a todos pela sua contribuição.

Answer 1

Isso poderia ter aplicações.Digamos que você implementou um Jogo da Vida de Conway 2D (que define um plano 2D, 1 para 'vivo', 0 para 'morto') e armazenou o histórico dos jogos para cada iteração (que então define um cubo 3D).Se você quisesse saber quantas bactérias existiram vivas ao longo da história, você usaria o algoritmo acima.Você poderia usar o mesmo algoritmo para uma versão 3D (e 4D, 5D etc.) da grade do Jogo da Vida.

Eu diria que esta é uma questão de recursão, ainda não sou programador C, mas sei que é possível em C.Em píton,

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 

1. Iterar sobre cada elemento da matriz
2. Se o elemento for outro array, chame a função novamente
3. Se o elemento não for array, adicione-o à soma
4. Soma de retorno

Você aplicaria isso a cada elemento da dimensão 'preocupado'.

Isso é mais fácil em python devido à digitação de pato ...

Answer 2

@Jeff

Na verdade, acho que essa é uma pergunta interessante.Não tenho certeza de quão útil é, mas é uma pergunta válida.

@Ed

Você pode fornecer um pouco mais de informação sobre esta questão?Você disse que a dimensão do array é dinâmica, mas o número de elementos também é dinâmico?

EDITAR:Vou tentar responder à pergunta de qualquer maneira.Não posso fornecer o código de cabeça (demoraria um pouco para acertar sem nenhum compilador aqui neste PC), mas posso apontar a direção certa ...

Vamos usar 8 dimensões (0-7) com índices de 0 a 3 como exemplo.Você se preocupa apenas com 1,2 e 6.Isso significa que você tem duas matrizes.Primeiro, array_care[4][4][4] para 1,2 e 6.O array_care[4][4][4] manterá o resultado final.

A seguir, queremos iterar de uma maneira muito específica.Temos a matriz input[4][4][4][4][4][4][4][4] para analisar e nos preocupamos com as dimensões 1, 2 e 6.

Precisamos definir alguns índices temporários:

int dim[8] = {0,0,0,0,0,0,0,0};

Também precisamos armazenar a ordem em que queremos aumentar os índices:

int increase_index_order[8] = {7,5,4,3,0,6,2,1};
int i = 0;

Esta ordem é importante para fazer o que você solicitou.

Defina um sinalizador de encerramento:

bool terminate=false;

Agora podemos criar nosso loop:

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;
}
}

Isso deve funcionar para 8 dimensões, preocupando-se com 3 dimensões.Levaria um pouco mais de tempo para torná-lo dinâmico e não tenho tempo.Espero que isto ajude.Peço desculpas, mas ainda não aprendi as marcações do código.:(

Answer 3

Esse tipo de coisa é muito mais fácil se você usar contêineres STL, ou talvez Boost.MultiArray.Mas se você precisar usar um array:

#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";
    }
}

Answer 4

Na verdade, ao recolher as colunas você já as somou, então a dimensão não importa em nada para o seu exemplo.Eu perdi alguma coisa ou você?

Answer 5

Acho que a melhor coisa a fazer aqui seria uma ou ambas as coisas:

1. Repense o design, se for muito complexo, encontre uma forma menos complexa.
2. Pare de tentar visualizá-lo.:P Basta armazenar as dimensões em questão que você precisa somar e depois fazê-las uma de cada vez.Depois de ter o código base, procure melhorar a eficiência do seu algoritmo.

Answer 6

Eu discordo, SEMPRE há outra maneira ..

E se você realmente não pode refatorar, então você precisa dividir o problema em partes menores.Como eu disse, estabeleça quais dimensões você precisa somar e, em seguida, acerte-as uma de cada vez.

Além disso, pare de alterar as edições, elas estão corrigindo seus erros ortográficos, estão tentando te ajudar ;)

Answer 7

Você está fazendo isso em c/c++...então você tem um array de array de array...você não precisa visualizar 20 dimensões, pois não é assim que os dados são dispostos na memória, para um formato bidimensional:

[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,...]
 .           .
 .           .
 .           .

então, por que você não pode iterar no primeiro, resumindo seu conteúdo?Se você está tentando encontrar o tamanho, então sizeof(array)/sizeof(int) é uma abordagem arriscada.Você deve conhecer a dimensão para poder processar esses dados e configurar a memória, para saber a profundidade da recursão a ser somada.Aqui está um pseudocódigo do que parece que você deveria fazer,

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

Answer 8

x = number_of_dimensions;
while (x > 1)
{
  switch (x)
  {
    case 20:
      reduce20DimensionArray();
      x--;
    break;
    case 19:
      .....
  }
}

(Desculpe, não pude resistir.)

Answer 9

Se bem entendi, você deseja somar todos os valores na seção transversal definida em cada "bin" ao longo de 1 dimensão.Sugiro fazer um array 1D para o seu destino e, em seguida, percorrer cada elemento do seu array adicionando o valor ao destino com o índice da dimensão de interesse.

Se você estiver usando um número arbitrário de dimensões, deverá ter uma maneira de endereçar os elementos (ficaria curioso para saber como você está implementando isso).Sua implementação afetará como você define o índice de destino.Mas uma maneira óbvia seria com instruções if verificadas nos loops de iteração.

Answer 10

Quando você diz que não sabe quantas dimensões existem, como exatamente você está definindo as estruturas de dados?

Em algum momento, alguém precisa criar esse array e, para isso, precisa saber as dimensões do array.Você pode forçar o criador a passar esses dados junto com o array.

A menos que a questão seja definir tal estrutura de dados...