런타임에 지정된 배열의 크기를 어떻게 합산합니까?

StackOverflow https://stackoverflow.com/questions/23190

문제

저는 분포의 엔트로피를 설정하는 기능을 연구 중입니다.익숙한 경우 코퓰러를 사용합니다.어떤 차원이 "관심"되는지에 따라 배열의 값을 합산해야 합니다.

예:다음 예를 고려해보세요... 

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++ 코드를 설정하는 데 도움을 줄 수 있다면 매우 감사하겠습니다.

업데이트:

그냥 집에있어.다음은 귀하의 질문에 답변할 수 있는 몇 가지 정보입니다.

  1. 편집 내용을 롤백해서 미안합니다. 롤백을 클릭하면 변경 사항이 표시되어 내가 망친 부분을 볼 수 있기를 바랐습니다. 위키피디아처럼 말이죠.알고 보니 그렇지 않았습니다.
  2. @jeff - 말이 안되는 것은 무엇입니까?나는 (내가 생각하기에) 정당한 이유로 이 훌륭한 서비스를 사용하고 있습니다.나는 고등학교에 다니면서 취미라는 것을 더 잘하고 싶다.내 게시물 중 상당수는 유전자 알고리즘 구현에 관한 것입니다(이 게시물은 sparsearray, 배열 순위 지정, 포인터 조작).
  3. 나는 전통적인 (밀집된) 배열을 사용하여 우주의 분자 수를 초과하는 것이 가능하기 때문에 희소 배열 표현을 사용하고 있습니다.지금은 sparseray 자체의 구현이 크게 중요하지 않습니다. 희소 표현으로 전환하기 전에 표준 배열과 함께 작동하도록 작업 중이기 때문입니다.이전 질문을 보지 못한 분들을 위해 희소 배열 포인트를 포함하는 구조로 이진 검색 트리를 사용하고 필요에 따라 트리를 순회하는 "드라이버" 함수를 사용하여 함수가 수행하도록 설계된 모든 것을 반환합니다.이는 유연하므로 배열에 액세스하는 다양한 방법을 수용할 수 있습니다.
  4. 구조는 하이퍼큐브이며, 차원 수는 런타임 시 지정되고 각 차원의 길이도 지정됩니다(하이퍼큐브이므로 모두 동일함).

귀하의 의견을 보내주신 모든 분들께 감사드립니다.

도움이 되었습니까?

해결책

여기에는 응용 프로그램이 있을 수 있습니다.2D Conway의 Life of Game(2D 평면 정의, 1은 '살아 있음', 0은 '죽음' 정의)을 구현하고 모든 반복에 대한 게임 기록을 저장했다고 가정해 보겠습니다(3D 큐브 정의).역사에 걸쳐 얼마나 많은 박테리아가 살아 있었는지 알고 싶다면 위의 알고리즘을 사용하면 됩니다.Game of Life 그리드의 3D(4D, 5D 등) 버전에도 동일한 알고리즘을 사용할 수 있습니다.

나는 이것이 재귀에 대한 질문이라고 말하고 싶습니다. 저는 아직 C 프로그래머는 아니지만 C에서 가능하다는 것을 알고 있습니다.파이썬에서는


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. 배열의 각 요소를 반복합니다.
  2. 요소가 다른 배열이면 함수를 다시 호출하십시오.
  3. 요소가 배열이 아닌 경우 합계에 추가합니다.
  4. 반환 금액

그런 다음 이를 '관심' 차원의 각 요소에 적용합니다.

python에서는 duck-typing으로 인해 이것이 더 쉽습니다.

다른 팁

@제프

실제로 이것은 흥미로운 질문이라고 생각합니다.그것이 얼마나 유용한지는 잘 모르겠지만 유효한 질문입니다.

@에드

이 질문에 대해 좀 더 자세한 정보를 제공해 주실 수 있나요?배열의 차원은 동적이라고 하셨는데, 요소의 개수도 동적인가요?

편집하다:어쨌든 나는 질문에 대답하려고 노력할 것입니다.머릿속에서 코드를 알려드릴 수는 없지만(이 PC에 컴파일러가 없으면 코드를 올바르게 작성하려면 시간이 좀 걸릴 것입니다) 올바른 방향을 알려드릴 수는 있습니다.

예를 들어 인덱스가 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;
}
}

이는 3차원을 고려하여 8차원에서 작동해야 합니다.동적으로 만들려면 시간이 좀 더 걸릴 것 같은데 시간이 없습니다.도움이 되었기를 바랍니다.죄송합니다. 아직 코드 마크업을 배우지 못했습니다.:(

이런 종류의 일은 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";
    }
}

실제로 열을 축소하면 이미 합산되었으므로 예에서는 차원이 전혀 중요하지 않습니다.내가 뭔가를 놓친 건가요, 아니면 당신이 놓친 건가요?

내 생각에 여기서 할 수 있는 가장 좋은 일은 다음 두 가지 중 하나 또는 둘 다를 하는 것입니다.

  1. 디자인을 다시 생각해 보세요. 너무 복잡하다면 덜 복잡한 방법을 찾으세요.
  2. 시각화하려고 노력하지 마세요..:P 합산해야 하는 문제의 차원을 저장한 다음 한 번에 하나씩 수행하세요.기본 코드가 있으면 알고리즘의 효율성을 향상시키는 방법을 살펴보십시오.

나는 다르게 간청합니다. 항상 다른 방법이 있습니다 ..

그리고 만약 당신이 정말로 할 수 없다 리팩터링을 수행한 다음에는 문제를 더 작은 부분으로 나누어야 합니다.내가 말했듯이 합산해야 할 차원을 설정한 다음 한 번에 하나씩 치십시오.

또한 편집 내용 변경을 중지하세요. 맞춤법 오류를 수정하고 있으며 도움을 드리고 있습니다. ;)

c/c++에서 이 작업을 수행하고 있습니다.그래서 당신은 배열의 배열을 가지고 있습니다 ...2차원의 경우 데이터가 메모리에 배치되는 방식이 아니기 때문에 20차원을 시각화할 필요가 없습니다.

[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차원을 따라 각 "빈"에 정의된 단면의 모든 값을 합산하려고 합니다.대상에 대한 1D 배열을 만든 다음 관심 차원의 인덱스를 사용하여 대상에 값을 추가하여 배열의 각 요소를 반복하는 것이 좋습니다.

임의의 수의 차원을 사용하는 경우 요소를 처리하는 방법이 있어야 합니다(이를 어떻게 구현하는지 궁금합니다).이를 구현하면 대상 색인을 설정하는 방법에 영향을 미칩니다.그러나 분명한 방법은 반복 루프에서 if 문을 확인하는 것입니다.

얼마나 많은 차원이 있는지 모른다고 할 때 데이터 구조를 정확히 어떻게 정의하고 있습니까?

어느 시점에서 누군가는 이 배열을 만들어야 하며, 그러기 위해서는 배열의 크기를 알아야 합니다.생성자가 이 데이터를 배열과 함께 전달하도록 강제할 수 있습니다.

문제가 그러한 데이터 구조를 정의하는 것이 아니라면 ...

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top